The complexity of simulating local measurements on quan-
tum systems
Sevag Gharibian
1,2
and Justin Yirka
2
1
Department of Computer Science, Universität Paderb orn, Germany
2
Department of Computer Science, The University of Texas at Austin, USA
An important task in quantum physics is the estimation of local quantities for ground
states of local Hamiltonians. Recently, [Ambainis, CCC 2014] deﬁned the complexity
class P
QMA[log]
, and motivated its study by showing that the physical task of estimating
the expectation value of a local observable against the ground state of a local Hamiltonian
is P
QMA[log]
-complete. In this paper, we continue the study of P
QMA[log]
, obtaining the
following lower and upper bounds.
Lower bounds (hardness results):
The P
QMA[log]
-completeness result of [Ambainis, CCC 2014] requires O(log n)-local
observables and Hamiltonians. We show that simulating even a single qubit mea-
surement on ground states of 5-local Hamiltonians is P
QMA[log]
-complete, resolving
an open question of Ambainis.
We formalize the complexity theoretic study of estimating two-point correlation
functions against ground states, and show that this task is similarly P
QMA[log]
-
complete.
We identify a ﬂaw in [Ambainis, CCC 2014] regarding a P
UQMA[log]
-hardness proof
for estimating spectral gaps of local Hamiltonians. By introducing a “query valida-
tion” technique, we build on [Ambainis, CCC 2014] to obtain P
UQMA[log]
-hardness
for estimating spectral gaps under polynomial-time Turing reductions.
Upper bounds (containment in complexity classes):
P
QMA[log]
is thought of as “slightly harder” than QMA. We justify this formally by
exploiting the hierarchical voting technique of [Beigel, Hemachandra, Wechsung,
SCT 1989] to show P
QMA[log]
PP. This improves the containment QMA PP
[Kitaev, Watrous, STOC 2000].
This work contributes a rigorous treatment of the subtlety involved in studying oracle
classes in which the oracle solves a promise problem. This is particularly relevant for
quantum complexity theory, where most natural classes such as BQP and QMA are
deﬁned as promise classes.
Sevag Gharibian: sgharibian@upb.de, http://groups.uni-paderborn.de/fg-qi/people.html
Justin Yirka: yirka@utexas.edu, https://www.justinyirka.com/
Accepted in Quantum 2019-04-24, click title to verify 1
arXiv:1606.05626v3 [quant-ph] 16 Sep 2019
Contents
1 Introduction 2
1.1 Background on Quantum Hamiltonian Complexity . . . . . . . . . . . . . . . . . . . 2
1.2 Simulating local measurements on low-temperature quantum systems . . . . . . . . . 4
1.3 Oracle complexity classes, P
QMA[log]
, and P
NP[log]
. . . . . . . . . . . . . . . . . . . . 4
1.4 Our results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 Proof techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6 Discussion and open questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2 Preliminaries 10
3 Ambainis’s Query Hamiltonian 13
4 Lower bounds (hardness results) 16
4.1 P
QMA[log]
-completeness of APX-SIM . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.2 P
QMA[log]
-completeness of APX-2-CORR . . . . . . . . . . . . . . . . . . . . . . . . 21
4.3 P
UQMA[log]
-hardness of SPECTRAL-GAP . . . . . . . . . . . . . . . . . . . . . . . 23
5 Upper bounds (containment in PP) 28
A Additional proofs 37
1 Introduction
1.1 Background on Quantum Hamiltonian Complexity
The use of computational complexity theory to study the inherent diﬃculty of computational
problems has proven remarkably fruitful over the last decades. For example, the theory of NP-
completeness [21, 42, 46] has helped classify the worst-case complexity of hundreds of computa-
tional problems which elude eﬃcient classical algorithms. In the quantum setting, the study of a
quantum analogue of NP, known as Quantum Merlin Arthur
1
(QMA), was started in 1999 by the
seminal “quantum Cook-Levin theorem” of Kitaev [45], which showed that estimating the ground
state energy of a given k-local Hamiltonian is QMA-complete for k 5. Here, a k-local Hamiltonian
H can be thought of as a quantum constraint satisfaction system in which each quantum clause
acts non-trivially on k qubits. More formally, H C
2
n
×2
n
is an exponentially large Hermitian
matrix acting on n qubits, but with a succinct description
2
H =
P
i
H
i
, where each local clause
H
i
C
2
k
×2
k
acts non-trivially on k qubits. The “largest total weight of satisﬁable clauses” is given
by the ground state energy of H, i.e. the smallest eigenvalue of H. Physically, the ground state
energy and its corresponding eigenvector, the ground state, are motivated in that they represent the
energy level and state of a given quantum system at low temperature, respectively. For this reason,
since Kitaev’s work [45], a number of physically motivated problems have been shown complete
for QMA (this has given rise to the ﬁeld of Quantum Hamiltonian Complexity, see, e.g., [52], [10]
1
More precisely, QMA is Merlin-Arthur (MA) with a quantum proof and quantum veriﬁer.
2
Implicitly, if H
i
acts on a subset S
i
[n] of qubits non-trivially, then more accurately one writes H
i
I
[n]\S
i
.
We write H =
P
i
H
i
for simplicity.
2
and [31] for surveys
3
). Many of these QMA-complete problems focus on estimating ground state
energies of local Hamiltonians.
Beyond ground state energies. In recent years, however, new directions in quantum complexity
theory involving other physical properties of local Hamiltonians have appeared. We attempt to
survey a number of such results here.
Brown, Flammia and Schuch [15] (also Shi and Zhang [59]) introduced a quantum analogue of
#P, denoted #BQP, and showed that computing the ground state degeneracy or density of states of
local Hamiltonians is #BQP-complete. Gharibian and Sikora [30] showed that determining whether
the ground space of a local Hamiltonian has an “energy barrier” is QCMA-complete, where QCMA [2]
is Merlin-Arthur (MA) with a classical proof and quantum prover. This was strengthened by Gosset,
Mehta, and Vidick [38], who showed that QCMA-completeness holds even for commuting local
Hamiltonians. Bravyi and Gosset [12] studied the complexity of quantum impurity problems, which
involve a bath of free fermions coupled to an interacting subsystem dubbed an “impurity”. Cubitt,
Montanaro, and Piddock [24] have shown that certain simple spin-lattice models are “universal”, in
the sense that they can replicate the entire physics of any other quantum many-body system.
From a hardness of approximation perspective, Gharibian and Kempe [29] introduced cq-Σ
2
,
a quantum generalization of Σ
p
2
, and showed that determining the smallest subset of interaction
terms of a given local Hamiltonian which yields a frustrated ground space is cq-Σ
2
-complete (and
2
-hard to approximate). Aharonov and Zhou [3] studied the task of “Hamiltonian
sparsiﬁcation” or “degree-reduction”, in which one attempts to simulate an input local Hamiltonian
with a new local Hamiltonian with an interaction graph of bounded degree while preserving only
the ground space and spectral gap (in general, [3] show this is impossible). This was in pursuit
of answering whether classical proof techniques for the classical PCP theorem carry over to the
quantum setting.
Finally, various authors have studied spectral gaps of local Hamiltonians from a computability
theory perspective. (In computability theory, one asks whether a decision or promise problem can be
decided by a Turing machine running in a ﬁnite number of steps. In the current paper, our focus is
instead on complexity theory, in which problems are typically known to be computable; the question
is rather to obtain an estimate of the resources the Turing machine requires to solve the problem.)
Gosset and Mozgunov [37] and Bravyi and Gosset [11] have studied spectral gaps for frustration-
free 1D translation-invariant systems (the latter, in particular, shows that distinguishing between
gapped and gapless phases is decidable in the spin-1/2 chains studied). Cubitt, Perez-Garcia and
Wolf [23] have shown undecidability of estimating spectral gaps in the thermodynamic limit for
translation-invariant, nearest-neighbor Hamiltonians on a 2D square lattice. This has very recently
been improved to undecidability for 1D translation invariant systems by Bausch, Cubitt, Lucia, and
3
Since these surveys were published, the study of ground spaces through the ﬁeld of Quantum Hamiltonian Com-
plexity has continued to grow. For example, recent variants on circuit-to-Hamiltonian mappings such as the space-time
construction of Breuckmann and Terhal [14], of Bausch and Crosson [6] for considering complex weights and branch-
ing transitions, of Bausch, Cubitt and Ozols [7] for embedding QMA
exp
computations into 1D translation invariant
systems of local dimension 42, or of Caha, Landau, and Nagaj [17] for achieving an arbitrarily high success probability
of extracting a computation result from a history state while only needing to increase the clock size logarithmically,
have been given. Bravyi and Hastings [13] have shown that the local Hamiltonian problem for the quantum Ising
model is StoqMA-complete, completing the complexity classiﬁcation scheme of Cubitt and Montanaro [22]. Gilyén
and Sattath [35] have given a constructive Quantum Lovasz Local Lemma which eﬃciently prepares a frustration-free
Hamiltonian’s ground state under the assumption that the system is “uniformly” gapped. (This list of results is a
small sample of recent work.)
3
Perez-Garcia [8]. Note that both the current paper and [5] also study spectral gaps, but from a
complexity theory perspective; in particular, in contrast to the undecidability studies listed above,
which consider the thermodynamic limit (i.e. the number of qubits n goes to inﬁnity), in our setting
the number of qubits n (expressed in unary) is part of the input to the problem, as is standard in
complexity theory.
1.2 Simulating local measurements on low-temperature quantum systems
In Section 1.1, we listed a number of results studying properties of local Hamiltonians beyond ground
state energies. We intentionally omitted one particular problem, however, which is extremely well
motivated physically and which is the starting point of this work. Suppose one cools a many-
body quantum system to low temperature in the lab and a priori does not know the system’s
properties (such as its ground state energy, ground space, etc); this is a natural assumption, as
many of these properties are QMA-complete to estimate to begin with. The most “basic” action an
experimenter can now take is to perform a local measurement (typically on a constant number of
qubits) in an attempt to extract information about the system. The question is: How diﬃcult is it
to computationally simulate this “basic” action?
This computational task was formalized by Ambainis [5] (formal deﬁnitions in Section 2) and
designated Approximate Simulation (APX-SIM): Given a k-local Hamiltonian H and an l-local
observable A, estimate the expectation value of the measurement A against the ground state of H,
i.e. estimate hAi := hψ|A |ψi for |ψi a ground state of H. It turned out that not only is this
problem “hard”, but that it is in fact harder then even QMA.
To formalize this, Ambainis introduced [5] the complexity class P
QMA[log]
, which intuitively is
“slightly harder” than QMA, and showed that APX-SIM is P
QMA[log]
-complete when the Hamilto-
nian H and observable A are both O(log n)-local. To help set context before stating our results, we
now discuss P
QMA[log]
and its classical analogue P
NP[log]
in further depth.
1.3 Oracle complexity classes, P
QMA[log]
, and P
NP[log]
Formally, P
QMA[log]
is the class of decision problems which can be decided by a polynomial-time
deterministic Turing machine making O(log n) queries to an oracle for QMA. Thus, it is an example
of an oracle complexity class.
Let us make three remarks. First, by “oracle for QMA”, one typically means an oracle for a
QMA-complete problem Π (since any other problem in QMA may be reduced in polynomial-time
to Π); in this paper, we shall set Π as the QMA-complete 2-local Hamiltonian problem (2-LH) [43],
an instance (H, a, b) of which asks: Is the ground state energy of H at most a (YES case), or at
least b (NO case), for b a 1/poly(n)? Second, although P
QMA[log]
uses a QMA oracle, it in fact
also contains the complementary class co-QMA. This is because to solve any co-QMA problem, a
P
QMA[log]
machine can plug the co-QMA problem instance into the QMA oracle, and subsequently
ﬂip the oracle’s answer in polynomial-time to solve the co-QMA problem. Thus, P
QMA[log]
6= QMA
unless co-QMA QMA (which is unlikely), and so P
QMA[log]
is likely strictly harder than QMA.
The third remark is that P
QMA[log]
uses an oracle for a class of promise problems; this is a subtle
but crucial point, which we discuss shortly; ﬁrst, let us set the stage by reviewing the analogous
classical class P
NP[log]
.
The class P
NP[log]
. P
NP[log]
is deﬁned analogously to P
QMA[log]
except it utilizes an NP oracle.
Analogous to P
QMA[log]
, P
NP[log]
contains both NP and co-NP and thus is likely strictly harder than
4
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 speciﬁed 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 satisﬁes 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-deﬁned (normally, the P machine conditions its future actions on
4
By deﬁnition, the P machine can only execute polynomial-time computations. Thus, even if we assume without
loss of generality that the P machine uses speciﬁc 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 satisﬁes 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 veriﬁed, say, inverse exponentially small promise gaps, since it would imply
PSPACE QMA, which follows since QMA with exponentially small gap equals PSPACE [25].
5
the response the oracle returns for each query)? To do so, we stipulate (see, e.g., Deﬁnition 3 of
Goldreich [36]) that the P machine must output the same answer regardless of how any invalid
queries are answered by the oracle. We view the issue of formally handling invalid queries as one of
the central themes and contributions of this work.
1.4 Our results
Our results fall into two categories: Lower bounds (hardness results) and upper bounds (containment
in complexity classes).
Lower bounds (hardness results). We begin by showing three hardness results; two focus on
computational problems introduced in [5] (APX-SIM and SPECTRAL-GAP) and one introduces
a new problem (APX-2-CORR).
1. P
QMA[log]
-completeness of APX-SIM for O(1)-local Hamiltonians and single-qubit observables.
Recall that in [5], Ambainis introduced P
QMA[log]
and showed that APX-SIM (i.e. given k-local
Hamiltonian H and l-local observable A, simulate measurement A on the ground state of H) is
P
QMA[log]
-complete. This proof required both the Hamiltonian H and observable A to be O(log n)-
local. From a physical standpoint, however, it is typically desirable to have O(1)-local Hamiltonians
and observables whether P
QMA[log]
-hardness holds in this regime was left as an open question
in [5]. We thus ﬁrst ask: Is APX-SIM still hard for O(1)-local Hamiltonians and 1-local observables?
Let us develop some intuition before answering this question. Typically, computational problems
(such as estimating ground state energies) of 1-local Hamiltonians are easy, since the qubits do
not interact. This intuition does not, however, carry over to the setting of simulating 1-local
measurements. For example, by embedding a 3-SAT instance φ into a 3-local Hamiltonian and then
using the ability to repeatedly measure observable Z against single qubits of the ground state, we
can extract a solution to φ! Thus, the 3-local Hamiltonian and 1-local observable case is at least
NP-hard. Indeed, here we show it is much harder, resolving Ambainis’s open question.
Theorem 1.1. Given a 5-local Hamiltonian H on n qubits and a 1-local observable A, estimating
hAi (i.e. APX-SIM) is P
QMA[log]
-complete.
Thus, measuring just a single qubit of the ground state of a local Hamiltonian H with a single-
qubit observable A (in fact, A is ﬁxed, independent of H in our construction) is harder than QMA
(assuming QMA 6= P
QMA[log]
, which is likely as otherwise co-QMA QMA).
2. P
QMA[log]
-completeness of APX-2-CORR for O(1)-local Hamiltonians and single-qubit observ-
ables. We next introduce a second natural problem related to APX-SIM, denoted APX-2-CORR.
APX-2-CORR is deﬁned similarly to APX-SIM except one is given Hamiltonian H and observ-
ables A and B and asked to estimate the two-point correlation function hA Bi hAihBi (recall
hAi := hψ|A |ψi for |ψi a ground state of H). By modifying the construction behind the proof of
Theorem 1.1, we also show APX-2-CORR is P
QMA[log]
-complete.
Theorem 1.2. Given a 5-local Hamiltonian H on n qubits and a pair of 1-local observables A and
B, estimating hA Bi hAihBi (i.e. APX-2-CORR) is P
QMA[log]
-complete.
3. P
UQMA[log]
-hardness of estimating spectral gaps. A third well-motivated problem involving Hamil-
tonians is SPECTRAL-GAP [5]: Given a k-local Hamiltonian H, estimate λ
1
(H) λ
2
(H), where
6
λ
i
(H) denotes the i-th smallest eigenvalue of H. (For clarity, if the ground space of H is degener-
ate, we deﬁne its spectral gap as 0.) In [5], it is shown that SPECTRAL-GAP P
QMA[log]
, and
a claimed proof is given that SPECTRAL-GAP for O(log n)-local Hamiltonians H is P
UQMA[log]
-
hard. Here, P
UQMA[log]
is P
QMA[log]
except with a Unique QMA oracle, and Unique QMA is roughly
QMA with a unique accepting quantum witness in the YES case (see Section 4.3 for formal deﬁni-
tions).
Recall now that, as discussed in Section 1.3, a central theme of this work is the subtlety involved
in the study of oracle classes in which the oracle solves a promise problem (such as P
QMA[log]
),
as opposed to a decision problem (such as P
NP[log]
). In particular, for 2-LH queries to the QMA
oracle which violate the promise gap for 2-LH, the oracle is allowed to give an arbitrary answer. We
observe that this point appears to have been missed in [5]’s claimed proofs of P
QMA[log]
-hardness
of APX-SIM and of P
UQMA[log]
-hardness of SPECTRAL-GAP, rendering the proofs incorrect.
Though, as shown by our ﬁrst result, we are able to correct and improve on the proof that APX-SIM
is P
QMA[log]
-hard.
In our last result, we also overcome this diﬃculty to recover P
UQMA[log]
-hardness of SPECTRAL-
GAP, with the tradeoﬀ that we obtain a “slightly weaker” hardness claim, in the sense that it follows
from a Turing reduction as opposed to a Karp or mapping reduction
5
([5] claimed hardness under
the latter). In the process, we also improve the locality of H to O(1).
Theorem 1.3. Given a 4-local Hamiltonian H, estimating its spectral gap (i.e. SPECTRAL-GAP)
is P
UQMA[log]
-hard under polynomial-time Turing reductions.
Thus, the ability to solve P
UQMA[log]
problems in polynomial time would imply a polynomial-time
algorithm for SPECTRAL-GAP. Note that whether UQMA = QMA remains open. For the cases
of NP [60] or MA and QCMA [4], it is known that Unique NP, Unique MA, and Unique QCMA
reduce to NP, MA, and QCMA, respectively, under randomized reductions.
Upper bounds (containment in complexity classes). As mentioned earlier, since both QMA
and co-QMA are contained in P
QMA[log]
, it is likely that P
QMA[log]
is strictly more powerful than both
QMA and co-QMA. This raises the question: What is an upper bound on the power of P
QMA[log]
?
Two points of reference are worth mentioning here. First, the classical analogue of P
QMA[log]
,
P
NP[log]
, is known to be upper bounded by PP [9]. Here, PP is the set of promise problems solvable
in probabilistic polynomial time with unbounded error; in other words, a PP machine accepts YES
instances with probability strictly larger than 1/2 and accepts NO instances with probability less
than or equal to 1/2. The second point of reference is that QMA is bounded by PP [44, 49] ([61]
actually shows the slightly stronger containment QMA A
0
PP). We thus ask whether, like its
classical analogue, P
QMA[log]
can bounded by PP, and so is “slightly harder” than QMA. Indeed, we
show this is the case.
Theorem 1.4. P
QMA[log]
PP.
5
A Karp, many-one, or mapping reduction from a decision problem A to a decision problem B maps any input
Π
A
for A into an input Π
B
for B such that Π
A
is a YES (NO) instance of A if and only if Π
B
is a YES (NO) instance
for B. A Turing reduction generalizes the notion of a Karp reduction; here, one is given access to an oracle solving
B, and the goal is to solve Π
A
using potentially multiple calls to the oracle. In this paper, both notions of reduction
are assumed to be deterministic polynomial-time.
7
Thus, QMA P
QMA[log]
PP, which rigorously justiﬁes the intuition that P
QMA[log]
should be
thought of as “slightly harder” than QMA.
1.5 Proof techniques
We now outline our proof techniques for both our upper bound and lower bound results.
Lower bounds. We begin with proof techniques techniques for our lower bounds involving APX-
SIM (Theorem 1.1), APX-2-CORR (Theorem 1.2), and SPECTRAL-GAP (Theorem 1.3).
1. P
QMA[log]
-hardness of APX-SIM. To show Theorem 1.1, our intuition is simple: To design
our local Hamiltonian H so that its ground state encodes a so-called history state
6
|ψi for a given
P
QMA[log]
instance such that measuring observable Z on the designated “output qubit” of |ψi reveals
the answer of the computation. At a high level, this is achieved by combining a variant of Kitaev’s
circuit-to-Hamiltonian construction [45] (which forces the ground state to follow the P circuit) with
Ambainis’s “query Hamiltonian” [5] (which forces the ground state to encode correctly answered
queries to the QMA oracle). Making this rigorous requires a careful analysis of the ground space
of Ambainis’s query Hamiltonian when queries violating the promise gap of the oracle are allowed
(Lemma 3.1), showing a simple but useful corollary of Kempe, Kitaev, and Regev’s Projection
Lemma [43] (Corollary 4.2) that any low energy state of H must be close to a valid history state,
which thus allows us to use just a single-qubit observable, and applying Kitaev’s unary encoding
trick [45] to bring the locality of the Hamiltonian H down to O(1) (Lemma 3.3).
2. Containment of APX-2-CORR in P
QMA[log]
. The hardness proof for APX-2-CORR is similar
to that of APX-SIM, so we focus instead on the containment proof of APX-2-CORR P
QMA[log]
,
for which a trick is required. For containment, the naive approach would be to run Ambainis’s
P
QMA[log]
protocol [5] for APX-SIM independently for each term hA Bi, hAi, and hBi. However,
if a cheating prover does not send the same ground state |ψi for each of these measurements,
soundness of the protocol can be violated.
To address this, we exploit a trick of Chailloux and Sattath [19] from the setting of QMA(2):
we observe that the correlation function requires only knowledge of the two-body reduced density
matrices {ρ
ij
} of |ψi. A prover can send classical descriptions of the {ρ
ij
} (which is possible since
each ρ
ij
is of constant size), along with a “consistency proof for the QMA-complete Consistency
problem [47] to ensure the {ρ
ij
} indeed correspond to some state. The veriﬁer can then freely copy
each ρ
ij
and thus can calculate each term.
3. P
UQMA[log]
-hardness of estimating spectral gaps. As mentioned in Sections 1.3 and 1.4, a central
theme of this work is the fact that a P
QMA[log]
machine can make invalid queries to the QMA oracle,
and this point appears to have been missed in [5], where all queries were assumed to satisfy the
LH promise. This results in the proofs of two key claims of [5] being incorrect. The ﬁrst claim was
used in the proof of P
QMA[log]
-completeness for APX-SIM (Claim 1 in [5]); we provide a corrected
6
A history state can be seen as a quantum analogue of the “tableau” which appears in the proof of the Cook-Levin
theorem, i.e. a history state encodes the history of a quantum computation. In contrast to tableaus, however, the
history encodes information in quantum superposition.
8
statement and proof in Lemma 3.1 (which suﬃces for the P
QMA[log]
-hardness results in [5] regarding
APX-SIM to hold).
The error in the second claim (Claim 2 of [5]), wherein P
UQMA[log]
-hardness of determining the
spectral gap of a local Hamiltonian is shown, appears arguably more serious. The construction of [5]
requires a certain “query Hamiltonian” to have a spectral gap, which indeed holds if the P
UQMA[log]
machine makes no invalid queries. However, if the machine makes invalid queries, this gap can close,
and it is not clear how one can recover P
UQMA[log]
-hardness under mapping reductions.
To overcome this, we introduce a technique of “query validation”: given a query to the UQMA
oracle, we would like to determine if the query is valid or “far” from valid. While it is not clear how a P
machine alone can perform such “query validation”, we show how to use a SPECTRAL-GAP oracle
to do so, allowing us to eliminate “suﬃciently invalid” queries. Combining this idea with Ambainis’s
original construction [5], we show Theorem 1.3, i.e. P
UQMA[log]
-hardness for SPECTRAL-GAP,
with the additional improvement that the input Hamiltonians are now O(1)-local, versus O(log n)-
local as in [5], via the same unary encoding trick from our previous results. Since our “query
validation” requires a polynomial number of calls to the SPECTRAL-GAP oracle, this result
requires a polynomial-time Turing reduction. Whether this can be improved to a mapping reduction
is left as an open question.
Upper bounds. We now move to our upper bound result, which is the most technically involved.
To show P
QMA[log]
PP (Theorem 1.4), we exploit the technique of hierarchical voting, used by
Beigel, Hemachandra, and Wechsung [9] to show P
NP[log]
PP, in conjunction with the QMA
strong ampliﬁcation results of Marriott and Watrous [49].
To give some intuition as to how the technique works, we sketch its application in the classical
case of P
NP[log]
[9]. There, we have a P machine making queries to an NP oracle for SAT (i.e. the
i-th query feeds the oracle some SAT formulae φ
i
), and the goal is to simulate this by a PP machine.
Since the PP machine does not have access to an NP oracle, the best it can do is guess the answer to
each query; so, it begins by guessing the answers to each NP query by picking a random assignment
x
i
for each formula φ
i
in the hope that φ
i
(x
i
) = 1. Of course, such a guess x
i
can be satisfying only
if φ
i
is satisﬁable to begin with; with a bit of thought, this implies that the “correct” query string y
(i.e. the i-th bit of y
equals 1 if and only if φ
i
is satisﬁable) is the lexicographically largest string
y
attainable by this guessing process.
Unfortunately, the PP machine might have a very small probability of guessing y
; thus, it next
“boosts” this probability via several rounds of “hierarchical voting”. Conceptually, this technique
does not actually increase the probability of outputting y
but rather decreases the probability of
outputting other, lexicographically smaller query strings y
0
6= y
. This works because the machine
is a PP machine (i.e. it can have unbounded error), and so it suﬃces to reduce the probability of
obtaining any such y
0
being output to be strictly smaller than the probability of y
being output,
in which case the PP machine is more likely to output the correct answer in its simulation of the
P
NP[log]
computation than not, as needed.
We develop a quantum variant of this scheme which is quite natural. However, its analysis is
markedly more involved than the classical setting due to both the probabilistic nature of QMA and
the possibility of “invalid queries” violating the QMA promise gap. To give a sense of the problems
which arise, for P
QMA[log]
it is no longer necessarily true that the lexicographically largest obtainable
y
is a correct query string.
9
1.6 Discussion and open questions
The problems studied here explore the line of research recently initiated by Ambainis [5] on P
QMA[log]
and focus on central problems for local Hamiltonian systems. The complexity theoretic study of
such problems is appealing in that it addresses the original motivation of physicist Richard Feyn-
man in proposing quantum computers [27], who was interested in avenues for simulating quantum
systems. Indeed, hardness results, such as Kitaev’s quantum Cook-Levin theorem, rigorously justify
Feynman’s intuition that such simulation problems are hard. Our work (e.g. Theorem 1.1) strongly
supports this view by demonstrating that even some of the simplest and most natural simulation
tasks, such as measuring a single qubit (!) of a ground state, can be harder than QMA. Our study
of spectral gaps (Theorem 1.3) further highlights another theme: the subtleties which must be care-
fully treated when studying oracle classes for promise problems (such as P
QMA[log]
). As quantum
complexity theory commonly focuses on such promise problems, we believe this theme could be of
interest to a broader computer science audience.
Moving to open questions, although we resolve one of the open questions from [5], there are others
we leave open, along with some new ones. Do our results for APX-SIM and APX-2-CORR hold
for more restricted classes of Hamiltonians, such as 2-local Hamiltonians, local Hamiltonians on a
2D lattice, or speciﬁc Hamiltonian models of interest (see e.g. [22, 53] for QMA-completeness results
for estimating ground state energies of the spin-1/2 Heisenberg anti-ferromagnet)? Is SPECTRAL-
GAP P
UQMA[log]
-complete or P
QMA[log]
-complete (recall SPECTRAL-GAP P
QMA[log]
and that
[5] and our work together show P
UQMA[log]
-hardness)? What is the relationship between P
QMA[log]
and P
UQMA[log]
? Finally, what is the complexity of other physical tasks “beyond” estimating ground
state energies?
Remark added later: Since the original preprint of this paper appeared, the present authors, together
with Stephen Piddock, have partially answered the ﬁrst open question above by showing [33] that
APX-SIM remains P
QMA[log]
-complete for any family of local Hamiltonians which can simulate
“spatially sparse” [51] Hamiltonians. This, in turn, implies (e.g. using [53], [58], [54]) that APX-SIM
remains P
QMA[log]
-complete even on physically motivated models, such as the Heisenberg interaction
on a 2D square lattice.
Organization. This paper is organized as follows: In Section 2, we give notation and formal
deﬁnitions. In Section 3, we show various lemmas regarding Ambainis’s query Hamiltonian. In
Section 4.1, Section 4.2, and Section 4.3 we show Theorem 1.1, Theorem 1.2, and Theorem 1.3,
respectively. Section 5 proves Theorem 1.4. A result used in Section 3 is proved in Appendix A.
2 Preliminaries
Notation. For x {0, 1 }
n
, |xi (C
2
)
n
denotes the computational basis state labeled by x. Let
X be a complex Euclidean space. Then, L (X) and D (X) denote the sets of linear and density
operators acting on X, respectively. For subspace S X, S
denotes the orthogonal complement
of S. For Hermitian operator H, λ(H) and λ(H|
S
) denote the smallest eigenvalue of H and the
smallest eigenvalue of H restricted to space S, respectively. The spectral and trace norms are
deﬁned kAk
:= max{kA |vik
2
: k|vik
2
= 1} and kAk
tr
:= Tr
A
A, respectively, where :=
denotes a deﬁnition. We set [m] := {1, . . . , m }.
10
Deﬁnitions and lemmas.
PP and PQP. The class PP [34] is the set of decision problems for which there exists a polynomial-
time probabilistic Turing machine which accepts any YES instance with probability > 1/2 and
accepts any NO instance with probability 1/2. The quantum analogue of PP, denoted PQP, is
deﬁned analogously to BQP except in the YES case the veriﬁer accepts with probability > 1/2 and
in the NO case the veriﬁer accepts with probability 1/2.
P
QMA[log]
. Deﬁned by Ambainis [5], P
QMA[log]
is the set of decision problems decidable by a
polynomial-time deterministic Turing machine with the ability to query an oracle for a QMA-
complete problem O(log n) times, where n is the size of the input. For clarity, without loss of
generality we assume that for any QMA problem instance Π the P machine wishes to solve, it ap-
plies a polynomial-time Karp/many-one reduction to map Π to an instance of the QMA-complete
problem 2-LH [43] which it then feeds to the QMA oracle. 2-LH is deﬁned as: Given a 2-local
Hamiltonian H and inverse polynomially separated thresholds a, b R, decide whether λ(H) a
(YES-instance) or λ(H) b (NO-instance). Note that the P machine is allowed to make queries
which violate the promise gap of 2-LH, i.e. with λ(H) (a, b); in this case, the oracle can output
YES or NO arbitrarily. The P machine is nevertheless required to output the same ﬁnal answer
(i.e. accept or reject) regardless of how such “invalid” queries are answered [36].
For any P machine M making m queries to a QMA oracle, we use the following terminology
throughout this article. A valid (invalid) query satisﬁes (violates) the promise gap of the QMA
oracle. A correct query string y {0, 1 }
m
encodes a sequence of correct answers to all of the
m queries. Note that for any invalid query by M, any answer is considered correct, yielding the
possible existence of multiple correct query strings. An incorrect query string is one which contains
at least one incorrect query answer.
The problem APX-SIM.
Deﬁnition 2.1 (APX-SIM(H, A, k, l, a, b, δ) (Ambainis [5])). Given a k-local Hamiltonian H, an
l-local observable A, and real numbers a, b, and δ such that b a n
c
and δ n
c
0
, for n the
number of qubits H acts on and c, c
0
> 0 some constants, decide:
If H has a ground state |ψi satisfying hψ|A |ψi a, output YES.
If for all |ψi satisfying hψ|H |ψi λ(H) + δ, it holds that hψ|A |ψi b, output NO.
Kitaev’s circuit-to-Hamiltonian construction. Next, we brieﬂy review Kitaev’s circuit-to-Hamiltonian
construction from the “quantum Cook-Levin theorem” [45]. Given a quantum circuit U = U
L
···U
1
consisting of 1- and 2-qubit gates U
i
and acting on registers Q (proof register) and W (workspace
register), this construction maps U to a 5-local Hamiltonian H = H
in
+ H
out
+ H
prop
+ H
stab
acting
on registers Q (proof register), W (workspace register), and C (clock register). Each of H’s terms
11
are deﬁned below:
H
in
:=
p
X
i=1
|1ih1|
W
i
!
|0ih0|
C
H
out
:= |0ih0|
W
1
|LihL|
C
H
prop
:=
L
X
j=1
H
j
, where H
j
is deﬁned as
1
2
U
j
|jihj 1|
C
1
2
U
j
|j 1ihj|
C
+
1
2
I (|jihj| + |j 1ihj 1|)
C
H
stab
:=
L1
X
i=1
|01ih01|
C
i
,C
i+1
.
Above, the notation R
i
refers to the i-th qubit of any given register R. For any candidate proof
|ψi to be evaluated in expression Tr(H |ψihψ|), each penalty term of H forces a structure on any
minimizing |ψi: at time zero, H
in
ensures the workspace register W is set to zero; H
out
checks that
at the end of the computation, i.e. at time step L, the output qubit is close to |1i; the propagation
Hamiltonian H
prop
ensures all steps of U appear in superposition in |ψi with equal weights. Finally,
although we have labeled (for ease of exposition) the clock register in H
out
and H
prop
in binary, note
that in Kitaev’s construction it is actually encoded in unary. In other words, time t in clock register
C is encoded as |1
t
0
Lt
i (note for H
stab
above, register C is already written in unary); H
stab
’s role is
thus to prevent invalid encodings of time steps. (For the interested reader, we remark that instead
of working explicitly with Kitaev’s construction, one can also consider the more general Quantum
Thue System framework [7].)
In this paper, we shall use two key properties of H
in
+ H
prop
+ H
stab
(note H
out
is omitted).
First, the null space of H
in
+ H
prop
+ H
stab
is spanned by history states, which for any proof |ψi
have form
|ψ
hist
i =
1
L + 1
L
X
t=0
U
t
···U
1
|ψi
Q
|0 ···0i
W
|ti
C
, (1)
where C is a clock register keeping track of time [45], and each U
i
acts on at most two qubits from
registers Q and W . Second, we use the following lower bound
7
on the smallest non-zero eigenvalue
of H
in
+ H
prop
+ H
stab
:
Lemma 2.2 (Lemma 3 (Gharibian, Kempe [29])). The smallest non-zero eigenvalue of ∆(H
in
+
H
prop
+ H
stab
) is at least π
2
/(64L
3
) Ω(∆/L
3
), for R
+
and L 1.
Miscellaneous useful facts. Let V denote a QMA veriﬁcation circuit acting on M proof qubits with
completeness c and soundness s. If one runs V on “proofρ = I/2
M
, then for a YES instance,
V accepts with probability c/2
M
(since I/2
M
can be viewed as “guessing” a correct proof with
probability 1/2
M
), and in a NO instance, V accepts with probability s (see, e.g., [49, 62]).
A useful fact for complex unit vectors |vi and |wi is (see, e.g., Equation 1.33 of [28])
k|vihv| |wihw|k
tr
= 2
q
1 |hv|wi|
2
2 k|vi |wik
2
. (2)
7
This bound is stated as Ω(∆/L
3
) in [29]; the constant π
2
/64 can be derived from the analysis therein .
12
3 Ambainis’s Query Hamiltonian
We now show various results regarding Ambainis’s “query Hamiltonian” [5], which intuitively aims
to have its ground space contain correct answers to a sequence of QMA queries. Let U be a P
QMA[log]
computation
8
, and let H
i,y
1
···y
i1
Y
i
be the 2-local Hamiltonian
9
corresponding to the i-th query made
by U given that the answers to the previous i 1 queries are given by y
1
···y
i1
{0, 1 }
0,1
.
(Without loss of generality, we may assume H
i,y
1
···y
i1
Y
i
0 by adding multiples of the identity and
rescaling.) The oracle query made at step i corresponds to an input (H
i,y
1
···y
i1
Y
i
, , 3) to 2-LH, with
(as in [5]) completeness/“YES case” and soundness/“NO case” parameters and 3, respectively,
for > 0 a ﬁxed inverse polynomial. Then, Ambainis’s [5] O(log(n))-local query Hamiltonian H
acts on X Y, where X = (X
i
)
m
= (C
2
)
m
and Y =
m
i=1
Y
i
, such that X
i
is intended to encode
the answer to query i with Y
i
encoding the ground state of the corresponding query Hamiltonian
H
i,y
1
···y
i1
Y
i
. Speciﬁcally,
H =
m
X
i=1
1
4
i1
X
y
1
,...,y
i1
i1
O
j=1
|y
j
ihy
j
|
X
j
2 |0ih0|
X
i
I
Y
i
+ |1ih1|
X
i
H
i,y
1
···y
i1
Y
i
=:
m
X
i=1
1
4
i1
X
y
1
,...,y
i1
M
y
1
···y
i1
. (3)
Recall from Section 2 that a sequence of query answers y = y
1
···y
m
{0, 1 }
m
is correct if it
corresponds to a possible execution of U. Since U can make queries to its QMA oracle which violate
the QMA promise gap, the set of correct y is generally not a singleton. However, we henceforth
assume without loss of generality that U makes at least one valid query (i.e. which satisﬁes the
QMA promise gap). (Assume to the contrary that U makes only invalid queries. Then, since recall
we stipulate [36] that the oracle’s answer on any invalid query must not aﬀect the ﬁnal output
of U, it follows that for all possible query strings, U outputs the same answer. Moreover, since
m O(log n), we can eﬃciently verify this property simply iterate via brute force through all
possible polynomially many query strings, and check that U outputs the same answer for each
one. Therefore, we can assume that any reduction includes such a check as an implicit subroutine,
prepended to the start of the reduction, which will handle any case in which U makes only invalid
queries.) We now prove the following about H:
Lemma 3.1. Deﬁne for any x {0, 1 }
m
the space H
x
1
···x
m
:=
N
m
i=1
|x
i
ihx
i
| Y
i
. Then, there
exists a correct query string x {0, 1 }
m
such that the ground state of H lies in H
x
1
···x
m
. Moreover,
suppose this space has minimum eigenvalue λ. Then, for any incorrect query string y
1
···y
m
, any
state in H
y
1
···y
m
has energy at least λ +
4
m
.
As discussed in Section 1, Claim 1 of [5] proved a similar statement under the assumption that the
correct query string x is unique. In that setting, [5] showed the ground state of H is in H
x
, and that
for all query strings y 6= x, the space H
y
has energy at least λ +
4
m1
. However, in general invalid
8
In this work, we let U denote a uniformly generated classical circuit, as opposed to a Turing machine; this is to
ease the transition to quantum circuits and corresponding application of Kitaev’s circuit-to-Hamiltonian construction
later.
9
While each query is encoded as a 2-local Hamiltonian, our hardness results in Section 4 will be for 5- and 4-local
Hamiltonians, since the query Hamiltonians are just components of our larger, ﬁnal Hamiltonian constructions.
13
queries must be allowed, and in this setting this claim no longer holds two distinct correct query
strings can have eigenvalues which are arbitrarily close if they contain queries violating the promise
gap. The key observation we make here is that even in the setting of non-unique x, a spectral gap
between the ground space and all incorrect query strings can be shown.
Proof of Lemma 3.1. Observe ﬁrst that H in Equation (3) is block-diagonal with respect to register
X, i.e. to understand the spectrum of H, it suﬃces to understand the eigenvalues in each of the
blocks corresponding to ﬁxing X
i
to some string y {0, 1 }
m
. Thus, we can restrict our attention
to spaces H
y
for y {0, 1 }
m
. To begin, let x {0, 1 }
m
denote a correct query string which has
lowest energy among all correct query strings against H, i.e. the block corresponding to x has
the smallest eigenvalue among such blocks. (Note that x is well-deﬁned, though it may not be
unique; in this latter case, any such x will suﬃce for our proof.) For any y {0, 1 }
m
, deﬁne λ
y
as the smallest eigenvalue in block H
y
. We show that for any incorrect query string y = y
1
···y
m
,
λ
y
λ
x
+ /(4
m
).
We use proof by contradiction, via an exchange argument
10
. Suppose there exists an incorrect
query string y = y
1
···y
m
such that λ
y
< λ
x
+ /(4
m
). Since y is an incorrect query string, there
exists an i [m] such that y
i
is the wrong answer to a valid query H
i,y
1
···y
i1
Y
i
. Let i denote the ﬁrst
such position. Now, consider operator M
y
1
···y
i1
, which recall is deﬁned as
M
y
1
···y
i1
=
i1
O
j=1
|y
j
ihy
j
|
X
j
2 |0ih0|
X
i
I
Y
i
+ |1ih1|
X
i
H
i,y
1
···y
i1
Y
i
and let λ
y
1
···y
i1
y
i
denote the smallest eigenvalue of M
y
1
···y
i1
restricted to space H
y
1
···y
i1
y
i
, where
y
i
denotes the complement of bit y
i
; for clarity, here we deﬁne
H
y
1
···y
i1
y
i
:= |y
1
ihy
1
|
X
1
··· |y
i
ihy
i
|
X
i
m
O
j=i+1
X
j
Y.
Note that string y
1
···y
i1
y
i
corresponds to i correct query bits, with y
i
the correct answer to
query i. Then, we claim that any state |φi H
y
1
···y
i
(i.e. |φi is of the same dimension as H, with
registers X
1
through X
i
ﬁxed to state |y
1
i ··· |y
i
i) satisﬁes the bound of the following lemma.
Lemma 3.2. For |φi, M
y
1
···y
i1
, and λ
y
1
···y
i1
y
i
as deﬁned above, we have
hφ|M
y
1
···y
i1
|φi λ
y
1
···y
i1
y
i
+ .
Here, for clarity, M
y
1
···y
i1
is of the same dimension as |φi, since we assume M
y
1
···y
i1
has an implicit
tensor product with term I
X
i+1
⊗Y
i+1
···⊗X
m
⊗Y
m
. (This is intuitively because M
y
1
···y
i1
corresponds
to making query i given responses to queries 1 through i 1, and queries i + 1 through m are yet
to be determined.)
10
At a high level, in an exchange argument, one begins with a solution y to some problem instance, where y is
lacking some additional desired property P . One then shows how to “exchange” y for another solution y
0
such that y
0
is at least as “good” as y for the problem at hand, and so that y
0
now has the desired property P . In our application
here, we will exchange query string y for a query string y
0
satisfying λ
y
0
< λ
y
. The property P in this case will be
whether the query string correct.
14
Proof. Constrained to space H
y
1
···y
i1
, M
y
1
···y
i1
reduces to operator M
0
:= 2 |0ih0|
X
i
I
Y
i
+
|1ih1|
X
i
H
i,y
1
···y
i1
Y
i
, which is block-diagonal in the standard basis with respect to X
i
. Thus, if
query i is a YES instance, the smallest eigenvalue of M
0
lies in the block corresponding to setting
X
i
to (the correct query answer) |1i, and is at most (since we are assuming each query has YES
and NO energy thresholds and 3). On the other hand, the block with X
i
set to |0i by deﬁnition
reduces to 2I
Y
i
, and hence has all eigenvalues equaling 2. Thus, setting X
i
to the correct query
answer |1i yields an energy penalty which is at least less than the penalty obtained for setting X
i
to the wrong query answer, |0i. Analogously, when query i is a NO instance (i.e. the correct query
answer is |0i), a similar argument shows the |0i-block again has eigenvalues equaling 2 and now
the |1i-block has eigenvalues at least 3. We conclude that in both YES and NO cases, setting X
i
to the correct query answer achieves an energy penalty at least less than setting X
i
to the wrong
query answer. As a result,
λ
y
1
···y
i1
y
i
λ
y
1
···y
i
,
which implies the claim.
With Lemma 3.2 in hand, we return to our exchange argument. Let
c
M
y
1
···y
t
denote the set
of terms from Equation (3) which are consistent with some preﬁx y
1
. . . y
t
(e.g. M
y
1
...y
t
, M
y
1
...y
t
0
,
M
y
1
...y
t
1
, etc). Recall that the bits y
i+1
···y
m
form the tail of the string y following the incorrect
i
. Set y
0
i+1
···y
0
m
so that y
0
:= y
1
···y
i
y
0
i+1
···y
0
m
is a correct query string. Care
is now required; the new query bits y
0
i+1
···y
0
m
may lead to diﬀerent energy penalties than the
previous string y
i+1
···y
m
against the Hamiltonian terms in set
c
M
y
1
···y
i
. In other words, we must
upper bound any possible energy penalty increase when exchanging y
1
···y
i
y
i+1
···y
m
for y
0
. To do
so, recall that all Hamiltonian terms in Equation (3) are positive semideﬁnite. Thus, for any state
|ψi in space H
y
1
···y
i
, the energy obtained by |ψi against terms in
c
M
y
1
···y
i
is at least 0. Conversely,
in the worst case, since each term in
c
M
y
1
···y
i
has minimum eigenvalue at most 2, the eigenvector
|ψi of smallest eigenvalue in block H
y
0
incurs an additional penalty against H for queries i + 1
through m of at most (taking into account the normalization factor 1/4
i1
in Equation (3))
2
X
k=i
1
4
k
=
2
3 · 4
i1
.
We conclude that (again taking into account the normalization factor 1/4
i1
in Equation (3))
λ
y
0
λ
y
4
i1
+
2
3 · 4
i1
<
λ
x
+
4
m
4
i1
+
2
3 · 4
i1
< λ
x
where the second inequality follows by the assumption λ
y
< λ
x
+ /4
m
. This is a contradiction.
The next lemma converts H from an O(log n)-local Hamiltonian to an O(1)-local one.
Lemma 3.3. For any x {0, 1 }
m
, let ˆx denote its unary encoding. Then, for any P
QMA[log]
circuit U acting on n bits and making m 1 queries to a QMA oracle, there exists a mapping to a
4-local Hamiltonian H
0
acting on space (C
2
)
2
m
1
Y such that there exists a correct query string
x = x
1
···x
m
satisfying:
1. The ground state of H
0
lies in subspace |ˆxihˆx| Y.
15
2. For any state |ψi in subspace |ˆx
0
ihˆx
0
|Y where either ˆx
0
is not a unary encoding of a binary
string x
0
or x
0
is an incorrect query string, one has hψ|H
0
|ψi λ(H
0
) + /4
m
, for inverse
polynomial .
3. For all strings x
0
{0, 1 }
m
, H
0
acts invariantly on subspace |ˆx
0
ihˆx
0
| Y.
4. The mapping can be computed in time polynomial in n (recall m O(log n)).
Proof. We show how to improve the O(log n)-local construction H of Lemma 3.1 to 4-local H
0
.
Speciﬁcally, recall that H from Equation (3) acts on (X Y). Using a trick of Kitaev [45], we
encode the X = X
1
··· X
m
register in unary. Speciﬁcally, we can write
M
y
1
···y
i1
=
X
y
i+1
,...,y
m
2
i1
O
j=1
|y
j
ihy
j
|
X
j
|0ih0|
X
i
m
O
k=i+1
|y
k
ihy
k
|
X
k
I
Y
+
i1
O
j=1
|y
j
ihy
j
|
X
j
|1ih1|
X
i
m
O
k=i+1
|y
k
ihy
k
|
X
k
H
i,y
1
···y
i1
Y
i
.
We now replace register X
1
···X
m
with register X
0
= (C
2
)
2
m
1
and encode each binary string
x {0, 1 }
m
as the unary string ˆx = |1i
⊗|x|
|0i
2
m
−|x|−1
, where |x| is the non-negative integer
corresponding to string x. In other words, for M
x
1
···x
i1
, we replace each string |xihx|
X
1
⊗···⊗X
m
with |1ih1|
X
1
⊗···⊗X
|x|
|0ih0|
X
|x|+1
⊗···⊗X
2
m
1
. Denote the resulting Hamiltonian as H
1
.
To ensure states in X
0
follow this encoding, add a weighted version of Kitaev’s [45] penalty
Hamiltonian, introduced in Section 2,
H
stab
= 3
2
m
2
X
j=1
|0ih0|
j
|1ih1|
j+1
,
i.e., our ﬁnal Hamiltonian is H
0
= H
1
+ H
stab
. To show that H
0
satisﬁes the same properties as H
as stated in the claim, we follow the analysis of Kitaev [45]. Namely, partition the space X
0
Y
into orthogonal spaces S and S
corresponding to the space of valid and invalid unary encodings
of X
0
, respectively. Since H
1
and H
stab
act invariantly on S and S
, we can consider S and S
separately. In S, H
0
is identical to H, implying the claim. In S
, the smallest non-zero eigenvalue
of H
stab
is at least 3. Thus, since H
1
0, if we can show that the smallest eigenvalue of H is at
most 3 /4
m
, we have shown the claim (since, in particular, we will have satisﬁed statement 2 of
our claim). To show this bound on the smallest eigenvalue, suppose x is all zeros, i.e. set register
X
1
···X
m
for H to all zeros. Then, each term M
0
1
···0
i1
yields an energy penalty of exactly 2,
yielding an upper bound on the smallest eigenvalue of H of 2
P
m1
k=0
1
4
k
8
3
= 3 /3.
4 Lower bounds (hardness results)
4.1 P
QMA[log]
-completeness of APX-SIM
In this section, we restate and prove Theorem 1.1. For this, we ﬁrst show a corollary of the Projection
Lemma of Kempe, Kitaev, Regev [43]. For completeness, we ﬁrst state the Projection Lemma.
16
Lemma 4.1 (Kempe, Kitaev, Regev [43]). Let H = H
1
+ H
2
be the sum of two Hamiltonians
operating on some Hilbert space H = S + S
. The Hamiltonian H
1
is such that S is a zero
eigenspace and the eigenvectors in S
have eigenvalue at least J > 2 kH
2
k
. Then,
λ(H
2
|
S
)
kH
2
k
2
J 2 kH
2
k
λ(H) λ(H
2
|
S
),
where recall λ(H
2
|
S
) denotes the smallest eigenvalue of H
2
restricted to space S.
Corollary 4.2. Let H = H
1
+ H
2
be the sum of two Hamiltonians operating on some Hilbert space
H = S + S
. The Hamiltonian H
1
is such that S is a zero eigenspace and the eigenvectors in S
have eigenvalue at least J > 2 kH
2
k
. Let K := kH
2
k
. Then, for any δ 0 and vector |ψi satis-
fying hψ|H |ψi λ(H) + δ, there exists a |ψ
0
i S such that |hψ|ψ
0
i|
2
1
K+
K
2
+δ(J2K)
J2K
2
.
Proof. Consider arbitrary |ψi such that hψ|H |ψi λ(H) + δ. We can write |ψi = α
1
|ψ
1
i+ α
2
|ψ
2
i
for |ψ
1
i S, |ψ
2
i S
, α
1
, α
2
R, α
1
, α
2
0, and α
2
1
+ α
2
2
= 1. The proof of Lemma 4.1 yields
hψ|H |ψi λ(H
2
|
S
) + (J 2K)α
2
2
2Kα
2
. (4)
For completeness, we reproduce the steps from [43] to derive this inequality as follows:
hψ|H |ψi hψ|H
2
|ψi + Jα
2
2
= (1 α
2
2
) hψ
1
|H
2
|ψ
1
i + 2α
1
α
2
Re hψ
1
|H
2
|ψ
2
i +
α
2
2
hψ
2
|H
2
|ψ
2
i + Jα
2
2
hψ
1
|H
2
|ψ
1
i K(α
2
2
+ 2α
2
+ α
2
2
) + Jα
2
2
= hψ
1
|H
2
|ψ
1
i + (J 2K)α
2
2
2Kα
2
λ(H
2
|
S
) + (J 2K)α
2
2
2Kα
2
.
Since by assumption hψ|H |ψi λ(H)+δ, Equation (4) implies λ(H)+δ λ(H
2
|
S
)+(J 2K)α
2
2
2Kα
2
. Combining this with Lemma 4.1, we have
0 λ(H) λ(H
2
|
S
) (J 2K)α
2
2
2Kα
2
δ,
which holds only if |α
2
|
K+
K
2
+δ(J2K)
J2K
. Thus, setting |ψ
0
i = |ψ
1
i yields the claim.
With Corollary 4.2 in hand, we now prove the main result of this section.
Theorem 1.1. APX-SIM is P
QMA[log]
-complete for k = 5 and l = 1, i.e., for 5-local Hamiltonian
H and 1-local observable A.
Proof. Containment in P
QMA[log]
was shown
11
for k, l O(log n) in [5], for n the input size. We
show P
QMA[log]
-hardness of APX-SIM via a polynomial-time mapping/Karp reduction.
11
Intuitively, the idea is as follows. First, the P machine uses O(log n) queries to perform a version of binary search
tailored to promise problems to estimate the ground state energy of the given Hamiltonian H to within additive
inverse polynomial error; call this estimate g. Then, the P machine makes one ﬁnal QMA query: Does H have a
ground state |ψi with ground state energy approximately g and with small expectation against the given observable
A?
17
Let U
0
be an arbitrary P
QMA[log]
circuit
12
for instance Π, such that U
0
acts on workspace register
W and query result register Q. Suppose U
0
consists of L
0
gates and makes m = c log(n) queries, for
c O(1). Without loss of generality, U
0
can be simulated with a similar unitary U which treats Q
as a proof register which it does not alter at any point: Namely, U does not have access to a QMA
oracle, but rather reads bit Q
i
whenever it desires the answer to the i-th query. Thus, if a correct
query string y
1
···y
m
corresponding to an execution of U
0
on input x is provided in Q as a “proof”,
then the output statistics of U
0
and U are identical. We can also assume that Q is encoded not in
binary, but in unary. Thus, Q consists of 2
m
1 poly(n) bits. For simplicity, however, in our
discussion we will speak of m-bit query strings y = y
1
···y
m
in register Q.
The construction. We now construct our instance of APX-SIM. First, we map U to a 5-local
Hamiltonian H
1
via a modiﬁcation of the circuit-to-Hamiltonian construction of Kitaev [45], such
that H
1
acts on registers W (workspace register), Q (proof register), and C (clock register). Recall
(Section 2) that Kitaev’s construction outputs Hamiltonian terms H
in
+ H
prop
+ H
stab
+ H
out
. Set
H
1
= ∆(H
in
+ H
prop
+ H
stab
) for to be set as needed. In contrast to [45], it is crucial that H
out
be omitted from H
1
, as we require our ﬁnal Hamiltonian H to enforce a certain structure on the
ground space regardless of whether the computation should accept or reject. The job of “checking
the output” will instead be delegated to the observable A. Formally, following the discussion
in Section 2 regarding Equation (1), H
1
has a non-trivial null space, which is its ground space,
consisting of history states |ψ
hist
i (see Equation (1)) which simulate U on registers W and Q.
These history states correctly simulate U
0
assuming that Q is initialized to a correct proof.
To thus enforce that Q is initialized to a correct proof, let H
2
be our variant H
0
of Ambainis’s
query Hamiltonian from Lemma 3.3, such that H
2
acts on registers Q and Q
0
, where for clarity
Q = (C
2
)
2
m
1
for m O(log n); moreover, setting Q
0
= Y from Lemma 3.3 enforces the ground
space of H
2
to contain unary encodings of valid strings of query answers y
1
···y
m
for input Π in
register Q, as desired. Our ﬁnal Hamiltonian is H = H
1
+ H
2
, which is 5-local since H
1
is 5-local