Instructions: To add a question/comment to a specific line, equation, table or graph simply click on it.
Click on the annotations on the left side of the paper to read and reply to the questions and comments.
QCMA hardness of ground space connectivity for
commuting Hamiltonians
David Gosset
1 2
, Jenish C. Mehta
1
, and Thomas Vidick
1
1
California Institute of Technology
2
IBM T.J Watson Research Center
July 14, 2017
In this work we consider the ground space connectivity problem for commuting local
Hamiltonians. The ground space connectivity problem asks whether it is possible to
go from one (eﬃciently preparable) state to another by applying a polynomial length
sequence of 2-qubit unitaries while remaining at all times in a state with low energy for
a given Hamiltonian H. It was shown in [GS15] that this problem is QCMA-complete for
general local Hamiltonians, where QCMA is deﬁned as QMA with a classical witness and
BQP veriﬁer. Here we show that the commuting version of the problem is also QCMA-
complete. This provides one of the ﬁrst examples where commuting local Hamiltonians
exhibit complexity theoretic hardness equivalent to general local Hamiltonians.
1 Introduction
Since the deﬁnition and development of NP completeness in the 1970s [Coo71], constraint satisfac-
tion problems and their hardness have been intensively studied. The following problem, called the
k-constraint satisfaction problem (k-CSP), generalizes many well-known NP-complete problems:
Given a set of n variables each taking values in a ﬁnite set S, and given a set of constraints on the
values that any k-tuple of variables can take, is there an assignment to the variables such that all
constraints are satisﬁed? A quantum variant of the k-CSP, called the k-local Hamiltonian problem
(k-LH), is deﬁned as follows: Given a Hamiltonian H =
P
m
i=1
H
i
acting on n qubits, such that
each H
i
is Hermitian positive semideﬁnite of norm at most 1 and acts non-trivially on at most k
qubits, decide whether the smallest eigenvalue of H is smaller than some threshold α or larger than
β (where β α = Ω(poly
1
(n)). The 5-local Hamiltonian problem was proven to be complete for
the complexity class QMA by Kitaev in 1999 [KSV02]; this result plays the same foundational role
as the Cook-Levin theorem in classical complexity theory. Following this result, it was shown that
the 3- and even 2-local Hamiltonian problems are QMA-complete [KR03, KKR06].
One can straightforwardly encode a classical k-CSP (acting on bits) as an instance of the k-local
Hamiltonian problem by converting each classical constraint into a diagonal Hermitian operator
H
i
. In this case, for all i and j, the terms H
i
and H
j
commute, i.e. H
i
H
j
= H
j
H
i
. The problem of
approximating the ground energy of commuting Hamiltonians (call it the k-CLH) thus lies between
the k-CSP and k-LH. Intriguingly, commuting Hamiltonians seem to share features of both classical
and quantum systems. It is known that ground states of commuting Hamiltonians can be highly
Accepted in Quantum 2017-06-19, click title to verify 1
arXiv:1610.03582v2 [cs.CC] 12 Jul 2017
entangled (e.g., Kitaev’s toric code [Kit03]). On the other hand, it was shown by Bravyi and Vyalyi
that 2-CLH for qudits is in NP [BV03]. It was subsequently shown that the 3-CLH for qubits and
4-CLH for qubits on a grid are also in NP[AE11, Sch11]. The complexity of k-CLH for general k
remains open.
In this paper we investigate the commutative version of a diﬀerent problem related to local
Hamiltonians. Speciﬁcally, we consider the ground state connectivity problem introduced in [GS15].
Given a local Hamiltonian H on n qubits and two quantum circuits that prepare starting and ﬁnal
states |ψi and |φi, is there a sequence of poly(n) local unitaries which maps |ψi to |φi and is
such that all intermediate states have energy close to the ground energy of H? This problem is
motivated by the analogous classical connectivity problems [GKMP09]. Although it is not believed
that QCMA is in NP, the inclusion is consistent with our current state of knowledge. In particular, all
known explicit constructions of commuting Hamiltonians have ground states that can be succinctly
described by a classical witness. This motivates the introduction of the ground state connectivity
problem as an attempt to deﬁne a “hard” problem for commuting Hamiltonians. An interesting class
of local Hamiltonian for which the problem is relevant are quantum memories based on stabilizer
codes [BLP
+
16], which by deﬁnition have the property that they have eﬃciently preparable ground
states that cannot be connected by a low-energy path, due to the presence of an energy barrier.
It was shown in [GS15] that the ground space connectivity problem is QCMA-complete for 5-
local Hamiltonians. Here we show that the connectivity problem for commuting local Hamiltonians
is just as hard.
Theorem (Informal). Given an n-qubit commuting local Hamiltonian H, and quantum circuits
which prepare two states |ψi and |φi in the ground space of H, it is QCMA-complete to decide
if there exists a poly(n)-length sequence of 2-local unitaries which maps |ψi to |φi such that all
intermediate states have low energy for H.
To the best of our knowledge, this is the ﬁrst problem in which commuting local Hamiltonians
exhibit complexity theoretic hardness equivalent to that of general local Hamiltonians.
To prove the theorem one must show both containment in, and hardness for, QCMA. Con-
tainment in QCMA is straightforward, and follows from [GS15]. To prove QCMA-hardness, we
give a reduction from a simple problem which we call the 2-layer problem. Roughly speaking this
problem can be described as follows. One is given two local Hamiltonians A and B which are each
composed of commuting local terms. One is asked to decide if A + B has an eﬃciently preparable
state with low energy, or all states have high energy for A + B (promised that one of these possibil-
ities holds). We deduce QCMA-completeness of this 2-layer problem using a simple reduction from
QCMA circuit satisﬁability. We include the proof in Appendix A.
1
Our main contribution is a Karp
reduction from the 2-layer problem to the ground space connectivity problem, whereby a 2-layer
Hamiltonian A + B is mapped to a commuting local Hamiltonian H
A
+ H
B
+ G. It is designed so
that we can use tools from [GS15] to analyze the resulting commuting Hamiltonian, after certain
small modiﬁcations that enhance their generality.
In section 2, we review relevant background, and deﬁne the computational problems of interest.
In section 3, we give the reduction which establishes QCMA-completeness of the ground state
connectivity problem for commuting Hamiltonians. We conclude in section 4.
1
We note that it may also be possible to establish QCMA-completeness of the 2-layer problem using known 1D
circuit-to-Hamiltonian mappings such as the one from [AGIK09].
2
2 Preliminar ies
The reader is referred to [Wat11] for relevant background in linear algebra and quantum information,
and [AB09] for background in complexity theory. We give less standard notation and deﬁnitions
here.
We consider ﬁnite-dimensional Hilbert spaces over the complex ﬁeld C. The space of n qudits
is (C
d
)
n
. Throughout the paper, for simplicity, we consider only qubits, for which d = 2, though
our results hold for any constant qudit dimension d.
For any operator A, the operator norm will be denoted as kAk = max
kxk=1
kAxk. The trace
norm is kAk
tr
= Tr(
A
A).
We use the following terminology. For an integer 1 k n, we say that a n-qubit linear
operator is k-local if it can be written as I L where L acts on at most k qubits. A k-local
Hamiltonian is H =
P
i
H
i
where each H
i
is a k-local Hermitian operator. We will always assume
the normalization kH
i
k 1 and that H
i
is positive semideﬁnite for each i. The Hamiltonian is said
to be commuting when the H
i
pairwise commute. To emphasize that a given Hamiltonian may
not be commuting we sometimes call it a general, or non-commuting, k-local Hamiltonian. We say
that a k-local Hamiltonian is a-layered if the H
i
can be partitioned into a sets such that the terms
within the same set commute. Thus a commuting Hamiltonian is 1-layered. The ground energy of
a Hamiltonian H is its smallest eigenvalue. A ground state of a Hamiltonian H is any unit vector
in its ground space, the eigenspace associated with the smallest eigenvalue of H. We use |0i
n
and
|0
n
i interchangeably.
Deﬁnition 1 (Eﬃciently preparable states). A family {|ψ
n
i} of states is eﬃciently preparable if
for each n, there is a sequence of poly(n) 2-local unitaries that can prepare |ψ
n
i from |0i
n
.
A promise language is a pair L = (L
yes
; L
no
) with L
yes
, L
no
{0, 1}
and L
yes
L
no
= , where
L
yes
are strings in the language and L
no
are strings not in the language.
Deﬁnition 2 (QCMA). We say that a promise language L is in the complexity class QCMA if
there exist polynomials p, q and a deterministic Turing machine that on input x {0, 1}
outputs
in time q(|x|) (where |x| is the length of x) the description of a quantum circuit Q
x
acting on p(|x|)
qubits such that the following holds:
x L y {0, 1}
p(|x|)
, kΠ
1
Q
x
|yik
2
3
,
x 6∈ L y {0, 1}
p(|x|)
, kΠ
1
Q
x
|yik
1
3
,
where Π
1
= |1ih1| I is the orthogonal projection onto the state |1i on the ﬁrst qubit.
The constants
2
3
and
1
3
are arbitrary and can be ampliﬁed to (1 2
poly(n)
, 2
poly(n)
) using
standard techniques (we will use this fact later on).
We ﬁnally deﬁne the ground space connectivity problem for commuting Hamiltonians. Given a
k-local commuting Hamiltonian H and two eﬃciently preparable states |ψi and |φi in the ground
space of H, the problem is to decide whether there exists a sequence of 2-local unitaries that takes
the initial state |ψi close to the ﬁnal state |φi in a way such that all the intermediate states have
low energy. Formally, the problem is stated as follows (adapted from [GS15]):
3
Deﬁnition 3 (k-CGSCON(c, s)). Given as input a k-local n-qubit commuting Hamiltonian H, n-
qubit poly(n)-size quantum circuits U
ψ
and U
φ
that prepare the states |ψi and |φi in the ground
space of H, and real numbers 0 c < s, decide whether
(YES) There exists an m = poly(n) and a sequence of 2-local unitaries U
1
to U
m
such that
max
n
kU
φ
|0
n
i U
m
...U
1
U
ψ
|0
n
ik, hψ
i
|H|ψ
i
i, 1 i m
o
c,
where |ψ
i
i = U
i
...U
1
U
ψ
|0
n
i, or
(NO) For any sequence of m = poly(n) 2-local unitaries U
1
to U
m
,
max
n
kU
φ
|0
n
i U
m
...U
1
U
ψ
|0
n
ik, hψ
i
|H|ψ
i
i, 1 i m
o
s.
where |ψ
i
i = U
i
...U
1
U
ψ
|0
n
i,
given the promise that one of the cases holds.
We deﬁne the 2-layer problem as follows:
Deﬁnition 4 (2-layer problem). Given as input a pair of n-qubit Hamiltonians A and B, each con-
sisting of a sum of mutually commuting 15-local terms (but terms appearing in the decomposition
of A do not necessarily commute with terms appearing in the decomposition of B), 0 A I and
0 B I and parameters 0 α < β such that α 2
poly(n)
, β poly
1
(n), decide whether
(YES) There exists an eﬃciently preparable state |ψi such that hψ|A + B|ψi α, or
(NO) For all states |φi, hφ|A + B|φi β,
given the promise that one of the cases holds.
In appendix A we prove that the 2-layer problem is QCMA-complete using a reduction from
QCMA circuit satisﬁability.
Lemma 5. The 2-layer problem is QCMA-complete.
3 QCMA-completeness of CGSCON
In this section we consider the problem of traversing the ground space of commuting Hamiltoni-
ans with constant locality. Informally, as stated in the introduction, we want to understand the
hardness of going from one low energy state of a commuting Hamiltonian to another by applying
a polynomial-length sequence of two-qubit unitaries, while maintaining low energy in each inter-
mediate state. Our main result is that the ground space connectivity problem for commuting local
Hamiltonians is QCMA-complete:
Theorem 6. 21-CGSCON(2
poly(n)
, poly
1
(n)) is QCMA-complete.
4
To prove this result we use many of the ideas from [GS15], where it is shown that the ground
space connectivity problem for general (not necessarily commuting) local Hamiltonians is QCMA-
complete. The main part of the proof is a reduction from the 2-layer problem which establishes
QCMA-hardness.
We begin by discussing one of the main tools used in [GS15], the Traversal Lemma. We modify
and slightly generalize the lemma to suit our needs. We ﬁrst review the deﬁnition of k-orthogonality
and establish a “small projection lemma” which we use to prove the Modiﬁed Traversal Lemma.
Deﬁnition 7 (k-orthogonality [GS15]). For k 1, a pair of states |ψi,|φi∈ (C
d
)
n
is k-orthogonal
if for all k-local unitaries U, we have hψ|U |φi = 0. Further, any two subspaces S, T (C
d
)
n
are
k-orthogonal if every pair of states |ψi,|φi in S and T respectively are k-orthogonal. For example,
the states |000i and |111i are 2-orthogonal.
Lemma 8. (Small Projection Lemma) Let S and T be k-orthogonal subspaces and let P
S
and P
T
be the orthogonal projections onto them. Let Π = I P
S
P
T
. Let |ψ
0
i S. Let U
1
, . . . , U
m
be any sequence of k-local unitaries, and let |ψ
i
i = U
i
|ψ
i1
i for 1 i m. Assume that for
every 0 i m, kΠ|ψ
i
ik ζ for some ζ 0. Then, for every 0 i m, kP
T
|ψ
i
ik and
kP
S
|ψ
i
ik 1 (i + 1)ζ.
Proof. We show by induction that for every 0 i m, kP
T
|ψ
i
ik . It is trivially true for i = 0.
Further,
kP
T
|ψ
i
ik = kP
T
U
i
(P
S
+ P
T
+ Π)|ψ
i1
ik
kP
T
U
i
Π|ψ
i1
ik + kP
T
U
i
P
T
|ψ
i1
ik
kΠ|ψ
i1
ik + kP
T
|ψ
i1
ik
< ζ + (i 1)ζ.
Here, the second line follows from the triangle inequality and the fact that P
T
U
i
P
S
|ψi = 0 since
the U
i
are k-local and the subspaces S and T are k-orthogonal, the third line uses kP k 1, and
the fourth the condition kΠ|ψ
i
ik < ζ for 0 i m and the induction hypothesis. Furthermore, by
the triangle inequality, for all 0 i m,
kP
S
|ψ
i
ik k|ψ
i
ik kP
T
|ψ
i
ik kΠ|ψ
i
ik 1 (i + 1)ζ.
We are now ready to prove a modiﬁed version of the Traversal Lemma from [GS15] that we
require in the next section. The main modiﬁcation compared to the original lemma is that ours
considers an additional pair (U, V ) of k-orthogonal subspaces that represent an excluded (high-
penalty) subspace for the traversal from one space to the other in the original pair (S, T ). Intuitively,
the Modiﬁed Traversal Lemma states the following. Let |ψi and |φi be any two k-orthogonal states
which are in the ground space of some Hamiltonian H and are contained in some subspace U. Let
V be a subspace such that U and V are k-orthogonal. Assume further that there is a high energy
penalty for any state that is outside the direct sum U + V . Then, for any sequence of m unitaries
that map |ψi to a state that is -close to |φi in a manner such that every intermediate state has
very little overlap with the orthogonal complement of U + V , there is some intermediate state that
has suﬃciently large overlap on the orthogonal complement of the union of the subspaces spanned
by |ψi and |φi.
5
Lemma 9. (Modiﬁed Traversal Lemma) Let S and T be two k-orthogonal subspaces, and let U
and V be another pair of k-orthogonal subspaces such that S T U. Let P
S
, P
T
, P
U
, P
V
be the
orthogonal projections onto them, and let Π = I P
U
P
V
, Q = P
S
+ P
T
, and P = P
U
Q.
Let |ψ
0
i S and |φi T be a pair of k-orthogonal states. Let U
1
, . . . , U
m
be a sequence of k-local
unitaries that map |ψ
0
i to |ψ
m
i, where |ψ
i
i = U
i
|ψ
i1
i.
Let , δ 0 be such that k|φi|ψ
m
ik and kΠ|ψ
i
ik δ for 1 i m. Then there exists an
i {1, . . . , m} such that kP |ψ
i
ik
2
1
m
2
2(m + 1)δ.
Proof. Using the assumption kΠ|ψ
i
ik δ and the Small Projection Lemma (Lemma 8) with the
subspaces U and V , we get that for all i {1, . . . , m}, kP
U
|ψ
i
ik 1 (m + 1)δ. Thus, letting
ζ = max
1im
kP |ψ
i
ik
2
, we have that for every i {1, . . . , m},
hψ
i
|Q|ψ
i
i = hψ
i
|P
U
|ψ
i
i hψ
i
|P |ψ
i
i
=
P
U
|ψ
i
i
2
P |ψ
i
i
2
(1 (m + 1)δ)
2
ζ
1 2(m + 1)δ ζ. (1)
Let |ψ
0
0
i = |ψ
0
i, and deﬁne |ψ
0
i
i, for 1 i m, by induction as |ψ
0
i
i = QU
i
|ψ
0
i1
i. We prove by
induction on i from 0 to m that
|ψ
0
i
i |ψ
i
i
i
q
2(m + 1)δ + ζ. (2)
The case i = 0 is clear. Use the triangle inequality to write
|ψ
0
i
i |ψ
i
i
=
QU
i
|ψ
0
i1
i |ψ
i
i
QU
i
(|ψ
0
i1
i |ψ
i1
i)
+
(Q I)|ψ
i
i
(i 1)
q
2(m + 1)δ + ζ +
q
2(m + 1)δ + ζ,
where the last inequality uses kQU
i
k 1 and the induction hypothesis for the ﬁrst term, and (1)
for the second: using that (I Q) is a projection,
(Q I)|ψ
i
i
2
= hψ
i
|(I Q)|ψ
i
i 2(m + 1)δ + ζ.
Now observe that |ψ
0
m
i always lies in S. This is because inductively, |ψ
0
i lies in S, and if |ψ
0
i1
i
lies in S, then
|ψ
0
i
i = QU
i
|ψ
0
i1
i = (P
S
+ P
T
)U
i
|ψ
0
i1
i = P
S
U
i
|ψ
0
i1
i,
where for the last equality we used that for any k-local unitary U
i
, P
T
U
i
|ψ
0
i1
i = 0 since the
subspaces S and T are k-orthogonal. But by assumption |φi T and thus hψ
0
m
|φi=0. Also
k|ψ
m
i |φik , and therefore by (2) for i = m we deduce that
1 k|ψ
0
m
i |φik k|ψ
0
m
i |ψ
m
ik + k|ψ
m
i |φik m
q
2(m + 1)δ + ζ + ,
proving the lemma.
The main step in our analysis is given by the following reduction from the 2-layer problem to
CGSCON.
6
Theorem 10 (Reduction from 2-layer problem). Let A and B be n-qubit local Hamiltonians with
0 A I and 0 B I such that A is a sum of commuting local terms and so is B. There
exists an (n + 6)-qubit Hamiltonian H, which is a sum of commuting local terms, each of which can
be computed in time polynomial in n from A and B, and which has the following properties. The
states |ψ
0
i = |0
n
i|000i|000i and |φi = |0
n
i|111i|000i are zero energy ground states of H. Moreover,
for any α, β such that 0 α < β 2, the following hold.
(Completeness) Suppose hψ|(A + B)|ψi α for some eﬃciently preparable state |ψi. Then
there exists a sequence of 2-local unitaries U
1
, . . . , U
m
, for m = poly(n), such that
U
m
U
m1
. . . U
1
|ψ
0
i = |φi
and
hψ
i
|H|ψ
i
i
1
2
α, 1 i m,
where |ψ
i
i = U
i
|ψ
i1
i.
(Soundness) Suppose hφ|(A + B)|φi β for all |φi. Then for any sequence of 2-local
unitaries U
1
, . . . , U
m
satisfying
kU
m
U
m1
. . . U
1
|ψ
0
i |φik
1
2
,
we have
max
hψ
i
|H|ψ
i
i, 1 i m
= Ω
1
m
6
β
2
.
Proof. We ﬁrst describe the construction of the commuting Hamiltonian H. Deﬁne 3-qubit projec-
tors
P
0
= |000ih000|, P
1
= |111ih111|, Π = I P
0
P
1
,
and
P
+
=
1
2
(|000i + |111i)(h000| + h111|), P
=
1
2
(|000i |111i)(h000| h111|).
Consider a system of n + 6 qubits partitioned into three registers, where the ﬁrst register contains
n qubits and the second and the third registers contain 3 qubits each. Deﬁne
H = H
A
+ H
B
+ G,
where
H
A
= A Π P
+
, H
B
= B Π P
, and G = I I Π.
Since A is a sum of local commuting terms, H
A
is also a sum of local commuting terms. Likewise
for B and H
B
. The projector G is itself a 3-local term. Since P
+
and P
are orthogonal, we see that
the local terms in H
A
commute with the local terms in H
B
. Moreover, all the local terms commute
with G. Thus H is a commuting local Hamiltonian. It is easily veriﬁed that |ψ
0
i = |0
n
i|000i|000i
and |φi = |0
n
i|111i|000i are zero energy ground states of H. Further, it is easy to create H from
A and B since each of the projectors P
+
, P
, Π acts only on 3 qubits.
The intuition behind the construction is as follows. Given Hamiltonians A and B acting on
n qubits, a simple way to make them commute is to make their ranges orthogonal to each other.
This can be achieved by letting H
A
= A W
1
and H
B
= B W
2
, where W
1
and W
2
are any
7
orthogonal projectors on r ancilla qubits. However, this makes it simple for any traversal to pass
only through the ground space of one of the Hamiltonians A or B: by remaining in a state that is
in the nullspace of W
1
or W
2
at all times.
To prevent this, ﬁx a state |Γi on the ancilla qubits such that hΓ|W
1
|Γi c and hΓ|W
2
|Γi c
for some constant c > 0, and introduce a penalty Hamiltonian G = I (I |ΓihΓ|). Concretely,
we set r = 3, W
1
= P
+
, W
2
= P
, |Γi = |000i, which gives c = 1/2 and G = I (I |000ih000|).
This ﬁxes our “trivial traversal” issue, but H
A
, H
B
and G no longer commute. The key insight
then is to notice that we can use G = I (I |000ih000| |111ih111|) instead. This choice of G
commutes with both H
A
and H
B
, and penalizes any state on the ancilla qubits that is not in the
direct sum of the subspaces spanned by |000i and |111i.
A ﬁnal issue now is that a unitary could map the state |000i on the ancilla qubits to e.g.
|GHZi =
1
2
(|000i + |111i), which is in the ground space of G, but trivially also in the ground
space of P
, and thus the traversal can ignore B completely, a problem similar to the one we
started with. Here we use 2-orthogonality: since the states |000i and |111i are 2-orthogonal, no
2-local unitary can map |000i to |111i, and thus any sequence of states that maps |000i to |GHZi
on the ancilla qubits must pass through a state on those qubits that G penalizes, ensuring that the
construction is sound.
Below we formally establish the required completeness and soundness properties.
Completeness. Suppose hψ|(A + B)|ψi α for some eﬃciently preparable |ψi. Let C be a
circuit consisting of m
0
= poly(n) 2-local unitaries which prepares |ψi starting from |0
n
i. Consider
the following sequence of 2-local unitaries which maps |ψ
0
i to |φi:
1. Starting from |ψ
0
i = |0
n
i|000i|000i, apply the circuit C to the ﬁrst register. (After this step
the state is |ψi|000i|000i.)
2. Apply a sequence of single-qubit X gates to ﬂip the bits of the second register from 000 to
111. (After this step the state is |ψi|111i|000i.)
3. Apply the circuit C
to the ﬁrst register. (After this step the state is |φi = |000i|111i|000i.)
Note that at all times during steps 1. and 3. we remain in the zero energy ground space of H.
At all times during step 2. the state is of the form |ψi|ai|000i where |ai is a computational basis
state of 3 qubits. Its energy is bounded as
hψ|ha|h000|(H
A
+ H
B
+ G)|ψi|ai|000i =
hψ|A|ψih000|P
+
|000i + hψ|B|ψih000|P
|000i
ha|Π|ai
1
2
hψ|A|ψi +
1
2
hψ|B|ψi
1
2
α.
The total number of 2-local unitaries in the sequence is m = 2m
0
+ 3.
Soundness. Suppose that hφ|(A + B)|φi β for all |φi. Let U
1
, . . . , U
m
be a sequence of 2-local
unitaries and let |ψ
i
i = U
i
|ψ
i1
i for 1 i m. Suppose k|ψ
m
i |φik = for some
1
2
. Let
δ = max
1im
kI I Π|ψ
i
ik, and note that the energy violation is at least max
1im
hψ
i
|G|ψ
i
i
δ
2
. Applying the Small Projection Lemma (Lemma 8) with the 2-orthogonal subspaces S and T
8
deﬁned as the +1 eigenspaces of the projectors P
S
= I I P
0
and P
T
= I I P
1
respectively,
we obtain that
k(I I P
1
)|ψ
i
ik < (3)
for all i. Next apply the Modiﬁed Traversal Lemma (Lemma 9) with subspaces S, T, U, V deﬁned
as the +1 eigenspaces of the projectors P
S
= I P
0
P
0
, P
T
= I P
1
P
0
, P
U
= I I P
0
, and
P
V
= I I P
1
respectively. We obtain that there is some i for which
hψ
i
|(I Π P
0
)|ψ
i
i
1
m
2
2(m + 1)δ. (4)
Then
hψ
i
|H
A
+ H
B
|ψ
i
i = hψ
i
|(A Π P
+
+ B Π P
)|ψ
i
i
=
1
2
hψ
i
|(A + B) Π P
0
|ψ
i
i + E
β
2

1
m
2
2(m + 1)δ
+ E,
where the last line uses the operator inequality (A + B) βI and (4), and E is the error term
deﬁned below, which we bound next. Letting P
01
= |000ih111| and P
10
= |111ih000| we have
|E| =
1
2
hψ
i
|(A B) Π P
01
|ψ
i
i + hψ
i
|(A B) Π P
10
|ψ
i
i + hψ
i
|(A + B) Π P
1
|ψ
i
i
1
2
k(I I P
1
)ψ
i
kkA Bk + k(I I P
1
)ψ
i
kkA Bk + k(I I P
1
)ψ
i
kkA + Bk
2k(I I P
1
)ψ
i
k
2mδ,
where the ﬁrst inequality uses the triangle inequality, the Cauchy-Schwarz inequality, and the fact
that the norm of a projection is less than 1, the second inequality uses kAk 1 and kBk 1, and
the third uses (3). Overall the energy lower bound for soundness is
max
1im
hψ
i
|H|ψ
i
i max
n
δ
2
,
β
2

1
m
2
2(m + 1)δ
2
o
.
To conclude it suﬃces to verify that for any 0 δ 1, this is Ω(β
2
/m
6
), as claimed. If δ =
Ω(β/m
3
), then recall that since β 2 due to our normalization of A and B, the statement is
true. If δ = O(β/m
3
) for a small enough implicit constant, the second expression in the max is
dominated by (β/2)((1 )/m)
2
= Ω(β
2
/m
2
) = Ω(β
2
/m
6
).
With Theorem 10 in hand, QCMA-hardness of CGSCON follows from QCMA-hardness of the
2-layer problem.
Proof of Theorem 6. Since commuting local Hamiltonians are a subset of general local Hamiltoni-
ans, the containment 21-CGSCON(2
poly(n)
, poly
1
(n)) QCMA follows from [GS15]. To see that
the problem is QCMA-hard, let A + B be an instance of the 2-layer problem with completeness and
soundness parameters c, s constructed from the QCMA veriﬁer circuit for some language L QCMA
according to Lemma 5. Construct the Hamiltonian H = H
A
+H
B
+G from A+B as in the proof of
9
Theorem 10. Then H is a 21-local commuting Hamiltonian. Moreover, the theorem states that the
2-layer problem instance A + B has the same solution (yes/no) as the CGSCON instance speciﬁed
by H, its ground states |ψ
0
i, |φi, completeness parameter c/2 = 2
poly(n)
and soundness parameter
Ω(s
2
/m
6
) = poly
1
(n). Since the 2-layer problem is QCMA-hard (by lemma 5), this establishes
that 21-CGSCON(2
poly(n)
, poly
1
(n)) is also QCMA-hard.
4 Conclusions
We have shown that the ground space connectivity problem for commuting local Hamiltonians is
QCMA-complete, strengthening the previous result [GS15] for general local Hamiltonians. Thus,
the commutativity restriction does not lower the complexity of this problem, as one might have a
priori expected. It remains open to determine whether there exist instances of the commuting local
Hamiltonian problem that are QMA-hard.
Acknowledgments
T.V. is supported by NSF CAREER grant CCF-1553477 and an AFOSR YIP award number
FA9550-16-1-0495. All authors were partially supported by the IQIM, an NSF Physics Fron-
tiers Center (NSF Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation
(GBMF-12500028).
References
[AB09] Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cam-
bridge University Press, 2009. https://doi.org/10.1017/CBO9780511804090.
[AE11] Dorit Aharonov and Lior Eldar. On the complexity of commuting local Hamiltonians,
and tight conditions for topological order in such systems. In Foundations of Computer
Science (FOCS), 2011 IEEE 52nd Annual Symposium on, pages 334–343. IEEE, 2011.
https://doi.org/10.1109/FOCS.2011.58.
[AGIK09] Dorit Aharonov, Daniel Gottesman, Sandy Irani, and Julia Kempe. The power of
quantum systems on a line. Communications in Mathematical Physics, 287(1):41–65,
2009. https://doi.org/10.1109/FOCS.2007.46.
[BLP
+
16] Benjamin J Brown, Daniel Loss, Jiannis K Pachos, Chris N Self, and James R Wootton.
Quantum memories at ﬁnite temperature. Reviews of Modern Physics, 88(4):045005,
2016. http://dx.doi.org/10.1103/RevModPhys.88.045005.
[BV03] Sergey Bravyi and Mikhail Vyalyi. Commutative version of the k-local Hamiltonian
problem and common eigenspace problem. arXiv preprint quant-ph/0308021, 2003.
[Coo71] Stephen A Cook. The complexity of theorem-proving procedures. In Proceedings of
the third annual ACM symposium on Theory of computing, pages 151–158. ACM, 1971.
https://doi.org/10.1145/800157.805047.
[GKMP09] Parikshit Gopalan, Phokion G Kolaitis, Elitza Maneva, and Christos H Papadimitriou.
The connectivity of Boolean satisﬁability: computational and structural dichotomies.
10
SIAM Journal on Computing, 38(6):2330–2355, 2009. https://doi.org/10.1137/
07070440X.
[GS15] Sevag Gharibian and Jamie Sikora. Ground state connectivity of local Hamiltonians.
In Automata, Languages, and Programming, pages 617–628. Springer, 2015. https:
[Kit03] A Yu Kitaev. Fault-tolerant quantum computation by anyons. Annals of Physics,
303(1):2–30, 2003. https://doi.org/10.1016/S0003-4916(02)00018-0.
[KKR06] Julia Kempe, Alexei Kitaev, and Oded Regev. The complexity of the local Hamiltonian
problem. SIAM Journal on Computing, 35(5):1070–1097, 2006. http://dx.doi.org/
10.1137/S0097539704445226.
[KR03] Julia Kempe and Oded Regev. 3-local Hamiltonian is QMA-complete. arXiv preprint
quant-ph/0302079, 2003. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=
10.1.1.252.4841.
[KSV02] Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vyalyi. Classical and quantum
computation, volume 47. American Mathematical Society Providence, 2002. http:
//dx.doi.org/10.1090/gsm/047.
[OT08] Roberto Oliveira and Barbara M Terhal. The complexity of quantum spin systems on a
two-dimensional square lattice. Quantum Information & Computation, 8(10):900–924,
2008.
[Sch11] Norbert Schuch. Complexity of commuting Hamiltonians on a square lattice of qubits.
Quantum Information & Computation, 11(11-12):901–912, 2011.
[Wat11] John Watrous. Theory of quantum information. University of Waterloo Fall, 128, 2011.
A Proof of Lemma 5
In this appendix we prove that the 2-layer problem is QCMA-complete.
Below we use the term (k, l)-local Hamiltonian” to describe a k-local Hamiltonian such that
each qubit is acted on nontrivially by at most l terms.
The ﬁrst step consists in applying a slight variant of Kitaev’s circuit to Hamiltonian construc-
tion, which ensures that the Hamiltonian constructed from any QMA or QCMA veriﬁcation circuit
is not only local but also such that every qubit is acted (nontrivially) upon by a constant number
of local Hamiltonian terms. In particular, it is a (5, 4)-local Hamiltonian. This step is crucial, as
without it our construction would eventually result in an Ω(log n)-local commuting Hamiltonian
instead of a commuting Hamiltonian with constant locality.
The idea to achieve this is simple: we introduce SWAP gates to ensure that every qubit is
acted upon by at most 3 unitaries: swapping in the state of a given qubit, applying a circuit
unitary, and swapping the state out to some new location. Once the circuit has been modiﬁed in
this way, Kitaev’s construction, which converts a circuit consisting of 2-local unitaries to a 5-local
Hamiltonian through the use of a unary clock, yields a Hamiltonian with the desired property. We
omit the details, and the interested reader is referred to Section 2 in [OT08]. We state the result
in the following lemma.
11
Lemma 11. Let C = U
m
...U
1
be an n-qubit quantum circuit where m =poly(n) such that each qubit
is acted upon by at most three gates. Then there exists a (5, 4)-local Hamiltonian H =
P
m
0
i=1
H
i
acting on n
0
= poly(n, m) qubits such that the following holds:
1. If there exists a state |ψi such that C accepts |ψi with probability 1, then hφ|H|φi
poly(m)
,
where
|φi =
1
m + 1
m
X
i=0
U
i
...U
1
|ψi |0i |ii, (5)
with i written in unary notation.
2. If C accepts any state |ψi with probability at most , then for all |ψi, hψ|H|ψi
1
poly(m)
.
By starting with an error-ampliﬁed QCMA veriﬁer for which the parameter is exponentially
small, we can make the completeness and soundness parameters 2
poly(n)
and
1
poly(n)
respectively
in Lemma 11. The second step of our construction consists in showing how the resulting instance of
the (5, 4)-local Hamiltonian can be converted into a 2-layered local Hamiltonian such that all terms
inside each of the layers commute, and are 15-local. The completeness and soundness parameters
will remain of order 2
poly(n)
and
1
poly(n)
respectively.
We explain the intuition behind the construction. The ﬁrst step is to individually modify each of
the local terms from the input Hamiltonian instance into local terms such that the new Hamiltonians
have orthogonal range. This results in a local Hamiltonian G that is trivially commuting. However,
it is now easy for a prover to specify a state in the simultaneous ground space of all the local terms,
irrespective of whether the initial instance was satisﬁable or not.
To prevent this we create another Hamiltonian R that forces any ground state to have high over-
lap with the ground space of each Hamiltonian in G. Speciﬁcally, consider a qubit j {1, . . . , n},
and let H
i
1
(j)
, H
i
2
(j)
, H
i
3
(j)
, H
i
4
(j)
be the local terms acting on it. We ﬁrst allocate an ancilla qudit
of dimension 4 (equivalently, two qubits) j
0
{1, . . . , n} for j. We then create four new Hamilto-
nians H
0
i
t
(j)
= H
i
t
(j)
|t 1iht 1| for t {1, . . . , 4}, where the second projector acts on j
0
, and
G = H
0
i
1
(j)
+ H
0
i
2
(j)
+ H
0
i
3
(j)
+ H
0
i
4
(j)
. Note that a malicious prover can now easily create a state
in the simultaneous null eigenspace of H
0
i
2
(j)
, H
0
i
3
(j)
, H
0
i
4
(j)
by creating a state that is |00i on j
0
.
To prevent this, we introduce a penalty Hamiltonian R = I (I |γihγ|), where |γi =
1
2
P
3
i=0
|ii.
Provided a large enough energy penalty is associated with R, any state in a low eigenspace of the
H
0
i
t
(j)
is forced to be close to the null eigenspace of R on j
0
, namely, by being in the state |γi,
eﬀectively translating the commuting terms in G into a sum of the non-commuting original terms.
In this case, there is a constant overlap with the projectors of each of H
0
i
t
(j)
, t {1, . . . , 4} on the
Hilbert space of the qudit j
0
, and thus none of the Hamiltonians can be trivially annihilated.
Lemma 12. (Ground Space Preserving Layers) Let H =
P
m
i=1
H
i
be a (5, 4)-local Hamiltonian
acting on a system of n qubits numbered from 1 to n, where kH
i
k 1. For each qubit j {1, . . . , n},
introduce a 4-dimensional ancilla qudit j
0
. Let c and s be two reals such that s c m
b
(for some
b > 0).
For i {1, . . . , m}, let H
i
act on qubits {j
1
(i), . . . , j
5
(i)}. For t {1, . . . , 5}, let p
t
(i)
{1, . . . , 4} be such that H
i
is the p
t
(i)-th Hamiltonian acting on j
t
(i). Deﬁne G
i
acting on qubits
{j
1
(i), ..., j
5
(i)} and {j
0
1
(1), . . . , j
0
5
(i)} as
G
i
= H
i
|p
1
(i) 1ihp
1
(i) 1| ... |p
5
(i) 1ihp
5
(i) 1|.
12
Let |γi =
1
2
P
3
i=0
|ii, and for every qubit j {1, . . . , n} deﬁne R
j
acting on j
0
as
R
j
= I |γihγ|.
Let G =
P
m
i=1
G
i
and R = m
r
P
n
j=1
R
j
, where r = b + 5. Then the following hold, for κ = 2
10
:
1. If there exists a state |ψi such that hψ|H|ψi c, then the state |ψ
0
i = |ψi |γi
n
satisﬁes
hψ
0
|(G + R)|ψ
0
i
c
κ
.
2. If for all states |ψi, hψ|H|ψi s, then for all states |ψ
0
i (on the extended system), hψ
0
|(G +
R)|ψ
0
i
s
κ
1
m
b+1
.
Proof. (Completeness) Let |ψi be such that hψ|H|ψi c. Deﬁne |ψ
0
i = |ψi |φi, where |φi =
|γi... |γi (n times) and where |ψi is a state on the initial n qubits and each copy of |γi acts on
one of the ancilla qudits. By direct calculation,
hψ
0
|(G + R)|ψ
0
i = hψ|hφ|G|ψi|φi + hψ|hφ|R|ψi|φi
=
m
X
i=1
hψ|H
i
|ψi|hγ|p
1
(i) 1i|
2
...|hγ|p
5
(i) 1i|
2
+ 0
=
m
X
i=1
1
4
5
hψ|H
i
|ψi
c
κ
.
(Soundness) Let |φ
0
i, |φ
1
i, . . . , |φ
d
i, for d = 2
2n
1, be an orthonormal basis on the n ancilla
qudits consisting of eigenvectors of R. Let λ
0
··· λ
d
be the eigenvalues of R, counted with
multiplicity. Then |φ
0
i = |γi
n
and λ
0
= 0; moreover for 1 i d, λ
i
m
r
.
We proceed by contradiction. Let |ψ
0
i be a state such that hψ
0
|(G+ R)|ψ
0
i
s
κ
1
m
b+1
. Expand
|ψ
0
i =
P
d
i=0
|a
i
i|φ
i
i, where {|a
0
i, . . . , |a
d
i} are vectors on the initial n qubits. Let |ui = |a
0
i|φ
0
i
and |vi =
P
d
i=1
|a
i
i|φ
i
i, so that |ψ
0
i = |ui + |vi. Let
c
0
= k|uik = k|a
0
ik and c
1
= k|vik =
d
X
i=1
k|a
i
ik
2
1/2
.
Since hu, vi = 0, we have 1 = k|ψ
0
ik
2
= c
2
0
+ c
2
1
. Then
hψ
0
|R|ψ
0
i =
d
X
i=0
λ
i
k|a
i
i|k
2
m
r
c
2
1
.
Further,
hu|G|ui = ha
0
|hφ
0
|G|a
0
i|φ
0
i =
1
κ
ha
0
|H|a
0
i
1
κ
sha
0
|a
0
i =
sc
2
0
κ
, (6)
where the inequality uses the soundness condition ∀|ψi, hψ|H|ψi shψ|ψi. Also note that
|hu|G|vi| = |hv|G|ui| kvkkGuk mkvkkuk mc
1
,
13
where the ﬁrst inequality is Cauchy-Schwarz and the second uses the fact that kGk m. Similarly,
|hv|G|vi| mc
1
, thus using (6),
hψ
0
|G|ψ
0
i hu|G|ui |hu|G|vi| |hv|G|ui| |hv|G|vi|
sc
2
0
κ
3c
1
m.
We then get
hψ
0
|(G + R)|ψ
0
i
sc
2
0
κ
3c
1
m + c
2
1
m
r
=
s
κ
(1 c
2
1
) 3c
1
m + c
2
1
m
r
s
κ
1.5
2
m
2
m
r
s
κ
s
κ
1
m
b+2
,
where the expression in the third line was obtained by setting c
1
=
1.5m
m
r
s
κ
, which minimizes the
expression in the second line. We have reached a contradiction with the assumption hψ
0
|(G +
R)|ψ
0
i
s
κ
1
m
b+1
.
Remark. Any Hamiltonian in layer G acts on the 5 qubits the original Hamiltonian acted on, and
further, the new Hamiltonian acts on one qudit or two ancilla qubits for every qubit the original
Hamiltonian acted on, increasing the locality by 10, making it 15-local. Each of the Hamiltonians
in R act on two qubits. Further, all the Hamiltonians in the layers G and R commute within the
layers.
Lemma 5 is an immediate corollary of Lemma 11 and Lemma 12.
Proof of Lemma 5. The containment in QCMA is immediate since the prover can provide the clas-
sical description of the poly(n)-sized quantum circuit consisting of 2-qubit unitaries that prepares
the state |ψi from |0i
n
such that hψ|(A + B)|ψi c if such an eﬃciently preparable state exists.
To see QCMA-hardness, let V be the QCMA veriﬁer for a language L QCMA, H =
P
m
i=1
H
i
the n-qubit (5, 4)-local Hamiltonian constructed from V and an input x to L as in Lemma 11.
Using standard error ampliﬁcation for QCMA , we may assume that the parameter in the lemma
is = 2
poly(n)
.
Let G
i
, i {1, . . . , m} and R
j
, j {1, . . . , n}, be the local projectors deﬁned in Lemma 12.
Note that the G
i
(resp. R
j
) are mutually commuting. Deﬁne
A =
1
nm
r
X
i
G
i
B =
1
n
X
j
R
j
, (7)
where r = O(1) is selected as in the lemma. The normalizing factors in Equation 7 are chosen to
ensure that 0 A, B I, and so that A + B is proportional to G + R as deﬁned in the lemma. The
proportionality factor is n
1
m
r
which is inverse polynomially small. H
0
= A + B is a 2-layered
15-local Hamiltonian whose ground state energy is exponentially small if x L (i.e. V accepts x)
and at least inverse polynomially large if x / L (i.e. V rejects x). Moreover, if x L there is an
eﬃciently preparable state which achieves exponentially small energy for H (it is a tensor product
of the history state (5) and a symmetric product state).
14