NP. As an upper bound, P
NP[log]
⊆ NP
NP
= Σ
p
2
, where an NP
NP
machine is an NP machine which
nondeterministically makes up to a polynomial number of calls to an NP oracle, and Σ
p
2
is the second
level of the Polynomial-Time Hierarchy (PH). In contrast, it is unlikely for P
QMA[log]
to be in PH,
as even BQP ⊆ QMA ⊆ P
QMA[log]
is generally not believed to be in PH [1, 20, 26, 55, 56]. A natural
question is whether P
QMA[log]
might instead be contained in an appropriate quantum analogue of
PH. The answer is not clear, since unlike the fact that Σ
p
2
= NP
NP
, it is not clear that “quantum
Σ
p
2
” should equal (say) QMA
QMA
; see [32] for a discussion and treatment of quantum analogues of
PH. Additional references on “quantum PH” are [29, 48, 63].
As far as we are aware, whether P
NP[k]
(i.e. k ∈ O(1) NP queries), P
NP[log
k
n]
(i.e. O(log
k
n)
NP queries for k ≥ 1), and P
NP
(i.e. polynomially many NP queries) coincide remains open.
Notably, if P
NP[1]
= P
NP[2]
, then P
NP[1]
= P
NP[log]
and PH collapses [39]. But, it is known is
that if the queries to the NP oracle are non-adaptive, meaning they are all made in parallel, then
the resulting class P
||NP
equals P
NP[log]
[16, 40]. (The analogous statement P
||QMA
= P
QMA[log]
has recently been shown [33].) Similarly, a P machine making O(log
k
n) adaptive NP queries is
equivalent in power to a P machine making O(log
k+1
n) non-adaptive queries for all k ≥ 1 [18].
In terms of complete problems, determining the election winner in Lewis Carroll’s 1876 voting
system is P
NP[log]
-complete [41], and model checking for certain branching-time temporal logics is
P
NP[log
2
n]
-complete [57].
Finally, it is important to note that NP is a class of decision problems. Formally, this means
any NP problem is specified by a language L ⊆ {0, 1 }
∗
with the corresponding decision problem:
Given input x ∈ {0, 1 }
∗
, is x ∈ L? In the context of P
NP[log]
, this means any string x ∈ {0, 1 }
∗
is a valid problem instance or query to an NP oracle for language L, since any such x is either
in the language or not. Unfortunately, an analogous statement cannot be made about P
QMA[log]
,
complicating its study; this brings us to our third, crucial remark about P
QMA[log]
from earlier.
Oracles for promise classes and the issue of invalid queries. In contrast to NP, QMA is a class of
promise problems. Formally, this means the space of all inputs {0, 1 }
∗
is partitioned into three
sets, A, B, C, where A and C are YES and NO instances, respectively, and B is the set of “invalid”
instances. (Classes of decision problems are a special case of this in which A = L, B = ∅, and
C = {0, 1 }
∗
\ L.) Why might this pose a problem for studying P
QMA[log]
?
Recall that we assume all calls by the P
QMA[log]
machine to the QMA oracle Q are for instances
(H, a, b) of 2-LH: Is the ground state energy of H at most a (YES case), or at least b (NO case),
for b − a ≥ 1/poly(n)? Unfortunately, a P machine cannot in general tell
4
whether the instance
(H, a, b) it feeds to Q satisfies the promise conditions of LH; in particular, the ground state energy
may lie in the interval (a, b). We call any such instance or query (H, a, b) violating the 2-LH promise
“invalid” (these instances belong in the set B of instances above). For any invalid query, the oracle
Q is allowed to accept or reject arbitrarily. This raises a potential issue: if the oracle is allowed
to respond arbitrarily to invalid queries, how does one ensure a YES instance (or NO instance)
of a P
QMA[log]
problem is well-defined (normally, the P machine conditions its future actions on
4
By definition, the P machine can only execute polynomial-time computations. Thus, even if we assume without
loss of generality that the P machine uses specific circuit-to-Hamiltonian constructions (for preparing queries to the
QMA oracle) whose promise gaps are precisely known (e.g. [6, 17]), it is not clear how the machine should know
whether the quantum circuit it feeds into said construction satisfies a promise gap to begin with — where such
circuit-to-Hamiltonian constructions require the input circuit to satisfy an inverse polynomial promise gap, which
is unlikely to be relaxed to more easily verified, say, inverse exponentially small promise gaps, since it would imply
PSPACE ⊆ QMA, which follows since QMA with exponentially small gap equals PSPACE [25].
5