# QCMA hardness of ground space connectivity for commuting Hamiltonians

David Gosset  California Institute of Technology  IBM T.J Watson Research
Center  Jenish C. Mehta  California Institute of Technology  Thomas Vidick
California Institute of Technology

(August 27, 2024)

###### Abstract

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 (efficiently 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 $\mathsf{QCMA}$-complete for general local Hamiltonians,
where $\mathsf{QCMA}$ is defined as $\mathsf{QMA}$ with a classical witness
and $\mathsf{BQP}$ verifier. Here we show that the commuting version of the
problem is also $\mathsf{QCMA}$-complete. This provides one of the first
examples where commuting local Hamiltonians exhibit complexity theoretic
hardness equivalent to general local Hamiltonians.

##  1 Introduction

Since the definition and development of $\mathsf{\mathsf{NP}}$ completeness in
the 1970s [Coo71], constraint satisfaction problems and their hardness have
been intensively studied. The following problem, called the $k$-constraint
satisfaction problem ($k$-CSP), generalizes many well-known
$\mathsf{NP}$-complete problems: Given a set of $n$ variables each taking
values in a finite 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 satisfied? A quantum variant of the $k$-CSP,
called the $k$-local Hamiltonian problem ($k$-LH), is defined as follows:
Given a Hamiltonian $H=\sum_{i=1}^{m}H_{i}$ acting on $n$ qubits, such that
each $H_{i}$ is Hermitian positive semidefinite 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 $\alpha$ or larger than $\beta$ (where
$\beta-\alpha=\Omega(\operatorname{poly}^{-1}(n))$. The $5$-local Hamiltonian
problem was proven to be complete for the complexity class $\mathsf{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
$\mathsf{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 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 $\mathsf{NP}$ [BV03]. It was subsequently shown that the
$3$-CLH for qubits and $4$-CLH for qubits on a grid are also in
$\mathsf{NP}$[AE11, Sch11]. The complexity of $k$-CLH for general $k$ remains
open.

In this paper we investigate the commutative version of a different problem
related to local Hamiltonians. Specifically, 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 final states
$|\psi\rangle$ and $|\phi\rangle$, is there a sequence of poly$(n)$ local
unitaries which maps $|\psi\rangle$ to $|\phi\rangle$ 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 $\mathsf{QCMA}$ is in
$\mathsf{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 define 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
definition have the property that they have efficiently 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
$\mathsf{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 $|\psi\rangle$ and $|\phi\rangle$ in the ground space of
$H$, it is $\mathsf{QCMA}$-complete to decide if there exists a
$\operatorname{poly}(n)$-length sequence of $2$-local unitaries which maps
$|\psi\rangle$ to $|\phi\rangle$ such that all intermediate states have low
energy for $H$.

To the best of our knowledge, this is the first 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,
$\mathsf{QCMA}$. Containment in $\mathsf{QCMA}$ is straightforward, and
follows from [GS15]. To prove $\mathsf{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 efficiently preparable state with low energy, or all
states have high energy for $A+B$ (promised that one of these possibilities
holds). We deduce $\mathsf{QCMA}$-completeness of this 2-layer problem using a
simple reduction from $\mathsf{QCMA}$ circuit satisfiability. We include the
proof in Appendix A.111We note that it may also be possible to establish
$\mathsf{QCMA}$-completeness of the 2-layer problem using known 1D circuit-to-
Hamiltonian mappings such as the one from [AGIK09]. 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
modifications that enhance their generality.

In section 2, we review relevant background, and define the computational
problems of interest. In section 3, we give the reduction which establishes
$\mathsf{QCMA}$-completeness of the ground state connectivity problem for
commuting Hamiltonians. We conclude in section 4.

##  2  Preliminaries

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

We consider finite-dimensional Hilbert spaces over the complex field
$\mathbb{C}$. The space of $n$ qudits is $(\mathbb{C}^{d})^{\otimes 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
$\|A\|=\max_{\|x\|=1}\|Ax\|$. The trace norm is
$\|A\|_{\mathrm{tr}}=\mathrm{Tr}(\sqrt{A^{\dagger}A})$.

We use the following terminology. For an integer $1\leq k\leq n$, we say that
a $n$-qubit linear operator is $k$-local if it can be written as $I\otimes L$
where $L$ acts on at most $k$ qubits. A _$k$ -local Hamiltonian_ is
$H=\sum_{i}H_{i}$ where each $H_{i}$ is a $k$-local Hermitian operator. We
will always assume the normalization $\|H_{i}\|\leq 1$ and that $H_{i}$ is
positive semidefinite 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 $|0\rangle^{\otimes n}$
and $|0^{n}\rangle$ interchangeably.

######  Definition 1 (Efficiently preparable states).

A family $\\{|\psi_{n}\rangle\\}$ of states is efficiently preparable if for
each $n$, there is a sequence of $\operatorname{poly}(n)$ 2-local unitaries
that can prepare $|\psi_{n}\rangle$ from $|0\rangle^{\otimes n}$.

A promise language is a pair $L=(L_{yes};L_{no})$ with
$L_{yes},L_{no}\subseteq\\{0,1\\}^{*}$ and $L_{yes}\cap L_{no}=\emptyset$,
where $L_{yes}$ are strings in the language and $L_{no}$ are strings not in
the language.

######  Definition 2 (QCMA).

We say that a promise language $L$ is in the complexity class $\mathsf{QCMA}$
if there exist polynomials $p,q$ and a deterministic Turing machine that on
input $x\in\\{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:

$\displaystyle x\in L$ $\displaystyle\Rightarrow$ $\displaystyle\exists
y\in\\{0,1\\}^{p(|x|)},\|\Pi_{1}Q_{x}|y\rangle\|\geq\frac{2}{3}\,,$
$\displaystyle x\not\in L$ $\displaystyle\Rightarrow$ $\displaystyle\forall
y\in\\{0,1\\}^{p(|x|)},\|\Pi_{1}Q_{x}|y\rangle\|\leq\frac{1}{3}\,,$

where $\Pi_{1}=|1\rangle\langle 1|\otimes I$ is the orthogonal projection onto
the state $|1\rangle$ on the first qubit.

The constants $\frac{2}{3}$ and $\frac{1}{3}$ are arbitrary and can be
amplified to $(1-2^{-\text{poly}(n)},2^{-\text{poly}(n)})$ using standard
techniques (we will use this fact later on).

We finally define the ground space connectivity problem for commuting
Hamiltonians. Given a $k$-local commuting Hamiltonian $H$ and two efficiently
preparable states $|\psi\rangle$ and $|\phi\rangle$ 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 $|\psi\rangle$ close to the final state
$|\phi\rangle$ in a way such that all the intermediate states have low energy.
Formally, the problem is stated as follows (adapted from [GS15]):

######  Definition 3 ($k$-$\mathsf{CGSCON}(c,s)$).

Given as input a $k$-local $n$-qubit commuting Hamiltonian $H$, $n$-qubit
$\text{poly}(n)$-size quantum circuits $U_{\psi}$ and $U_{\phi}$ that prepare
the states $|\psi\rangle$ and $|\phi\rangle$ in the ground space of $H$, and
real numbers $0\leq c<s$, decide whether

  * •

(YES) There exists an $m=\operatorname{poly}(n)$ and a sequence of $2$-local
unitaries $U_{1}$ to $U_{m}$ such that

$\max\Big{\\{}\|U_{\phi}|0^{n}\rangle-
U_{m}...U_{1}U_{\psi}|0^{n}\rangle\|,\,\langle\psi_{i}|H|\psi_{i}\rangle,\,1\leq
i\leq m\Big{\\}}\leq c,$

where $|\psi_{i}\rangle=U_{i}...U_{1}U_{\psi}|0^{n}\rangle$, or

  * •

(NO) For _any_ sequence of $m=\operatorname{poly}(n)$ $2$-local unitaries
$U_{1}$ to $U_{m}$,

$\max\Big{\\{}\|U_{\phi}|0^{n}\rangle-
U_{m}...U_{1}U_{\psi}|0^{n}\rangle\|,\,\langle\psi_{i}|H|\psi_{i}\rangle,\,1\leq
i\leq m\Big{\\}}\geq s.$

where $|\psi_{i}\rangle=U_{i}...U_{1}U_{\psi}|0^{n}\rangle$,

given the promise that one of the cases holds.

We define the 2-layer problem as follows:

######  Definition 4 (2-layer problem).

Given as input a pair of $n$-qubit Hamiltonians $A$ and $B$, each consisting
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\leq A\leq I$ and $0\leq B\leq I$ and parameters
$0\leq\alpha<\beta$ such that $\alpha\leq 2^{-\operatorname{poly}(n)}$,
$\beta\geq\operatorname{poly}^{-1}(n)$, decide whether

  * •

(YES) There exists an efficiently preparable state $|\psi\rangle$ such that
$\langle\psi|A+B|\psi\rangle\leq\alpha$, or

  * •

(NO) For all states $|\phi\rangle$, $\langle\phi|A+B|\phi\rangle\geq\beta$,

given the promise that one of the cases holds.

In appendix A we prove that the 2-layer problem is $\mathsf{QCMA}$-complete
using a reduction from $\mathsf{QCMA}$ circuit satisfiability.

######  Lemma 5.

The $2$-layer problem is $\mathsf{QCMA}$-complete.

##  3 QCMA-completeness of $\mathsf{CGSCON}$

In this section we consider the problem of traversing the ground space of
commuting Hamiltonians 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
intermediate state. Our main result is that the ground space connectivity
problem for commuting local Hamiltonians is $\mathsf{QCMA}$-complete:

######  Theorem 6.

$21$-$\mathsf{CGSCON}(2^{-\operatorname{poly}(n)},\operatorname{poly}^{-1}(n))$
is $\mathsf{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 $\mathsf{QCMA}$-complete. The main part of
the proof is a reduction from the 2-layer problem which establishes
$\mathsf{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 first
review the definition of $k$-orthogonality and establish a “small projection
lemma” which we use to prove the Modified Traversal Lemma.

######  Definition 7 ($k$-orthogonality [GS15]).

For $k\geq 1$, a pair of states
$|\psi\rangle$,$|\phi\rangle$$\in(\mathbb{C}^{d})^{\otimes n}$ is
$k$-orthogonal if for all $k$-local unitaries $U$, we have
$\langle\psi|U|\phi\rangle=0$. Further, any two subspaces
$S,T\subseteq(\mathbb{C}^{d})^{\otimes n}$ are $k$-orthogonal if every pair of
states $|\psi\rangle$,$|\phi\rangle$ in $S$ and $T$ respectively are
$k$-orthogonal. For example, the states $|000\rangle$ and $|111\rangle$ 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
$\Pi=I-P_{S}-P_{T}$. Let $|\psi_{0}\rangle\in S$. Let $U_{1},\ldots,U_{m}$ be
any sequence of k-local unitaries, and let
$|\psi_{i}\rangle=U_{i}|\psi_{i-1}\rangle$ for $1\leq i\leq m$. Assume that
for every $0\leq i\leq m$, $\|\Pi|\psi_{i}\rangle\|\leq\zeta$ for some
$\zeta\geq 0$. Then, for every $0\leq i\leq m$, $\|P_{T}|\psi_{i}\rangle\|\leq
i\zeta$ and $\|P_{S}|\psi_{i}\rangle\|\geq 1-(i+1)\zeta$.

###### Proof.

We show by induction that for every $0\leq i\leq m$,
$\|P_{T}|\psi_{i}\rangle\|\leq i\zeta$. It is trivially true for $i=0$.
Further,

$\displaystyle\|P_{T}|\psi_{i}\rangle\|$ $\displaystyle=$
$\displaystyle\|P_{T}U_{i}(P_{S}+P_{T}+\Pi)|\psi_{i-1}\rangle\|$
$\displaystyle\leq$
$\displaystyle\|P_{T}U_{i}\Pi|\psi_{i-1}\rangle\|+\|P_{T}U_{i}P_{T}|\psi_{i-1}\rangle\|$
$\displaystyle\leq$
$\displaystyle\|\Pi|\psi_{i-1}\rangle\|+\|P_{T}|\psi_{i-1}\rangle\|$
$\displaystyle<$ $\displaystyle\zeta+(i-1)\zeta.$

Here, the second line follows from the triangle inequality and the fact that
$P_{T}U_{i}P_{S}|\psi\rangle=0$ since the $U_{i}$ are $k$-local and the
subspaces $S$ and $T$ are $k$-orthogonal, the third line uses $\|P\|\leq 1$,
and the fourth the condition $\|\Pi|\psi_{i}\rangle\|<\zeta$ for $0\leq i\leq
m$ and the induction hypothesis. Furthermore, by the triangle inequality, for
all $0\leq i\leq m$,

$\|P_{S}|\psi_{i}\rangle\|\geq\||\psi_{i}\rangle\|-\|P_{T}|\psi_{i}\rangle\|-\|\Pi|\psi_{i}\rangle\|\geq
1-(i+1)\zeta.$

∎

We are now ready to prove a modified version of the Traversal Lemma from
[GS15] that we require in the next section. The main modification 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 Modified Traversal Lemma states the following. Let
$|\psi\rangle$ and $|\phi\rangle$ 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
$|\psi\rangle$ to a state that is $\epsilon$-close to $|\phi\rangle$ 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
sufficiently large overlap on the orthogonal complement of the union of the
subspaces spanned by $|\psi\rangle$ and $|\phi\rangle$.

######  Lemma 9.

(Modified 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\cup T\subseteq U$. Let $P_{S},P_{T},P_{U},P_{V}$ be the orthogonal
projections onto them, and let $\Pi=I-P_{U}-P_{V}$, $Q=P_{S}+P_{T}$, and
$P=P_{U}-Q$. Let $|\psi_{0}\rangle\in S$ and $|\phi\rangle\in T$ be a pair of
$k$-orthogonal states. Let $U_{1},\ldots,U_{m}$ be a sequence of $k$-local
unitaries that map $|\psi_{0}\rangle$ to $|\psi_{m}\rangle$, where
$|\psi_{i}\rangle=U_{i}|\psi_{i-1}\rangle$.

Let $\epsilon,\delta\geq 0$ be such that
$\||\phi\rangle-|\psi_{m}\rangle\|\leq\epsilon$ and
$\|\Pi|\psi_{i}\rangle\|\leq\delta$ for $1\leq i\leq m$. Then there exists an
$i\in\\{1,\ldots,m\\}$ such that
$\|P|\psi_{i}\rangle\|^{2}\geq\big{(}\frac{1-\epsilon}{m}\big{)}^{2}-2(m+1)\delta$.

###### Proof.

Using the assumption $\|\Pi|\psi_{i}\rangle\|\leq\delta$ and the Small
Projection Lemma (Lemma 8) with the subspaces $U$ and $V$, we get that for all
$i\in\\{1,\ldots,m\\}$, $\|P_{U}|\psi_{i}\rangle\|\geq 1-(m+1)\delta$. Thus,
letting $\zeta=\max_{1\leq i\leq m}\|P|\psi_{i}\rangle\|^{2}$, we have that
for every $i\in\\{1,\ldots,m\\}$,

$\displaystyle\langle\psi_{i}|Q|\psi_{i}\rangle$
$\displaystyle=\langle\psi_{i}|P_{U}|\psi_{i}\rangle-\langle\psi_{i}|P|\psi_{i}\rangle$
$\displaystyle=\big{\|}P_{U}|\psi_{i}\rangle\big{\|}^{2}-\big{\|}P|\psi_{i}\rangle\big{\|}^{2}$
$\displaystyle\geq(1-(m+1)\delta)^{2}-\zeta$ $\displaystyle\geq
1-2(m+1)\delta-\zeta.$ (1)

Let $|\psi^{\prime}_{0}\rangle=|\psi_{0}\rangle$, and define
$|\psi^{\prime}_{i}\rangle$, for $1\leq i\leq m$, by induction as
$|\psi^{\prime}_{i}\rangle=QU_{i}|\psi^{\prime}_{i-1}\rangle$. We prove by
induction on $i$ from $0$ to $m$ that

$\big{\|}|\psi^{\prime}_{i}\rangle-|\psi_{i}\rangle\big{\|}\leq
i\sqrt{2(m+1)\delta+\zeta}.$ (2)

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

$\displaystyle\big{\|}|\psi^{\prime}_{i}\rangle-|\psi_{i}\rangle\big{\|}$
$\displaystyle=\big{\|}QU_{i}|\psi^{\prime}_{i-1}\rangle-|\psi_{i}\rangle\big{\|}$
$\displaystyle\leq\big{\|}QU_{i}(|\psi^{\prime}_{i-1}\rangle-|\psi_{i-1}\rangle)\big{\|}+\big{\|}(Q-I)|\psi_{i}\rangle\big{\|}$
$\displaystyle\leq(i-1)\sqrt{2(m+1)\delta+\zeta}+\sqrt{2(m+1)\delta+\zeta},$

where the last inequality uses $\|QU_{i}\|\leq 1$ and the induction hypothesis
for the first term, and (1) for the second: using that $(I-Q)$ is a
projection,

$\big{\|}(Q-I)|\psi_{i}\rangle\big{\|}^{2}=\langle\psi_{i}|(I-Q)|\psi_{i}\rangle\leq
2(m+1)\delta+\zeta.$

Now observe that $|\psi^{\prime}_{m}\rangle$ always lies in $S$. This is
because inductively, $|\psi_{0}\rangle$ lies in $S$, and if
$|\psi^{\prime}_{i-1}\rangle$ lies in $S$, then

$|\psi^{\prime}_{i}\rangle=QU_{i}|\psi^{\prime}_{i-1}\rangle=(P_{S}+P_{T})U_{i}|\psi^{\prime}_{i-1}\rangle=P_{S}U_{i}|\psi^{\prime}_{i-1}\rangle,$

where for the last equality we used that for any $k$-local unitary $U_{i}$,
$P_{T}U_{i}|\psi^{\prime}_{i-1}\rangle=0$ since the subspaces $S$ and $T$ are
$k$-orthogonal. But by assumption $|\phi\rangle\in T$ and thus
$\langle\psi^{\prime}_{m}|\phi\rangle$=0. Also
$\||\psi_{m}\rangle-|\phi\rangle\|\leq\epsilon$, and therefore by (2) for
$i=m$ we deduce that

$1\leq\||\psi^{\prime}_{m}\rangle-|\phi\rangle\|\leq\||\psi^{\prime}_{m}\rangle-|\psi_{m}\rangle\|+\||\psi_{m}\rangle-|\phi\rangle\|\leq
m\sqrt{2(m+1)\delta+\zeta}+\epsilon,$

proving the lemma. ∎

The main step in our analysis is given by the following reduction from the
$2$-layer problem to $\mathsf{CGSCON}$.

######  Theorem 10 (Reduction from 2-layer problem).

Let $A$ and $B$ be $n$-qubit local Hamiltonians with $0\leq A\leq I$ and
$0\leq B\leq 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
$|\psi_{0}\rangle=|0^{n}\rangle|000\rangle|000\rangle$ and
$|\phi\rangle=|0^{n}\rangle|111\rangle|000\rangle$ are zero energy ground
states of $H$. Moreover, for any $\alpha$, $\beta$ such that
$0\leq\alpha<\beta\leq 2$, the following hold.

  * •

(Completeness) Suppose $\langle\psi|(A+B)|\psi\rangle\leq\alpha$ for some
efficiently preparable state $|\psi\rangle$. Then there exists a sequence of
2-local unitaries $U_{1},\ldots,U_{m}$, for $m=\operatorname{poly}(n)$, such
that

$U_{m}U_{m-1}\ldots U_{1}|\psi_{0}\rangle=|\phi\rangle$

and

$\langle\psi_{i}|H|\psi_{i}\rangle\leq\frac{1}{2}\alpha,\qquad\forall\,1\leq
i\leq m,$

where $|\psi_{i}\rangle=U_{i}|\psi_{i-1}\rangle$.

  * •

(Soundness) Suppose $\langle\phi|(A+B)|\phi\rangle\geq\beta$ for all
$|\phi\rangle$. Then for any sequence of 2-local unitaries
$U_{1},\ldots,U_{m}$ satisfying

$\|U_{m}U_{m-1}\ldots U_{1}|\psi_{0}\rangle-|\phi\rangle\|\leq\frac{1}{2},$

we have

$\max\big{\\{}\langle\psi_{i}|H|\psi_{i}\rangle\mbox{,}\,1\leq i\leq
m\big{\\}}=\Omega\left(\frac{1}{m^{6}}\beta^{2}\right).$

###### Proof.

We first describe the construction of the commuting Hamiltonian $H$. Define
$3$-qubit projectors

$P_{0}=|000\rangle\langle 000|,\qquad P_{1}=|111\rangle\langle
111|,\qquad\Pi=I-P_{0}-P_{1},$

and

$P_{+}=\frac{1}{2}(|000\rangle+|111\rangle)(\langle 000|+\langle 111|),\qquad
P_{-}=\frac{1}{2}(|000\rangle-|111\rangle)(\langle 000|-\langle 111|).$

Consider a system of $n+6$ qubits partitioned into three registers, where the
first register contains $n$ qubits and the second and the third registers
contain 3 qubits each. Define

$H=H_{A}+H_{B}+G,$

where

$H{}_{A}=A\otimes\Pi\otimes P_{+},\qquad H{}_{B}=B\otimes\Pi\otimes
P_{-},\qquad\text{and}\qquad G=I\otimes I\otimes\Pi.$

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 verified that
$|\psi_{0}\rangle=|0^{n}\rangle|000\rangle|000\rangle$ and
$|\phi\rangle=|0^{n}\rangle|111\rangle|000\rangle$ 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_{-},\Pi$ 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\otimes W_{1}$ and $H_{B}=B\otimes W_{2}$, where $W_{1}$ and $W_{2}$
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_{1}$ or $W_{2}$ at all times.

To prevent this, fix a state $|\Gamma\rangle$ on the ancilla qubits such that
$\langle\Gamma|W_{1}|\Gamma\rangle\geq c$ and
$\langle\Gamma|W_{2}|\Gamma\rangle\geq c$ for some constant $c>0$, and
introduce a penalty Hamiltonian $G=I\otimes(I-|\Gamma\rangle\langle\Gamma|)$.
Concretely, we set $r=3,W_{1}=P_{+},W_{2}=P_{-},|\Gamma\rangle=|000\rangle$,
which gives $c=1/2$ and $G=I\otimes(I-|000\rangle\langle 000|)$.

This fixes 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\otimes(I-|000\rangle\langle 000|-|111\rangle\langle 111|)$ 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 $|000\rangle$ and $|111\rangle$.

A final issue now is that a unitary could map the state $|000\rangle$ on the
ancilla qubits to e.g.
$|GHZ\rangle=\frac{1}{\sqrt{2}}(|000\rangle+|111\rangle)$, 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 $|000\rangle$
and $|111\rangle$ are $2$-orthogonal, no $2$-local unitary can map
$|000\rangle$ to $|111\rangle$, and thus any sequence of states that maps
$|000\rangle$ to $|GHZ\rangle$ 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 $\langle\psi|(A+B)|\psi\rangle\leq\alpha$ for some efficiently
preparable $|\psi\rangle$. Let $C$ be a circuit consisting of
$m^{\prime}=\mbox{poly}(n)$ $2$-local unitaries which prepares $|\psi\rangle$
starting from $|0^{n}\rangle$. Consider the following sequence of $2$-local
unitaries which maps $|\psi_{0}\rangle$ to $|\phi\rangle$:

  1. 1.

Starting from $|\psi_{0}\rangle=|0^{n}\rangle|000\rangle|000\rangle$, apply
the circuit $C$ to the first register. (After this step the state is
$|\psi\rangle|000\rangle|000\rangle$.)

  2. 2.

Apply a sequence of single-qubit $X$ gates to flip the bits of the second
register from $000$ to $111$. (After this step the state is
$|\psi\rangle|111\rangle|000\rangle$.)

  3. 3.

Apply the circuit $C^{\dagger}$ to the first register. (After this step the
state is $|\phi\rangle=|000\rangle|111\rangle|000\rangle$.)

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
$|\psi\rangle|a\rangle|000\rangle$ where $|a\rangle$ is a computational basis
state of $3$ qubits. Its energy is bounded as

$\displaystyle\langle\psi|\langle a|\langle
000|(H_{A}+H_{B}+G)|\psi\rangle|a\rangle|000\rangle$
$\displaystyle=\big{(}\langle\psi|A|\psi\rangle\langle
000|P_{+}|000\rangle+\langle\psi|B|\psi\rangle\langle
000|P_{-}|000\rangle\big{)}\langle a|\Pi|a\rangle$
$\displaystyle\leq\frac{1}{2}\langle\psi|A|\psi\rangle+\frac{1}{2}\langle\psi|B|\psi\rangle$
$\displaystyle\leq\frac{1}{2}\alpha.$

The total number of $2$-local unitaries in the sequence is $m=2m^{\prime}+3$.

### Soundness.

Suppose that $\langle\phi|(A+B)|\phi\rangle\geq\beta$ for all $|\phi\rangle$.
Let $U_{1},\ldots,U_{m}$ be a sequence of $2$-local unitaries and let
$|\psi_{i}\rangle=U_{i}|\psi_{i-1}\rangle$ for $1\leq i\leq m$. Suppose
$\||\psi_{m}\rangle-|\phi\rangle\|=\epsilon$ for some
$\epsilon\leq\frac{1}{2}$. Let $\delta=\max_{1\leq i\leq m}\|I\otimes
I\otimes\Pi|\psi_{i}\rangle\|$, and note that the energy violation is at least
$\max_{1\leq i\leq m}\langle\psi_{i}|G|\psi_{i}\rangle\geq\delta^{2}$.
Applying the Small Projection Lemma (Lemma 8) with the $2$-orthogonal
subspaces $S$ and $T$ defined as the +1 eigenspaces of the projectors
$P_{S}=I\otimes I\otimes P_{0}$ and $P_{T}=I\otimes I\otimes P_{1}$
respectively, we obtain that

$\|(I\otimes I\otimes P_{1})|\psi_{i}\rangle\|<i\delta$ (3)

for all $i$. Next apply the Modified Traversal Lemma (Lemma 9) with subspaces
$S,T,U,V$ defined as the +1 eigenspaces of the projectors $P_{S}=I\otimes
P_{0}\otimes P_{0}$, $P_{T}=I\otimes P_{1}\otimes P_{0}$, $P_{U}=I\otimes
I\otimes P_{0}$, and $P_{V}=I\otimes I\otimes P_{1}$ respectively. We obtain
that there is some $i$ for which

$\langle\psi_{i}|(I\otimes\Pi\otimes
P_{0})|\psi_{i}\rangle\geq\Big{(}\frac{1-\epsilon}{m}\Big{)}^{2}-2(m+1)\delta.$
(4)

Then

$\displaystyle\langle\psi_{i}|H_{A}+H_{B}|\psi_{i}\rangle$ $\displaystyle=$
$\displaystyle\langle\psi_{i}|(A\otimes\Pi\otimes P_{+}+B\otimes\Pi\otimes
P_{-})|\psi_{i}\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{2}\langle\psi_{i}|(A+B)\otimes\Pi\otimes
P_{0}|\psi_{i}\rangle+E$ $\displaystyle\geq$
$\displaystyle\frac{\beta}{2}\Big{(}\Big{(}\frac{1-\epsilon}{m}\Big{)}^{2}-2(m+1)\delta\Big{)}+E,$

where the last line uses the operator inequality $(A+B)\geq\beta I$ and (4),
and $E$ is the error term defined below, which we bound next. Letting
$P_{01}=|000\rangle\langle 111|$ and $P_{10}=|111\rangle\langle 000|$ we have

$\displaystyle|E|$
$\displaystyle=\frac{1}{2}\big{|}\langle\psi_{i}|(A-B)\otimes\Pi\otimes
P_{01}|\psi_{i}\rangle+\langle\psi_{i}|(A-B)\otimes\Pi\otimes
P_{10}|\psi_{i}\rangle+\langle\psi_{i}|(A+B)\otimes\Pi\otimes
P_{1}|\psi_{i}\rangle\big{|}$ $\displaystyle\leq\frac{1}{2}\big{(}\|(I\otimes
I\otimes P_{1})\psi_{i}\|\|A-B\|+\|(I\otimes I\otimes
P_{1})\psi_{i}\|\|A-B\|+\|(I\otimes I\otimes P_{1})\psi_{i}\|\|A+B\|\big{)}$
$\displaystyle\leq 2\|(I\otimes I\otimes P_{1})\psi_{i}\|$ $\displaystyle\leq
2m\delta,$

where the first 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 $\|A\|\leq 1$ and $\|B\|\leq 1$, and the third uses
(3). Overall the energy lower bound for soundness is

$\max_{1\leq i\leq
m}\langle\psi_{i}|H|\psi_{i}\rangle\geq\max\Big{\\{}\delta^{2},\,\frac{\beta}{2}\Big{(}\Big{(}\frac{1-\epsilon}{m}\Big{)}^{2}-2(m+1)\delta\Big{)}-2m\delta\Big{\\}}.$

To conclude it suffices to verify that for any $0\leq\delta\leq 1$, this is
$\Omega(\beta^{2}/m^{6})$, as claimed. If $\delta=\Omega(\beta/m^{3})$, then
recall that since $\beta\leq 2$ due to our normalization of $A$ and $B$, the
statement is true. If $\delta=O(\beta/m^{3})$ for a small enough implicit
constant, the second expression in the max is dominated by
$(\beta/2)((1-\epsilon)/m)^{2}=\Omega(\beta^{2}/m^{2})=\Omega(\beta^{2}/m^{6})$.

∎

With Theorem 10 in hand, $\mathsf{QCMA}$-hardness of $\mathsf{CGSCON}$ follows
from $\mathsf{QCMA}$-hardness of the $2$-layer problem.

###### Proof of Theorem 6.

Since commuting local Hamiltonians are a subset of general local Hamiltonians,
the containment
$21$-$\mathsf{CGSCON}(2^{-\operatorname{poly}(n)},\operatorname{poly}^{-1}(n))\in\mathsf{QCMA}$
follows from [GS15]. To see that the problem is $\mathsf{QCMA}$-hard, let
$A+B$ be an instance of the $2$-layer problem with completeness and soundness
parameters $c,s$ constructed from the $\mathsf{QCMA}$ verifier circuit for
some language $L\in\mathsf{QCMA}$ according to Lemma 5. Construct the
Hamiltonian $H=H_{A}+H_{B}+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
$\mathsf{CGSCON}$ instance specified by $H$, its ground states
$|\psi_{0}\rangle,|\phi\rangle$, completeness parameter
$c/2=2^{-\text{poly}(n)}$ and soundness parameter
$\Omega(s^{2}/m^{6})=\operatorname{poly}^{-1}(n)$. Since the $2$-layer problem
is $\mathsf{QCMA}$-hard (by lemma 5), this establishes that
$21$-$\mathsf{CGSCON}(2^{-\operatorname{poly}(n)},\operatorname{poly}^{-1}(n))$
is also $\mathsf{QCMA}$-hard. ∎

##  4 Conclusions

We have shown that the ground space connectivity problem for commuting local
Hamiltonians is $\mathsf{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 $\mathsf{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 Frontiers 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.  Cambridge 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 finite 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 satisfiability: 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.

##  Appendix A Proof of Lemma 5

In this appendix we prove that the 2-layer problem is
$\mathsf{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 first step consists in applying a slight variant of Kitaev’s circuit to
Hamiltonian construction, which ensures that the Hamiltonian constructed from
any $\mathsf{QMA}$ or $\mathsf{QCMA}$ verification 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 $\Omega(\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 modified 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_{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=\sum_{i=1}^{m^{\prime}}H_{i}$ acting on
$n^{\prime}=\operatorname{poly}(n,m)$ qubits such that the following holds:

  1. 1.

If there exists a state $|\psi\rangle$ such that $C$ accepts $|\psi\rangle$
with probability $1-\epsilon$, then
$\langle\phi|H|\phi\rangle\leq\frac{\epsilon}{\operatorname{poly}(m)}$, where

$|\phi\rangle=\frac{1}{\sqrt{m+1}}\sum_{i=0}^{m}U_{i}...U_{1}|\psi\rangle\otimes|0\rangle\otimes|i\rangle,$
(5)

with $i$ written in unary notation.

  2. 2.

If $C$ accepts any state $|\psi\rangle$ with probability at most $\epsilon$,
then for all $|\psi\rangle$,
$\langle\psi|H|\psi\rangle\geq\frac{1-\epsilon}{\operatorname{poly}(m)}$.

By starting with an error-amplified $\mathsf{QCMA}$ verifier for which the
$\epsilon$ parameter is exponentially small, we can make the completeness and
soundness parameters $2^{-\text{poly}(n)}$ and $\frac{1}{\text{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^{-\text{poly}(n)}$ and
$\frac{1}{\text{poly}(n)}$ respectively.

We explain the intuition behind the construction. The first 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 satisfiable or not.

To prevent this we create another Hamiltonian $R$ that forces any ground state
to have high overlap with the ground space of each Hamiltonian in $G$.
Specifically, consider a qubit $j\in\\{1,\ldots,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 first allocate an ancilla qudit of dimension $4$
(equivalently, two qubits) $j^{\prime}\in\\{1,\ldots,n\\}$ for $j$. We then
create four new Hamiltonians
$H_{i_{t}(j)}^{\prime}=H_{i_{t}(j)}\otimes|t-1\rangle\langle t-1|$ for
$t\in\\{1,\ldots,4\\}$, where the second projector acts on $j^{\prime}$, and
$G=H^{\prime}_{i_{1}(j)}+H^{\prime}_{i_{2}(j)}+H^{\prime}_{i_{3}(j)}+H^{\prime}_{i_{4}(j)}$.
Note that a malicious prover can now easily create a state in the simultaneous
null eigenspace of
$H^{\prime}_{i_{2}(j)},H^{\prime}_{i_{3}(j)},H^{\prime}_{i_{4}(j)}$ by
creating a state that is $|00\rangle$ on $j^{\prime}$. To prevent this, we
introduce a penalty Hamiltonian $R=I\otimes(I-|\gamma\rangle\langle\gamma|)$,
where $|\gamma\rangle=\frac{1}{2}\sum_{i=0}^{3}|i\rangle$. Provided a large
enough energy penalty is associated with $R$, any state in a low eigenspace of
the $H_{i_{t}(j)}^{\prime}$ is forced to be close to the null eigenspace of
$R$ on $j^{\prime}$, namely, by being in the state $|\gamma\rangle$,
effectively 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^{\prime}_{i_{t}(j)}$, $t\in\\{1,\ldots,4\\}$ on the
Hilbert space of the qudit $j^{\prime}$, and thus none of the Hamiltonians can
be trivially annihilated.

######  Lemma 12.

(Ground Space Preserving Layers) Let $H=\sum_{i=1}^{m}H_{i}$ be a
$(5,4)$-local Hamiltonian acting on a system of $n$ qubits numbered from $1$
to $n$, where $\|H_{i}\|\leq 1$. For each qubit $j\in\\{1,\ldots,n\\}$,
introduce a $4$-dimensional ancilla qudit $j^{\prime}$. Let $c$ and $s$ be two
reals such that $s-c\geq m^{-b}$ (for some $b>0$).

For $i\in\\{1,\ldots,m\\}$, let $H_{i}$ act on qubits
$\\{j_{1}(i),\ldots,j_{5}(i)\\}$. For $t\in\\{1,\ldots,5\\}$, let
$p_{t}(i)\in\\{1,\ldots,4\\}$ be such that $H_{i}$ is the $p_{t}(i)$-th
Hamiltonian acting on $j_{t}(i)$. Define $G_{i}$ acting on qubits
$\\{j_{1}(i),...,j_{5}(i)\\}$ and
$\\{j^{\prime}_{1}(1),\ldots,j^{\prime}_{5}(i)\\}$ as

$G_{i}=H_{i}\otimes|p_{1}(i)-1\rangle\langle
p_{1}(i)-1|\otimes...\otimes|p_{5}(i)-1\rangle\langle p_{5}(i)-1|.$

Let $|\gamma\rangle=\frac{1}{2}\sum_{i=0}^{3}|i\rangle$, and for every qubit
$j\in\\{1,\ldots,n\\}$ define $R_{j}$ acting on $j^{\prime}$ as

$R_{j}=I-|\gamma\rangle\langle\gamma|.$

Let $G=\sum_{i=1}^{m}G_{i}$ and $R=m^{r}\sum_{j=1}^{n}R_{j}$, where $r=b+5$.
Then the following hold, for $\kappa=2^{10}$:

  1. 1.

If there exists a state $|\psi\rangle$ such that
$\langle\psi|H|\psi\rangle\leq c$, then the state
$|\psi^{\prime}\rangle=|\psi\rangle\otimes|\gamma\rangle^{\otimes n}$
satisfies
$\langle\psi^{\prime}|(G+R)|\psi^{\prime}\rangle\leq\frac{c}{\kappa}$.

  2. 2.

If for all states $|\psi\rangle$, $\langle\psi|H|\psi\rangle\geq s$, then for
all states $|\psi^{\prime}\rangle$ (on the extended system),
$\langle\psi^{\prime}|(G+R)|\psi^{\prime}\rangle\geq\frac{s}{\kappa}-\frac{1}{m^{b+1}}$.

###### Proof.

_(Completeness)_ Let $|\psi\rangle$ be such that
$\langle\psi|H|\psi\rangle\leq c$. Define
$|\psi^{\prime}\rangle=|\psi\rangle\otimes|\phi\rangle$, where
$|\phi\rangle=|\gamma\rangle\otimes...\otimes|\gamma\rangle$ ($n$ times) and
where $|\psi\rangle$ is a state on the initial $n$ qubits and each copy of
$|\gamma\rangle$ acts on one of the ancilla qudits. By direct calculation,

$\displaystyle\langle\psi^{\prime}|(G+R)|\psi^{\prime}\rangle$
$\displaystyle=$
$\displaystyle\langle\psi|\langle\phi|G|\psi\rangle|\phi\rangle+\langle\psi|\langle\phi|R|\psi\rangle|\phi\rangle$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{m}\langle\psi|H_{i}|\psi\rangle|\langle\gamma|p_{1}(i)-1\rangle|^{2}...|\langle\gamma|p_{5}(i)-1\rangle|^{2}+0$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{m}\frac{1}{4^{5}}\langle\psi|H_{i}|\psi\rangle$
$\displaystyle\leq$ $\displaystyle\frac{c}{\kappa}.$

_(Soundness)_ Let $|\phi_{0}\rangle,|\phi_{1}\rangle,\ldots,|\phi_{d}\rangle$,
for $d=2^{2n}-1$, be an orthonormal basis on the $n$ ancilla qudits consisting
of eigenvectors of $R$. Let $\lambda_{0}\leq\cdots\leq\lambda_{d}$ be the
eigenvalues of $R$, counted with multiplicity. Then
$|\phi_{0}\rangle=|\gamma\rangle^{\otimes n}$ and $\lambda_{0}=0$; moreover
for $1\leq i\leq d$, $\lambda_{i}\geq m^{r}$.

We proceed by contradiction. Let $|\psi^{\prime}\rangle$ be a state such that
$\langle\psi^{\prime}|(G+R)|\psi^{\prime}\rangle\leq\frac{s}{\kappa}-\frac{1}{m^{b+1}}$.
Expand $|\psi^{\prime}\rangle=\sum_{i=0}^{d}|a_{i}\rangle|\phi_{i}\rangle$,
where $\\{|a_{0}\rangle,\ldots,|a_{d}\rangle\\}$ are vectors on the initial
$n$ qubits. Let $|u\rangle=|a_{0}\rangle|\phi_{0}\rangle$ and
$|v\rangle=\sum_{i=1}^{d}|a_{i}\rangle|\phi_{i}\rangle$, so that
$|\psi^{\prime}\rangle=|u\rangle+|v\rangle$. Let

$c_{0}=\||u\rangle\|=\||a_{0}\rangle\|\qquad\text{and}\qquad
c_{1}=\||v\rangle\|=\Big{(}\sum_{i=1}^{d}\||a_{i}\rangle\|^{2}\Big{)}^{1/2}.$

Since $\langle u,v\rangle=0$, we have
$1=\||\psi^{\prime}\rangle\|^{2}=c_{0}^{2}+c_{1}^{2}$. Then

$\langle\psi^{\prime}|R|\psi^{\prime}\rangle=\sum_{i=0}^{d}\lambda_{i}\||a_{i}\rangle|\|^{2}\geq
m^{r}c_{1}^{2}.$

Further,

$\langle u|G|u\rangle=\langle
a_{0}|\langle\phi_{0}|G|a_{0}\rangle|\phi_{0}\rangle=\frac{1}{\kappa}\langle
a_{0}|H|a_{0}\rangle\geq\frac{1}{\kappa}s\langle
a_{0}|a_{0}\rangle=\frac{sc_{0}^{2}}{\kappa},$ (6)

where the inequality uses the soundness condition
$\forall|\psi\rangle,\langle\psi|H|\psi\rangle\geq s\langle\psi|\psi\rangle$.
Also note that

$|\langle u|G|v\rangle|=|\langle v|G|u\rangle|\leq\|v\|\|Gu\|\leq
m\|v\|\|u\|\leq mc_{1},$

where the first inequality is Cauchy-Schwarz and the second uses the fact that
$\|G\|\leq m$. Similarly, $|\langle v|G|v\rangle|\leq mc_{1}$, thus using (6),

$\langle\psi^{\prime}|G|\psi^{\prime}\rangle\geq\langle u|G|u\rangle-|\langle
u|G|v\rangle|-|\langle v|G|u\rangle|-|\langle
v|G|v\rangle|\geq\frac{sc_{0}^{2}}{\kappa}-3c_{1}m.$

We then get

$\displaystyle\langle\psi^{\prime}|(G+R)|\psi^{\prime}\rangle$
$\displaystyle\geq$
$\displaystyle\frac{sc_{0}^{2}}{\kappa}-3c_{1}m+c_{1}^{2}m^{r}$
$\displaystyle=$
$\displaystyle\frac{s}{\kappa}(1-c_{1}^{2})-3c_{1}m+c_{1}^{2}m^{r}$
$\displaystyle\geq$
$\displaystyle\frac{s}{\kappa}-\frac{1.5^{2}m^{2}}{m^{r}-\frac{s}{\kappa}}$
$\displaystyle\geq$ $\displaystyle\frac{s}{\kappa}-\frac{1}{m^{b+2}},$

where the expression in the third line was obtained by setting
$c_{1}=\frac{1.5m}{m^{r}-\frac{s}{\kappa}}$, which minimizes the expression in
the second line. We have reached a contradiction with the assumption
$\langle\psi^{\prime}|(G+R)|\psi^{\prime}\rangle\leq\frac{s}{\kappa}-\frac{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 $\mathsf{QCMA}$ is immediate since the prover can provide
the classical description of the poly($n$)-sized quantum circuit consisting of
2-qubit unitaries that prepares the state $|\psi\rangle$ from
$|0\rangle^{\otimes n}$ such that $\langle\psi|(A+B)|\psi\rangle\leq c$ if
such an efficiently preparable state exists. To see $\mathsf{QCMA}$-hardness,
let $V$ be the $\mathsf{QCMA}$ verifier for a language $L\in\mathsf{QCMA}$,
$H=\sum_{i=1}^{m}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
amplification for $\mathsf{QCMA}$, we may assume that the parameter $\epsilon$
in the lemma is $\epsilon=2^{-\operatorname{poly}(n)}$.

Let $G_{i}$, $i\in\\{1,\ldots,m\\}$ and $R_{j}$, $j\in\\{1,\ldots,n\\}$, be
the local projectors defined in Lemma 12. Note that the $G_{i}$ (resp.
$R_{j}$) are mutually commuting. Define

$A=\frac{1}{nm^{r}}\sum_{i}G_{i}\qquad\qquad B=\frac{1}{n}\sum_{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\leq A,B\leq I$, and so that $A+B$ is
proportional to $G+R$ as defined in the lemma. The proportionality factor is
$n^{-1}m^{-r}$ which is inverse polynomially small. $H^{\prime}=A+B$ is a
2-layered $15$-local Hamiltonian whose ground state energy is exponentially
small if $x\in L$ (i.e. $V$ accepts $x$) and at least inverse polynomially
large if $x\notin L$ (i.e. $V$ rejects $x$). Moreover, if $x\in L$ there is an
efficiently preparable state which achieves exponentially small energy for $H$
(it is a tensor product of the history state (5) and a symmetric product
state). ∎