# Perturbative gadgets without strong interactions

Yudong Cao<EMAIL_ADDRESS>Department of Computer Science, Purdue University,
West Lafayette, IN 47906, USA Daniel Nagaj<EMAIL_ADDRESS>Institute of
Physics, Slovak Academy of Sciences, Dúbravská cesta 9, 84215 Bratislava,
Slovakia

###### Abstract

_Perturbative gadgets_ are used to construct a quantum Hamiltonian whose low-
energy subspace approximates a given quantum $k$-body Hamiltonian up to an
absolute error $\epsilon$. Typically, gadget constructions involve terms with
large interaction strengths of order $\text{poly}(\epsilon^{-1})$. Here we
present a 2-body gadget construction and prove that it approximates a target
many-body Hamiltonian of interaction strength $\gamma=O(1)$ up to absolute
error $\epsilon\ll\gamma$ using interactions of strength $O(\epsilon)$ instead
of the usual inverse polynomial in $\epsilon$. A key component in our proof is
a new condition for the convergence of the perturbation series, allowing our
gadget construction to be applied in parallel on multiple many-body terms. We
also show how to apply this gadget construction for approximating 3- and
$k$-body Hamiltonians.

The price we pay for using much weaker interactions is a large overhead in the
number of ancillary qubits, and the number of interaction terms per particle,
both of which scale as $O(\text{poly}(\epsilon^{-1}))$. Our strong-from-weak
gadgets have their primary application in complexity theory (QMA hardness of
restricted Hamiltonians, a generalized area law counterexample, gap
amplification), but could also motivate practical implementations with many
weak interactions simulating a much stronger quantum many-body interaction.

##  1 Introduction

The physical properties of (quantum mechanical) spin systems can often be
understood in terms of effective interactions arising from the complex
interplay of microscopic interactions. Powerful methods for analyzing
effective interactions have been developed, for example the renormalization
group approach distills effective interactions at different length scales.
Another common approach is perturbation theory – treating some interaction
terms in the Hamiltonian as a perturbation to a simple original system, giving
us a sense of how the fully interacting system behaves. Here, instead of
trying to understand an unknown system, we ask an engineering question: how
can we build a particular (many-body) effective interaction from local terms
of restricted forms?

The idea of _perturbative gadgets_ provides a powerful answer to that
question. Initially introduced by Kempe, Kitaev and Regev [1] for showing the
QMA-hardness of 2-Local Hamiltonian problem and subsequently used and
developed further in numerous works [2, 3, 4, 5, 6, 7, 8], the perturbative
gadgets are convenient tools by which arbitrary many-body effective
interactions (which we call the _target Hamiltonian_) can be obtained using a
_gadget Hamiltonian_ consisting of only two-body interactions. In a broader
context, these gadgets have also been used to understand the computational
complexity of physical systems (e.g. how hard it is to determine the ground
state energy) with restricted geometry of interactions [2], locality [1, 2,
6], or interaction types [4]. Here, we choose to focus on the issue of
restricted coupling strengths.

In a nutshell, perturbative gadgets allow us to map between different forms of
microscopic Hamiltonians. This is reminiscent of the use of gadgets in the
classical theory of NP-completeness which starts from Constraint Satisfaction
Problem (CSP). In the context of combinatorial reduction in classical
complexity theory, a gadget is a finite structure which maps a set of
constraints from one optimization problem into constraints of another. Using
such gadgets, an instance of 3-SAT (an NP-complete problem) can be efficiently
mapped to an instance of Graph 3-coloring (another NP-complete problem [9]).
On the other hand, more complex constructions allow us to create more
frustrated instances of such problems without significant overhead, resulting
in inapproximability as well as the existence of probabilistically checkable
proofs [10].

For classical CSP instances, gadgets can be used to reduce the arity of
clauses, to reduce the size of the alphabet, or to reduce the degree of each
variable on the constraint graph. It is now interesting to ask whether we
could create quantum versions of gadgets that reduce the locality of
interactions (analogous to arity reduction in classical CSPs), the dimension
of particles (alphabet reduction) or the number of interactions that each
particle is involved (degree reduction). Such gadget reductions for quantum
Hamiltonians could give us tools that might help explore the way to the
quantum PCP conjecture [11]. More modestly, gadget translations between types
of local Hamiltonians would have implications for the area law [12, 13, 14]
and other global properties. However, generating approximate quantum
interactions from a restricted set of terms is not straightforward.

Creating effective interactions with arbitrary strength by coupling a system
to several ancilla degrees of freedom is a relatively simple task for
classical spin systems. For example, we can create an effective (and twice
stronger) ferromagnetic interaction between target spins $a,b$ using two
ancilla spins $x,y$ and connecting them to $a,b$ as illustrated in Figure 1.
The lowest energy states of this new system correspond to the lowest energy
states of a system with a ferromagnetic interaction between $a$ and $b$, with
double strength.

Figure 1: A ferromagnetic interaction $E(a,b)=-2Jab$ of two classical spins
$a,b=\in\\{-1,1\\}$ can be “built” from half-strength interactions involving
two extra ancillas. The ground states of the system on the right have $a=b$,
while the lowest excited states have $a\neq b$ and energy $4J$ above the
ground state energy. Each edge between two classical spins $u$ and $v$ in this
illustration represents a term $uv$ in the expression for energy. The
$\ocircle$ nodes symbolize target spins and $\Box$ nodes are ancillas.

For general quantum interactions where the target Hamiltonian consists of
many-body Pauli operators, the common perturbative gadget introduces a
strongly bound ancillary system and couple the target spins to it via weaker
interactions, treating the latter as a perturbation. The target many-body
Hamiltonian is then generated in some low order of perturbation theory of the
combined system that consists of both ancillary and target spins. Such gadgets
first appeared in the proof of QMA-completeness of the 2-Local Hamiltonian
problem via a reduction from 3-Local Hamiltonian [1]. There they helped build
effective 3-body interactions from 2-body ones. Perturbative gadgets can also
be used for reducing a target Hamiltonian with general interaction topology to
a planar interaction graph [2], approximating certain restricted forms of
2-body interactions using other forms of 2-body interactions [4], realizing
Hamiltonians exhibiting non-abelian anyonic excitations [15] and reducing
$k$-body interactions to 2-body [6, 5].

All existing constructions of perturbative gadgets [1, 2, 6, 5, 4, 8] require
interaction terms or local fields with norms much higher than the strength of
the effective interaction which they generate, in order for the perturbation
theory to apply111 Note that there exist special cases (e.g. Hamiltonians with
all terms diagonal in the same basis) when one can analyze the Hamiltonian
with non-perturbative techniques [16, 17]. (see Figure 2b). However,
physically realizable systems often allow only limited interaction strengths.
The main result of our paper is a way around this problem.

We first build a system with a large spectral gap between the ground state and
the first excited state using many relatively weak interactions: consider a
collection of $n$ spins that interact with each other via ZZ coupling of
constant strength $J$. Then the first excited state of this $n$-spin system is
separated from the ground energy by $\Omega(n)$. This way we can use weaker
interactions to construct a _core_ with a large spectral gap. We then use it
to replace the large local field applied onto the single ancilla (Figure 2b)
with weak interactions of a collection of ancillas (Figure 2c). Finally, we
connect the target spins to multiple ancillas instead of just one, which
allows us to use weaker $\beta$ to achieve the same effective interaction
strength between the target spins (Figure 2d).

Let us review a few definitions and then state our results precisely. An
$n$-qubit222Here we use the terms _qubit_ , _spin_ and _particle_
interchangeably. Hamiltonian is an $2^{n}\times 2^{n}$ Hermitian matrix; it is
$k$-local (for a constant $k$) if it can be written as a sum of
$M\leq\text{poly}(n)$ terms $H_{j}$, each acting non-trivially on at most $k$
qubits. Furthermore, we require333We use the operator norm $\|\cdot\|$,
defined as
$\|M\|\equiv\max_{|\psi\rangle\in\mathcal{M}}|\langle\psi|M|\psi\rangle|$ for
an operator $M$ acting on a Hilbert space $\mathcal{M}$).
$\|H_{j}\|\leq\text{poly}(n)$, and that the entries of $H_{j}$ be specified by
poly$(n)$ bits. The smallest eigenvalue of $H$ is its _ground state energy_ ,
and we denote it $\lambda(H)$. We use $\lambda_{j}(H)$ to represent the $j$-th
smallest eigenvalue of $H$, hence $\lambda(H)=\lambda_{1}(H)$. Taking a
2-local Hamiltonian acting on $n$ qubits, we can associate it with an
_interaction graph_ $G(V,E)$. Every $v\in V$ corresponds to a qubit, and there
is an edge $e\in E$ between vertices $a$ and $b$ if and only if there is a
non-zero 2-local term $H_{e}$ on qubits $a$ and $b$ such that $H_{e}$ is
neither 1-local nor proportional to the identity operator. More generally, we
can pair a $k$-local Hamiltonian with its interaction hypergraph in which the
$k$-local terms correspond to hyper-edges involving (at most) $k$ vertices. In
particular, 1-local terms correspond to self-loops. Next, because we can
decompose any 2-local Hamiltonian term in the Pauli basis444 For example, the
spin chain Hamiltonian $H=\sum_{i=1}^{n}|01-10\rangle\langle 01-10|_{i,i+1}$
has interaction edges between successive spins. Each 2-local interaction can
be rewritten in the Pauli basis as
$\frac{1}{4}\left(\mathbb{I}\otimes\mathbb{I}-X\otimes X-Y\otimes Y-Z\otimes
Z\right)$. It gives us an overall energy shift (from the first term), and
three Pauli edges., we can define a Pauli edge of an interaction graph $G$ as
an edge between vertices $a$ and $b$ associated with an operator
$\gamma_{ab}\,P_{a}\otimes Q_{b}$ where $P,Q\in\\{\mathbb{I},X,Y,Z\\}$ are
Pauli matrices and $\gamma_{ab}$ is a real number representing the coupling
coefficient. We refer to the maximum value of $|\gamma_{ab}|$ over all terms
in the Hamiltonian as the _interaction strength_ of the Hamiltonian. For an
interaction graph where every edge is a _Pauli edge_ , the degree of a vertex
is called its _Pauli degree_. The maximum Pauli degree of vertices in an
interaction graph is the Pauli degree of the graph.

###  1.1 Summary

We start in Section 2 with an introduction to the formalism of perturbation
theory that we use, then in Section 3, we present and prove our main result –
a construction that generates a target 2-local Hamiltonian via weak 2-local
couplings using many ancilla particles:

######  Theorem 1 (Effective 2-body interactions from weak couplings).

Let
$H_{\text{targ}}=H_{\text{else}}+\sum_{j=1}^{M}\gamma_{j}\,A_{a_{j}}\otimes
B_{b_{j}}$ be a 2-local Hamiltonian acting on $n$ qubits with an interaction
graph of Pauli degree $p$ and ground state energy $\lambda(H_{\text{targ}})$,
assuming $M\leq\text{poly}(n)$, and the interaction strength is bounded555To
deal with Hamiltonians with large interaction strengths, we can view the Pauli
edges as multi-edges. We then decompose each large term into as many $O(1)$
terms as necessary. as $\gamma_{\text{max}}=\max_{j}|\gamma_{j}|=O(1)$. Here
$a_{j},b_{j}\in[n]$ refers to the qubits that the $A$ and $B$ operators in the
$j^{\text{th}}$ term act on respectively. Let $H_{\text{else}}$ be some
Hamiltonian with a non-negative spectrum and
$\|H_{\text{else}}\|\leq\text{poly}(n)$. Then for any $\epsilon>0$ and
$\epsilon\ll\gamma$ there exists a 2-local Hamiltonian $\tilde{H}$ with
interaction strength $O(\epsilon)$ and low-lying spectrum approximating the
full spectrum of $H_{\text{targ}}$ as
$|\lambda_{j}(\tilde{H})-\lambda_{j}(H_{\text{targ}})|\leq\epsilon$ for all
$j$. The gadget Hamiltonian $\tilde{H}$ acts on
$n+\text{poly}(\|H_{\text{else}}\|,\epsilon^{-1},M)$ qubits and has an
interaction graph of Pauli degree
$\text{poly}(p,\|H_{\text{else}}\|,\epsilon^{-1},M)$.

The above theorem deals with 2-local target Hamiltonians. We also know gadget
constructions for reducing 3-local interactions [1, 2, 6] or $k$-local
interactions [5, 6] to 2-local ones. These typically involve strong
interaction terms, which could be further reduced to a construction consisting
of only weak interactions using ideas from the proof for Theorem 5. In
particular:

######  Theorem 2 (3-body terms from weak 2-body interactions).

Let
$H_{\text{targ}}=H_{\text{else}}+\sum_{i=1}^{M}\gamma_{i}\,A_{a_{i}}\otimes
B_{b_{i}}\otimes F_{f_{i}}$ be a 3-local Hamiltonian acting on $n$ qubits with
an interaction graph of Pauli degree $p$ and ground state energy
$\lambda(H_{\text{targ}})$, assuming $M\leq\text{poly}(n)$. Here
$a_{j},b_{j},f_{j}\in[n]$ refers to the qubits that the $A$, $B$ and $F$
operators in the $j^{\text{th}}$ term act on respectively. The interaction
strength of $H_{\text{targ}}$ satisfies
$\gamma_{\text{max}}=\max_{j}|\gamma_{j}|=O(1)$. Let $H_{\text{else}}$ be a
Hamiltonian with non-negative spectrum and satisfies
$\|H_{\text{else}}\|\leq\text{poly}(n)$. Then for any choice $\epsilon>0$,
there exists a 2-local Hamiltonian $\tilde{H}$ with interaction strength
$O(\epsilon)$, acting on $n+\text{poly}(\|H_{\text{else}}\|,\epsilon^{-1},M)$
qubits, with an interaction graph of Pauli degree
$\text{poly}(p,\|H_{\text{else}}\|,\epsilon^{-1},M)$ and
$|\lambda_{j}(\tilde{H})-\lambda_{j}(H_{\text{targ}})|\leq\epsilon$ for all
$j$.

We provide basic ideas of the proof of Theorem 2 in Section 4, hoping for a
more efficient construction to be proposed in the future.

An important property of the new construction is that it can be repeated in
parallel, in essence generating arbitrary strong interaction from weak ones.
Thus, we can effectively rescale interaction strengths and amplify the
eigenvalue gap of a local Hamiltonian. The price we pay is the addition of
many ancillas and a large increase in the number of interactions per particle.

######  Corollary 1 (Coupling strength amplification by gadgets).

Let $H=\sum_{j=1}^{M}H_{j}$ be a $k$-local Hamiltonian on $n$ qubits where
$M=poly(n)$ and each $H_{j}$ satisfies $\left\|H_{j}\right\|\leq s$ for some
constant $s$. Let $|\phi_{j}\rangle$ and $\lambda_{j}$ be the $j$-th
eigenstate and eigenvalue of $H$, and let $\Delta$ be the gap between the
ground and first excited energy of $H$. Choose a magnifying factor $\theta>1$
and an error tolerance $\epsilon>0$. Then there exists a 2-local Hamiltonian
$\tilde{H}$ with interactions of strength $O(1)$ or weaker. The low-lying
eigenstates of $\tilde{H}$ are $\epsilon$-close666Here by _$\epsilon$ -close_
we mean the norm of the difference between the two quantities (scalar, vector
or matrix operator) is no greater than $\epsilon$. to
$|\phi_{j}\rangle\otimes|0\cdots 0\rangle_{anc}$ where $|0\cdots
0\rangle_{\text{anc}}$ is the state of the ancilla qubits of $\tilde{H}$, and
the low-lying spectrum of $\tilde{H}$ is $\epsilon$-close to
$\theta\lambda_{j}$. The low energy effective Hamiltonian of $\tilde{H}$ is
$\epsilon$-close to $\theta H\otimes|0\cdots 0\rangle\langle 0\cdots
0|_{anc}$.

Whereas Theorem 5 states that a 2-local target Hamiltonian can be gadgetized
to a Hamiltonian with arbitrarily weak interactions, Corollary 6 states that
the same could be accomplished for a $k$-local target Hamiltonian. Moreover,
besides producing a gadget Hamiltonian with weak interaction that generates
the target $k$-local Hamiltonian, we could also generate the target
Hamiltonian multiplied by a positive factor $\theta$. In case where
$\theta>1$, this can be viewed as a coupling strength amplification relative
to the original target $k$-local Hamiltonian. The basic idea for proving
Corollary 6 is to view the target Hamiltonian $\theta H$ (with $\theta>1$) as
a sum of $O(\theta)$ copies of itself with interaction strength $O(1)$. Using
the gadget constructions from [5], we transform the $k$-local Hamiltonian
$\theta H$ to a 2-local one. Finally, using our 2-body gadget construction in
this work, we translate this Hamiltonian to one with only weak interactions
(2-body). What is the efficiency of this way of amplifying the couplings? We
expect that the final gadget Hamiltonian acts on a system whose total number
of qubits scales exponentially in $k$ (which of course is not a problem for
$k=3$).

###  1.2 Conclusions and Open Questions

The gadget construction based on perturbation theory allows us to map between
Hamiltonians of different types, with the same low-lying spectrum.
Intuitively, the _core_ construction that we introduce can be thought of as
replacing strong interactions by repetition of interactions with “classical”
ancillas; it works because for a low-energy state, all our extra qubits are
close to the state $|0\rangle$. This is reminiscent of repetition encoding
found e.g. in [18]. Another feature of 2-body gadget that we use heavily is
parallelization; it is crucial to show that the perturbation series converges
even with many gadgets, relaxing the usual assumption about the norm of the
perturbation.

The 2-body gadget constructed here should find use in computer science as well
as physics. First, in complexity theory, Theorem 5 together with [1] or
Theorem 2 with [19] implies QMA-completeness of the 2-local Hamiltonian
problem with $O(1)$ terms and an $O(1)$ promise gap. As a consequence, we also
obtain efficient universality for quantum computation with time-independent,
2-local Hamiltonians with restricted form/strength of terms, complementing
[20, 2, 21]. Second, our amplification method from Corollary 6 has been
utilized in a counterexample to the generalized area law in [22]. Finally, we
envision practical experimental applications of Theorem 5 – strengthening
effective interactions between target (atomic) spins through many coupled
mediator spins.

Thinking further about interaction strengths and spectra of local
Hamiltonians, we realize that Corollary 6 allows us to amplify the eigenvalue
gap (low eigenvalue spacing) of a Hamiltonian. Does it have direct
implications for hardness of Local Hamiltonian problems? When we use it on
Hamiltonians appearing in QMA-complete constructions, the fractional promise
gap (the ratio of the number of frustrated terms to the number of all terms in
the Hamiltonian for a ground state of a local Hamiltonian) gets smaller. Thus,
it does not provide us with a tool that would directly help us to move towards
the quantum PCP conjecture [11]. Nevertheless, we have added another tool for
mapping between Hamiltonians to our repertoire.

An important problem remains open. The price we pay for our construction is a
massive blowup in the degree (the number of interactions per particle). Is
there a possibility of a quantum degree-reduction gadget? One might try to use
a “bad” quantum code for encoding each spin into several particles, whose
encoded low-weight operators that can be implemented in many possible ways;
this does not seem possible for both $X$ and $Z$ operators. As things stand,
without a degree-reduction gadget, we do not have a way to reproduce our
results in simpler geometry. It would be really interesting if one indeed
could create $O(1)$-norm effective interactions from $O(1)$-terms in 3D or
even 2D lattices.

We also need to think about the robustness of our results – what will change
when the Hamiltonians are not exactly what we asked for? How precise do we
need to be e.g. for the 3-body to 2-body gadgets, so that the second- and
first-order terms get canceled? Next, we realize that given an absolute error
$\epsilon$, we do not have an algorithm that computes the optimal assignments
to $R,C,\beta,$ etc. such that the resulting error is close to but smaller
than $\epsilon$ (as in the case of [8]). Finally, Bravyi, Terhal, DiVincenzo
and Loss [6] mentioned whether a $k$-body to 2-body reduction can be
implemented with poly$(k)$ overhead in interaction strength (instead of
exponential in $k$). This question remains open. In [6] the exponential
scaling in the overhead is due to the usual gadget constructions which require
poly$(\epsilon^{-1})$ interaction strength. We hope that with our new gadget
construction, the results in [6] could be improved.

##  2 Effective interactions based on perturbation theory

The purpose of a perturbative gadget is to approximate a target $n$-qubit
Hamiltonian $H_{\text{targ}}$ by a gadget Hamiltonian $\tilde{H}$ which uses a
restricted form of interactions among the $n$ qubits that $H_{\text{targ}}$
acts on and poly($n$) additional ancilla qubits. The subspace spanned by the
lowest $2^{n}$ eigenstates of $\tilde{H}$ should approximate the spectrum of
$H_{\text{targ}}$ up to a prescribed error tolerance $\epsilon$ in the sense
that the $j^{\text{th}}$ lowest eigenvalue of $\tilde{H}$ differs from that of
$H_{\text{targ}}$ by at most $\epsilon$ and the inner product between the
corresponding eigenstates of $\tilde{H}$ and $H_{\text{targ}}$ (assume no
degeneracy) is at least $1-\epsilon$. These error bounds can be established
using perturbation theory [1, 2]. There are various versions of perturbation
theory available for constructing and analyzing gadgets (for a review see
[23]). For example, Jordan and Farhi [5] use Bloch’s formalism, while Bravyi
et al. rely on the Schrieffer-Wolff transformation [6]. For our gadget
construction in Section 3, we use the technique from [1, 2].

Let us now review the basic ideas underlying the construction of effective
Hamiltonians from gadgets. The gadget Hamiltonian $\tilde{H}=H+V$ is a sum of
an unperturbed Hamiltonian $H$ and a perturbation $V$. $H$ acts only on the
ancilla space, energetically penalizing certain configurations, and favoring a
specific ancilla state or subspace. Second, we have a perturbation $V$
describing how the target spins interact with the ancillas.

Let us introduce the following notations: let $\lambda_{j}$ and
$|\psi_{j}\rangle$ be the $j^{\text{th}}$ eigenvalue and eigenvector of $H$
and similarly define $\tilde{\lambda}_{j}$ and $|\tilde{\psi}_{j}\rangle$ for
$\tilde{H}$, assuming all the eigenvalues are labeled in a weakly increasing
order ($\lambda_{1}\leq\lambda_{2}\leq\cdots$, similarly for
$\tilde{\lambda}_{j}$). Using a cutoff value $\lambda_{*}$, let us call
$\mathcal{L}_{-}=\text{span}\\{|\psi_{j}\rangle\,|\,\lambda_{j}\leq\lambda_{*}\\}$
the low-energy subspace and
$\mathcal{L}_{+}=\text{span}\\{|\psi_{j}\rangle\,|\,\lambda_{j}>\lambda_{*}\\}$
the high-energy subspace. Let ${\Pi_{-}}$ and ${\Pi_{+}}$ be the orthogonal
projectors onto the subspaces $\mathcal{L}_{-}$ and $\mathcal{L}_{+}$. For an
operator $O$ we define the partitioning of $O$ into these subspaces as
$O_{-}={\Pi_{-}}O{\Pi_{-}}$, $O_{+}={\Pi_{+}}O{\Pi_{+}}$,
$O_{-+}={\Pi_{-}}O{\Pi_{+}}$ and $O_{+-}={\Pi_{+}}O{\Pi_{-}}$. We define
similar notations $\tilde{\mathcal{L}}_{-}$ and $\tilde{\mathcal{L}}_{+}$ for
$\tilde{H}$.

Our first goal is to understand $\tilde{H}_{-}$, the restriction of the gadget
Hamiltonian to the low-energy subspace. Let us consider the operator-valued
resolvent $\tilde{G}(z)=(z\mathbb{I}-\tilde{H})^{-1}$ where $\mathbb{I}$ is
the identity operator. Similarly let us define $G(z)=(z\mathbb{I}-H)^{-1}$.
Note that $\tilde{G}^{-1}(z)-G^{-1}(z)=-V$, which allows an expansion of
$\tilde{G}$ in powers of $V$:

$\tilde{G}=(G^{-1}-V)^{-1}=G(\mathbb{I}-VG)^{-1}=G+GVG+GVGVG+\cdots.$ (1)

It is also standard to define the self-energy
$\Sigma_{-}(z)=z\mathbb{I}-({\tilde{G}}_{-}(z))^{-1}$. It is important because
the spectrum of $\Sigma_{-}(z)$ gives an approximation to the spectrum of
$\tilde{H}_{-}$, since by definition
$\tilde{H}_{-}=z\mathbb{I}-{\Pi_{-}}(\tilde{G}^{-1}(z)){\Pi_{-}}$ while
$\Sigma_{-}(z)=z\mathbb{I}-({\Pi_{-}}\tilde{G}(z){\Pi_{-}})^{-1}$. As
explained in [2], if $\Sigma_{-}(z)$ is roughly constant in some range of $z$
(see Theorem 3 below for details) then $\Sigma_{-}(z)$ is (loosely speaking)
playing the role of $\tilde{H}_{-}$. This was formalized in Theorem 3 in [1]
(and improved in Theorem A.1 in [2]). Similarly to [2], we choose to work with
$H$ whose lowest eigenvalue is zero and whose spectral gap is $\Delta$.
However, for establishing our main results as stated in Theorems 5 and 2, here
we use a slightly modified version of Theorem 3 from [1]:

######  Theorem 3 (Gadget approximation theorem, modified from [1]).

Let $H$ be a Hamiltonian with a gap $\Delta$ between its ground state and
first excited state. Assuming the ground state energy of $H$ is 0, let
$\lambda_{*}=\Delta/2$. Consider a bounded norm perturbation $V$. The
perturbed Hamiltonian is then $\tilde{H}=H+V$. Following the notations
introduced previously, if the following holds:

  1. 1.

$\tilde{\mathcal{L}}_{-}\cap\mathcal{L}_{+}=\varnothing$, _i.e._ when the
perturbed low- and the unperturbed high-energy states are separated: the
energy
$\langle\xi_{+}|{H}|\xi_{+}\rangle>\lambda_{*}>\langle\xi_{-}|\tilde{H}|\xi_{-}\rangle$
for any normalized state $|\xi_{+}\rangle\in\mathcal{L}_{+}$ and
$|\xi_{-}\rangle\in\tilde{\mathcal{L}}_{-}$.

  2. 2.

There is an effective Hamiltonian $H_{\text{eff}}$ with a spectrum contained
in $[E_{1},E_{2}]$ for some $\epsilon>0$ and $E_{1}<E_{2}<\Delta/2-\epsilon$,
such that for every $z\in[E_{1}-\epsilon,E_{2}+\epsilon]$, the self-energy
$\Sigma_{-}(z)$ obeys $\|\Sigma_{-}(z)-H_{\text{eff}}\|\leq\epsilon$.

then all the eigenvalues of $\tilde{H}_{-}$ are close to the eigenvalues of
$H$, obeying

$|\lambda_{j}(H_{\text{eff}})-\lambda_{j}(\tilde{H}_{-})|\leq\epsilon.$

Here is how our statement of Theorem 3 differs from the original version [1].
There, $\|V\|\leq\Delta/2$ is used as a condition, while we only assume that
$\tilde{\mathcal{L}}_{-}\cap\mathcal{L}_{+}=\varnothing$, meaning that the
energy levels of the perturbed low-energy subspace do not mix with the
unperturbed excited subspace. Our assumption is weaker, yet it is sufficient
to yield the same conclusion as Theorem 3 in [1]. We choose to avoid enforcing
$\|V\|\leq\Delta/2$ in our construction since it imposes limitations on the
_global_ properties of the gadget construction, in particular the number of
ancillas we use, disregarding the structure of the perturbation. One might
question whether the use of perturbation theory is sensible if we assume that
the perturbation $\|V\|$ is no longer small compared to the spectral gap
$\Delta$. We note that such use has been justified previously by Bravyi et al.
[6] in a similar context.

To apply Theorem 3, a series expansion for the self-energy
$\Sigma_{-}(z)=z\mathbb{I}-\tilde{G}_{-}^{-1}(z)$ is truncated at some low
order, for which $H_{\text{eff}}$ is approximated. Using the series expansion
of $\tilde{G}$ in (1), the self-energy can be expanded as (see [1] for
details)

$\Sigma_{-}(z)=H_{-}+V_{-}+V_{-+}G_{+}(z)V_{+-}+V_{-+}G_{+}(z)V_{+}G_{+}(z)V_{+-}+\cdots,$
(2)

with $G_{+}(z)=\Pi_{+}(z\mathbb{I}-H)^{-1}\Pi_{+}$. The $2^{\text{nd}}$ and
higher order terms in this expansion give rise to effective many-body
interactions. Introducing auxiliary spins and a suitable selection of 2-local
$H$ and $V$, we can engineer $\Sigma_{-}(z)$ to be $\epsilon$-close to
$H_{\text{eff}}=H_{\text{targ}}\otimes\Pi_{-}$ (here $\Pi_{-}$ is the
projector to the ground state subspace of the ancillas) in the range of $z$
considered in Theorem 3. Therefore with
$\|\Sigma_{-}(z)-H_{\text{eff}}\|\leq\epsilon$, condition 2 of Theorem 3 is
satisfied.

In the next Section, we will look at the usual 2-body gadgets and see how the
second order terms in the self-energy result in the desired effective
Hamiltonian. Then we present our construction that involves more ancillas with
weaker interactions, and show that the effective Hamiltonian is again what we
want, and both conditions for Theorem 3 are satisfied.

##  3 A new gadget for 2-body interactions

We can decompose any 2-local interaction of spin-$\frac{1}{2}$ particles into
the Pauli basis777It is useful that the Pauli matrices
$A,B\in\\{\mathbb{I},X,Y,Z\\}$ square to identity, because $A^{2}$ and $B^{2}$
terms in our effective Hamiltonian will become simple overall energy shifts,
using terms of the form $\gamma A\otimes B$, with the operator $A$ acting on
spin $a$ and $B$ acting on spin $b$, and $\gamma$ the interaction strength. It
will be enough to show how to replace any such Pauli’ interaction in our
system by a gadget, aiming at the target interaction
$H_{\text{targ}}=H_{\text{else}}+\gamma A\otimes B$, with $H_{\text{else}}$
some $O(1)$-norm, 2-local Hamiltonian. First, we briefly review the existing
constructions [2, 6, 8] for generating $H_{\text{targ}}$ using a gadget
Hamiltonian $\tilde{H}$. Then we present a new 2-body gadget which simulates
an arbitrary $\gamma=O(1)$ strength 2-local interaction using a gadget
Hamiltonian with terms of strength only $o(1)$, “building” quantum
interactions from many weaker ones.

Figure 2: Effective two-body interaction mediated by ancilla qubits. Each node
represents a particle. The size of the node indicates the strength of local
field applied onto it. The width of each edge shows the strength of the
interaction between the particles that the edge connects. (a) The desired
2-local interaction between target spins $a,b$. (b) The usual perturbative
gadget uses a single ancilla $w$ in a strong local field, and large-norm
interactions with the target spins. (c) We can replace the strong local field
$\Delta/2$ by ferromagnetic interactions with a fixed core – a group of $C$
“core” ancilla qubits located in a field of strength $J/2$, interacting with
each other ferromagnetically (as a complete graph), with strength $J/2$. (d)
Instead of the strong interactions between target spins $a,b$ and a single
ancilla $w$, we can use $R$ different “direct” ancillas (labelled as $w_{1}$,
$w_{2}$, $\cdots$, $w_{R}$) and weaker interactions of strength $\beta$.

_The usual construction._ Consider a target 2-local term involving two qubits
$a,b$ as depicted in Figure 2(a). The standard construction of a gadget
Hamiltonian $\tilde{H}$ that captures the 2-local target term is shown in
Figure 2(b). First, we introduce an ancilla qubit $w$ bound by a local field,
with the Hamiltonian $H=-\frac{\Delta}{2}Z_{w}$. Alternatively, up to a
spectral shift we could write $H=\Delta|1\rangle\langle{1}|_{w}$ where
$|1\rangle\langle{1}|_{w}=\frac{1}{2}(\mathbb{I}-Z_{w})$. Then we let $w$
interact with $a$ and $b$ through $\sqrt{\Delta/2}\,A\otimes\mathbb{I}\otimes
X_{w}$ and $-\sqrt{\Delta/2}\,\mathbb{I}\otimes B\otimes X_{w}$, and choose
$\Delta=\Theta(\epsilon^{-1})$, according to the analysis in [8]. We can view
these terms as a perturbation to $H$ and show that up to an error $\epsilon$,
the low energy effective Hamiltonian as calculated via Equation 2 is
approximately $A\otimes B\otimes|0\rangle\langle{0}|_{w}$ (up to an overall
energy shift) [8]. Here “up to an error $\epsilon$” means that the $j$-th
lowest eigenvalue of $\tilde{H}$ differs from that of $H_{\text{targ}}$ by at
most $\epsilon$ and the inner product between the corresponding eigenstates of
$\tilde{H}$ and $H_{\text{targ}}$ (assume no degeneracy) is at least
$1-\epsilon$.

_Our construction._ In the usual construction, with better precision
(decreasing $\epsilon$), the spectral gap $\Delta$ (related to local field
strength) and interaction strengths grow as _inverse_ polynomials in
$\epsilon$. We now suggest a 2-body gadget which simulates an arbitrary $O(1)$
strength target interaction using a gadget Hamiltonian of only $O(\epsilon)$
interaction strength _i.e._ without the need for large-norm terms. We build it
in a sequence of steps illustrated in Figure 2.

The first step is to reduce the large local field $\Delta$ in Figure 2(b). Let
us call the ancilla $w$ directly interacting with the target spins a direct
ancilla. We add a core $\mathcal{C}$ – a set of $C$ ancilla qubits
$c_{1},\dots,c_{C}$, with a complete graph of ferromagnetic (ZZ) interactions
of strength $\frac{J}{2}$, and in a local field of strength $\frac{J}{2}$
where $J=O(\epsilon)$. We then let the direct ancilla $w$ interact
(ferromagnetically) with each of the core ancillas, as in Figure 2(c). The
Hamiltonian for the direct and core ancillas then reads

$\displaystyle{\frac{J}{2}\sum_{c\in\mathcal{C}}(\mathbb{I}-Z_{w}Z_{c})}+\underbrace{\frac{J}{2}\sum_{c\in\mathcal{C}}(\mathbb{I}-Z_{c})+\frac{J}{2}\sum_{c,c^{\prime}\in\mathcal{C}}(\mathbb{I}-Z_{c}Z_{c^{\prime}})}_{\equiv
H_{\mathcal{C}}}.$ (3)

$H_{\mathcal{C}}$ is the Hamiltonian describing the core $\mathcal{C}$. The
ground state of this Hamiltonian is $|0\rangle_{w}|0\cdots
0\rangle_{\mathcal{C}}$, and the gap between its ground and first excited
state $|1\rangle_{w}|0\cdots 0\rangle_{\mathcal{C}}$ is $\Delta=JC$. Here $C$
is the number of ancillas in the core $\mathcal{C}$.

The second step is to use $R$ direct ancillas $w_{1},\dots,w_{R}$ instead of
just one, connecting each of them to the core ancillas as in Figure 2(d). The
Hamiltonian then becomes

$\displaystyle H$
$\displaystyle=\frac{J}{2}\sum_{i=1}^{R}\sum_{c\in\mathcal{C}}(\mathbb{I}-Z_{w_{i}}Z_{c})+H_{\mathcal{C}}.$
(4)

Its ground state is $|0\cdots 0\rangle_{w}\otimes|0\cdots
0\rangle_{\mathcal{C}}$ (here we use the subscript $w$ to refer to all the
direct ancillas connected to the target qubits), and the gap between the two
lowest energies is still $\Delta=JC$.

We want to engineer an effective interaction $H_{\text{targ}}=\gamma
A_{a}\otimes B_{b}+H_{\text{else}}$, where the first term is our desired
Hamiltonian, and $H_{\text{else}}$ is a finite-norm Hamiltonian that includes
all the other terms that we want to leave unchanged by this gadget. Starting
with the Hamiltonian $H$ in (4), we add a perturbation

$\displaystyle V=H_{\text{else}}+\beta\sum_{i=1}^{R}\left(A_{a}\otimes
X_{w_{i}}-B_{b}\otimes X_{w_{i}}\right),$ (5)

where $\beta>0$ is the strength of the interactions between the target spins
and the direct ancillas. Showing that we can use perturbation theory to obtain
the effective Hamiltonian crucially relies on Theorem 3, and we will justify
that its conditions hold later. Let us now prepare the notations and tools for
this. Let $\mathcal{L}_{-}$ be the subspace with the ancillas in the state
$|0\rangle^{\otimes(R+C)}$, let the subspace of all unit vectors in the
Hilbert space that is orthogonal to $\mathcal{L}_{-}$ be denoted as
$\mathcal{L}_{+}$, and let $\Pi_{-}$ and $\Pi_{+}$ be the projectors onto
these subspaces. We then have

$\displaystyle V_{-}$
$\displaystyle=\Pi_{-}V\Pi_{-}=H_{\text{else}}\otimes\Pi_{-},$ (6)
$\displaystyle V_{-+}$
$\displaystyle=\Pi_{-}V\Pi_{+}=\beta(A_{a}-B_{b})\otimes\sum_{i=1}^{R}|0\rangle\langle{1}|_{w_{i}},$
(7) $\displaystyle V_{+-}$
$\displaystyle=\Pi_{+}V\Pi_{-}=\beta(A_{a}-B_{b})\otimes\sum_{i=1}^{R}|1\rangle\langle{0}|_{w_{i}},$
(8) $\displaystyle V_{+}$
$\displaystyle=\Pi_{+}V\Pi_{+}=H_{\text{else}}\otimes\Pi_{+}+\beta\sum_{i=1}^{R}(A_{a}-B_{b})\otimes\Pi_{+}X_{w_{i}}\Pi_{+}.$
(9)

The self-energy expansion which describes the low-energy sector of the gadget
Hamiltonian $\tilde{H}=H+V$ becomes888For details see Section 2.

$\displaystyle\Sigma_{-}(z)=\underbrace{H_{\text{else}}}_{\text{$1^{\text{st}}$
order}}+\underbrace{\frac{1}{z-\Delta}R\beta^{2}(A_{a}-B_{b})^{2}}_{\text{$2^{\text{nd}}$
order}}+\underbrace{\sum_{m=1}^{\infty}V_{-+}G_{+}(V_{+}G_{+})^{m}V_{+-}}_{\text{error
term}}.$ (10)

Recall that $G(z)=(z\mathbb{I}-H)^{-1}$. The range of $z$ we consider is
$|z|\leq\|H_{\text{else}}\|+|\gamma|$. Assuming999For negative $\gamma$, we
replace the factor $(A_{a}-B_{b})$ in (5) with
$(A_{a}-\text{sgn}(\gamma)B_{b})$. $\gamma>0$ in $H_{\text{targ}}$, we can
choose

$\displaystyle\beta=\sqrt{\frac{\gamma\Delta}{2R}}=\sqrt{\frac{\gamma
JC}{2R}}.$ (11)

Since $z\ll\Delta$, we can write
$\frac{1}{z-\Delta}=-\frac{1}{\Delta}\left(1-\frac{z}{\Delta}\right)^{-1}\approx-\frac{1}{\Delta}+O\left(\frac{1}{\Delta^{2}}\right)$.
Then the $1^{\text{st}}$ and $2^{\text{nd}}$ order terms are approximately
equal to the desired effective Hamiltonian
$H_{\text{eff}}=H_{\text{targ}}\otimes\Pi_{-}$ up to an overall spectral shift
(because $A^{2}=B^{2}=\mathbb{I}$). We will show later, in Claim 2, that with
good choices of $R$ and $C$ we can make $\beta$ and $J$ as small as we want.

Figure 3: Parallel composition of $M$ (here $M=4$) two-body gadgets from
Figure 2(d), using a single common core with $C$ “core” ancillas. Each gadget
has $R$ “direct” ancillas interacting with the target spins. The total number
of ancillas is thus $MR+C$.

_Parallel 2-body gadgets._ So far, we have focused on a single 2-local term in
our target Hamiltonian (see Figure 2). Similarly to [2], we can apply our
gadgets _in parallel_ , which enables us to deal with a target Hamiltonian
with $M$ such 2-local terms. Let us then consider a target Hamiltonian of the
form

$H_{\text{targ}}=H_{\text{else}}+\sum_{j=1}^{M}\gamma_{j}A_{a_{j}}\otimes
B_{b_{j}}$ (12)

and apply our construction to every term $\gamma_{j}A_{a_{j}}\otimes
B_{b_{j}}$ in parallel, as in Figure 3. Note that we save a lot of resources
by using only a single core. Each target term $\gamma_{j}A_{a_{j}}\otimes
B_{b_{j}}$ is associated with $R$ direct ancilla qubits $w_{1}^{(i)}$,
$w_{2}^{(i)}$, $\cdots$, $w_{R}^{(i)}$ that are connected to target spins
$a_{i}$ and $b_{i}$. All of the direct ancillas also interact with each of the
$C$ core ancillas. As before, the core consists of $C$ qubits that are fully
connected with ferromagnetic (ZZ) interactions of strength $\frac{J}{2}$ and
also with local fields of strength $\frac{J}{2}$ on each qubit. Hence the full
gadget Hamiltonian for the general 2-local target Hamiltonian in (12) takes
the form $\tilde{H}=H+V$ with

$\displaystyle H$
$\displaystyle=\frac{J}{2}\sum_{j=1}^{M}\sum_{i=1}^{R}\sum_{c\in\mathcal{C}}(\mathbb{I}-Z_{w_{i}^{(j)}}Z_{c})+H_{\mathcal{C}},$
(13) $\displaystyle V$
$\displaystyle=H_{\text{else}}+\sum_{j=1}^{M}\beta_{j}\sum_{i=1}^{R}\left(A_{a_{j}}-B_{b_{j}}\right)\otimes
X_{w_{i}^{(j)}}.$

where $H_{\mathcal{C}}$ is the core Hamiltonian from (4),
$\beta_{j}=\sqrt{\frac{\gamma_{j}JC}{2R}}$ and the spectral gap between the
ground state and the first excited state of $H$ is $\Delta=JC$. Computing the
self-energy expansion as in (10) for the gadget Hamiltonian in (13) yields a
contribution
$-\frac{1}{z-\Delta}\sum_{j=1}^{M}\beta_{j}^{2}R(A_{a_{j}}-B_{b_{j}})^{2}$ at
the second order (see Claim 2 for more details). Because each term in the
perturbative expansion $\Sigma_{-}(z)$ corresponds to a sequence of state
transitions from $\mathcal{L}_{-}$ to $\mathcal{L}_{+}$ and back101010Note
that in fact $\mathcal{L}_{-}=\text{span}\\{|0\cdots 0\rangle_{w}|0\cdots
0\rangle_{\mathcal{C}}\\}$ where the subscript $w$ refers to all the ancillas
$w_{1}^{(j)}$, $w_{2}^{(j)}$, $\cdots$, $w_{R}^{(j)}$, for $j=1,2,\cdots,M$.
The transitions that contribute to the perturbative expansion $\Sigma_{-}(z)$
are restricted to only to the direct ancillas $|0\cdots 0\rangle_{w}$ since
the core ancillas do not interact with the target qubits., the second order
contribution comes from those transitions where one ancilla is flipped from
$|0\rangle$ to $|1\rangle$ and back to $|0\rangle$. Such transitions cannot
involve more than one ancilla qubit. Hence we can regard the second order
transitions involving different ancillas as occuring independently of each
other, or _in parallel_. This “parallelism” enables the 2-body gadgets to
capture multiple 2-local target terms. Let us now clarify the notions of
_parallel_ and _serial_ application of gadgets.

######  Remark 1.

(Parallel gadgets) Given a target Hamiltonian
$H_{\text{targ}}=H_{\text{else}}+\sum_{j=1}^{M}H_{\text{targ,$j$}}$ that is a
sum of multiple components $H_{\text{targ,$j$}}$, parallel application of
gadgets combines individual gadget constructions for each
$H_{\text{targ,$i$}}$ to form a gadget Hamiltonian $\tilde{H}$ such that its
low-lying spectrum captures that of $H_{\text{targ}}$.

######  Remark 2.

(Serial gadgets) Suppose some target Hamiltonian $H_{\text{targ}}$ is
approximated by a gadget Hamiltonian $\tilde{H}^{(1)}$ such that its low-lying
sector approximates the spectrum of $H_{\text{targ}}$. If one further replaces
some terms in $\tilde{H}^{(1)}$, creating another gadget Hamiltonian
$\tilde{H}^{(2)}$ whose low-lying spectrum captures the spectrum of
$\tilde{H}^{(1)}$, we say that the two gadgets are applied in series to reduce
$H_{\text{targ}}$ to $\tilde{H}^{(2)}$.

In order to show that the low-lying subspace of our gadget Hamiltonian
$\tilde{H}$ captures the spectrum of $H_{\text{targ}}$ using Theorem 3, it is
necessary to establish that $\tilde{H}$ meets both conditions of the theorem.
The first condition ($\tilde{\mathcal{L}}_{-}\cap\mathcal{L}_{+}=\varnothing$)
requires the perturbed low-energy subspace of the gadget Hamiltonian to be
disjoint from the unperturbed high-energy subspace. We will prove this as
Claim 1 below. The second condition says that the self-energy expansion
$\Sigma_{-}(z)$ can be approximated by an effective Hamiltonian when $z$ is in
a certain range. We establish this as Claim 2 for $\tilde{H}$ by proving that
the perturbation series converges for $\Sigma_{-}(z)$. Theorem 5 then follows
from Theorem 3 with $\tilde{H}$ being the Hamiltonian in (13).

###  3.1 The 2-local construction satisfies the subspace condition.

The first condition in Theorem 3 is a property of the high-energy subspace of
the original Hamiltonian. We need it in order to avoid the need to bound the
norm of the whole perturbation. Let us provide a high-level description of the
condition and the ideas behind its proof.

Consider the gadget Hamiltonian $\tilde{H}=H+V$ defined in (13). We need to
lower bound the lowest energy
$E_{+}=\min_{\psi}\langle\psi|\tilde{H}|\psi\rangle$ of a state $|\psi\rangle$
that comes from the subspace $\mathcal{L}_{+}$, the excited subspace of $H$,
spanned by states orthogonal to the state $|0\cdots 0\rangle_{w}$. The terms
in $H$ involve only ancilla qubits, while $V$ includes $H_{\text{else}}$, and
terms that couple some computational (target) qubit $a$ and a direct ancilla
$w$. These 2-local terms have form $\beta_{w}A_{a}\otimes X_{w}$, with
interaction strengths $\left|\beta_{w}\right|\leq\beta_{\text{max}}=O(1)$, as
in Figure 4(a). We now want to show that $E_{+}$ is strictly above
$\lambda_{*}=\frac{\Delta}{2}$. To do this, we lower bound $E_{+}$ using a
sequence of progressively simpler Hamiltonians, ending up with 1-local ones in
(19), (23) and (25).

Figure 4: A sequence of gadget Hamiltonians with progressively lower bounds on
$E_{+}$. (a) Taking the terms acting on the target spins to be all the same.
(b) Decoupling the target spins from the direct ancillas using $-\mathbb{I}$
operators on the target spins and (weighted) $X$-fields on the direct
ancillas. (c) Replacing the interactions with core ancillas by an overall
shift, and a (weighted) $Z$-field on the direct ancillas, arriving at (25).

Consider the following sequence of lower bounds (see Appendix B for a detailed
derivation). First, $E_{+}$ for the general Hamiltonian $\tilde{H}$ is greater
or equal to the value of $E_{+}$ for a similar system in which all of the
operators $A_{a}$ are the same (so that they do not compete against each other
in lowering the energy) as in Figure 4(a). Second, we can only lower $E_{+}$
by making all of the operators $A_{a}$ identities, and using only operators
$-\left|\beta_{w}\right|X_{w}$ on the direct ancillas. Because the target
spins are now independent from the ancillas, the contribution from
$H_{\text{else}}$ is then no larger in magnitude than
$\left\|H_{\text{else}}\right\|$. This is depicted in Figure 4(b).

We are now left with a Hamiltonian which is a sum of $H_{\text{else}}$,
single-qubit terms on the direct ancilla qubits, and their
interactions111111If the values of $\beta$ are different for different bonds,
we still use a single core with a fixed $J$, fixed $C$, fixed $\Delta=JC$, and
adjust each $\beta_{w}$ for each target interaction individually so that the
resulting effective interaction strength $\frac{\beta_{w}^{2}R}{\Delta}=O(1)$
is what we desire. with the core ancillas. The Hilbert space divides into a
direct sum of invariant subspaces labeled by the state of the core ancillas.
These subspaces are decoupled (the original Hamiltonian $H$ and the
perturbation $V$ do not flip the core ancillas), so we can analyze them one by
one. We do so for the subspaces with $a\geq 1$ core ancillas flipped to
$|1\rangle$, and then finally for the subspace with all core ancillas equal to
$|0\rangle$. It turns out that in each such subspace we can map the terms
$Z_{w}Z_{c},Z_{c}Z_{c^{\prime}},Z_{c}$ and $H_{\text{else}}$ of the
Hamiltonian121212Note that there is no direct $Z_{w}$ term on the direct
ancillas, so that a single direct ancilla flip increases the energy by
$\Delta=JC$. to one that is simply an overall shift, and a
$-\frac{\Delta_{a}}{2}Z_{w}$ term on each of the direct ancillas, with
$\Delta_{a}$ a function of how many ancillas were flipped. The resulting
1-local Hamiltonian illustrated in Figure 4(c) can be analyzed, and yields the
desired lower bound on $E_{+}$. Let us then state and prove our first Claim.

######  Claim 1.

Consider the 2-body gadget Hamiltonian $\tilde{H}=H+V$ from (13),
corresponding to a target Hamiltonian
$H_{\text{targ}}=H_{\text{else}}+\sum_{i=1}^{M}\gamma_{i}A_{i}\otimes B_{i}$
with $\gamma_{j}\leq O(1)$ and $H_{\text{else}}$ positive semi-definite. Let
$\Delta$ be the spectral gap between the ground and the first excited subspace
of $H$, and define a cutoff $\lambda_{*}=\Delta/2$. Following Section 2, we
define
$\mathcal{L}_{+}=\text{span}\\{|\psi\rangle:\langle\psi|H|\psi\rangle>\lambda_{*}\\}$
and
$\tilde{\mathcal{L}}_{-}=\text{span}\\{|\psi\rangle:\langle\psi|\tilde{H}|\psi\rangle<\lambda_{*}\\}$.
Then if $\Delta\geq 160M\gamma_{\text{max}}$, with
$\gamma_{\text{max}}=\max_{j=1,\cdots,M}|\gamma_{j}|$, we have

$\tilde{\mathcal{L}}_{-}\cap\mathcal{L}_{+}=\varnothing.$

To prove Claim 1, it suffices to show that if $|\psi\rangle\in\mathcal{L}_{+}$
then $\langle\psi|\tilde{H}|\psi\rangle>\lambda_{*}$ for any normalized state
$|\psi\rangle$. The subspace $\mathcal{L}_{+}$ is spanned by (direct + core)
ancilla qubit states with at least one $|1\rangle$. Let
$\mathcal{K}_{-}=|0\cdots 0\rangle_{w}$ be the all-zero state the direct
ancillas, and let
$\mathcal{S}_{a}=\text{span}\\{|x\rangle_{\mathcal{C}}:h(x)=a\\}$ be the
subspace of the core ancillas with exactly $a$ qubits131313Here $h(x)$ is the
Hamming weight of the binary string $x$. in the state $|1\rangle$. Thus, the
subspace $\mathcal{L}_{+}$ splits into two parts as
$\mathcal{L}_{+}=\mathcal{L}_{1}\oplus\mathcal{L}_{2}$, where141414Here
$\mathcal{H}_{w}$ is the Hilbert space of the direct ancillas.

$\displaystyle\mathcal{L}_{1}=\mathcal{H}_{w}\otimes\left(\bigoplus_{a=1}^{C}\mathcal{S}_{a}\right),\qquad\qquad\mathcal{L}_{2}=\mathcal{K}_{-}^{\perp}\otimes\mathcal{S}_{0}.$
(14)

The first part $\mathcal{L}_{1}$ spanned by all the states where the core has
at least one qubit $|1\rangle$, while the second part $\mathcal{L}_{2}$ is
spanned by all the states with the core ancillas all $|0\rangle$, and at least
one direct ancillas being $|1\rangle$. We now first show that
$\forall|\psi\rangle\in\mathcal{L}_{1}$,
$\langle\psi|\tilde{H}|\psi\rangle>\lambda_{*}$, and then similarly for
$\mathcal{L}_{2}$.

(1) _If $|\psi\rangle\in\mathcal{L}_{1}$, then
$\langle\psi|\tilde{H}|\psi\rangle>\lambda_{*}$._

Let us first consider
$|\psi_{a}\rangle\in\mathcal{H}_{w}\otimes\mathcal{S}_{a}$ for some fixed
$a\in\\{1,2,\cdots,C\\}$. Then $|\psi_{a}\rangle$ is a (linear combination of)
state(s) where $a$ ancillas in the core are $|1\rangle$ and the other $C-a$
core ancillas are $|0\rangle$. We will find a lower bound for
$\tilde{E}_{+,a}=\langle\psi_{a}|\tilde{H}|\psi_{a}\rangle$ by considering
each component of $\tilde{H}$. Recall from (3) the definition of the core
Hamiltonian

$H_{\mathcal{C}}=\frac{J}{2}\sum_{c\in\mathcal{C}}(\mathbb{I}-Z_{c})+\frac{J}{2}\sum_{c,c^{\prime}\in\mathcal{C}}(\mathbb{I}-Z_{c}Z_{c^{\prime}}).$
(15)

Then the energy of $|\psi_{a}\rangle$ with respect to the core Hamiltonian is
$E_{\mathcal{C},a}=\langle\psi_{a}|H_{\mathcal{C}}|\psi_{a}\rangle=Ja(C-a+1)\geq
JC$. Let

$\displaystyle
H_{w}=\frac{J}{2}\sum_{j=1}^{M}\sum_{i=1}^{R}\sum_{c\in\mathcal{C}}(\mathbb{I}-Z_{w_{i}^{(j)}}Z_{c})=\frac{J}{2}\sum_{j=1}^{M}\sum_{i=1}^{R}\left(C\mathbb{I}-Z_{w_{i}^{(j)}}\sum_{c\in\mathcal{C}}Z_{c}\right)$
(16)

be the interaction Hamiltonian between the direct ancillas and the core
ancillas. Recall from (13) that $H=H_{w}+H_{\mathcal{C}}$. The second equality
in (16) indicates that $H_{w}$ consists of a sum of terms of the form
$C\mathbb{I}-Z_{w_{i}^{(j)}}\sum_{c\in\mathcal{C}}Z_{c}$. Let us focus on such
a term for a particular direct ancilla $w$. Consider the states
$|0\rangle_{w}\otimes|a\rangle_{\mathcal{C}}$ and
$|1\rangle_{w}\otimes|a\rangle_{\mathcal{C}}$ with
$|a\rangle_{\mathcal{C}}\in\mathcal{S}_{a}$ and look at the term
$Z_{w}\sum_{c\in\mathcal{C}}Z_{c}$. Its expectation value in these states is
$C-2a$ and $2a-C$, regardless of the state of the core ancillas. Thus, we get
an effective Hamiltonian

$h^{\prime}_{w}=C\mathbb{I}-(C-2a)Z_{w}$ (17)

for each direct ancilla $w$. Collecting these effective Hamiltonians for each
direct ancilla, we get

$H^{\prime}_{w}=\frac{J}{2}\sum_{j=1}^{M}\sum_{i=1}^{R}h^{\prime}_{w_{i}^{(j)}}=\frac{J}{2}\sum_{k=1}^{N}h^{\prime}_{k},$
(18)

whose lowest energy in the subspace $\mathcal{H}_{w}\otimes\mathcal{S}_{a}$ is
equal to that of $H_{w}$. For convenience, we relabel the direct ancillas by
$k=1,\dots N$ with $N=MR$, and replace the sum over $i$ and $j$ with a single
index summation over $k$.

Let us now add the perturbation $V$ (13). For each direct ancilla $k$ there is
a term in $V$ of the form $v_{k}=\beta_{k}(A\otimes X_{k}-B\otimes
X_{k})=\beta_{k}O_{AB}\otimes X_{k}$. Since we assume that $A$ and $B$ are
unit-norm operators, the lowest energy of $v_{k}$ in
$\mathcal{H}_{k}\otimes\mathcal{S}_{a}$ is lower bounded by that of
$v^{\prime}_{k}=2\beta_{k}X_{k}$. Thus, when we label
$V^{\prime}=\sum_{k=1}^{N}v^{\prime}_{k}=\sum_{k=1}^{N}2\beta_{k}X_{k}$, we
get a 1-local Hamiltonian

$\begin{array}[]{ccl}\tilde{H}^{\prime}&=&\displaystyle
E_{\mathcal{C},a}\mathbb{I}+H^{\prime}_{w}+V^{\prime}=E_{\mathcal{C},a}\mathbb{I}+\sum_{k=1}^{N}\left(2\beta_{k}X_{k}+\frac{JC}{2}\mathbb{I}-\frac{J(C-2a)}{2}Z_{k}\right)\\\\[7.22743pt]
&=&\displaystyle\left(Ja(C-a+1)+\frac{JCN}{2}\right)\mathbb{I}+\sum_{k=1}^{N}\sqrt{4\beta_{k}^{2}+\frac{J^{2}}{4}(C-2a)^{2}}P_{k}\end{array}$
(19)

acting only on the direct ancillas, which gives us a lower bound on $E_{+}$,
i.e. for any $|\psi_{a}\rangle\in\mathcal{H}_{w}\otimes\mathcal{S}_{a}$,

$\min_{\mathcal{H}_{w}\otimes\mathcal{S}_{a}}\langle\psi_{a}|\tilde{H}|\psi_{a}\rangle\geq\min_{\mathcal{H}_{w}\otimes\mathcal{S}_{a}}\langle\psi_{a}|\tilde{H}^{\prime}|\psi_{a}\rangle,$
(20)

with $P_{k}$ a single qubit operator of the form
$\hat{p}\cdot\vec{\hat{\sigma}}$, with $\vec{\hat{\sigma}}=\\{X,Y,Z\\}$ and
unit vector $\hat{p}$. Note that the lower bound (20) does not include
$H_{else}$ in $\tilde{H}^{\prime}$; because $H_{\text{else}}\geq 0$, we are
only lowering the right side by omitting it.

Note that the above argument can be generalized to
$\mathcal{L}_{1}=\mathcal{H}_{w}\otimes(\oplus_{a=1}^{C}\mathcal{S}_{a})$. For
a general $|\psi\rangle\in\mathcal{L}_{1}$, $|\psi\rangle$ must take the form

$|\psi\rangle=|\phi\rangle_{w}\otimes\sum_{a=1}^{C}\eta_{a}|a\rangle_{\mathcal{C}},\qquad\text{where}\qquad|a\rangle=\sum_{h(x)=a}c_{a,x}|x\rangle,\quad
x\in\\{0,1\\}^{C}$ (21)

for some sets of complex coefficients $\\{\eta_{a}\\}$ and $\\{c_{a,x}\\}$
that are both normalized. Then
$\langle\psi|H_{\mathcal{C}}|\psi\rangle=\sum_{a=1}^{C}|\eta_{a}|^{2}Ja(C-a+1)$.
Let $\mathcal{A}$ be the set of $a$ for which $\eta_{a}\neq 0$. Let
$a_{\text{max}}$ be the value of $a$ in $\mathcal{A}$ that maximizes
$(C-2a)^{2}$. Define

$\begin{array}[]{ccl}|\psi^{\prime}\rangle&=&\displaystyle|\phi\rangle_{w}\otimes|a_{\text{max}}\rangle_{\mathcal{C}},\\\\[7.22743pt]
h^{\prime}_{w,a_{\text{max}}}&=&\displaystyle
C\mathbb{I}-(C-2a_{\text{max}})Z_{w},\\\\[7.22743pt]
H^{\prime}_{w,a_{\text{max}}}&=&\displaystyle\frac{J}{2}\sum_{k=1}^{N}h^{\prime}_{k}.\end{array}$
(22)

Then
$\langle\psi|H_{w}|\psi\rangle\geq\langle\psi_{a}|H^{\prime}_{w,a_{\text{max}}}|\psi_{a}\rangle$
for any $|\phi\rangle_{w}\in\mathcal{H}_{w}$. Since the generalization from
$\mathcal{H}_{w}\otimes\mathcal{S}_{a}$ to
$\mathcal{H}_{w}\otimes(\oplus_{a=1}^{C}\mathcal{S}_{a})$ does not concern the
direct ancillas, we can use the same argument as before to construct a 1-local
Hamiltonian

$\tilde{H}^{\prime}_{a_{\text{max}}}=\sum_{a=1}^{C}|\eta_{a}|^{2}\left(Ja(C-a+1)+\frac{JCN}{2}\right)\mathbb{I}+\sum_{k=1}^{N}\sqrt{4\beta_{k}^{2}+\frac{J^{2}}{4}(C-2a_{\text{max}})^{2}}P_{k,a_{\text{max}}}$
(23)

such that for any $|\psi_{a}\rangle\in\mathcal{L}_{1}$, there always exists a
value $a_{\text{max}}$ such that
$\min_{|\psi\rangle\in\mathcal{L}_{1}}\langle\psi|\tilde{H}|\psi\rangle\geq\min_{|\psi\rangle\in\mathcal{L}_{1}}\langle\psi|\tilde{H}^{\prime}_{a_{\text{max}}}|\psi\rangle$.

Let us now find a lower bound on
$\langle\psi|\tilde{H}^{\prime}_{a_{\text{max}}}|\psi\rangle$. Note that
$Ja(C-a+1)\geq JC$ for any $a=1,2,\cdots,C$. Let
$\beta_{\text{max}}=\max_{k=1,2,\cdots,N}|\beta_{k}|$. Noting that
$P_{k,a_{\text{max}}}$ in (23) is a unit-norm operator, for any
$|\psi\rangle\in\mathcal{L}_{1}$ we get

$\displaystyle\langle\psi|\tilde{H}^{\prime}_{a_{\text{max}}}|\psi\rangle$
$\displaystyle\geq\displaystyle\left(JC+\frac{JCN}{2}\right)-N\sqrt{4\beta_{\text{max}}^{2}+\frac{J^{2}}{4}(C-2a_{\text{max}})^{2}}$
$\displaystyle=JC+\frac{JCN}{2}-\frac{JCN}{2}\sqrt{1+\frac{16\beta_{\text{max}}^{2}}{J^{2}C^{2}}}$
$\displaystyle\geq
JC-\frac{JCN}{2}\cdot\frac{16\beta_{\text{max}}^{2}}{2J^{2}C^{2}}=JC-\frac{4N\beta_{\text{max}}^{2}}{JC}$
$\displaystyle=\Delta-\frac{4MR\beta_{\text{max}}^{2}}{\Delta}\geq\frac{79\Delta}{80}>\frac{\Delta}{2}=\lambda_{*},$
(24)

where we have used $2R\beta^{2}_{\text{max}}/\Delta=\gamma_{\text{max}}$ from
(11) and asked for $\Delta\geq 160M\gamma_{\text{max}}$ in the last line. Here
$\gamma_{\text{max}}=\max_{j=1,\cdots,M}|\gamma_{j}|$ where $\gamma_{j}$ are
coefficients in the target Hamiltonian. Putting (24) into (20), we get
$E_{+}>\frac{\Delta}{2}=\lambda_{*}$. We have thus shown the desired lower
bound on $E_{+}$ in the subspace $\mathcal{L}_{1}$. Let us now deal with the
other part, $\mathcal{L}_{2}$.

(2) _If $|\psi\rangle\in\mathcal{L}_{2}$, then
$\langle\psi|\tilde{H}|\psi\rangle>\lambda_{*}$._

Any state in the subspace
$\mathcal{L}_{2}=\mathcal{K}_{-}^{\perp}\otimes\mathcal{S}_{0}$ has the core
ancillas in the state $|0\cdots 0\rangle_{\mathcal{C}}$, hence
$\langle\psi|H_{\mathcal{C}}|\psi\rangle=0$. To find a lower bound for the
energy of $H_{w}$ in this subspace, we use the construction $H^{\prime}_{w}$
in (18) with $a=0$. For the energy of $V$ we use the same simplifying argument
and obtain (again) a 1-local Hamiltonian acting only on the direct ancillas
(cf. Equation 19)

$\displaystyle\tilde{H}^{\prime}_{0}=\sum_{k=1}^{N}\left(\frac{\Delta}{2}\mathbb{I}-\frac{\Delta}{2}Z_{k}-2\beta_{k}X_{k}\right)=\sum_{k=1}^{N}S_{k},$
(25)

such that

$\min_{|\psi\rangle\in\mathcal{L}_{2}}\langle\psi|\tilde{H}|\psi\rangle\geq\min_{|\psi\rangle\in\mathcal{L}_{2}}\langle\psi|\tilde{H}^{\prime}_{0}|\psi\rangle.$
(26)

We now show that the energy of any direct ancilla state orthogonal to
$\mathcal{K}_{-}=\text{span}\\{|0\dots 0\rangle_{w}\\}$ is strictly lower
bounded by $\lambda_{*}=\Delta/2$. Since the core ancilla state will always be
$|0\cdots 0\rangle_{\mathcal{C}}$, we will exclude it from our discussion and
thus omit the $w$ subscript for the direct ancilla. All quantum states in the
proof from here on refer to the state of the direct ancillas.

To show the energy lower bound we use induction on the number of direct
ancillas, $n$. Let

$E_{n}=\min_{|\phi\rangle\perp|0\rangle^{\otimes
n}}\langle\phi|\sum_{k=1}^{n}S_{k}|\phi\rangle.$ (27)

Specifically, we prove the following statement:

$\displaystyle
E_{n}\geq\frac{3\Delta}{4}-\delta_{n},\qquad\textrm{with}\qquad\delta_{n}=\frac{40n\beta^{2}}{9\Delta},\qquad
n=1,\cdots,N.$ (28)

We start with the initial case $n=1$. There the only state orthogonal to
$|0\rangle$ is $|1\rangle$. Hence $E_{1}=\Delta$, which satisfies (28). Now
assume (28) holds for some $n$. An $(n+1)$-qubit state that is orthogonal to
$|0\cdots 0\rangle$ (denoted by the superscript ø) must have the form

$\displaystyle|\psi^{\text{\text{\o}}}_{n+1}\rangle=a|\xi^{\text{\text{\o}}}_{n}\rangle|0\rangle+b|\phi^{\text{\text{\o}}}_{n}\rangle|1\rangle+c|0\cdots
0\rangle|1\rangle,$ (29)

where $|\xi^{\text{\text{\o}}}_{n}\rangle$ and
$|\phi^{\text{\text{\o}}}_{n}\rangle$ are some states that are orthogonal to
$|0\cdots 0\rangle$. Let us calculate the energy of the state (29).

$\displaystyle E_{n+1}$
$\displaystyle=\sum_{i=1}^{n}\langle\psi^{\o}_{n+1}|S_{i}|\psi^{\o}_{n+1}\rangle+\langle\psi^{\o}_{n+1}|S_{n+1}|\psi^{\o}_{n+1}\rangle$
(30)
$\displaystyle=|a|^{2}\sum_{i=1}^{n}\langle\xi^{\text{\text{\o}}}_{n}|S_{i}|\xi^{\text{\o}}_{n}\rangle\langle
0|0\rangle+|b|^{2}\sum_{i=1}^{n}\langle\phi^{\text{\text{\o}}}_{n}|S_{i}|\phi^{\text{\o}}_{n}\rangle\langle
1|1\rangle+|c|^{2}\sum_{i=1}^{n}\langle 0\cdots 0|S_{i}|0\cdots
0\rangle\langle 0|0\rangle$ (31)
$\displaystyle+2\textrm{Re}\left(ab^{*}\sum_{i=1}^{n}\langle\xi^{\text{\text{\o}}}_{n}|S_{i}|\phi^{\text{\o}}_{n}\rangle\langle
0|1\rangle+ac^{*}\sum_{i=1}^{n}\langle\xi^{\text{\o}}_{n}|S_{i}|0\cdots
0\rangle\langle
0|1\rangle+bc^{*}\sum_{i=1}^{n}\langle\phi^{\text{\o}}_{n}|S_{i}|0\cdots
0\rangle\langle 1|1\rangle\right)$ $\displaystyle+|a|^{2}\langle
0|S|0\rangle_{n+1}+|b|^{2}\langle 1|S|1\rangle_{n+1}+|c|^{2}\langle
1|S|1\rangle_{n+1}$
$\displaystyle+2\textrm{Re}\left(ab^{*}\langle\xi^{\text{\o}}_{n}|\phi^{\text{\o}}_{n}\rangle\langle
0|S|1\rangle+ac^{*}\langle\xi^{\text{\o}}_{n}|0\cdots 0\rangle\langle
0|S|1\rangle+bc^{*}\langle\phi^{\text{\o}}_{n}|0\cdots 0\rangle\langle
1|S|1\rangle\right).$

Note that $\langle 0|1\rangle=0$ and $\langle\psi_{n}^{\text{\o}}|0\cdots
0\rangle=\langle\phi_{n}^{\text{\o}}|0\cdots 0\rangle=0$. Also recall that
$\langle 0|S_{i}|0\rangle=0$, $\langle 1|S_{i}|1\rangle=\Delta$ and $\langle
0|S_{i}|1\rangle=-2\beta_{i}$. Hence,

$\displaystyle E_{n+1}$
$\displaystyle=|a|^{2}\sum_{i=1}^{n}\langle\xi^{\text{\o}}_{n}|S_{i}|\xi^{\text{\o}}_{n}\rangle+|b|^{2}\sum_{i=1}^{n}\langle\phi^{\text{\o}}_{n}|S_{i}|\phi^{\text{\o}}_{n}\rangle+0+0+0+2\textrm{Re}\left(bc^{*}\sum_{i=1}^{n}\langle\phi^{\text{\o}}_{n}|S_{i}|0\cdots
0\rangle\right)$ (32)
$\displaystyle+0+|b|^{2}\Delta+|c|^{2}\Delta+2\textrm{Re}\left(-ab^{*}\langle\xi^{\text{\o}}_{n}|\phi^{\text{\o}}_{n}\rangle
2\beta_{n+1}\right)+0+0$
$\displaystyle\geq|a|^{2}E_{n}+|b|^{2}E_{n}+2\textrm{Re}\left(bc^{*}\sum_{i=1}^{n}\langle\phi^{\text{\o}}_{n}|S_{i}|0\cdots
0\rangle\right)+|b|^{2}\Delta+|c|^{2}\Delta-4|a||b|\beta_{\text{max}},$ (33)

where we lower bounded the last term using absolute values, a maximum
magnitude of the $\beta$’s, and
$\left|\langle\psi^{\text{\o}}_{n}|\phi_{n}^{\text{\o}}\rangle\right|\leq 1$.
Next, we observe that the term $\langle\phi^{\text{\o}}_{n}|S_{i}|0\cdots
0\rangle_{n}$ is nonzero only for parts of $|\phi^{\text{\o}}_{n}\rangle$ with
a single $|1\rangle$. The largest magnitude it could possibly have is when the
state $|\phi^{\text{\o}}_{n}\rangle$ is made only from states with a single
$|1\rangle$ as $\frac{1}{\sqrt{n}}\sum_{i=1}^{n}|0\cdots 1_{i}\cdots
0\rangle$. We then get
$\sum_{i=1}^{n}\langle\phi^{\text{\o}}_{n}|S_{i}|0\cdots
0\rangle\geq-2\beta_{\text{max}}\sqrt{n}$. Putting this in, recalling (28) and
using absolute values, we get

$\displaystyle E_{n+1}$
$\displaystyle\geq\left(|a|^{2}+|b|^{2}\right)\left(\frac{3\Delta}{4}-\delta_{n}\right)-|b||c|\cdot
4\beta_{\text{max}}\sqrt{n}+\left(|b|^{2}+|c|^{2}\right)\Delta-|a||b|\cdot
4\beta_{\text{max}}$ (34)
$\displaystyle=\frac{3\Delta}{4}\left(|a|^{2}+|b|^{2}+|c|^{2}\right)-\left(|a|^{2}+|b|^{2}\right)\delta_{n}+|b|^{2}\Delta-|a||b|\cdot
4\beta_{\text{max}}-|b||c|\cdot
4\beta_{\text{max}}\sqrt{n}+|c|^{2}\cdot\frac{\Delta}{4}$
$\displaystyle\geq\frac{3\Delta}{4}-\delta_{n}+|b|^{2}\Delta-|b|\cdot
4\beta_{\text{max}}+\underbrace{|c|\left(|c|\frac{\Delta}{4}-|b|\cdot
4\beta_{\text{max}}\sqrt{n}\right)}_{f(|c|)},$ (35)

where we have used (28), and then $|a|^{2}+|b|^{2}\leq 1$ and $|a|\leq 1$.
Independent of $|b|$, let us look at $f(|c|)$, a quadratic function of $|c|$.
Its minimum is at $|c|=\frac{|b|\cdot 8\beta_{\text{max}}\sqrt{n}}{\Delta}$,
with the value $f_{\text{min}}=-\frac{|b|^{2}\cdot
16n\beta_{\text{max}}^{2}}{\Delta}$. In (35) it means

$\displaystyle E_{n+1}$
$\displaystyle\geq\frac{3\Delta}{4}-\delta_{n}+|b|^{2}\Delta-|b|\cdot
4\beta_{\text{max}}-\frac{16|b|^{2}n\beta_{\text{max}}^{2}}{\Delta}$ (36)
$\displaystyle=\frac{3\Delta}{4}-\delta_{n}+|b|^{2}\underbrace{\left(\Delta-\frac{16n\beta_{\text{max}}^{2}}{\Delta}\right)}_{\geq
9\Delta/10}-|b|\cdot 4\beta_{\text{max}}$ (37)
$\displaystyle\geq\frac{3\Delta}{4}-\delta_{n}+\underbrace{|b|\left(|b|\frac{9\Delta}{10}-4\beta_{\text{max}}\right)}_{g(|b|)},$
(38)

where in the second line we have used $\Delta\geq 160M\gamma_{\text{max}}$ to
guarantee
$\Delta-\frac{16\beta_{\text{max}}^{2}n}{\Delta}\geq\Delta-\frac{16\beta_{\text{max}}^{2}N}{\Delta}=\Delta-16M\gamma_{\text{max}}\geq\frac{9\Delta}{10}$.
The expression $g(|b|)$ is quadratic in $|b|$, minimized at
$|b|=\frac{20\beta_{\text{max}}}{9\Delta}$, giving the value
$g_{\text{min}}=-\frac{40\beta_{\text{max}}^{2}}{9\Delta}$. Putting it into
(38), we get

$\displaystyle E_{n+1}$
$\displaystyle\geq\frac{3\Delta}{4}-\delta_{n}-\frac{40\beta_{\text{max}}^{2}}{9\Delta}=\frac{3\Delta}{4}-\delta_{n+1},$
(39)

which proves our induction step, as
$\delta_{n}=\frac{40n\beta_{\text{max}}^{2}}{9\Delta}$. Therefore, (28) holds.
Let $n=N$ and we have for any $|\psi\rangle\in\mathcal{L}_{2}$,

$\displaystyle\langle\psi|\tilde{H}^{\prime}_{0}|\psi\rangle\geq E_{N}$
$\displaystyle\geq\frac{3\Delta}{4}-\frac{40N\beta_{\text{max}}^{2}}{9\Delta}=\frac{3\Delta}{4}-\frac{40MR\beta_{\text{max}}^{2}}{9\Delta}$
$\displaystyle=\frac{3\Delta}{4}-\frac{20M\gamma_{\text{max}}}{9}\geq\left(\frac{3}{4}-\frac{1}{72}\right)\Delta=\frac{53}{72}\Delta>\frac{\Delta}{2}=\lambda_{*},$
(40)

where in the last line we have used (11) and $\Delta\geq
160M\gamma_{\text{max}}$. Combining the above statement with (26), we have
$\langle\psi|\tilde{H}|\psi\rangle>\lambda_{*}$ for any
$|\psi\rangle\in\mathcal{L}_{2}$. This concludes the proof of Claim 1.

$\Box$

###  3.2 The perturbation series converges.

Let us now state and prove our second claim – the convergence of the
perturbation series for our gadget construction.

######  Claim 2.

Consider the 2-body gadget Hamiltonian $\tilde{H}=H+V$ defined in (13) with
spectral gap $\Delta$ between the ground and the first excited subspace of
$H$, and a target Hamiltonian
$H_{\text{targ}}=H_{\text{else}}+\sum_{j=1}^{M}\gamma_{j}A_{j}\otimes B_{j}$
with $\gamma_{j}=O(1)$ and $H_{\text{else}}$ positive semi-definite. Choose a
constant parameter $d\in(0,1)$ and an error tolerance $\epsilon$. If we set
$\Delta=M^{3}R^{d}$ and choose the number of direct ancillas per target term
$R$ and the core size $C$ according to

$\displaystyle R$
$\displaystyle\gg\max\left\\{\epsilon^{-\frac{2}{d}},\left(\frac{\|H_{\text{else}}\|^{2}}{2M^{4}\gamma_{\text{max}}}\right)^{\frac{1}{d}},\left(M^{3}\epsilon^{-2}\right)^{\frac{1}{1-d}}\right\\},\qquad
C\gg M^{3}R^{d}\,\epsilon^{-1},$ (41)

then the strengths of the interaction terms in the gadget Hamiltonian are
small, i.e. $\beta_{j},J=O(\epsilon)$.

Furthermore, the self energy expansion (2) satisfies

$\|\Sigma_{-}(z)-H_{\text{targ}}\otimes\Pi_{-}\|=O(\epsilon),$ (42)

where $\Pi_{-}$ is the projector onto $\mathcal{L}_{-}$, and $z$ obeys
$|z|\leq\epsilon+\|H_{\text{else}}\|+\sum_{j=1}^{M}|\gamma_{j}|$.

This claim is one of the central results of this work – it shows that our
gadget Hamiltonian (for a 2-local target Hamiltonian) uses only interactions
of strength $O(\epsilon)$, _i.e._ no strong interactions. This is
qualitatively different from previous constructions which require interactions
of strength poly$(\epsilon^{-1})$. However, the price we pay for avoiding
strong interactions is that the number of ancillas scales as
poly$(\epsilon^{-1})$, as shown in (41), while previous constructions require
some number of ancillas independent of $\epsilon$. Hence we present a tradeoff
between interaction strength and ancilla number in a gadget Hamiltonian.

Let us prove Claim 2. First we show that $\tilde{H}$ consists of only weak
interaction terms. When we choose $\Delta=M^{3}R^{d}$ for some $d\in(0,1)$ and
substitute it into (11), we find that the interaction strength between the
target spins and direct ancillas will be
$\beta_{j}=\sqrt{\frac{\gamma_{j}\Delta}{2R}}=O(\epsilon)$, if we choose

$\displaystyle R\gg\left(M^{3}\epsilon^{-2}\right)^{\frac{1}{1-d}}.$ (43)

Next, recalling $\Delta=CJ$, the strength of the interaction $J$ between the
core ancillas will be $O(\epsilon)$ if we choose $C\gg
M^{3}R^{d}\,\epsilon^{-1}$.

Furthermore, once we set $\Delta=M^{3}R^{d}$, we can easily satisfy the
requirement $\Delta\geq 160M\gamma_{\max}$ in Claim 1 for reasonable $R$ –
more specifically, we need
$R\gg\left(160\gamma_{\text{max}}/M^{2}\right)^{1/d}$.

We will now analyze the higher order terms in the self energy expansion
$\Sigma_{-}(z)$ according to (2) and show that the error term in Equation 2
scales as $O(\epsilon)$. The perturbative expansion of $\Sigma_{-}(z)$ for the
construction in (13) yields

$\displaystyle\Sigma_{-}(z)=H_{\text{else}}+\frac{1}{z-\Delta}\sum_{j=1}^{M}R\beta_{j}^{2}(A_{a_{j}}-B_{b_{j}})^{2}+\underbrace{\sum_{k=1}^{\infty}V_{-+}\left(G_{+}V_{+}\right)^{k}G_{+}V_{+-}}_{\text{error}}.$
(44)

We can associate every term in the perturbation series with a transition
process starting in the ancilla state $|0\rangle_{w}|0\rangle_{\mathcal{C}}$
(i.e. belonging to $\mathcal{L}_{-}$) to states in $\mathcal{L}_{+}$ and back
to $\mathcal{L}_{-}$. Specifically, at the $k$-th order, such transitions are

$\displaystyle\mathcal{L}_{-}\xrightarrow{V_{-+}}|y\rangle\underbrace{\xrightarrow{V_{+}}|y_{1}\rangle\xrightarrow{V_{+}}|y_{2}\rangle\xrightarrow{V_{+}}\cdots\xrightarrow{V_{+}}|y_{k-2}\rangle\xrightarrow{V_{+}}}_{\text{$(k-2)$
steps}}|y^{\prime}\rangle\xrightarrow{V_{+-}}\mathcal{L}_{-},$ (45)

where both $y$ and $y^{\prime}$ are $r$-bit strings with Hamming weight 1, and
$|y_{i}\rangle\in\mathcal{L}_{+}$. Specifically, they belong to the subspace
$\mathcal{L}_{2}=\mathcal{K}_{-}^{\perp}\otimes\mathcal{S}_{0}$ in (14). In a
transition, the $V_{+}$ component of the perturbation $V$ either flips a
direct qubit $w$ or leaves it unchanged. In the former case, $V_{+}$
contributes terms that contain the interaction with $w$ via $\dots\otimes
X_{w}$. In the latter case, $V_{+}$ contributes terms that contain interaction
with $w$ via $\dots\otimes|1\rangle\langle 1|_{w}$. In general, out of the
$k-2$ transitions, the number of flips $k_{f}$ cannot exceed $k$. Furthermore,
it must be even for the transition to terminate in $\mathcal{L}_{-}$. Every
transition step $|y_{i}\rangle\rightarrow|y_{i+1}\rangle$ also contributes a
factor $\frac{1}{z-h(y_{i})\Delta}$ to the corresponding term in the expansion
$\Sigma_{-}(z)$, where $h(y_{i})$ is the Hamming weight of the string $y_{i}$.

####  3.2.1 A simplified calculation without $H_{\text{else}}$

Figure 5: Upper bounding the contributions to the error term at order $2k$ for
a 2-body gadget without $H_{else}$. Each up- and right-moving path corresponds
to a sequence of flips on the direct ancillas. We are overcounting here,
allowing paths that touch the diagonal, as well as paths that wander farther
than $N$ from the diagonal when $k>N$.

To bound the norm of the error, let us start by considering the simplified
case where $\|H_{\text{else}}\|=0$. The general calculation is presented below
in Section 3.2.2.

In this simpler case, we have $\|V_{+}\|=0$ and all terms at odd orders vanish
since $k_{f}$ must be even. Let $T_{k}=V_{-+}(G_{+}V_{+})^{k-2}G_{+}V_{+-}$ be
the $k$-th order term in $\Sigma_{-}(z)$. In Appendix A, the reader can find
the upper bound calculations for the first few terms of $\Sigma_{-}(z)$ as
examples. Here, let us present the general even-order calculation.

Finding an upper bound for $\|T_{2k}\|$ for $k\geq 1$ amounts to enumerating
all possible transitions and computing their respective contributions. For
this, we introduce a graphical representation of the $(2k)^{\text{th}}$ order
transitions in Figure 5. Each grid point in the lower-right triangle,
including the diagonal points, corresponds to a state of the direct ancillas.
We start from the lower-leftmost point, which corresponds to the all-zero
subspace $\mathcal{L}_{-}$. Each step of the transition maps to a rightwards
or upwards movement on the graph. A valid transition process ends at the top-
rightmost point, which again belongs to the ground state subspace
$\mathcal{L}_{-}$. Furthermore, a valid path can touch the diagonal line only
at the last step of the transition. Suppose at a certain point the direct
ancillas are in a state $|y\rangle$ with $h(y)$ ancillas in $|1\rangle$ and
the rest in $|0\rangle$, with $h(y)\in\\{1,2,\cdots,N\\}$ being the Hamming
weight of $y$. Then the next step will take $|y\rangle$ to a new state
$|y^{\prime}\rangle$ where $y$ and $y^{\prime}$ differ by one bit. If an
ancilla in $|y\rangle$ is flipped from $|0\rangle$ to $|1\rangle$ then we move
to the right on the graph. If an ancilla is flipped from $|1\rangle$ to
$|0\rangle$, we move up.

Since each _fixed_ path in the graph only records the change in the number of
the direct ancillas that are in the state $|1\rangle$, our graphical
representation is oblivious to the _order_ in which each of the direct
ancillas are flipped. For a given path, we overcount the number of ways the
ancillas were flipped ($|0\rangle\rightarrow|1\rangle$, horizontal lines in
Figure 5), using $N^{k}$ – the number of ways to draw $k$ out of $N$ objects
_with replacement_. Next, we bound the contribution from $G_{+}$ by
$\|G_{+}\|\leq\frac{1}{|h(y)\Delta-z|}\leq\frac{1}{\Delta}$ where $h(y)$ is
the Hamming weight of the state $|y\rangle$ in which a particular flip step
starts. For each $|1\rangle\rightarrow|0\rangle$ flip (vertical line in Figure
5) that brings $|y\rangle$ to $|y^{\prime}\rangle$, the resolvent $G_{+}$
contributes a factor $\frac{1}{z-h(y)\Delta}$. Furthermore, there are in total
$h(y)$ different choices of which ancilla to unflip at this point, which gives
us a factor $h(y)$ that “cancels”151515Here “cancel” means that the product
$\frac{h(y)}{|h(y)\Delta-z|}$ is $O(\Delta^{-1})$. the factor $h(y)$ in
$\frac{1}{z-h(y)\Delta}$ from the resolvent. Therefore, the contribution of a
path in Figure 5 to $\|T_{2k}\|$ is at most

$c_{\text{path}}\leq\frac{N^{k}(2\beta_{\text{max}})^{2k}}{\Delta^{2k-1}}.$
(46)

We can upper bound the number of valid paths such as the one shown in Figure 5
by the $k^{\text{th}}$ Catalan number – the number of up- & right-moving paths
between corners of a square that don’t pass beyond the diagonal. Besides all
the valid paths that contribute non-trivially to $\|T_{2k}\|$, the Catalan
number $C_{k}$ also counts paths that are illegal for us – those that touch
the diagonal at places other than the start and finish points, and paths that
possibly move farther than $N$ from the diagonal (for large $k$). In this way,
we get the upper bound161616The Catalan number $C_{k}$ is trivially upper
bounded by $4^{k}$, the number of possibilities for a $2k$-step process with 2
choices at each step.

$\|T_{2k}\|\leq C_{k}\cdot c_{\text{path}}\leq
4^{k}\cdot\frac{N^{k}(2\beta_{\text{max}})^{2k}}{\Delta^{2k-1}}=8^{k}\Delta\left(\frac{N\cdot
2\beta_{\text{max}}^{2}}{\Delta}\right)^{k}\frac{1}{\Delta^{k}}=\Delta\left(\frac{8M\gamma_{\text{max}}}{\Delta}\right)^{k},$
(47)

using (11). Note that this is small for $k\geq 2$, as $\Delta\gg M$. Thus, the
error term $\|T_{2k}\|$ for a model without $H_{\text{else}}$ decays
exponentially with $k$, and the series $\sum_{k=1}^{\infty}\|T_{2k}\|$
converges. Moreover, because we can choose $\Delta\gg M$, it can be upper
bounded by a small number.

####  3.2.2 A general calculation including $H_{\text{else}}$

Now we turn to the general case where $\|H_{\text{else}}\|\neq 0$. In this
scenario, each term in $T_{m}=V_{-+}(G_{+}V_{+})^{m-2}G_{+}V_{+-}$ is composed
from transitions of the following three types

  1. 1.

a $|0\rangle\rightarrow|1\rangle$ flip of some direct ancilla qubit $w$,

  2. 2.

a $|1\rangle\rightarrow|0\rangle$ flip of some $w$,

  3. 3.

the state of the ancillas staying the same.

In the first two cases, $V_{+}$ (also $V_{-+}$ or $V_{+-}$) contributes the
term from $V$ that flips the direct ancilla $w$ via $\dots\otimes X_{w}$. In
the third case, the ancilla state stays the same, and $V_{+}$ brings us the
factor $H_{\text{else}}$.

Figure 6: Upper bounding the contributions to the error term of order $2k$ or
$2k+1$. Up- and right-moving, subdiagonal paths correspond to sequences of
flips of direct ancillas. A bit flip moves 2 squares horizontally/vertically,
“staying” moves across one square diagonally.

We modify our graphic approach from Figure 5 to include the valid third type
of transitions, corresponding to non-trivial terms in the expansion of
$\Sigma_{-}(z)$. This approach is illustrated in Figure 6. For a fixed $k$,
the number of $2k$-step (resp. $(2k+1)$-step) transitions is now upper bounded
by the _Motzkin number_ of order $2k$ (resp. $2k+1$). These numbers correspond
to a number of up-, diagonal-, and right-moving paths across a square,
remaining below the diagonal. Just as we easily upper bounded the Catalan
numbers, it suffices for our purposes to upper bound the Motzkin numbers by
$M_{2k}\leq 3^{2k}$ and $M_{2k+1}\leq 3\cdot 3^{2k}$.

_Upper bounds on the $(2k)^{\text{th}}$ order._ In estimating the error, we
here consider only the $4^{\text{th}}$ order and onward, i.e. $k\geq 2$, as
the second order is the actual term that we want to generate (for details of
the 2nd order, see Appendix A).

In order to make sure that the sequence of transitions finishes at
$\mathcal{L}_{-}$, the number of flips $k_{f}=2f$ must be even
($f\in\mathbb{N}$, $f\leq k$). Hence, the number of steps where the ancilla
state stays the same is $2(k-f)$, an even number. A contribution from some
path to $\Sigma_{-}(z)$ is a term whose norm is upper bounded by

$\displaystyle\leq\frac{\overbrace{N(2\beta_{\text{max}})^{2}\times\dots\times
N(2\beta_{\text{max}})^{2}}^{f}\times\overbrace{\left\|H_{\text{else}}\right\|^{2}\times\dots\times\left\|H_{\text{else}}\right\|^{2}}^{k-f}}{\Delta^{2k-1}}.$
(48)

The condition
$R\geq\left(\frac{\|H_{\text{else}}\|^{2}}{2M^{4}\gamma_{\text{max}}}\right)^{\frac{1}{d}}$
from (41) implies

$\displaystyle\|H_{\text{else}}\|^{2}\leq
2M^{4}R^{d}\gamma_{\text{max}}=4MR\frac{\Delta\gamma_{\text{max}}}{2R}=N\left(2\beta_{\text{max}}\right)^{2}.$
(49)

Therefore, the overall contribution of a path (48) is further upper bounded by

$\displaystyle\leq\left(\frac{N(2\beta_{\text{max}})^{2}}{\Delta}\right)^{k}\frac{1}{\Delta^{k-1}}=2^{k}\left(M\gamma_{\text{max}}\right)^{k}\frac{1}{\Delta^{k-1}}=\Delta\left(\frac{2M\gamma_{\text{max}}}{\Delta}\right)^{k}.$
(50)

The number of paths is upper bounded by $9^{k}$. Therefore, the overall norm
of the $(2k)^{\text{th}}$ order is upper bounded by

$\displaystyle\left\|T_{2k}\right\|$ $\displaystyle\leq
9^{k}\Delta\left(\frac{2M\gamma_{\text{max}}}{\Delta}\right)^{k}=\Delta\left(\frac{18M\gamma_{\text{max}}}{\Delta}\right)^{k}.$
(51)

We have chosen $\Delta\gg M$, so this is again a small contribution. Note also
the similarity between the form of the upper bound in the above result and
(47).

_Upper bounds on the $(2k+1)^{\text{th}}$ order._ Bounding the $3^{\text{rd}}$
order is straightforward:

$\displaystyle\|T_{3}\|=N\cdot(2\beta_{\text{max}})\cdot\frac{1}{\Delta}\cdot\|H_{\text{else}}\|\cdot\frac{1}{\Delta}\cdot(2\beta_{\text{max}})\leq\frac{\left(4N\beta_{\text{max}}^{2}\right)^{\frac{3}{2}}}{\Delta^{2}}=\sqrt{\frac{\left(2M\gamma_{\text{max}}\right)^{3}}{\Delta}},$
(52)

using (11). Recalling $\Delta=M^{3}R^{d}$, we thus get
$\|T_{3}\|\leq(2\gamma_{\text{max}})^{3/2}R^{-d/2}=O\left(R^{-d/2}\right)$, a
small contribution.

Similarly as above, we then calculate this for the $(2k+1)^{\text{st}}$ order
in general and obtain

$\displaystyle\|T_{2k+1}\|$ $\displaystyle\leq 3\cdot
9^{k}\cdot\frac{[N(2\beta_{\text{max}})^{2}]^{f}\cdot\|H_{\text{else}}\|^{2(k-f)+1}}{\Delta^{2k}}\leq
3\cdot
9^{k}\cdot\frac{[N(2\beta_{\text{max}})^{2}]^{k+\frac{1}{2}}}{\Delta^{2k}}$
$\displaystyle\leq 3\cdot 2^{k}\cdot
9^{k}\cdot\left(\frac{M\gamma_{\text{max}}}{\Delta}\right)^{k}\sqrt{2M\gamma_{\text{max}}\Delta}=\left(3\sqrt{2}\right)\Delta\left(\frac{18M\gamma_{\text{max}}}{\Delta}\
\right)^{k+\frac{1}{2}}$ (53)

Comparing with (52), we find that the last expression is also true for $k=1$.
Therefore, using also (51) we can bound all of the terms in the error series
by

$\displaystyle\left\|T_{m}\right\|$ $\displaystyle\leq
3\sqrt{2}\,\Delta\left(\frac{18M\gamma_{\text{max}}}{\Delta}\right)^{\frac{m}{2}}=3\sqrt{2}\Delta
q^{m},$ (54)

for $m\geq 3$ with
$q=\sqrt{18M\gamma_{\text{max}}/\Delta}=O\left(M^{-1}R^{-\frac{d}{2}}\right)$.
Thus, the whole series $\sum_{m=3}^{\infty}\left\|T_{m}\right\|$ is upper
bounded by a geometric series that converges. We can upper bound it by

$\displaystyle\sum_{m=3}^{\infty}\left\|T_{m}\right\|\leq const.\times\Delta
q^{3}=O\left(R^{-\frac{d}{2}}\right)\leq\epsilon,$ (55)

for our choice of $\epsilon$ when we choose a suitably large
$R\gg\epsilon^{-\frac{2}{d}}$. This concludes the proof of Claim 2.

$\Box$

In conclusion, in Equation 10 we have
$\|\Sigma_{-}(z)-H_{\text{eff}}\|=O(\epsilon)$ where the effective Hamiltonian
$H_{\text{eff}}=H_{\text{targ}}\otimes\Pi_{-}+\gamma\Pi_{-}$ (up to an overall
shift) captures the target Hamiltonian. Therefore we have proven Theorem 5.
Let us have a last look at the resources we require for Theorem 5 with the
following remark.

######  Remark 3.

If $H_{\text{targ}}$ acts on $n$ qubits, our gadget hamiltonian $\tilde{H}$
acts on

$\displaystyle n+MR+C$ $\displaystyle\gg n+MR+M^{3}R^{d}\,\epsilon^{-1}$ (56)
$\displaystyle\gg
n+\max\left\\{M\epsilon^{-\frac{2}{d}}+M^{3}\epsilon^{-3},\,\left(M^{4-d}\epsilon^{-2}\right)^{\frac{1}{1-d}},\,M\left(\frac{\|H_{\text{else}}\|^{2}}{2M^{4}\gamma_{\text{max}}}\right)^{\frac{1}{d}}+\epsilon^{-1}\,\frac{\|H_{\text{else}}\|^{2}}{2M\gamma_{\text{max}}}\right\\}$

qubits. If the interaction graph of $H_{\text{targ}}$ has degree $D$, then the
interaction graph of the gadget hamiltonian has total degree
$\max\\{DR,RC\\}=\text{poly}(D,\epsilon^{-1},\|H_{\text{else}}\|,M)$.

This concludes the story of the 2-body gadgets with weak interactions. Let us
now apply the construction to reducing $k$-local to $2$-body with weak
interaction $(k\geq 3)$.

##  4 Reducing $k$-body to 2-body interactions $(k\geq 3)$

Figure 7: 3-local interactions from weak interactions. (a) The 3-local
interaction we want to approximate. (b) The standard construction by Oliveira
and Terhal [2] with target term $A_{a}\otimes B_{b}\otimes F_{f}$ replaced by
one (direct) ancilla $w$ in a large field $\Delta$, interacting with the
target spins via strong interactions of order $\Delta^{2/3}$. In addition, $a$
and $b$ interact with strength of order $\Delta^{1/3}$ to compensate for the
error term at $2^{\text{nd}}$ order perturbation theory. (c) The local fields
are replaced by interactions with a core. (d) Each strong 2-local interaction
term can be reduced to many $O(1)$ terms by our 2-body gadget construction,
using another common core.

With the new 2-body construction in mind, is it possible to use the _core_
idea and “parallelism” of the 2-body gadgets to construct a 3-body to 2-body
gadget that also uses only weak interactions? In Appendix C, we show one such
attempt. However, the resulting construction does not have all the desirable
properties of the 2-body construction. We hope that the problems we have
experienced will be useful for future efforts along similar lines. The
difficulty to construct $k$-body gadgets along these lines is similarly
difficult.

However, we are not doomed. Generating effective 3-body interactions such as
$\gamma A\otimes B\otimes C$ using only weak interactions is possible. We
could simply apply our new 2-local construction on top of standard 3-body to
2-body gadgets as sketched in Figure 7. We start from the usual construction
in [2] and replace the strong 1-local term of magnitude $\Delta$ by
interactions with a core. Finally, we reduce the large-norm 2-body
interactions in these gadgets with weak ones using the 2-body gadgets from
Section 3.

For general $k$-body to 2-body reduction, we can resort to the construction
from [5], where the gadget Hamiltonian consists of only 2-local interaction
terms (_i.e._ no extra 1-local terms). This makes it easy to directly apply
our new 2-body gadgets and reduce the gadget Hamiltonian to one with only weak
interactions. In subsequent work, we plan to elaborate on the detailed
constructions and make them more efficient.

##  5 Acknowledgements

We thank David Gosset, Dom Williamson, Ramis Movassagh, Sergei Bravyi and
Sabre Kais for helpful discussions, and the Simons Institute for Theory of
Computing at University of California, Berkeley, where the main part of this
work was done. DN was supported by the Slovak Research and Development Agency
grant APVV-0808-12 QIMABOS. YC gratefully acknowledges support from Sabre Kais
under the NSF Center for Quantum Information and Computation for Chemistry
grant award number CHE-1037992.

## References

  * [1] J. Kempe, A. Kitaev, and O. Regev.  The Complexity of the Local Hamiltonian Problem.  SIAM J. Computing, 35(5):1070–1097, 2006.  quant-ph/0406180.
  * [2] R. Oliveira and B. Terhal.  The complexity of quantum spin systems on a two-dimensional square lattice.  Quant. Inf. and Comp., 8(10):0900–0924, 2008.  arXiv:quant-ph/0504050.
  * [3] Sergey Bravyi, David P. Divincenzo, Roberto Oliveira, and Barbara M. Terhal.  The Complexity of Stoquastic Local Hamiltonian Problems.  Quantum Info. Comput., 8(5):361–385, May 2008.
  * [4] J. D. Biamonte and P. J. Love.  Realizable Hamiltonians for Universal Adiabatic Quantum Computers.  Phys. Rev. A, 8(1):012352, 2008.  arXiv:0704.1287.
  * [5] S. P. Jordan and E. Farhi.  Perturbative gadgets at arbitrary orders.  Phys. Rev. A, 062329, 2008.  arXiv:0802.1874v4.
  * [6] S. Bravyi, D. DiVincenzo, D. Loss, and B. Terhal.  Quantum Simulation of Many-Body Hamiltonians Using Perturbation Theory with Bounded-Strength Interactions.  Phys. Rev. Lett., 101:070503, 2008.  arXiv:0803.2686v1.
  * [7] N. Schuch and F. Verstraete.  Computational complexity of interacting electrons and fundamental limitations of density functional theory.  Nature Physics, 5:732–735, 2009.  arXiv:0712.0483v2.
  * [8] Yudong Cao, Ryan Babbush, Jacob Biamonte, and Sabre Kais.  Improved Hamiltonian gadgets.  preprint, 2014.  arXiv:1311.2555 [quant-ph].
  * [9] Michael R. Garey and David S. Johnson.  Computers and Intractability: A Guide to the Theory of NP-Completeness.  W. H. Freeman & Co., New York, NY, USA, 1979.
  * [10] Irit Dinur.  The PCP Theorem by Gap Amplification.  J. ACM, 54(3), June 2007.
  * [11] Dorit Aharonov, Itai Arad, and Thomas Vidick.  Guest Column: The Quantum PCP Conjecture.  SIGACT News, 44(2):47–79, June 2013.
  * [12] M B Hastings.  An area law for one-dimensional quantum systems.  Journal of Statistical Mechanics: Theory and Experiment, 2007(08):P08024, 2007.
  * [13] D. Aharonov, I. Arad, Z. Landau, and U. Vazirani.  The 1D Area Law and the Complexity of Quantum States: A Combinatorial Approach.  In Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, pages 324–333, Oct 2011.
  * [14] J. Eisert, M. Cramer, and M. B. Plenio.  Colloquium.  Rev. Mod. Phys., 82:277–306, Feb 2010.
  * [15] Robert Koenig.  Simplifying quantum double Hamiltonians using perturbative gadgets.  Quant. Inf. Comp., 10(3):292–324, 2010.  arXiv:0901.1333 [quant-ph].
  * [16] J. D. Biamonte.  Non-perturbative $k$-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins.  Phys. Rev. A, 77(5):052331, 2008.  arXiv:0801.3800.
  * [17] Samuel A. Ocko and Beni Yoshida.  Nonperturbative Gadget for Topological Quantum Codes.  Phys. Rev. Lett., 107(250502), 2011.  arXiv:1107.2697 [quant-ph].
  * [18] Kevin C. Young, Robin Blume-Kohout, and Daniel A. Lidar.  Adiabatic quantum optimization with the wrong Hamiltonian.  Phys. Rev. A, 88:062314, Dec 2013.
  * [19] D. Nagaj and S. Mozes.  New construction for a QMA complete three-local Hamiltonian.  Journal of Mathematical Physics, 48(7):072104, July 2007.
  * [20] Dominik Janzing and Pawel Wocjan.  Ergodic quantum computing.  Quantum Information Processing, 4(2):129–158, June 2005.
  * [21] Daniel Nagaj.  Universal two-body-hamiltonian quantum computing.  Phys. Rev. A, 85:032330, Mar 2012.
  * [22] Dorit Aharonov, Aram Harrow, Zeph Landau, Daniel Nagaj, Mario Szegedy, and Umesh Vazirani.  Local tests of global entanglement and a counterexample to the generalized area law.  In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, 2014.  to appear.
  * [23] S. Bravyi, D. DiVincenzo, and D. Loss.  Schrieffer-Wolff transformation for quantum many-body systems.  Ann. Phys., 326(10), 2011.  arXiv:1105.0675.

##  Appendix A Upper bounds on low-order perturbation series terms for 2-body
gadgets

In this Appendix, for the purpose of illustration we calculate upper bounds on
the norm of the first few orders in the perturbation series for the self-
energy for our 2-body gadget construction from Section 3.2.

_The $2^{\text{nd}}$ order._ This order is what contributes to the effective
Hamiltonian, which has $M$ terms of norm $O(1)$ there. Let us see what we get
here. From (44) we see that
$T_{2}=\frac{1}{z-\Delta}\sum_{j=1}^{M}R\beta_{j}^{2}(A_{a_{j}}-B_{b_{j}})^{2}$.
Every term at the second order corresponds to a transition of the form

$\mathcal{L}_{-}\rightarrow|y\rangle\rightarrow\mathcal{L}_{-}.$ (57)

Here $|y\rangle$ is a state where only one direct ancilla qubit $w$ is flipped
to $|1\rangle$ while the others remain at $|0\rangle$. From our construction
of $V$ in (13), observe that each term that involves a particular direct
ancilla $w_{i}^{(j)}$ is associated with a corresponding coefficient
$\beta_{j}$. Therefore all the transitions of the form (57) involving
$w_{i}^{(j)}$ would contribute a term of the form

$\underbrace{\beta_{j}(A_{a_{j}}-B_{b_{j}})}_{V_{-+}}\cdot\underbrace{\frac{1}{z-\Delta}}_{G_{+}}\cdot\underbrace{\beta_{j}(A_{a_{j}}-B_{b_{j}})}_{V_{+-}}$
(58)

to the perturbative expansion $\Sigma_{-}(z)$. Note that because the Hamming
weight of $y$ is $h(y)=1$, the resolvent component $G_{+}$ contributes a
factor $\frac{1}{z-h(y)\Delta}=\frac{1}{z-\Delta}$. Since $R$ direct ancillas
are introduced for the target 2-local term involving $a_{j}$ and $b_{j}$, the
total contribution of the direct ancillas used for generating the $j$-th
target term would be multiplied by a factor of $R$. Summing over all the
target terms from $j=1$ to $M$, we get the current form of $T_{2}$. Assuming
$A_{a_{j}}$ and $B_{b_{j}}$ are both unit-norm operators,

$\|T_{2}\|\leq\frac{1}{\Delta}\cdot
MR(2\beta_{\text{max}})^{2}=2M\gamma_{\text{max}},$ (59)

using the choice $\beta_{i}=\sqrt{\frac{\gamma_{i}\Delta}{2R}}$. This is just
what we expected (because the norm of what we are generating should be
something on the order of $M$).

_The $4^{\text{th}}$ order._ Transitions at the $4^{\text{th}}$ order could
involve one or two direct ancillas171717See also [8] for a detailed
explanation.. In the former case the transition would take the form of

$\mathcal{L}_{-}\rightarrow|y\rangle\rightarrow|y\rangle\rightarrow|y\rangle\rightarrow\mathcal{L}_{-}$
(60)

where $y$ is a string of Hamming weight 1. Such processes all contribute 0 to
the perturbative expansion since $\|H_{\text{else}}\|=0$. Now we consider
processes that involve two different direct ancillas $w_{a}$ and $w_{b}$.
There are two possibilities:

$\displaystyle\uparrow_{a}\uparrow_{b}\downarrow_{a}\downarrow_{b},\qquad\uparrow_{a}\uparrow_{b}\downarrow_{b}\downarrow_{a}$
(61)

where $\uparrow_{a}$ means flipping $w_{a}$ from $|0\rangle$ to $|1\rangle$
and $\downarrow_{a}$ from $|1\rangle$ to $|0\rangle$. Similar for $w_{b}$.
From $N=MR$ direct ancillas, there are in total $N(N-1)$ ways to choose
$w_{a}$ and $w_{b}$. For a fixed choice of $w_{a}$ and $w_{b}$, each of the
possible transitions listed above gives rise to at most
$(2\beta_{\text{max}})^{4}$ from the 4 flipping processes (from the above
discussion on (58) each flipping process contributes a factor of
$2\beta_{j}\leq 2\beta_{\text{max}}$ in $\|T_{k}\|$). The $G_{+}$ terms
contribute an overall factor of
$\frac{1}{z-\Delta}\cdot\frac{1}{z-2\Delta}\cdot\frac{1}{z-\Delta}$ to the
perturbative expansion. In particular the factor 2 in the component
$\frac{1}{z-2\Delta}$ is due to the fact that after the second flipping
process the state has two ancillas flipped to 1, resulting in a state
$|y^{\prime}\rangle$ with $h(y^{\prime})=2$. Combining these arguments, we
have

$\begin{array}[]{ccl}\|T_{4}\|&\leq&\displaystyle
2N(N-1)\cdot(2\beta_{\text{max}})^{4}\cdot\frac{1}{\Delta\cdot(2\Delta)\cdot\Delta}=\frac{N(N-1)(2\beta_{\text{max}})^{4}}{\Delta^{3}}\\\\[7.22743pt]
&\leq&\displaystyle\left(\frac{N(2\beta_{\text{max}})^{2}}{\Delta}\right)^{2}\frac{1}{\Delta}=2M\gamma_{\text{max}}\cdot\left(\frac{2M\gamma_{\text{max}}}{\Delta}\right).\end{array}$
(62)

Note that compared with the $2^{\text{nd}}$ order term, we collect a factor of
$2M\gamma_{\text{max}}/\Delta$ in the upper bound for $\|T_{4}\|$.

_$6^{\text{th}}$ order._ Following the same notation as before, at
$6^{\text{th}}$ order the following transitions contribute non-trivially to
$\|T_{6}\|$:

$\displaystyle\uparrow_{a}\uparrow_{b}\uparrow_{c}(\downarrow)^{3},\qquad\uparrow_{a}\uparrow_{b}\downarrow_{a}\uparrow_{c}(\downarrow)^{2}.$
(63)

The former type of transitions has $N(N-1)(N-2)\cdot 6$ different ways of
occuring and the $G_{+}$ terms contribute a factor of
$\frac{1}{z-\Delta}\cdot\frac{1}{z-2\Delta}\cdot\frac{1}{z-3\Delta}\cdot\frac{1}{z-2\Delta}\cdot\frac{1}{z-\Delta}$.
The latter has $N(N-1)\cdot 2\cdot(N-1)\cdot 2$ different ways of occuring and
a factor
$\frac{1}{z-\Delta}\cdot\frac{1}{z-2\Delta}\cdot\frac{1}{z-\Delta}\cdot\frac{1}{z-2\Delta}\cdot\frac{1}{z-\Delta}$
from the $G_{+}$ components. Both types involve 6 flipping processes, which
amounts to a factor of $(2\beta_{\text{max}})^{6}$. Hence

$\displaystyle\left\|T_{6}\right\|$
$\displaystyle=6N(N-1)(N-2)(2\beta_{\text{max}})^{6}\frac{1}{\Delta^{2}(2\Delta)^{2}(3\Delta)}+4N(N-1)(N-1)(2\beta_{\text{max}})^{6}\frac{1}{\Delta^{3}(2\Delta)^{2}}$
(64)
$\displaystyle\leq\frac{3}{2}\left(\frac{N(2\beta_{\text{max}})^{2}}{\Delta}\right)^{3}\frac{1}{\Delta^{2}}=3M\gamma_{\text{max}}\left(\frac{2M\gamma_{\text{max}}}{\Delta}\right)^{2}.$
(65)

Note that another $2M\gamma_{\text{max}}/\Delta$ factor is collected at the
$6^{\text{th}}$ order compared with the $4^{\text{th}}$. Given our choice that
$\Delta=M^{3}R^{d}$, it is clear that
$2M\gamma_{\text{max}}/\Delta=O(M^{-2}R^{-d})$. It is reasonable to speculate
that $\|T_{2m}\|=O(M^{-2m}R^{-dm})$ converges exponentially as
$m\rightarrow\infty$, which implies that the series
$\sum_{m=2}^{\infty}\|T_{2m}\|$ converges.

##  Appendix B Justification for the sequence of simplifying Hamiltonians when
bounding $E_{+}$

Let $|\psi\rangle\in\mathcal{L}_{+}$ be the state with minimum energy, i.e.
$\langle\psi|\tilde{H}|\psi\rangle=E_{+}$. The Hamiltonian $\tilde{H}$
connects target spins to direct ancillas via terms of the type $A_{a}\otimes
X_{j}$. We now argue that $E_{+}$ can be only lowered if we decouple the
target spins from the direct ancillas, and simply use $-\mathbb{I}\otimes
X_{j}$ instead of $A_{a}\otimes X_{j}$.

The expectation value $\langle\psi|\tilde{H}|\psi\rangle=E_{H}+E_{V}$ comes
from the expectation value of $H$ which is diagonal in the computational basis
(the $Z$ and $ZZ$ terms involving the ancillas) and the expectation of $V$,
which includes the interactions with target spins as well as the term
$H_{\text{else}}$. Let us rewrite the state $|\psi\rangle$ as

$\displaystyle|\psi\rangle=\sum_{w}c_{w}|w\rangle\otimes|\phi_{w}\rangle,$
(66)

where $w$ is a binary string labeling computational basis state of all the
ancillas. The expectation value of the term $H$ depends only on the magnitudes
of the $c_{w}$’s. The contribution from $H_{\text{else}}$ is

$\displaystyle\sum_{w}\left|c_{w}\right|^{2}\langle\phi_{w}|H_{\text{else}}|\phi_{w}\rangle.$
(67)

Finally, each term in $V$ of the form $A_{a}\otimes X_{j}$ contributes

$\displaystyle c_{v}^{*}c_{v^{\prime}}\langle
v|X_{j}|v^{\prime}\rangle\langle\phi_{v}|A_{a}|\phi_{v^{\prime}}\rangle$ (68)

for every pair $v,v^{\prime}$ that differ only at bit $j$. This expression can
be positive or negative, depending on $c_{v}$ and $c_{v^{\prime}}$. More
crucially, its magnitude will depend on
$\langle\phi_{v}|A_{a}|\phi_{v^{\prime}}\rangle$. Because $A_{a}$ is a Pauli
operator, this magnitude can never exceed 1. Let us now consider a state

$\displaystyle|\psi^{\prime}\rangle=\left(\sum_{w}\left|c_{w}\right||w\rangle\right)\otimes|\phi\rangle,$
(69)

with positive coefficients $|c_{w}|$, and a particular state $|\phi\rangle$
chosen to minimize $\langle\phi|H_{\text{else}}|\phi\rangle$. The expectation
value of $H$ does not change, while the contribution from $H_{\text{else}}$
can only decrease, because we have chosen $|\phi\rangle$ to minimize it. In
other words,
$\langle\psi^{\prime}|H\psi^{\prime}\rangle\leq\langle\psi|H|\psi\rangle$ and
$\langle\psi^{\prime}|H_{\text{else}}|\psi^{\prime}\rangle\leq\langle\psi|H_{\text{else}}|\psi\rangle$.
Finally, the expectation value of the interaction terms in $V^{\prime}$ (when
we set $A_{a}=-\mathbb{I}$) like (68) now become

$\displaystyle-|c_{v}|\cdot|c_{v^{\prime}}|\langle
v|X_{u}|v^{\prime}\rangle\leq-c_{v}^{*}c_{v^{\prime}}\langle
v|X_{u}|v^{\prime}\rangle\langle{\phi_{v}}|A_{a}|\phi_{v^{\prime}}\rangle.$
(70)

Thus,
$\langle\psi^{\prime}|V^{\prime}|\psi^{\prime}\rangle\leq\langle\psi|V|\psi\rangle$
and we conclude that the new minimum energy of $\tilde{H^{\prime}}$ restricted
to $\mathcal{L}_{+}$ is
$E^{\prime}_{+}\leq\langle\psi^{\prime}|H|\psi^{\prime}\rangle+\langle\psi^{\prime}|V^{\prime}|\psi^{\prime}\rangle\leq
E_{+}$. It means that when we replace the Hamiltonian $V$ with one that has no
interactions between the direct ancillas and the target spins, and uses
operators $-X_{w}$ on the direct ancillas, $E_{+}$ decreases (or remains what
it was).

##  Appendix C An alternative idea for 3-local gadget construction

Figure 8: A proposed effective three-body interaction on target spins $a,b,f,$
made from many weak 2-body interactions. The construction (72) involves a core
of size $C$ and a set of direct ancillas $q_{1},\dots,q_{R}$ whose 2-body
interactions with the target spins mediate the desired 3-local interaction
(but also some extra terms). We then add two more sets of direct ancillas
$w_{1},\dots,w_{R}$ and $y_{1},\dots,y_{R}$, in order to cancel out unwanted
2-local and 1-body terms. We can choose the interaction strengths
$\beta,\xi,\kappa,J\ll 1$.

Inspired by the 2-body gadget construction, one might naturally ask how to
construct a similar gadget Hamiltonian for 3-local interactions. Consider a
target 3-local term in a Hamiltonian $H_{\text{targ}}=H_{\text{else}}+\gamma
A_{a}\otimes B_{b}\otimes F_{f}$ on three qubits $a,b,f$, with $\gamma=O(1)$
and $\|H_{\text{else}}\|=O(1)$. Can we simulate this 3-local term by 2-local
terms with small norms directly, without using an intermediate 3-body to
strong-2-body gadget step? It turns out that we soon run into difficulties; we
highlight them now and hope that they will be instructive for further work.

Let us try combining the 3-body to 2-body construction of Oliveira and Terhal
[2] with the core and parallelization ideas from Section 3. The resulting
gadget (for a single 3-local term) is illustrated in Figure 8. Besides the
three target particles, it contains a core $\mathcal{C}$ of $C$ qubits in a
local field $\frac{J}{2}$, interacting with each other (as a complete graph)
ferromagnetically with strength $\frac{J}{2}$. Next, we introduce three sets
of (direct) ancilla qubits $q_{i},w_{i}$ and $y_{i}$ (each set has size $R$),
connect them to the core, and also let them interact with the three target
spins $a,b,f$.

Suppose we build a 2-body gadget Hamiltonian that from two parts,
$\tilde{H}=H+V$, and treat $V$ as a perturbation. We will generate the desired
target interaction from the third order of the perturbation expansion. Note
that since no third order transition that starts from the ground state
subspace of the direct ancilla and ends in it could involve more than one
direct ancilla, the gadgets can be applied in parallel on $M$ target terms.
Similar to (13), we can then write the gadget construction for $M$ different
3-local target terms.

To effectively capture a target 3-local Hamiltonian
$H_{\text{targ}}=H_{\text{else}}+\sum_{j=1}^{M}\gamma_{j}A_{a_{j}}\otimes
B_{b_{j}}\otimes F_{f_{j}}$, we use

$\displaystyle H$
$\displaystyle=\displaystyle\frac{J}{2}\sum_{j=1}^{M}\sum_{i=1}^{R}\sum_{c\in\mathcal{C}}(3\mathbb{I}-Z_{w_{i}^{(j)}}Z_{c}-Z_{q_{i}^{(j)}}Z_{c}-Z_{y_{i}^{(j)}}Z_{c})+H_{\mathcal{C}}$
(71) $\displaystyle V$
$\displaystyle=H_{\text{else}}+\sum_{j=1}^{M}\sum_{i=1}^{R}\Big{(}\beta_{j}\left(A_{a_{j}}+B_{b_{j}}\right)\otimes
X_{q_{i}^{(j)}}+\xi_{j}F_{f_{j}}\otimes|1\rangle\langle 1|_{q_{i}^{(j)}}$ (72)
$\displaystyle\makebox[79.49744pt]{}+\beta_{j}\left(A_{a_{j}}-B_{b_{j}}\right)\otimes
X_{w_{i}^{(j)}}+\kappa_{j}\left(F_{f_{j}}-\mathbb{I}\right)\otimes
X_{y_{i}^{(j)}}\Big{)}.$

where $H_{\mathcal{C}}$ is the core Hamiltonian from (3). Working out the self
energy expansion (2), we find

$\begin{array}[]{ccl}\Sigma_{-}(z)&=&\displaystyle
H_{\text{else}}+\underbrace{\frac{R}{z-\Delta}\sum_{j=1}^{M}\beta_{j}^{2}(A_{a_{j}}+B_{b_{j}})^{2}}_{\text{(a)}}+\underbrace{\frac{R}{z-\Delta}\sum_{j=1}^{M}\kappa_{j}^{2}(F_{f_{j}}-\mathbb{I})^{2}}_{\text{(b)}}\\\
&+&\underbrace{\frac{R}{z-\Delta}\sum_{j=1}^{M}\beta_{j}^{2}(A_{a_{j}}-B_{b_{j}})^{2}}_{\text{(c)}}+\underbrace{\frac{R}{(z-\Delta)^{2}}\sum_{j=1}^{M}\beta_{j}^{2}\xi_{j}(A_{a_{j}}+B_{b_{j}})F_{f_{j}}(A_{a_{j}}+B_{b_{j}})}_{\text{(d)}}+\cdots\end{array}$
(73)

Observe that the desired three-body interaction
$\sum_{j=1}^{M}\frac{2R\beta_{j}^{2}\xi_{j}}{\Delta^{2}}A_{a_{j}}\otimes
B_{b_{j}}\otimes F_{f_{j}}$ appears at the third order (d); it comes from the
interplay of the terms involving $q_{i}$ in (72). To make the 3-local coupling
coefficient of the $j^{\text{th}}$ target term to be $\gamma_{j}$, we have to
choose $\beta_{j},\xi_{j},\Delta,$ and $R$ (recalling that $\Delta=CJ$) so
that

$\displaystyle\frac{2R\beta_{j}^{2}\xi_{j}}{\Delta^{2}}=\gamma_{j}.$ (74)

Besides our target 3-local interaction, the term (d) in the expansion of
$\Sigma_{-}(z)$ (73) also gives us undesired interactions of the type
$A_{a_{j}}\otimes B_{b_{j}}$ and a 1-local term $F_{f_{j}}$. Nevertheless, we
can cancel them out – the last two terms in (72) compensate for these
undesired terms by generating the terms (b) and (c) in (73). The cancellation
happens for the choice 181818 Using the same prefactor $\beta$ in the first
and third terms in (72) takes care of the term $A\otimes B$. Next, we have
$\frac{R\beta^{2}\xi}{\Delta^{2}}\,F_{f}$ generated at the third order from
the first two terms in (72). We cancel it out by
$\frac{-2R\kappa}{\Delta}F_{f}$ generated at the second order from the last
term in (72).

$\displaystyle\kappa_{j}=\sqrt{\frac{\beta_{j}^{2}\xi_{j}}{\Delta}}=\sqrt{\frac{\gamma_{j}\Delta}{2R}},\qquad\qquad\xi_{j}=\beta_{j}=\left(\frac{\gamma_{j}\Delta^{2}}{2R}\right)^{\frac{1}{3}}.$
(75)

This way, we obtain only the desired 3-local interaction (and
$H_{\text{else}}$), and an overall energy shift.

Showing that this 3-local gadget satisfies the conditions of Theorem 3 is now
more difficult than what we did for the 2-body gadget. It is not clear that
the proofs (the subspace condition and convergence of the perturbation series)
will go through with the interaction strengths
$\xi_{j},\beta_{j},\kappa_{j},J=O(\epsilon)$ for an input error parameter
$\epsilon$. However, it is possible that this construction will result in a
better scaling of the necessary interaction strengths. We leave this as an
open question, and highlight the following difficulty.

Instead of (11) for the 2-body gadget, in (75) we have a relationship between
$\beta_{j}$ and $\Delta^{2}/R$, instead of $\Delta/R$. This difference has
non-trivial consequences. If we were to proceed to prove that the 3-local
gadget construction follows the subspace condition of the Theorem 3 as in
Claim 1, for subspaces $\mathcal{L}_{1}$ and $\mathcal{L}_{2}$ (see Equation
14) we could find the lower bound for $\langle\psi|\tilde{H}|\psi\rangle$ by
constructing 1-local Hamiltonians whose energy is lower than
$\langle\psi|\tilde{H}|\psi\rangle$ for any $|\psi\rangle\in\mathcal{L}_{+}$.
Then for $\mathcal{L}_{1}$ we would obtain an inequality in the form of (in
comparison with (24))

$\Delta>C\cdot N\beta_{\text{max}}$ (76)

for some constant $C$. Using the definition
$\beta_{\text{max}}(\gamma_{\text{max}}\Delta^{2}/(2R))^{1/3}$, we have
$\Delta=\Omega\left(M^{3}R^{2}\right)$. For $\mathcal{L}_{2}$ we would
similarly obtain an inequality of the form (compare this to (40))

$\Delta>C^{\prime}\cdot\frac{N\beta_{\text{max}}^{2}}{\Delta}$ (77)

for some constant $C^{\prime}$. By the definition of $\beta_{\text{max}}$ we
have $\Delta=\Omega\left(M^{3/2}R^{1/2}\right)$. Hence combining the
asymptotic requirement for $\Delta$, we need
$\Delta=\Omega\left(M^{3}R^{2}\right)$ for the gadget to satisfy the subspace
condition of Theorem 3. Bounding the terms in the perturbation expansion will
also show that this asymptotic requirement for $\Delta$ is enough for the
series to converge. However, in order for the coupling coefficients $J$,
$\beta_{i}$, $\xi_{i}$ and $\kappa_{i}$ to be $O(\epsilon)$ for any
$\epsilon>0$, we need each of them to scale as $O\left(R^{d}\right)$ where the
exponent $d<0$. This could not be the case if we impose the above requirement
for $\Delta$. For example, consider the $\beta_{i}$ coefficients. If we
require that $\Delta=\Omega\left(M^{3}R^{2}\right)$,

$\beta_{i}=\left(\frac{\gamma_{i}\Delta^{2}}{2R}\right)^{\frac{1}{3}}=\Theta\left(R^{-\frac{1}{3}}\Delta^{\frac{2}{3}}\right)=\Omega\left(M^{2}R\right).$
(78)

This is where the gadget construction cannot consist of only weak terms. We
hope that a way to circumvent this problem can be found in the future.

### Reducing k-body to 2-body interactions

Similarly, one can use standard k-body to 2-body gadgets to get a $2$-body
Hamiltonian with large interaction strengths. After this, we apply the strong-
from-weak gadget construction of Section 3 and end up with $k$-local from weak
$2$-body interactions. However, the efficiency is nothing to sing about.
Therefore, we propose to look at a direct, parallelized construction similar
to Figure 8, including interactions with a core to replace strong couplings.
However, as noted above for the proposed $3$-body gadget, it will not be easy
to show that the subspace conditions are met, the perturbation series
converges, and the interactions remain weak.