Fermat's Library | QCMA hardness of ground space connectivity for commuting Hamiltonians annotated/explained version.

QCMA hardness of ground space connectivity for

commuting Hamiltonians

David Gosset

1 2

, Jenish C. Mehta

, and Thomas Vidick

California Institute of Technology

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 =

i=1

acting on n qubits, such that

each H

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

. In this case, for all i and j, the terms H

and H

commute, i.e. H

= H

. 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.

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

+ H

+ 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.

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 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

)

⊗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(

√

†

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 =

where each H

is a k-local Hermitian operator. We will always assume

the normalization kH

k ≤ 1 and that H

is positive semideﬁnite for each i. The Hamiltonian is said

to be commuting when the H

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

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

i interchangeably.

Deﬁnition 1 (Eﬃciently preparable states). A family {|ψ

i} of states is eﬃciently preparable if

for each n, there is a sequence of poly(n) 2-local unitaries that can prepare |ψ

i from |0i

⊗n

A promise language is a pair L = (L

yes

; L

) with L

yes

, L

⊆ {0, 1}

∗

and L

yes

∩L

= ∅, where

yes

are strings in the language and L

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

acting on p(|x|)

qubits such that the following holds:

x ∈ L ⇒ ∃y ∈ {0, 1}

p(|x|)

, kΠ

|yik ≥

x 6∈ L ⇒ ∀y ∈ {0, 1}

p(|x|)

, kΠ

|yik ≤

where Π

= |1ih1| ⊗ I is the orthogonal projection onto the state |1i on the ﬁrst qubit.

The constants

and

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]):

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

to U

such that

max

i − U

...U

ik, hψ

|H|ψ

i, 1 ≤ i ≤ m

≤ c,

where |ψ

i = U

...U

i, or

• (NO) For any sequence of m = poly(n) 2-local unitaries U

to U

max

i − U

...U

ik, hψ

|H|ψ

i, 1 ≤ i ≤ m

≥ s.

where |ψ

i = U

...U

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.

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

)

⊗n

is k-orthogonal

if for all k-local unitaries U, we have hψ|U |φi = 0. Further, any two subspaces S, T ⊆ (C

)

⊗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

and P

be the orthogonal projections onto them. Let Π = I − P

− P

. Let |ψ

i ∈ S. Let U

, . . . , U

be any sequence of k-local unitaries, and let |ψ

i = U

|ψ

i−1

i for 1 ≤ i ≤ m. Assume that for

every 0 ≤ i ≤ m, kΠ|ψ

ik ≤ ζ for some ζ ≥ 0. Then, for every 0 ≤ i ≤ m, kP

|ψ

ik ≤ iζ and

|ψ

ik ≥ 1 − (i + 1)ζ.

Proof. We show by induction that for every 0 ≤ i ≤ m, kP

|ψ

ik ≤ iζ. It is trivially true for i = 0.

Further,

|ψ

ik = kP

+ P

+ Π)|ψ

i−1

≤ kP

Π|ψ

i−1

ik + kP

|ψ

i−1

≤ kΠ|ψ

i−1

ik + kP

|ψ

i−1

< ζ + (i − 1)ζ.

Here, the second line follows from the triangle inequality and the fact that P

|ψi = 0 since

the U

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Π|ψ

ik < ζ for 0 ≤ i ≤ m and the induction hypothesis. Furthermore, by

the triangle inequality, for all 0 ≤ i ≤ m,

|ψ

ik ≥ k|ψ

ik − kP

|ψ

ik − kΠ|ψ

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.

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

, P

be the

orthogonal projections onto them, and let Π = I − P

− P

, Q = P

+ P

, and P = P

− Q.

Let |ψ

i ∈ S and |φi ∈ T be a pair of k-orthogonal states. Let U

, . . . , U

be a sequence of k-local

unitaries that map |ψ

i to |ψ

i, where |ψ

i = U

|ψ

i−1

Let , δ ≥ 0 be such that k|φi−|ψ

ik ≤  and kΠ|ψ

ik ≤ δ for 1 ≤ i ≤ m. Then there exists an

i ∈ {1, . . . , m} such that kP |ψ

≥



1−



− 2(m + 1)δ.

Proof. Using the assumption kΠ|ψ

ik ≤ δ and the Small Projection Lemma (Lemma 8) with the

subspaces U and V , we get that for all i ∈ {1, . . . , m}, kP

|ψ

ik ≥ 1 − (m + 1)δ. Thus, letting

ζ = max

1≤i≤m

kP |ψ

, we have that for every i ∈ {1, . . . , m},

hψ

|Q|ψ

i = hψ

|ψ

i − hψ

|P |ψ



|ψ



−



P |ψ



≥ (1 − (m + 1)δ)

− ζ

≥ 1 − 2(m + 1)δ − ζ. (1)

Let |ψ

i = |ψ

i, and deﬁne |ψ

i, for 1 ≤ i ≤ m, by induction as |ψ

i = QU

|ψ

i−1

i. We prove by

induction on i from 0 to m that



|ψ

i − |ψ



≤ i

2(m + 1)δ + ζ. (2)

The case i = 0 is clear. Use the triangle inequality to write



|ψ

i − |ψ



|ψ

i−1

i − |ψ



≤



(|ψ

i−1

i − |ψ

i−1



(Q − I)|ψ



≤ (i − 1)

2(m + 1)δ + ζ +

2(m + 1)δ + ζ,

where the last inequality uses kQU

k ≤ 1 and the induction hypothesis for the ﬁrst term, and (1)

for the second: using that (I − Q) is a projection,



(Q − I)|ψ



= hψ

|(I − Q)|ψ

i ≤ 2(m + 1)δ + ζ.

Now observe that |ψ

i always lies in S. This is because inductively, |ψ

i lies in S, and if |ψ

i−1

lies in S, then

|ψ

i = QU

|ψ

i−1

i = (P

+ P

|ψ

i−1

i = P

|ψ

i−1

where for the last equality we used that for any k-local unitary U

, P

|ψ

i−1

i = 0 since the

subspaces S and T are k-orthogonal. But by assumption |φi ∈ T and thus hψ

|φi=0. Also

k|ψ

i − |φik ≤ , and therefore by (2) for i = m we deduce that

1 ≤ k|ψ

i − |φik ≤ k|ψ

i − |ψ

ik + k|ψ

i − |φik ≤ m

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.

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 |ψ

i = |0

i|000i|000i and |φi = |0

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

, . . . , U

, for m = poly(n), such that

m−1

. . . U

|ψ

i = |φi

and

hψ

|H|ψ

i ≤

α, ∀1 ≤ i ≤ m,

where |ψ

i = U

|ψ

i−1

• (Soundness) Suppose hφ|(A + B)|φi ≥ β for all |φi. Then for any sequence of 2-local

unitaries U

, . . . , U

satisfying

m−1

. . . U

|ψ

i − |φik ≤

we have

max



hψ

|H|ψ

i, 1 ≤ i ≤ m



= Ω





Proof. We ﬁrst describe the construction of the commuting Hamiltonian H. Deﬁne 3-qubit projec-

tors

= |000ih000|, P

= |111ih111|, Π = I − P

− P

and

(|000i + |111i)(h000| + h111|), P

−

(|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

+ H

+ G,

where

= A ⊗ Π ⊗ P

, H

= B ⊗ Π ⊗ P

−

, and G = I ⊗ I ⊗ Π.

Since A is a sum of local commuting terms, H

is also a sum of local commuting terms. Likewise

for B and H

. The projector G is itself a 3-local term. Since P

and P

−

are orthogonal, we see that

the local terms in H

commute with the local terms in H

. Moreover, all the local terms commute

with G. Thus H is a commuting local Hamiltonian. It is easily veriﬁed that |ψ

i = |0

i|000i|000i

and |φi = |0

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 ⊗ W

and H

= B ⊗ W

, where W

and W

are any

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

or W

at all times.

To prevent this, ﬁx a state |Γi on the ancilla qubits such that hΓ|W

|Γi ≥ c and hΓ|W

|Γi ≥ c

for some constant c > 0, and introduce a penalty Hamiltonian G = I ⊗ (I − |ΓihΓ|). Concretely,

we set r = 3, W

= P

, W

= P

−

, |Γi = |000i, which gives c = 1/2 and G = I ⊗(I −|000ih000|).

This ﬁxes our “trivial traversal” issue, but H

, H

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

and H

, 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 =

√

(|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

= poly(n) 2-local unitaries which prepares |ψi starting from |0

i. Consider

the following sequence of 2-local unitaries which maps |ψ

i to |φi:

1. Starting from |ψ

i = |0

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

+ H

+ G)|ψi|ai|000i =



hψ|A|ψih000|P

|000i + hψ|B|ψih000|P

−

|000i



ha|Π|ai

≤

hψ|A|ψi +

hψ|B|ψi

≤

α.

The total number of 2-local unitaries in the sequence is m = 2m

+ 3.

Soundness. Suppose that hφ|(A + B)|φi ≥ β for all |φi. Let U

, . . . , U

be a sequence of 2-local

unitaries and let |ψ

i = U

|ψ

i−1

i for 1 ≤ i ≤ m. Suppose k|ψ

i − |φik =  for some  ≤

. Let

δ = max

1≤i≤m

kI ⊗I ⊗Π|ψ

ik, and note that the energy violation is at least max

1≤i≤m

hψ

|G|ψ

i ≥

. Applying the Small Projection Lemma (Lemma 8) with the 2-orthogonal subspaces S and T

deﬁned as the +1 eigenspaces of the projectors P

= I ⊗ I ⊗ P

and P

= I ⊗ I ⊗ P

respectively,

we obtain that

k(I ⊗ I ⊗P

)|ψ

ik < iδ (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

= I ⊗P

⊗P

, P

= I ⊗P

⊗P

, P

= I ⊗I ⊗P

, and

= I ⊗ I ⊗P

respectively. We obtain that there is some i for which

hψ

|(I ⊗ Π ⊗ P

)|ψ

i ≥



1 − 



− 2(m + 1)δ. (4)

Then

hψ

+ H

|ψ

i = hψ

|(A ⊗ Π ⊗ P

+ B ⊗ Π ⊗ P

−

)|ψ

hψ

|(A + B) ⊗ Π ⊗ P

|ψ

i + E

≥



1 − 



− 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

= |000ih111| and P

= |111ih000| we have

|E| =



hψ

|(A − B) ⊗ Π ⊗ P

|ψ

i + hψ

|(A − B) ⊗ Π ⊗ P

|ψ

i + hψ

|(A + B) ⊗ Π ⊗ P

|ψ



≤



k(I ⊗ I ⊗P

)ψ

kkA − Bk + k(I ⊗ I ⊗ P

)ψ

kkA − Bk + k(I ⊗ I ⊗ P

)ψ

kkA + Bk



≤ 2k(I ⊗ I ⊗ P

)ψ

≤ 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

1≤i≤m

hψ

|H|ψ

i ≥ max



1 − 



− 2(m + 1)δ



− 2mδ

To conclude it suﬃces to verify that for any 0 ≤ δ ≤ 1, this is Ω(β

), as claimed. If δ =

Ω(β/m

), then recall that since β ≤ 2 due to our normalization of A and B, the statement is

true. If δ = O(β/m

) for a small enough implicit constant, the second expression in the max is

dominated by (β/2)((1 − )/m)

= Ω(β

) = Ω(β

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

+G from A+B as in the proof of

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 |ψ

i, |φi, completeness parameter c/2 = 2

−poly(n)

and soundness parameter

Ω(s

) = 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.

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:

//link.springer.com/chapter/10.1007/978-3-662-47672-7_50.

[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.

Lemma 11. Let C = U

...U

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 =

i=1

acting on n

= 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 =

√

m + 1

i=0

...U

|ψ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

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

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

(j)

, H

(j)

, H

(j)

, H

(j)

be the local terms acting on it. We ﬁrst allocate an ancilla qudit

of dimension 4 (equivalently, two qubits) j

∈ {1, . . . , n} for j. We then create four new Hamilto-

nians H

(j)

= H

(j)

⊗ |t − 1iht − 1| for t ∈ {1, . . . , 4}, where the second projector acts on j

, and

G = H

(j)

+ H

(j)

+ H

(j)

+ H

(j)

. Note that a malicious prover can now easily create a state

in the simultaneous null eigenspace of H

(j)

, H

(j)

, H

(j)

by creating a state that is |00i on j

To prevent this, we introduce a penalty Hamiltonian R = I ⊗(I − |γihγ|), where |γi =

i=0

|ii.

Provided a large enough energy penalty is associated with R, any state in a low eigenspace of the

(j)

is forced to be close to the null eigenspace of R on j

, 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

(j)

, t ∈ {1, . . . , 4} on the

Hilbert space of the qudit j

, and thus none of the Hamiltonians can be trivially annihilated.

Lemma 12. (Ground Space Preserving Layers) Let H =

i=1

be a (5, 4)-local Hamiltonian

acting on a system of n qubits numbered from 1 to n, where kH

k ≤ 1. For each qubit j ∈ {1, . . . , n},

introduce a 4-dimensional ancilla qudit j

. Let c and s be two reals such that s −c ≥ m

−b

(for some

b > 0).

For i ∈ {1, . . . , m}, let H

act on qubits {j

(i), . . . , j

(i)}. For t ∈ {1, . . . , 5}, let p

(i) ∈

{1, . . . , 4} be such that H

is the p

(i)-th Hamiltonian acting on j

(i). Deﬁne G

acting on qubits

(i), ..., j

(i)} and {j

(1), . . . , j

(i)} as

= H

⊗ |p

(i) − 1ihp

(i) − 1| ⊗ ... ⊗ |p

(i) − 1ihp

(i) − 1|.

Let |γi =

i=0

|ii, and for every qubit j ∈ {1, . . . , n} deﬁne R

acting on j

= I − |γihγ|.

Let G =

i=1

and R = m

j=1

, where r = b + 5. Then the following hold, for κ = 2

1. If there exists a state |ψi such that hψ|H|ψi ≤ c, then the state |ψ

i = |ψi ⊗ |γi

⊗n

satisﬁes

hψ

|(G + R)|ψ

i ≤

2. If for all states |ψi, hψ|H|ψi ≥ s, then for all states |ψ

i (on the extended system), hψ

|(G +

R)|ψ

i ≥

−

b+1

Proof. (Completeness) Let |ψi be such that hψ|H|ψi ≤ c. Deﬁne |ψ

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ψ

|(G + R)|ψ

i = hψ|hφ|G|ψi|φi + hψ|hφ|R|ψi|φi

i=1

hψ|H

|ψi|hγ|p

(i) − 1i|

...|hγ|p

(i) − 1i|

+ 0

i=1

hψ|H

|ψi

≤

(Soundness) Let |φ

i, |φ

i, . . . , |φ

i, for d = 2

− 1, be an orthonormal basis on the n ancilla

qudits consisting of eigenvectors of R. Let λ

≤ ··· ≤ λ

be the eigenvalues of R, counted with

multiplicity. Then |φ

i = |γi

⊗n

and λ

= 0; moreover for 1 ≤ i ≤ d, λ

≥ m

We proceed by contradiction. Let |ψ

i be a state such that hψ

|(G+ R)|ψ

i ≤

−

b+1

. Expand

|ψ

i =

i=0

i|φ

i, where {|a

i, . . . , |a

i} are vectors on the initial n qubits. Let |ui = |a

i|φ

and |vi =

i=1

i|φ

i, so that |ψ

i = |ui + |vi. Let

= k|uik = k|a

ik and c

= k|vik =



i=1

k|a



1/2

Since hu, vi = 0, we have 1 = k|ψ

= c

+ c

. Then

hψ

|R|ψ

i =

i=0

k|a

i|k

≥ m

Further,

hu|G|ui = ha

|hφ

|G|a

i|φ

i =

|H|a

i ≥

sha

i =

, (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

where the ﬁrst inequality is Cauchy-Schwarz and the second uses the fact that kGk ≤ m. Similarly,

|hv|G|vi| ≤ mc

, thus using (6),

hψ

|G|ψ

i ≥ hu|G|ui − |hu|G|vi| − |hv|G|ui|− |hv|G|vi| ≥

− 3c

We then get

hψ

|(G + R)|ψ

i ≥

− 3c

m + c

(1 − c

) − 3c

m + c

≥

−

1.5

−

≥

−

b+2

where the expression in the third line was obtained by setting c

1.5m

−

, which minimizes the

expression in the second line. We have reached a contradiction with the assumption hψ

|(G +

R)|ψ

i ≤

−

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 =

i=1

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 ∈ {1, . . . , m} and R

, j ∈ {1, . . . , n}, be the local projectors deﬁned in Lemma 12.

Note that the G

(resp. R

) are mutually commuting. Deﬁne

A =

B =

, (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

−r

which is inverse polynomially small. H

= 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).

Comments

Products

Project