# Hamiltonian gadgets with reduced resource requirements

Yudong Cao<EMAIL_ADDRESS>Department of Computer Science, Purdue
University, 601 Purdue Mall, West Lafayette, IN 47907, USA  Qatar Energy and
Environment Research Institute (QEERI), Ar-Rayyān, P.O Box 5825, Doha, Qatar
Ryan Babbush<EMAIL_ADDRESS>Department of Chemistry and Chemical
Biology, Harvard University, Cambridge, MA 02138, USA  Jacob Biamonte
<EMAIL_ADDRESS>ISI Foundation, Via Alassio 11/c, 10126, Torino,
Italy  Sabre Kais<EMAIL_ADDRESS>Department of Computer Science, Purdue
University, 601 Purdue Mall, West Lafayette, IN 47907, USA  Qatar Energy and
Environment Research Institute (QEERI), Ar-Rayyān, P.O Box 5825, Doha, Qatar
Department of Chemistry, Physics and Birck Nanotechnology Center, Purdue
University, 601 Purdue Mall, West Lafayette, IN 47907, USA  Santa Fe
Institute, 1399 Hyde Park Rd, Santa Fe, NM 87501, USA

###### Abstract

Application of the adiabatic model of quantum computation requires efficient
encoding of the solution to computational problems into the lowest eigenstate
of a Hamiltonian that supports universal adiabatic quantum computation.
Experimental systems are typically limited to restricted forms of 2-body
interactions. Therefore, universal adiabatic quantum computation requires a
method for approximating quantum many-body Hamiltonians up to arbitrary
spectral error using at most 2-body interactions. Hamiltonian gadgets,
introduced around a decade ago, offer the only current means to address this
requirement. Although the applications of Hamiltonian gadgets have steadily
grown since their introduction, little progress has been made in overcoming
the limitations of the gadgets themselves. In this experimentally motivated
theoretical study, we introduce several gadgets which require significantly
more realistic control parameters than similar gadgets in the literature. We
employ analytical techniques which result in a reduction of the resource
scaling as a function of spectral error for the commonly used subdivision, 3-
to 2-body and $k$-body gadgets. Accordingly, our improvements reduce the
resource requirements of all proofs and experimental proposals making use of
these common gadgets. Next, we numerically optimize these new gadgets to
illustrate the tightness of our analytical bounds. Finally, we introduce a new
gadget that simulates a $YY$ interaction term using Hamiltonians containing
only $\\{X,Z,XX,ZZ\\}$ terms. Apart from possible implications in a
theoretical context, this work could also be useful for a first experimental
implementation of these key building blocks by requiring less control
precision without introducing extra ancillary qubits.

Although adiabatic quantum computation is known to be a universal model of
quantum computation 2004quant.ph..5098A ; 2007PhRvL..99g0502M ; OT06 ; BL07 ;
CL08  and hence, in principle equivalent to the circuit model, the mappings
between an adiabatic process and an arbitrary quantum circuit require
significant overhead. Currently the approaches to universal adiabatic quantum
computation require implementing multiple higher order and non-commuting
interactions by means of perturbative gadgets BL07 . Such gadgets arose in
early work on quantum complexity theory and the resources required for their
implementation are the subject of this study.

Early work by Kitaev _et al_. KSV02  established that an otherwise arbitrary
Hamiltonian restricted to have at most 5-body interactions has a ground state
energy problem which is complete for the quantum analog of the complexity
class NP (QMA-complete). Reducing the locality of the Hamiltonians from 5-body
down to 2-body remained an open problem for a number of years. In their 2004
proof that 2-local Hamiltonian is QMA-Complete, Kempe, Kitaev and Regev
formalized the idea of a perturbative gadget, which finally accomplished this
task KKR06 . Oliveira and Terhal further reduced the problem, showing
completeness when otherwise arbitrary 2-body Hamiltonians were restricted to
act on a square lattice OT06 . The form of the simplest QMA-complete
Hamiltonian is reduced to physically relevant models in BL07  (see also CM13
), e.g.

$H=\sum_{i}h_{i}Z_{i}+\sum_{i<j}J_{ij}Z_{i}Z_{j}+\sum_{i<j}K_{ij}X_{i}X_{j}.$
(1)

Although this model contains only physically accessible terms, programming
problems into a universal adiabatic quantum computer BL07  or an adiabatic
quantum simulator sim11 ; 2014arXiv1401.3186V  involves several types of
$k$-body interactions (for bounded $k$). To reduce from $k$-body interactions
to 2-body is accomplished through the application of gadgets. Hamiltonian
gadgets were introduced as theorem-proving tools in the context of quantum
complexity theory yet their experimental realization currently offers the only
path towards universal adiabatic quantum computation. In terms of experimental
constraints, an important parameter in the construction of these gadgets is a
large spectral gap introduced into the ancilla space as part of a penalty
Hamiltonian. This large spectral gap often requires control precision well
beyond current experimental capabilities and must be improved for practical
physical realizations.

A perturbative gadget consists of an ancilla system acted on by Hamiltonian
$H$, characterized by the spectral gap $\Delta$ between its ground state
subspace and excited state subspace, and a perturbation $V$ which acts on both
the ancilla and the system. $V$ perturbs the ground state subspace of $H$ such
that the perturbed low-lying spectrum of the gadget Hamiltonian
$\widetilde{H}=H+V$ captures the spectrum of the target Hamiltonian,
$H_{\text{targ}}$, up to error $\epsilon$. The purpose of a gadget is
dependent on the form of the target Hamiltonian $H_{\text{targ}}$. For
example, if the target Hamiltonian is $k$-local with $k\geq 3$ while the
gadget Hamiltonian is 2-local, the gadget serves as a tool for reducing
locality. Also if the target Hamiltonian involves interactions that are hard
to implement experimentally and the gadget Hamiltonian contains only
interactions that are physically accessible, the gadget becomes a generator of
physically inaccesible terms from accessible ones. For example the gadget
which we introduce in Sec. VI might fall into this category. Apart from the
physical relevance to quantum computation, gadgets have been central to many
results in quantum complexity theory BDLT08 ; BL07 ; BDOT06 ; CM13 .
Hamiltonian gadgets were also used to characterize the complexity of density
functional theory Schuch09  and are required components in current proposals
related to error correction on an adiabatic quantum computer Ganti2013  and
the adiabatic and ground state quantum simulator sim11 ; 2014arXiv1401.3186V .
Since these works employ known gadgets which we provide improved constructions
of here, our results hence imply a reduction of the resources required in
these past works.

The first use of perturbative gadgets KKR06  relied on a 2-body gadget
Hamiltonian to simulate a 3-body Hamiltonian of the form
$H_{\text{targ}}=H_{\text{else}}+\alpha\cdot A\otimes B\otimes C$ with three
auxiliary spins in the ancilla space. Here $H_{\text{else}}$ is an arbitrary
Hamiltonian that does not operate on the auxiliary spins. Further, $A$, $B$
and $C$ are unit-norm operators and $\alpha$ is the desired coupling. For such
a system, it is shown that it suffices to construct $V$ with $\|V\|<\Delta/2$
to guarantee that the perturbative self-energy expansion approximates
$H_{\text{targ}}$ up to error $\epsilon$ OT06 ; KKR06 ; BDLT08 . Because the
gadget Hamiltonian is constructed such that in the perturbative expansion
(with respect to the low energy subspace), only virtual excitations that flip
all 3 ancilla bits would have non-trivial contributions in the $1^{\text{st}}$
through $3^{\text{rd}}$ order terms. In JF08  Jordan and Farhi generalized the
construction in KKR06  to a general $k$-body to 2-body reduction using a
perturbative expansion due to Bloch bloch58 . They showed that one can
approximate the low-energy subspace of a Hamiltonian containing $r$ distinct
$k$-local terms using a 2-local Hamiltonian. Two important gadgets were
introduced by Oliveira and Terhal OT06  in their proof that 2-local
Hamiltonian on square lattice is QMA-Complete. In particular, they introduced
an alternative 3- to 2-body gadget which uses only one additional spin for
each 3-body term as well as a “subdivision gadget” that reduces a $k$-body
term to a $(\lceil k/2\rceil+1)$-body term using only one additional spin OT06
. These gadgets, which we improve in this work, find their use as the de facto
standard whenever the use of gadgets is necessitated. For instance, the
gadgets from OT06  were used by Bravyi, DiVincenzo, Loss and Terhal BDLT08  to
show that one can combine the use of subdivision and 3- to 2-body gadgets to
recursively reduce a $k$-body Hamiltonian to $2$-body, which is useful for
simulating quantum many-body Hamiltonians. We note that these gadgets solve a
different problem than the type of many-body operator simulations considered
previously cory99 ; cory00  for gate model quantum computation, where the
techniques developed therein are not directly applicable to our situation.

While recent progress in the experimental implementation of adiabatic quantum
processors 2006cond.mat..8253H ; Boixo2012 ; BCM+13 ; Lidar2014  suggests the
ability to perform sophisticated adiabatic quantum computing experiments, the
perturbative gadgets require very large values of $\Delta$. This places high
demands on experimental control precision by requiring that devices enforce
very large couplings between ancilla qubits while still being able to resolve
couplings from the original problem — even though those fields may be orders
of magnitude smaller than $\Delta$. Accordingly, if perturbative gadgets are
to be used, it is necessary to find gadgets which can efficiently approximate
their target Hamiltonians with significantly lower values of $\Delta$.

Results summary and manuscript structure. Previous works in the literature
KKR06 ; OT06 ; BDOT06 ; BL07 ; BDLT08  choose $\Delta$ to be a polynomial
function of $\epsilon^{-1}$ which is sufficient for yielding a spectral error
$O(\epsilon)$ between the gadget and the target Hamiltonian. Experimental
realizations however, will require a recipe for assigning the minimum $\Delta$
that guarantees error within specified $\epsilon$, which we consider here.
This recipe will need to depend on three parameters: (i) the desired coupling,
$\alpha$; (ii) the magnitude of the non-problematic part of the Hamiltonian,
$\|H_{\text{else}}\|$; and (iii) the specified error tolerance, $\epsilon$.
For simulating a target Hamiltonian up to error $\epsilon$, previous
constructions OT06 ; BDOT06 ; BDLT08  use $\Delta=\Theta(\epsilon^{-2})$ for
the subdivision gadget and $\Delta=\Theta(\epsilon^{-3})$ for the 3- to 2-body
gadget. We will provide analytical results and numerics which indicate that
$\Delta=\Theta(\epsilon^{-1})$ is sufficient for the subdivision gadget (Sec.
II and III) and $\Delta=\Theta(\epsilon^{-2})$ for the 3- to 2-body gadget
(Sec. IV and Appendix A), showing that the physical resources required to
realize the gadgets are less than previously assumed elsewhere in the
literature.

In our derivation of the $\Delta$ scalings, we use an analytical approach that
involves bounding the infinite series in the perturbative expansion. For the
3- to 2-body reduction, in Appendix A we show that complications arise when
there are multiple 3-body terms in the target Hamiltonian that are to be
reduced concurrently and bounding the infinite series in the multiple-bit
perturbative expansion requires separate treatments of odd and even order
terms. Furthermore, in the case where $\Delta=\Theta(\epsilon^{-2})$ is used,
additional terms which are dependent on the commutation relationship among the
3-body target terms are added to the gadget in order to compensate for the
perturbative error due to cross-gadget contributions (Appendix B).

The next result of this paper, described in Sec. V, is a 3- to 2-body gadget
construction that uses a 2-body Ising Hamiltonian with a local transverse
field. This opens the door to use existing flux-qubit hardware
2006cond.mat..8253H  to simulate $H_{\text{targ}}=H_{\text{else}}+\alpha
Z_{i}Z_{j}Z_{k}$ where $H_{\text{else}}$ is not necessarily diagonal. One
drawback of this construction is that it requires
$\Delta=\Theta(\epsilon^{-5})$, rendering it challenging to realize in
practice. For cases where the target Hamiltonian is diagonal, there are non-
perturbative gadgets B08 ; WFB12 ; BOA13  that can reduce a $k$-body
Hamiltonian to 2-body. In this work, however, we focus on perturbative
gadgets.

The final result of this paper in Sec. VI is to propose a gadget which is
capable of reducing arbitrary real-valued Hamiltonians to a Hamiltonian with
only XX and ZZ couplings. In order to accomplish this, we go to fourth-order
in perturbation theory to find an XXZZ Hamiltonian which serves as an
effective Hamiltonian dominated by YY coupling terms. Because YY terms are
especially difficult to realize in some experimental architectures, this
result is useful for those wishing to encode arbitrary QMA-Hard problems on
existing hardware. This gadget in fact now opens the door to solve electronic
structure problems on an adiabatic quantum computer.

To achieve both fast readability and completeness in presentation, each
section from Sec. II to Sec. VI consists of a Summary subsection and an
Analysis subsection. The former is mainly intended to provide a high-level
synopsis of the main results in the corresponding section. Readers could only
refer to the Summary sections on their own for an introduction to the results
of the paper. The Analysis subsections contain detailed derivations of the
results in the Summary.

##  I Perturbation theory

In our notation the spin-1/2 Pauli operators will be represented as
$\\{X,Y,Z\\}$ with subscript indicating which spin-1/2 particle (qubit) it
acts on. For example $X_{2}$ is a Pauli operator
$X=|0\rangle\langle{1}|+|1\rangle\langle{0}|$ acting on the qubit labelled as
$2$.

In the literature there are different formulations of the perturbation theory
that are adopted when constructing and analyzing the gadgets. This adds to the
challenge faced in comparing the physical resources required among the various
proposed constructions. For example, Jordan and Farhi JF08  use a formulation
due to Bloch, while Bravyi et al. use a formulation based on the Schrieffer-
Wolff transformation BDLT08 . Here we employ the formulation used in KKR06 ;
OT06 . For a review on various formulations of perturbation theory, refer to
BDL11 .

A gadget Hamiltonian $\tilde{H}=H+V$ consists of a penalty Hamiltonian $H$,
which applies an energy gap onto an ancilla space, and a perturbation $V$. To
explain in further detail how the low-lying sector of the gadget Hamiltonian
$\tilde{H}$ approximates the entire spectrum of a certain target Hamiltonian
$H_{\text{targ}}$ with error $\epsilon$, we set up 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$ as those of $\tilde{H}$, assuming all the
eigenvalues are labelled in a weakly increasing order
($\lambda_{1}\leq\lambda_{2}\leq\cdots$, same for $\tilde{\lambda}_{j}$).
Using a cutoff value $\lambda_{*}$, let
$\mathcal{L}_{-}=\text{span}\\{|\psi_{j}\rangle|\forall
j:\lambda_{j}\leq\lambda_{*}\\}$ be the low energy subspace and
$\mathcal{L}_{+}=\text{span}\\{|\psi_{j}\rangle|\forall
j:\lambda_{j}>\lambda_{*}\\}$ be the high energy subspace. Let ${\Pi_{-}}$ and
${\Pi_{+}}$ be the orthogonal projectors onto the subspaces $\mathcal{L}_{-}$
and $\mathcal{L}_{+}$ respectively. For an operator $O$ we define the
partitions of $O$ into the subspaces as $O_{-}={\Pi_{-}}O{\Pi_{-}}$,
$O_{+}={\Pi_{+}}O{\Pi_{+}}$, $O_{-+}={\Pi_{-}}O{\Pi_{+}}$ and
$O_{+-}={\Pi_{+}}O{\Pi_{-}}$.

With the definitions above, one can turn to perturbation theory to approximate
$\tilde{H}_{-}$ using $H$ and $V$. We now consider the operator-valued
resolvent $\tilde{G}(z)=(z\openone-\tilde{H})^{-1}$. Similarly one would
define $G(z)=(z\openone-H)^{-1}$. Note that $\tilde{G}^{-1}(z)-G^{-1}(z)=-V$
so that this allows an expansion in powers of $V$ as

$\tilde{G}=(G^{-1}-V)^{-1}=G(\openone-VG)^{-1}=G+GVG+GVGVG+GVGVGVG+\cdots.$
(2)

It is then standard to define the self-energy
$\Sigma_{-}(z)=z\openone-({\tilde{G}}_{-}(z))^{-1}$. The self-energy is
important because the spectrum of $\Sigma_{-}(z)$ gives an approximation to
the spectrum of $\tilde{H}_{-}$ since by definition
$\tilde{H}_{-}=z\openone-{\Pi_{-}}(\tilde{G}^{-1}(z)){\Pi_{-}}$ while
$\Sigma_{-}(z)=z\openone-({\Pi_{-}}\tilde{G}(z){\Pi_{-}})^{-1}$. As is
explained by Oliveira and Terhal OT06 , loosely speaking, if $\Sigma_{-}(z)$
is roughly constant in some range of $z$ (defined below in Theorem I.1) then
$\Sigma_{-}(z)$ is playing the role of $\tilde{H}_{-}$. This was formalized in
KKR06  and improved in OT06  where the following theorem is proven (as in OT06
we state the case where $H$ has zero as its lowest eigenvalue and a spectral
gap of $\Delta$. We use operator norm $\|\cdot\|$ which is 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}$):

######  Theorem I.1 (Gadget Theorem KKR06 ; OT06 ).

Let $\|V\|\leq\Delta/2$ where $\Delta$ is the spectral gap of $H$ and let the
low and high spectrum of $H$ be separated by a cutoff $\lambda_{*}=\Delta/2$.
Now let there be an effective Hamiltonian $H_{\text{eff}}$ with a spectrum
contained in $[a,b]$. If for some real constant $\epsilon>0$ and $\forall
z\in[a-\epsilon,b+\epsilon]$ with $a<b<\Delta/2-\epsilon$, the self-energy
$\Sigma_{-}(z)$ has the property that
$\|\Sigma_{-}(z)-H_{\text{eff}}\|\leq\epsilon$, then each eigenvalue
$\tilde{\lambda}_{j}$ of $\tilde{H}_{-}$ differs to the $j^{\text{th}}$
eigenvalue of $H_{\text{eff}}$, $\lambda_{j}$, by at most $\epsilon$. In other
words $|\tilde{\lambda}_{j}-\lambda_{j}|\leq\epsilon$, $\forall j$.

To apply Theorem I.1, a series expansion for $\Sigma_{-}(z)$ is truncated at
low order for which $H_{\text{eff}}$ is approximated. The 2-body terms in $H$
and $V$ by construction can give rise to higher order terms in
$H_{\text{eff}}$. For this reason it is possible to engineer $H_{\text{eff}}$
from $\Sigma_{-}(z)$ to approximate $H_{\text{targ}}$ up to error $\epsilon$
in the range of $z$ considered in Theorem I.1 by introducing auxiliary spins
and a suitable selection of 2-body $H$ and $V$. Using the series expansion of
$\tilde{G}$ in Eq. 2, the self-energy
$\Sigma_{-}(z)=z\openone-\tilde{G}_{-}^{-1}(z)$ can be expanded as (for
further details see KKR06 )

$\Sigma_{-}(z)=H_{-}+V_{-}+V_{-+}G_{+}(z)V_{+-}+V_{-+}G_{+}(z)V_{+}G_{+}(z)V_{+-}+\cdots.$
(3)

The terms of $2^{\text{nd}}$ order and higher in this expansion give rise to
the effective many-body interactions.

(a)

(b)

Figure 1: Numerical illustration of gadget theorem using a subdivision gadget.
Here we use a subdivision gadget to approximate
$H_{\text{targ}}=H_{\text{else}}+\alpha Z_{1}Z_{2}$ with
$\|H_{\text{else}}\|=0$ and $\alpha\in[-1,1]$. $\epsilon=0.05$. “analytical”
stands for the case where the value of $\Delta$ is calculated using Eq. 14
when $|\alpha|=1$. “numerical” represents the case where $\Delta$ takes the
value that yield the spectral error to be $\epsilon$. In (a) we let
$\alpha=1$. $z\in[-\max z,\max z]$ with $\max
z=\|H_{\text{else}}\|+\max\alpha+\epsilon$. The operator $\Sigma_{-}(z)$ is
computed up to the $3^{\text{rd}}$ order. Subplot (b) shows for every value of
$\alpha$ in its range, the maximum difference between the eigenvalues
$\tilde{\lambda}_{j}$ in the low-lying spectrum of $\tilde{H}$ and the
corresponding eigenvalues $\lambda_{j}$ in the spectrum of
$H_{\text{targ}}\otimes|0\rangle\langle{0}|_{w}$.

##  II Improved Oliveira and Terhal subdivision gadget

Summary. The subdivision gadget is introduced by Oliveira and Terhal OT06  in
their proof that 2-local Hamiltonian on square lattice is QMA-Complete. Here
we show an improved lower bound for the spectral gap $\Delta$ needed on the
ancilla of the gadget. A subdivision gadget simulates a many-body target
Hamiltonian $H_{\text{targ}}=H_{\text{else}}+\alpha\cdot A\otimes B$
($H_{\text{else}}$ is a Hamiltonian of arbitrary norm, $\|A\|=1$ and
$\|B\|=1$) by introducing an ancilla spin $w$ and applying onto it a penalty
Hamiltonian $H=\Delta|1\rangle\langle{1}|_{w}$ so that its ground state
subspace $\mathcal{L}_{-}=\text{span}\\{|0\rangle_{w}\\}$ and its excited
subspace $\mathcal{L}_{+}=\text{span}\\{|1\rangle_{w}\\}$ are separated by
energy gap $\Delta$. In addition to the penalty Hamiltonian $H$, we add a
perturbation $V$ of the form

$V=H_{\text{else}}+|\alpha||0\rangle\langle{0}|_{w}+\sqrt{\frac{|\alpha|\Delta}{2}}(\text{sgn}(\alpha)A-B)\otimes
X_{w}.$ (4)

Hence if the target term $A\otimes B$ is $k$-local, the gadget Hamiltonian
$\tilde{H}=H+V$ is at most $(\lceil{k/2}\rceil+1)$-local, accomplishing the
locality reduction. Assume $H_{\text{targ}}$ acts on $n$ qubits. Prior work
OT06  shows that $\Delta=\Theta(\epsilon^{-2})$ is a sufficient condition for
the lowest $2^{n}$ levels of the gadget Hamiltonian $\widetilde{H}$ to be
$\epsilon$-close to the corresponding spectrum of $H_{\text{targ}}$. However,
by bounding the infinite series of error terms in the perturbative expansion,
we are able to obtain a tighter lower bound for $\Delta$ for error $\epsilon$.
Hence we arrive at our first result (details will be presented later in this
section), that it suffices to let

$\Delta\geq\left(\frac{2|\alpha|}{\epsilon}+1\right)(2\|H_{\text{else}}\|+|\alpha|+\epsilon).$
(5)

In Fig. 2 we show numerics indicating the minimum $\Delta$ required as a
function of $\alpha$ and $\epsilon$. In Fig. 2a the numerical results and the
analytical lower bound in Eq. 5 show that for our subdivision gadgets,
$\Delta$ can scale as favorably as $\Theta(\epsilon^{-1})$. For the
subdivision gadget presented in OT06 , $\Delta$ scales as
$\Theta(\epsilon^{-2})$. Though much less than the original assignment in OT06
, the lower bound of $\Delta$ in Eq. 5, still satisfies the condition of
Theorem I.1. In Fig. 2 we numerically find the minimum value of such $\Delta$
that yields a spectral error of exactly $\epsilon$.

(a)(b)

Figure 2: Comparison between our subdivision gadget with that of Oliveira and
Terhal OT06 . The data labelled as “numerical” represent the $\Delta$ values
obtained from the numerical search such that the spectral error between
$H_{\text{targ}}$ and $\widetilde{H}_{-}$ is $\epsilon$. The data obtained
from the calculation using Eq. 5 are labelled as “analytical”. “[OT06]” refers
to values of $\Delta$ calculated according to the assignment by Oliveira and
Terhal OT06 . In this example we consider
$H_{\text{targ}}=H_{\text{else}}+\alpha Z_{1}Z_{2}$. (a) Gap scaling with
respect to $\epsilon^{-1}$. Here $\|H_{\text{else}}\|=0$ and $\alpha=1$. (b)
The gap $\Delta$ as a function of the desired coupling $\alpha$. Here
$\|H_{\text{else}}\|=0$, $\epsilon=0.05$.

Analysis. The currently known subdivision gadgets in the literature assume
that the gap in the penalty Hamiltonian $\Delta$ scales as
$\Theta(\epsilon^{-2})$ (see for example OT06 ; BDLT08 ). Here we employ a
method which uses infinite series to find the upper bound to the norm of the
high order terms in the perturbative expansion. We find that in fact
$\Delta=\Theta(\epsilon^{-1})$ is sufficient for the error to be within
$\epsilon$. A variation of this idea will also be used to reduce the gap
$\Delta$ needed in the $3$\- to 2-body gadget (see Sec. IV).

The key aspect of developing the gadget is that given
$H=\Delta|1\rangle\langle{1}|_{w}$, we need to determine a perturbation $V$ to
perturb the low energy subspace

$\mathcal{L}_{-}=\text{span}\\{|\psi\rangle\otimes|0\rangle_{w},\makebox[1.42271pt]{}\text{
$|\psi\rangle$ is any state of the system excluding the ancilla spin $w$}\\}$

such that the low energy subspace of the gadget Hamiltonian $\tilde{H}=H+V$
approximates the spectrum of the entire operator
$H_{\text{targ}}\otimes|0\rangle\langle{0}|_{w}$ up to error $\epsilon$. Here
we will define $V$ and work backwards to show that it satisfies Theorem I.1.
We let

$V=H_{\text{else}}+\frac{1}{\Delta}({\kappa}^{2}A^{2}+{\lambda}^{2}B^{2})\otimes|0\rangle\langle{0}|_{w}+({\kappa}A+{\lambda}B)\otimes
X_{w}$ (6)

where ${\kappa}$, ${\lambda}$ are constants which will be determined such that
the dominant contribution to the perturbative expansion which approximates
$\tilde{H}_{-}$ gives rise to the target Hamiltonian
$H_{\text{targ}}=H_{\text{else}}+\alpha\cdot A\otimes B$. In Eq. 6 and the
remainder of the section, by slight abuse of notation, we use $\kappa
A+\lambda B$ to represent
$\kappa(A\otimes\openone_{\mathcal{B}})+\lambda(\openone_{\mathcal{A}}\otimes
B)$ for economy. Here $\openone_{\mathcal{A}}$ and $\openone_{\mathcal{B}}$
are identity operators acting on the subspaces $\mathcal{A}$ and $\mathcal{B}$
respectively. The partitions of $V$ in the subspaces, as defined in Sec. I are

$\begin{array}[]{c}\displaystyle
V_{+}=H_{\text{else}}\otimes|1\rangle\langle{1}|_{w},\quad
V_{-}=\left(H_{\text{else}}+\frac{1}{\Delta}({\kappa}^{2}A^{2}+{\lambda}^{2}B^{2})\openone\right)\otimes|0\rangle\langle{0}|_{w},\\\\[7.22743pt]
V_{-+}=({\kappa}A+{\lambda}B)\otimes|0\rangle\langle{1}|_{w},\quad
V_{+-}=({\kappa}A+{\lambda}B)\otimes|1\rangle\langle{0}|_{w}.\end{array}$ (7)

We would like to approximate the target Hamiltonian $H_{\text{targ}}$ and so
expand the self-energy in Eq. 3 up to $2^{\text{nd}}$ order. Note that
$H_{-}=0$ and $G_{+}(z)=(z-\Delta)^{-1}|1\rangle\langle{1}|_{w}$. Therefore
the self energy $\Sigma_{-}(z)$ can be expanded as

$\begin{array}[]{ccl}\Sigma_{-}(z)&=&\displaystyle
V_{-}+\frac{1}{z-\Delta}V_{-+}V_{+-}+\sum_{k=1}^{\infty}\frac{V_{-+}V_{+}^{k}V_{+-}}{(z-\Delta)^{k+1}}\\\\[7.22743pt]
&=&\displaystyle\underbrace{\left(H_{\text{else}}-\frac{2{\kappa}{\lambda}}{\Delta}A\otimes
B\right)\otimes|0\rangle\langle{0}|_{w}}_{H_{\text{eff}}}+\underbrace{\frac{z}{\Delta(z-\Delta)}({\kappa}A+{\lambda}B)^{2}\otimes|0\rangle\langle{0}|_{w}+\sum_{k=1}^{\infty}\frac{V_{-+}V_{+}^{k}V_{+-}}{(z-\Delta)^{k+1}}}_{\text{error
term}}.\end{array}$ (8)

By selecting ${\kappa}=\text{sgn}(\alpha)(|\alpha|\Delta/2)^{1/2}$ and
${\lambda}=-(|\alpha|\Delta/2)^{1/2}$, the leading order term in
$\Sigma_{-}(z)$ becomes
$H_{\text{eff}}=H_{\text{targ}}\otimes|0\rangle\langle{0}|_{w}$. We must now
show that the condition of Theorem I.1 is satisfied i.e. for a small real
number $\epsilon>0$, $\|\Sigma_{-}(z)-H_{\text{eff}}\|\leq\epsilon,\forall
z\in[\min z,\max z]$ where $\max z=\|H_{\text{else}}\|+|\alpha|+\epsilon=-\min
z$. Essentially this amounts to choosing a value of $\Delta$ to cause the
error term in Eq. 8 to be $\leq\epsilon$. In order to derive a tighter lower
bound for $\Delta$, we bound the norm of the error term in Eq. 8 by letting
$z\mapsto\max z$ and from the triangle inequality for operator norms:

$\begin{array}[]{rcl}\displaystyle\left\|\frac{z}{\Delta(z-\Delta)}(\kappa
A+\lambda
B)^{2}\otimes|0\rangle\langle{0}|_{w}\right\|&\leq&\displaystyle\frac{\max{z}}{\Delta(\Delta-\max{z})}\cdot
4\kappa^{2}=\frac{2|\alpha|\max{z}}{\Delta-\max{z}}\\\\[7.22743pt]
\displaystyle\left\|\sum_{k=1}^{\infty}\frac{V_{-+}V_{+}^{k}V_{+-}}{(z-\Delta)^{k+1}}\right\|&\leq&\displaystyle\sum_{k=1}^{\infty}\frac{\|V_{-+}\|\cdot\|V_{+}\|^{k}\cdot\|V_{+-}\|}{(\Delta-\max{z})^{k+1}}\\\\[7.22743pt]
&\leq&\displaystyle\sum_{k=1}^{\infty}\frac{2|\kappa|\cdot\|H_{\text{else}}\|^{k}\cdot
2|\kappa|}{(\Delta-\max{z})^{k+1}}=\sum_{k=1}^{\infty}\frac{2|\alpha|\Delta\|H_{\text{else}}\|^{k}}{(\Delta-\max{z})^{k+1}}.\end{array}$
(9)

Using $H_{\text{eff}}=H_{\text{targ}}\otimes|0\rangle\langle{0}|_{w}$, from
(8) we see that

$\displaystyle\begin{array}[]{ccl}\|\Sigma_{-}(z)-H_{\text{targ}}\otimes|0\rangle\langle{0}|_{w}\|&\leq&\displaystyle\frac{2|\alpha|\max
z}{\Delta-\max
z}+\sum_{k=1}^{\infty}\frac{2|\alpha|\Delta\|H_{\text{else}}\|^{k}}{(\Delta-\max
z)^{k+1}}\end{array}$ (11)
$\displaystyle\begin{array}[]{ccl}&=&\displaystyle\frac{2|\alpha|\max
z}{\Delta-\max z}+\frac{2|\alpha|\Delta}{\Delta-\max
z}\cdot\frac{\|H_{\text{else}}\|}{\Delta-\max
z-\|H_{\text{else}}\|}.\end{array}$ (13)

Here going from Eq. 11 to Eq. 13 we have assumed the convergence of the
infinite series in Eq. 11, which adds the reasonable constraint that
$\Delta>|\alpha|+\epsilon+2\|H_{\text{else}}\|$. To ensure that
$\|\Sigma_{-}(z)-H_{\text{targ}}\otimes|0\rangle\langle{0}|_{w}\|\leq\epsilon$
it is sufficient to let expression Eq. 13 be $\leq\epsilon$, which implies
that

$\Delta\geq\left(\frac{2|\alpha|}{\epsilon}+1\right)(|\alpha|+\epsilon+2\|H_{\text{else}}\|)$
(14)

which is $\Theta(\epsilon^{-1})$, a tighter bound than $\Theta(\epsilon^{-2})$
in the literature BDLT08 ; KKR06 ; OT06 . This bound is illustrated with a
numerical example (Fig. 1). From the data labelled as “analytical” in Fig. 1a
we see that the error norm $\|\Sigma_{-}(z)-H_{\text{eff}}\|$ is within
$\epsilon$ for all $z$ considered in the range, which satisfies the condition
of the theorem for the chosen example. In Fig. 1b, the data labelled
“analytical” show that the spectral difference between $\tilde{H}_{-}$ and
$H_{\text{eff}}=H_{\text{targ}}\otimes|0\rangle\langle{0}|_{w}$ is indeed
within $\epsilon$ as the theorem promises. Furthermore, note that the
condition of Theorem I.1 is only sufficient, which justifies why in Fig. 1b
for $\alpha$ values at $\max\alpha$ and $\min\alpha$ the spectral error is
strictly below $\epsilon$. This indicates that an even smaller $\Delta$,
although below the bound we found in Eq. 14 to satisfy the theorem, could
still yield the spectral error within $\epsilon$ for all $\alpha$ values in
the range. The smallest value $\Delta$ can take would be one such that the
spectral error is exactly $\epsilon$ when $\alpha$ is at its extrema. We
numerically find this $\Delta$ (up to numerical error which is less than
$10^{-5}\epsilon$) and as demonstrated in Fig. 1b, the data labelled
“numerical” shows that the spectral error is indeed $\epsilon$ at
$\max(\alpha)$ and $\min(\alpha)$, yet in Fig. 1a the data labelled
“numerical” shows that for some $z$ in the range the condition of the Theorem
I.1,
$\|\Sigma_{-}(z)-H_{\text{targ}}\otimes|0\rangle\langle{0}|_{w}\|\leq\epsilon$,
no longer holds. In Fig. 1 we assume that $\epsilon$ is kept constant. In Fig.
2a we compute both analytical and numerical $\Delta$ values for different
values of $\epsilon$.

_Comparison with Oliveira and TerhalOT06 ._ We also compare our $\Delta$
assignment with the subdivision gadget by Oliveira and Terhal OT06 , where
given a target Hamiltonian $H_{\text{targ}}=H_{\text{else}}+Q\otimes R$ it is
assumed that $Q$ and $R$ are operators with finite norm operating on two
separate spaces $\mathcal{A}$ and $\mathcal{B}$.

The construction of the subdivision gadget in OT06  is the same as the
construction presented earlier: introduce an ancillary qubit $w$ with energy
gap $\Delta$, then the unperturbed Hamiltonian is
$H=\Delta|1\rangle\langle{1}|_{w}$. In OT06  they add a perturbation $V$ that
takes the form of (OT06, , Eq. 15)

$V=H^{\prime}_{\text{else}}+\sqrt{\frac{\Delta}{2}}(-Q+R)\otimes{X_{w}}$ (15)

where $H^{\prime}_{\text{else}}=H_{\text{else}}+Q^{2}/2+R^{2}/2$. Comparing
the form of Eq. 15 and Eq. 6 we can see that if we redefine
$Q=\sqrt{|\alpha|}A$ and $R=\sqrt{|\alpha|}B$, the gadget formulation is
identical to our subdivision gadget approximating
$H_{\text{targ}}=H_{\text{else}}+\alpha{A\otimes B}$ with $\alpha>0$. In the
original work $\Delta$ is chosen as (OT06, , Eq. 20)

$\Delta=\frac{(\|H^{\prime}_{\text{else}}\|+C_{2}r)^{6}}{\epsilon^{2}}$

where $C_{2}\geq\sqrt{2}$ and $r=\max\\{\|Q\|,\|R\|\\}$. In the context of our
subdivision gadget, this choice of $\Delta$ translates to a lower bound

$\Delta\geq\frac{(\|H_{\text{else}}+|\alpha|\openone\|+\sqrt{2|\alpha|})^{6}}{\epsilon^{2}}.$
(16)

In Fig. 2a we compare the lower bound in Eq. 16 with our lower bound in Eq. 14
and the numerically optimized $\Delta$ described earlier.

##  III Parallel subdivision and $k$\- to $3$-body reduction

Summary. Applying subdivision gadgets iteratively one can reduce a $k$-body
Hamiltonian
$H_{\text{targ}}=H_{\text{else}}+\alpha\bigotimes_{i=1}^{k}\sigma_{i}$ to
3-body. Here each $\sigma_{i}$ is a single spin Pauli operator. Initially, the
term $\bigotimes_{i=1}^{k}\sigma_{i}$ can be broken down into $A\otimes B$
where $A=\bigotimes_{i=1}^{r}\sigma_{i}$ and
$B=\bigotimes_{i=r+1}^{k}\sigma_{i}$. Let $r=k/2$ for even $k$ and $r=(k+1)/2$
for odd $k$. The gadget Hamiltonian will be $(\lceil{k/2}\rceil+1)$-body,
which can be further reduced to a
$(\lceil{\lceil{k/2}\rceil+1}\rceil/2+1)$-body Hamiltonian in the same
fashion. Iteratively applying this procedure, we can reduce a $k$-body
Hamiltonian to $3$-body, with the $i^{\text{th}}$ iteration introducing the
same number of ancilla qubits as that of the many-body term to be subdivided.
Applying the previous analysis on the improved subdivision gadget
construction, we find that
$\Delta_{i}=\Theta(\epsilon^{-1}\Delta_{i-1}^{3/2})$ is sufficient such that
during each iteration the spectral difference between $\widetilde{H}_{i}$ and
$\widetilde{H}_{i-1}$ is within $\epsilon$. From the recurrence relation
$\Delta_{i}=\Theta(\epsilon^{-1}\Delta_{i-1}^{3/2})$, we hence were able to
show a quadratic improvement over previous $k$-body constructions BDLT08 .

Analysis. The concept of parallel application of gadgets has been introduced
in OT06 ; KKR06 . The idea of using subdivision gadgets for iteratively
reducing a $k$-body Hamiltonian to 3-body has been mentioned in OT06 ; BDLT08
. Here we elaborate the idea by a detailed analytical and numerical study. We
provide explicit expressions of all parallel subdivision gadget parameters
which guarantees that during each reduction the error between the target
Hamiltonian and the low-lying sector of the gadget Hamiltonian is within
$\epsilon$. For the purpose of presentation, let us define the notions of
“parallel” and “series” gadgets in the following remarks.

######  Remark III.1 (Parallel gadgets).

Parallel application of gadgets refers to using gadgets on multiple terms
$H_{\text{targ,i}}$ in the target Hamiltonian
$H_{\text{targ}}=H_{\text{else}}+\sum_{i=1}^{m}H_{\text{targ,i}}$
concurrently. Here one will introduce $m$ ancilla spins $w_{1},\cdots,w_{m}$
and the parallel gadget Hamiltonian takes the form of
$\tilde{H}=\sum_{i=1}^{m}H_{i}+V$ where
$H_{i}=\Delta|1\rangle\langle{1}|_{w_{i}}$ and
$V=H_{\text{else}}+\sum_{i=1}^{m}V_{i}$. $V_{i}$ is the perturbation term of
the gadget applied to $H_{\text{targ,i}}$.

######  Remark III.2 (Serial gadgets).

Serial application of gadgets refers to using gadgets sequentially. Suppose
the target Hamiltonian $H_{\text{targ}}$ is approximated by a gadget
Hamiltonian $\tilde{H}^{(1)}$ such that $\tilde{H}^{(1)}_{-}$ approximates the
spectrum of $H_{\text{targ}}$ up to error $\epsilon$. If one further applies
onto $\tilde{H}^{(1)}$ another gadget and obtains a new 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)}$.

Based on Remark III.1, a parallel subdivision gadget deals with the case where
$H_{\text{targ,i}}=\alpha_{i}A_{i}\otimes B_{i}$. $\alpha_{i}$ is a constant
and $A_{i}$, $B_{i}$ are unit norm Hermitian operators that act on separate
spaces $\mathcal{A}_{i}$ and $\mathcal{B}_{i}$. Note that with
$H_{i}=\Delta|1\rangle\langle{1}|_{w_{i}}$ for every $i\in\\{1,2,\cdots,m\\}$
we have the total penalty Hamiltonian
$H=\sum_{i=1}^{m}H_{i}=\sum_{x\in\\{0,1\\}^{m}}h(x)\Delta|x\rangle\langle{x}|$
where $h(x)$ is the Hamming weight of the $m$-bit string $x$. This penalty
Hamiltonian ensures that the ground state subspace is
$\mathcal{L}_{-}=\text{span}\\{|0\rangle^{\otimes{m}}\\}$ while all the states
in the subspace
$\mathcal{L}_{+}=\text{span}\\{|x\rangle|x\in\\{0,1\\}^{m},x\neq 00\cdots
0\\}$ receives an energy penalty of at least $\Delta$. The operator-valued
resolvent $G$ for the penalty Hamiltonian is (by definition in Sec. I)

$G(z)=\sum_{x\in\\{0,1\\}^{m}}\frac{1}{z-h(x)\Delta}|x\rangle\langle{x}|.$
(17)

The perturbation Hamiltonian $V$ is defined as

$V=H_{\text{else}}+\frac{1}{\Delta}\sum_{i=1}^{m}({\kappa_{i}^{2}}A_{i}^{2}+{\lambda_{i}^{2}}B_{i}^{2})+\sum_{i=1}^{m}({\kappa_{i}}A_{i}+{\lambda_{i}}B_{i})\otimes
X_{u_{i}}$ (18)

where the coefficients ${\kappa_{i}}$ and ${\lambda_{i}}$ are defined as
${\kappa_{i}}=\text{sgn}(\alpha_{i})\sqrt{{|\alpha_{i}|\Delta}/{2}},{\lambda_{i}}=-\sqrt{{|\alpha_{i}|\Delta}/{2}}$.
Define $P_{-}=|0\rangle^{\otimes m}\langle{0}|^{\otimes m}$ and
$P_{+}=\openone-P_{-}$. Then if $H_{\text{targ}}$ acts on the Hilbert space
$\mathcal{M}$, $\Pi_{-}=\openone_{\mathcal{M}}\otimes P_{-}$ and
$\Pi_{+}=\openone_{\mathcal{M}}\otimes P_{+}$. Comparing Eq. 18 with Eq. 6 we
see that the projector to the low-lying subspace $|0\rangle\langle{0}|_{w}$ in
Eq. 6 is replaced by an identity $\openone$ in Eq. 18. This is because in the
case of $m$ parallel gadgets $P_{-}$ cannot be realized with only 2-body terms
when $m\geq 3$.

The partition of $V$ in the subspaces are

$\begin{array}[]{ll}\displaystyle
V_{-}=\left(H_{\text{else}}+\frac{1}{\Delta}\sum_{i=1}^{m}({\kappa_{i}^{2}}A_{i}^{2}+{\lambda_{i}^{2}}B_{i}^{2})\right)\otimes{P_{-}},&\displaystyle
V_{+}=\left(H_{\text{else}}+\frac{1}{\Delta}\sum_{i=1}^{m}({\kappa_{i}^{2}}A_{i}^{2}+{\lambda_{i}^{2}}B_{i}^{2})\right)\otimes{P_{+}}\\\\[7.22743pt]
\displaystyle
V_{-+}=\sum_{i=1}^{m}({\kappa_{i}}A_{i}+{\lambda_{i}}B_{i})\otimes{P_{-}}X_{u_{i}}{P_{+}},&\displaystyle
V_{+-}=\sum_{i=1}^{m}({\kappa_{i}}A_{i}+{\lambda_{i}}B_{i})\otimes{P_{+}}X_{u_{i}}{P_{-}}.\\\\[7.22743pt]
\end{array}$ (19)

The self-energy expansion in Eq. 3 then becomes

$\begin{array}[]{ccl}\displaystyle\Sigma_{-}(z)&=&\displaystyle\left(H_{\text{else}}+\frac{1}{\Delta}\sum_{i=1}^{m}({\kappa_{i}^{2}}A_{i}^{2}+{\lambda_{i}^{2}}B_{i}^{2})\right)\otimes{P_{-}}+\frac{1}{z-\Delta}\sum_{i=1}^{m}({\kappa_{i}}A_{i}+{\lambda_{i}}B_{i})^{2}\otimes{P_{-}}\\\\[7.22743pt]
&+&\displaystyle\sum_{k=1}^{\infty}V_{-+}(G_{+}V_{+})^{k}G_{+}V_{+-}.\end{array}$
(20)

Rearranging the terms we have

$\begin{array}[]{ccl}\displaystyle\Sigma_{-}(z)&=&\displaystyle\underbrace{\left(H_{\text{else}}+\sum_{i=1}^{m}\left(-\frac{2{\kappa_{i}}{\lambda_{i}}}{\Delta}A_{i}\otimes
B_{i}\right)\right)\otimes{P_{-}}}_{H_{\text{eff}}}+\underbrace{\left(\frac{1}{\Delta}+\frac{1}{z-\Delta}\right)\sum_{i=1}^{m}({\kappa_{i}^{2}}A_{i}^{2}+{\lambda_{i}^{2}}B_{i}^{2})\otimes{P_{-}}}_{E_{1}}\\\\[7.22743pt]
&+&\displaystyle\underbrace{\left(\frac{1}{\Delta}+\frac{1}{z-\Delta}\right)\sum_{i=1}^{m}2{\kappa_{i}}{\lambda_{i}}A_{i}\otimes
B_{i}\otimes{P_{-}}}_{E_{2}}+\underbrace{\sum_{k=1}^{\infty}V_{-+}(G_{+}V_{+})^{k}G_{+}V_{+-}}_{E_{3}}\\\\[7.22743pt]
\end{array}$ (21)

where the term $H_{\text{eff}}=H_{\text{targ}}\otimes{P_{-}}$ is the effective
Hamiltonian that we would like to obtain from the perturbative expansion and
$E_{1}$, $E_{2}$, and $E_{3}$ are error terms. Theorem I.1 states that for
$z\in[-\max(z),\max(z)]$, if
$\|\Sigma_{-}(z)-H_{\text{targ}}\otimes{P_{-}}\|\leq\epsilon$ then
$\tilde{H}_{-}$ approximates the spectrum of $H_{\text{targ}}\otimes P_{-}$ by
error at most $\epsilon$. Similar to the triangle inequality derivation shown
in (9), to derive a lower bound for $\Delta$, let
$z\mapsto\max(z)=\|H_{\text{else}}\|+\sum_{i=1}^{m}|\alpha_{i}|+\epsilon$ and
the upper bounds of the error terms $E_{1}$ and $E_{2}$ can be found as

$\begin{array}[]{ccl}\|E_{1}\|&\leq&\displaystyle\frac{\max(z)}{\Delta-\max(z)}\sum_{i=1}^{m}|\alpha_{i}|\leq\frac{\max(z)}{\Delta-\max(z)}\left(\sum_{i=1}^{m}|\alpha_{i}|^{1/2}\right)^{2}\\\\[7.22743pt]
\|E_{2}\|&\leq&\displaystyle\frac{\max(z)}{\Delta-\max(z)}\left(\sum_{i=1}^{m}|\alpha_{i}|^{1/2}\right)^{2}.\end{array}$
(22)

From the definition in Eq. 17 we see that
$\|G_{+}(z)\|\leq\frac{1}{\Delta-\max(z)}$. Hence the norm of $E_{3}$ can be
bounded by

$\begin{array}[]{ccl}\|E_{3}\|&\leq&\displaystyle\sum_{k=1}^{\infty}\frac{\|\sum_{i=1}^{m}({\kappa_{i}}A_{i}+{\lambda_{i}}B_{i})\|^{2}\|H_{\text{else}}+\frac{1}{\Delta}\sum_{i=1}^{m}({\kappa_{i}^{2}}A_{i}^{2}+{\lambda_{i}^{2}}B_{i}^{2}){\openone}\|^{k}}{(\Delta-\max(z))^{k+1}}\\\\[7.22743pt]
&\leq&\displaystyle\sum_{k=1}^{\infty}\frac{2\Delta(\sum_{i=1}^{m}|\alpha_{i}|^{1/2})^{2}(\|H_{\text{else}}\|+\sum_{i=1}^{m}|\alpha_{i}|)^{k}}{(\Delta-\max(z))^{k+1}}\\\\[7.22743pt]
&=&\displaystyle\frac{2\Delta(\sum_{i=1}^{m}|\alpha_{i}|^{1/2})^{2}}{\Delta-\max(z)}\frac{\|H_{\text{else}}\|+\sum_{i=1}^{m}|\alpha_{i}|}{\Delta-\max(z)-(\|H_{\text{else}}\|+\sum_{i=1}^{m}|\alpha_{i}|)}.\end{array}$
(23)

Similar to the discussion in Sec. II, to ensure that
$\|\Sigma_{-}(z)-H_{\text{targ}}\otimes{P_{-}}\|\leq\epsilon$, which is the
condition of Theorem I.1, it is sufficient to let
$\|E_{1}\|+\|E_{2}\|+\|E_{3}\|\leq\epsilon$:

$\begin{array}[]{ccl}\|E_{1}\|+\|E_{2}\|+\|E_{3}\|&\leq&\displaystyle\frac{2\max(z)}{\Delta-\max(z)}\left(\sum_{i=1}^{m}|\alpha_{i}|^{1/2}\right)^{2}\\\\[7.22743pt]
&+&\displaystyle\frac{2\Delta(\sum_{i=1}^{m}|\alpha_{i}|^{1/2})^{2}}{\Delta-\max(z)}\cdot\frac{\|H_{\text{else}}\|+\sum_{i=1}^{m}|\alpha_{i}|}{\Delta-\max(z)-(\|H_{\text{else}}\|+\sum_{i=1}^{m}|\alpha_{i}|)}\\\\[7.22743pt]
&=&\displaystyle\frac{2(\sum_{i=1}^{m}|\alpha_{i}|^{1/2})^{2}(\max(z)+\|H_{\text{else}}\|+\sum_{i=1}^{m}|\alpha_{i}|)}{\Delta-\max(z)-(\|H_{\text{else}}\|+\sum_{i=1}^{m}|\alpha_{i}|)}\leq\epsilon\end{array}$
(24)

where we find the lower bound of $\Delta$ for parallel subdivision gadget

$\Delta\geq\left[\frac{2(\sum_{i=1}^{m}|\alpha_{i}|^{1/2})^{2}}{\epsilon}+1\right](2\|H_{\text{else}}\|+2\sum_{i=1}^{m}|\alpha_{i}|+\epsilon).$
(25)

Note that if one substitutes $m=1$ into Eq. 25 the resulting expression is a
lower bound that is less tight than that in Eq. 14. This is because of the
difference in the perturbation $V$ between Eq. 18 and Eq. 6 which is explained
in the text preceding Eq. 19. Also we observe that the scaling of this lower
bound for $\Delta$ is $O(\text{poly}(m)/\epsilon)$ for $m$ parallel
applications of subdivision gadgets, assuming $|\alpha_{i}|=O(\text{poly}(m))$
for every $i\in\\{1,2,\cdots,m\\}$. This confirms the statement in OT06 ;
KKR06 ; BDLT08  that subdivision gadgets can be applied to multiple terms in
parallel and the scaling of the gap $\Delta$ in the case of $m$ parallel
subdivision gadgets will only differ to that of a single subdivision gadget by
a polynomial in $m$.

_Iterative scheme for $k$\- to 3-body reduction._ The following iterative
scheme summarizes how to use parallel subdivision gadgets for reducing a
$k$-body Ising Hamiltonian to 3-body (Here we use superscript (i) to represent
the $i^{\text{th}}$ iteration and subscript i for labelling objects within the
same iteration):

$\begin{array}[]{c l}\tilde{H}^{(0)}=&H_{\text{targ}};\text{$H_{\text{targ}}$
acts on the Hilbert space $\mathcal{M}^{(0)}$.}\\\ \text{\bf
while}&\text{$\tilde{H}^{(i)}$ is more than 3-body}\\\ &\text{Step 1: Find all
the terms that are no more than 3-body (including $H_{\text{else}}$ from
$\tilde{H}^{(0)}$) in $\tilde{H}^{(i-1)}$}\\\ &\text{$\qquad\quad$ and let
their sum be $H_{\text{else}}^{(i)}$.}\\\ &\text{Step 2: Partition the rest of
the terms in $\tilde{H}^{(i-1)}$ into $\alpha_{1}^{(i)}A_{1}^{(i)}\otimes
B_{1}^{(i)}$, }\\\ &\text{$\qquad\quad$ $\alpha_{2}^{(i)}A_{2}^{(i)}\otimes
B_{2}^{(i)}$, $\cdots$, $\alpha_{m}^{(i)}A_{m}^{(i)}\otimes B_{m}^{(i)}$. Here
$\alpha_{j}^{(i)}$ are coefficients.}\\\ &\text{Step 3: Introduce $m$ ancilla
qubits $w_{1}^{(i)}$, $w_{2}^{(i)}$, $\cdots w_{m}^{(i)}$ and construct
$\tilde{H}^{(i)}$ using the}\\\ &\text{$\qquad\quad$ parallel subdivision
gadget. Let $P^{(i)}_{-}=|0\cdots 0\rangle\langle 0\cdots
0|_{w_{1}^{(i)}\cdots w_{m}^{(i)}}$. Define
$\Pi_{-}^{(i)}=\openone_{\mathcal{M}^{(i)}}\otimes P_{-}^{(i)}$.}\\\
&\text{$\qquad$ 3.1: Apply the penalty Hamiltonian
$H^{(i)}=\sum_{x\in\\{0,1\\}}^{m}h(x)\Delta^{(i)}|x\rangle\langle x|$.}\\\
&\text{$\qquad\qquad$ Here $\Delta^{(i)}$ is calculated by the lower bound in
Eq.\ \ref{eq:D_par_sub}.}\\\ &\text{$\qquad$ 3.2: Apply the perturbation
$V^{(i)}=H_{\text{else}}^{(i)}+\sum_{j=1}^{m}\sqrt{\frac{|\alpha_{j}^{(i)}|\Delta^{(i)}}{2}}(\text{sgn}(\alpha_{j}^{(i)})A_{j}^{(i)}-B_{j}^{(i)})\otimes
X_{w_{j}^{(i)}}$}\\\
&\text{$\qquad\qquad+\sum_{j=1}^{m}|\alpha_{j}^{(i)}|{\openone}$.}\\\
&\text{$\qquad$ 3.3: $\tilde{H}^{(i)}=H^{(i)}+V^{(i)}$ acts on the space
$\mathcal{M}^{(i)}$ and the maximum spectral difference}\\\
&\text{$\qquad\qquad$ between
$\tilde{H}^{(i)}_{-}=\Pi^{(i)}_{-}\tilde{H}^{(i)}\Pi^{(i)}_{-}$ and
$\tilde{H}^{(i-1)}\otimes P^{(i)}_{-}$ is at most $\epsilon$.}\\\
&\text{$i\rightarrow{i+1}$}\\\ \text{\bf end}&\\\ \end{array}$ (26)

${S_{1}}{S_{2}}{S_{3}}{S_{4}}|{S_{5}}{S_{6}}{S_{7}}$iteration (tree depth)
$i$0.05(-0.5,3.55)(7.5,3.55)
$i=1$${S_{1}}{S_{2}}{S_{3}}|{S_{4}}X_{u_{1}}$$X_{u_{1}}{S_{5}}|{S_{6}}{S_{7}}$0.05(-0.5,2.3)(7.5,2.3)
$i=2$${S_{1}}{S_{2}}|{S_{3}}X_{u_{2}}$$X_{u_{2}}{S_{4}}X_{u_{1}}$$X_{u_{1}}{S_{5}}{X_{u_{3}}}$$X_{u_{3}}{S_{6}}{S_{7}}$0.05(-0.5,1.2)(7.5,1.2)
$i=3$${S_{1}}{S_{2}}X_{u_{4}}$$X_{u_{4}}{S_{3}}X_{u_{2}}$

(a)

(b) (c)

Figure 3: (a) Reduction tree diagram for reducing a 7-body term to 3-body
using parallel subdivision gadgets. Each $S_{i}$ is a single-qubit Pauli
operator acting on qubit $i$. The vertical lines $|$ show where the
subdivisions are made at each iteration to each term. (b) An example where we
consider the target Hamiltonian $H_{\text{targ}}=\alpha
S_{1}S_{2}S_{3}S_{4}S_{5}S_{6}S_{7}$ with $\alpha=5\times 10^{-3}$,
$S_{i}=X_{i}$, $\forall i\in\\{1,2,\cdots,7\\}$, and reduce it to 3-body
according to (a) up to error $\epsilon=5\times 10^{-4}$. This plot shows the
energy gap applied onto the ancilla qubits introduced at each iteration. (c)
The spectral error between the gadget Hamiltonian at each iteration
$\tilde{H}^{(i)}$ and the target Hamiltonian $H_{\text{targ}}$. For both
(b)(c) the data labelled as “numerical” correspond to the case where during
each iteration $\Delta^{(i)}$ is optimized such that the maximum spectral
difference between $\Pi_{-}^{(i)}\tilde{H}^{(i)}\Pi_{-}^{(i)}$ and
$\tilde{H}^{(i-1)}\otimes P^{(i)}_{-}$ is $\epsilon$. For definitions of
$\Delta^{(i)}$, $\tilde{H}^{(i)}$, $\Pi^{(i)}_{-}$ and $P^{(i)}_{-}$, see Eq.
26. Those labelled as ‘analytical’ correspond to cases where each iteration
uses the gap bound derived in Eq. 25.

We could show that after $s$ iterations, the maximum spectral error between
$\Pi^{(s)}_{-}\tilde{H}^{(s)}\Pi^{(s)}_{-}$ and
$\tilde{H}^{(0)}\bigotimes_{i=1}^{s}P^{(s)}_{-}$ is guaranteed to be within
$s\epsilon$. Suppose we would like to make target Hamiltonian $\tilde{H}_{0}$,
we construct a gadget $\tilde{H}=H^{(1)}+V^{(1)}$ according to algorithm (26),
such that $|\lambda(\tilde{H}^{(1)})-\lambda(\tilde{H}^{(0)})|\leq\epsilon$
for low-lying eigenvalues $\lambda(\cdot)$. Note that in a precise sense we
should write
$|\lambda(\Pi_{-}^{(1)}\tilde{H}^{(1)}\Pi_{-}^{(1)})-\lambda(\tilde{H}^{(0)}\otimes
P_{-}^{(0)})|$. Since the projectors $\Pi_{-}^{(i)}$ and $P_{-}^{(i)}$ do not
affect the low-lying spectrum of $\tilde{H}^{(i)}$ and $\tilde{H}^{(i-1)}$,
for simplicity and clarity we write only $\tilde{H}^{(i-1)}$ and
$\tilde{H}^{(i)}$. After $\tilde{H}^{(1)}$ is introduced, according to
algorithm (26) the second gadget $\tilde{H}^{(2)}$ is then constructed by
considering the _entire_ $\tilde{H}^{(1)}$ as the new target Hamiltonian and
introducing ancilla particles with unperturbed Hamiltonian $H^{(2)}$ and
perturbation $V^{(2)}$ such that the low-energy spectrum of $\tilde{H}^{(2)}$
approximates the spectrum of $\tilde{H}^{(1)}$ up to error $\epsilon$. In
other words $|\lambda(\tilde{H}^{(1)})-\lambda(\tilde{H}^{(2)})|\leq\epsilon$.
With the serial application of gadgets we have produced a sequence of
Hamiltonians
$\tilde{H}^{(0)}\rightarrow\tilde{H}^{(1)}\rightarrow\tilde{H}^{(2)}\rightarrow\cdots\rightarrow\tilde{H}^{(k)}$
where $\tilde{H}^{(0)}$ is the target Hamiltonian and each subsequent gadget
Hamiltonian $\tilde{H}^{(i)}$ captures the _entire_ previous gadget
$\tilde{H}^{(i-1)}$ in its low-energy sector with
$|\lambda(\tilde{H}^{(i)})-\lambda(\tilde{H}^{(i-1)})|\leq\epsilon$. Hence to
bound the spectral error between the last gadget $\tilde{H}^{(k)}$ and the
target Hamiltonian $\tilde{H}^{(0)}$ we could use triangle inequality:
$|\lambda(\tilde{H}^{(s)})-\lambda(\tilde{H}^{(0)})|\leq|\lambda(\tilde{H}^{(s)})-\lambda(\tilde{H}^{(s-1)})|+\cdots+|\lambda(\tilde{H}^{(1)})-\lambda(\tilde{H}^{(0)})|\leq
s\epsilon$.

_Total number of iterations for a $k$\- to 3-body reduction._ In general,
given a $k$-body Hamiltonian, we apply the following parallel reduction scheme
at each iteration until every term is 3-body: if $k$ is even, this reduces it
to two $(k/2+1)$-body terms; if $k$ is odd, this reduces it to a
$(\frac{k+1}{2}+1)$\- and a $(\frac{k-1}{2}+1)$-body term. Define a function
$f$ such that a $k$-body term needs $f(k)$ iterations to be reduced to 3-body.
Then we have the recurrence

$f(k)=\left\\{\begin{array}[]{cr}\displaystyle
f\left(\frac{k}{2}+1\right)+1&\text{$k$ even}\\\\[7.22743pt] \displaystyle
f\left(\frac{k+1}{2}+1\right)+1&\text{$k$ odd}\end{array}\right.$ (27)

with $f(3)=0$ and $f(4)=1$. One can check that
$f(k)=\lceil\log_{2}(k-2)\rceil$, $k\geq 4$ satisfies this recurrence.
Therefore, using subdivision gadgets, one can reduce a $k$-body interaction to
$3$-body in $s=\lceil\log_{2}(k-2)\rceil$ iterations and the spectral error
between $\tilde{H}^{(s)}$ and $\tilde{H}^{(0)}$ is within
$\lceil\log_{2}(k-2)\rceil\epsilon$.

_Gap scaling._ From the iterative scheme shown previously one can conclude
that $\Delta^{(i+1)}=\Theta(\epsilon^{-1}(\Delta^{(i)})^{3/2})$ for the
$(i+1)^{\text{th}}$ iteration, which implies that for a total of $s$
iterations,

$\Delta^{(s)}=\Theta\left(\epsilon^{-2[(3/2)^{s-1}-1]}(\Delta^{(1)})^{(3/2)^{s-1}}\right).$
(28)

Since $s=\lceil\log_{2}(k-2)\rceil$ and $\Delta^{(1)}=\Theta(\epsilon^{-1})$
we have

$\Delta^{(s)}=\Theta\left(\epsilon^{-3(\frac{1}{2}\lceil
k-2\rceil)^{\log_{2}(3/2)}-2}\right)=\Theta\left(\epsilon^{-\text{poly}(k)}\right)$
(29)

accumulating exponentially as a function of $k$. The exponential nature of the
scaling with respect to $k$ agrees with results by Bravyi et al. BDLT08 .
However, in our construction, due to the improvement of gap scaling in a
single subdivision gadget from $\Delta=\Theta(\epsilon^{-2})$ to
$\Theta(\epsilon^{-1})$, the scaling exponents in
$\Delta^{(i+1)}=\Theta(\epsilon^{-1}(\Delta^{(i)})^{3/2})$ are also improved
quadratically over those in BDLT08 , which is
$\Delta^{(i+1)}=\Theta(\epsilon^{-2}(\Delta^{(i)})^{3})$.

_Qubit cost._ Based on the reduction scheme described in Eq. 26 (illustrated
in Fig. 3a for 7-body), the number of ancilla qubits needed for reducing a
$k$-body term to 3-body is $k-3$. Suppose we are given a $k$-body target term
$S_{1}S_{2}\cdots S_{k}$ (where all of the operators $S_{i}$ act on separate
spaces) and we would like to reduce it to 3-body using the iterative scheme
Eq. 26. At each iteration, if we describe every individual subdivision gadget
by a vertical line $|$ at the location where the partition is made, for
example $S_{1}S_{2}S_{3}S_{4}|S_{5}S_{6}S_{7}$ in the case of the first
iteration in Fig. 3a, then after $\lceil\log_{2}(k-2)\rceil$ iterations all
the partitions made to the $k$-body term can be described as
$S_{1}S_{2}|S_{3}|S_{4}|\cdots|S_{k-2}|S_{k-1}S_{k}$. Note that there are
$k-3$ vertical lines in total, each corresponding to an ancilla qubit needed
for a subdivision gadget. Therefore in total $k-3$ ancilla qubits are needed
for reducing a $k$-body term to 3-body.

_Example: Reducing 7-body to 3-body._ We have used numerics to test the
reduction algorithm Eq. 26 on a target Hamiltonian $H_{\text{targ}}=\alpha
S_{1}S_{2}S_{3}S_{4}S_{5}S_{6}S_{7}$. Here we let $S_{i}=X_{i}$, $\forall
i\in\\{1,2,\cdots,7\\}$, $\epsilon=5\times 10^{-4}$ and $\alpha=5\times
10^{-3}$. During each iteration the values of $\Delta^{(i)}$ are assigned
according to the lower bound in Eq. 25. From Fig. 3c we can see that the lower
bounds are sufficient for keeping the total spectral error between
$\tilde{H}_{-}^{(3)}$ and $\tilde{H}^{(0)}\bigotimes_{i=1}^{3}P^{(i)}_{-}$
within $3\epsilon$. Furthermore, numerical search is also used at each
iteration to find the minimum value of $\Delta^{(i)}$ so that the spectral
error between $\Pi_{-}^{(i)}\tilde{H}^{(i)}\Pi_{-}^{(i)}$ and
$\tilde{H}^{(i-1)}\bigotimes_{j=1}^{i}P^{(j)}_{-}$ is $\epsilon$. The
numerically found gaps $\Delta^{(i)}$ are much smaller than their analytical
counterparts at each iteration (Fig. 3b), at the price that the error is
larger (Fig. 3c). In both the numerical and the analytical cases, the error
appears to accumulate linearly as the iteration proceeds.

##  IV Improved Oliveira and Terhal 3- to 2-body gadget

Summary. Subdivision gadgets cannot be used for reducing from 3- to 2-body;
accordingly, the final reduction requires a different type of gadget KKR06 ;
OT06 ; BDLT08 . Consider 3-body target Hamiltonian of the form
$H_{\text{targ}}=H_{\text{else}}+\alpha A\otimes B\otimes C$. Here $A$, $B$
and $C$ are unit-norm Hermitian operators acting on separate spaces
$\mathcal{A}$, $\mathcal{B}$ and $\mathcal{C}$. Here we focus on the gadget
construction introduced in Oliveira and Terhal OT06  and also used in Bravyi,
DiVincenzo, Loss and Terhal BDLT08 . To accomplish the 3- to 2-body reduction,
we introduce an ancilla spin $w$ and apply a penalty Hamiltonian
$H=\Delta|1\rangle\langle{1}|_{w}$. We then add a perturbation $V$ of form,

$V=H_{\text{else}}+\mu C\otimes|1\rangle\langle{1}|_{w}+(\kappa A+\lambda
B)\otimes X_{w}+V_{1}+V_{2}$ (30)

where $V_{1}$ and $V_{2}$ are 2-local compensation terms (details presented
later in this section):

$\begin{array}[]{ccl}V_{1}&=&\displaystyle\frac{1}{\Delta}(\kappa^{2}+\lambda^{2})|0\rangle\langle{0}|_{w}+\frac{2\kappa\lambda}{\Delta}{A}\otimes{B}-\frac{1}{\Delta^{2}}(\kappa^{2}+\lambda^{2})\mu{C}\otimes|0\rangle\langle{0}|_{w}\\\\[7.22743pt]
V_{2}&=&\displaystyle-\frac{2\kappa\lambda}{\Delta^{3}}\text{sgn}(\alpha)\bigg{[}(\kappa^{2}+\lambda^{2})|0\rangle\langle{0}|_{w}+2\kappa\lambda{A}\otimes{B}\bigg{]}.\end{array}$
(31)

Here we let
$\kappa=\text{sgn}(\alpha)\left({\alpha}/{2}\right)^{1/3}\Delta^{3/4}$,
$\lambda=\left({\alpha}/{2}\right)^{1/3}\Delta^{3/4}$ and
$\mu=\left({\alpha}/{2}\right)^{1/3}\Delta^{1/2}$.

For sufficiently large $\Delta$, the low-lying spectrum of the gadget
Hamiltonian $\widetilde{H}$ captures the entire spectrum of $H_{\text{targ}}$
up to arbitrary error $\epsilon$. In the construction of BDLT08  it is shown
that $\Delta=\Theta(\epsilon^{-3})$ is sufficient. In KKR06 ,
$\Delta=\Theta(\epsilon^{-3})$ is also assumed, though the construction of $V$
is slightly different from Eq. 30. By adding terms in $V$ to compensate for
the perturbative error due to the modification, we find that
$\Delta=\Theta(\epsilon^{-2})$ is sufficient for accomplishing the 3- to
2-body reduction:

$\Delta\geq\frac{1}{4}({-b+\sqrt{b^{2}-4c}})^{2}$ (32)

where $b$ and $c$ are defined as

$\begin{array}[]{ccl}b&=&\displaystyle-\left[\xi+\frac{2^{4/3}\alpha^{2/3}}{\epsilon}(\max{z}+\eta+\xi^{2})\right]\\\\[7.22743pt]
c&=&\displaystyle-\left(1+\frac{2^{4/3}\alpha^{2/3}}{\epsilon}\xi\right)(\max{z}+\eta)\end{array}$
(33)

with $\max z=\|H_{\text{else}}\|+|\alpha|+\epsilon$,
$\eta=\|H_{\text{else}}\|+2^{2/3}\alpha^{4/3}$ and
$\xi=2^{-1/3}\alpha^{1/3}+2^{1/3}\alpha^{2/3}$. From Eq. 32 we can see the
lower bound to $\Delta$ is $\Theta({\epsilon^{-2}})$. Our improvement results
in a power of $\epsilon^{-1}$ reduction in the gap. For the dependence of
$\Delta$ on $\|H_{\text{else}}\|$, $\alpha$ and $\epsilon^{-1}$ for both the
original OT06  and the optimized case, see Fig. 4. Results show that the bound
in Eq. 32 is tight with respect to the minimum $\Delta$ numerically found that
yields the spectral error between $\tilde{H}_{-}$ and
$H_{\text{targ}}\otimes|0\rangle\langle{0}|_{w}$ to be $\epsilon$.

Analysis. We will proceed by first presenting the improved construction of the
3- to 2-body gadget and then show that $\Delta=\Theta(\epsilon^{-2})$ is
sufficient for the spectral error to be $\leq\epsilon$. Then we present the
construction in the literature OT06 ; BDLT08  and argue that
$\Delta=\Theta(\epsilon^{-3})$ is required for yielding a spectral error
between $\tilde{H}$ and $H_{\text{eff}}$ within $\epsilon$ using this
construction.

In the improved construction we define the perturbation $V$ as in Eq. 30. Here
the coefficients are chosen to be $\kappa=\Theta(\Delta^{3/4})$,
$\lambda=\Theta(\Delta^{3/4})$ and $\mu=\Theta(\Delta^{1/2})$. In order to
show that the assigned powers of $\Delta$ in the coefficients are optimal, we
introduce a parameter $r$ such that

${\kappa}=\text{sgn}(\alpha)\left(\frac{\alpha}{2}\right)^{1/3}\Delta^{r},\qquad{\lambda}=\left(\frac{\alpha}{2}\right)^{1/3}\Delta^{r},\qquad{\mu}=\left(\frac{\alpha}{2}\right)^{1/3}\Delta^{2-2r}.$
(34)

It is required that $\|V\|\leq\Delta/2$ (Theorem I.1) for the convergence of
the perturbative series. Therefore let $r<1$ and $2-2r<1$, which gives
$1/2<r<1$. With the definitions $\mathcal{L}_{-}$ and $\mathcal{L}_{+}$ being
the ground and excited state subspaces respectively, $V_{-}$, $V_{+}$,
$V_{-+}$, $V_{+-}$ can be calculated as the following:

$\begin{array}[]{ccl}V_{-}&=&\displaystyle\left[H_{\text{else}}+\frac{1}{\Delta}(\kappa
A+\lambda B)^{2}-\frac{1}{\Delta}(\kappa^{2}+\lambda^{2})\mu
C-\frac{2\kappa\lambda}{\Delta^{3}}\text{sgn}(\alpha)(\kappa A+\lambda
B)^{2}\right]\otimes|0\rangle\langle{0}|_{w}\\\\[7.22743pt]
V_{+}&=&\displaystyle\left[H_{\text{else}}+\mu
C+\frac{2\kappa\lambda}{\Delta}A\otimes
B-\frac{4\kappa^{2}\lambda^{2}}{\Delta^{3}}\text{sgn}(\alpha)A\otimes
B\right]\otimes|1\rangle\langle{1}|_{w}\\\\[7.22743pt]
V_{-+}&=&\displaystyle(\kappa A+\lambda
B)\otimes|0\rangle\langle{1}|_{w}\\\\[7.22743pt] V_{+-}&=&\displaystyle(\kappa
A+\lambda B)\otimes|1\rangle\langle{0}|_{w}.\end{array}$ (35)

The self-energy expansion, referring to Eq. 3, becomes

$\begin{array}[]{ccl}\Sigma_{-}(z)&=&\displaystyle
V_{-}+\frac{1}{z-\Delta}V_{-+}V_{+-}+\frac{1}{(z-\Delta)^{2}}V_{-+}V_{+}V_{+-}+\sum_{k=2}^{\infty}\frac{V_{-+}V_{+}^{k}V_{+-}}{(z-\Delta)^{k+1}}\\\\[7.22743pt]
&=&\displaystyle\underbrace{H_{\text{else}}}_{(a)}+\underbrace{\frac{1}{\Delta}(\kappa
A+\lambda
B)^{2}}_{(b)}\underbrace{-\frac{1}{\Delta}(\kappa^{2}+\lambda^{2})\mu
C}_{(c)}\underbrace{-\frac{2\kappa\lambda}{\Delta^{3}}\text{sgn}(\alpha)(\kappa
A+\lambda B)^{2}}_{(d)}+\underbrace{\frac{1}{z-\Delta}(\kappa A+\lambda
B)^{2}}_{(e)}\\\\[7.22743pt] &+&\displaystyle\frac{1}{(z-\Delta)^{2}}(\kappa
A+\lambda B)\left[\underbrace{H_{\text{else}}}_{(f)}+\underbrace{\mu
C}_{(g)}+\underbrace{\frac{2\kappa\lambda}{\Delta}A\otimes
B}_{(h)}\underbrace{-\frac{4\kappa^{2}\lambda^{2}}{\Delta^{3}}\text{sgn}(\alpha)A\otimes
B}_{(i)}\right](\kappa A+\lambda B)\\\\[7.22743pt]
&+&\displaystyle\underbrace{\sum_{k=2}^{\infty}\frac{V_{-+}V_{+}^{k}V_{+-}}{(z-\Delta)^{k+1}}}_{(j)}.\end{array}$
(36)

Now we rearrange the terms in the self energy expansion so that the target
Hamiltonian arising from the leading order terms can be separated from the
rest, whcih are error terms. Observe that term $(g)$ combined with the factors
outside the bracket could give rise to a 3-body $A\otimes B\otimes C$ term:

$\begin{array}[]{ccl}\displaystyle\frac{1}{(z-\Delta)^{2}}(\kappa A+\lambda
B)^{2}\mu
C&=&\displaystyle\underbrace{\frac{2\kappa\lambda\mu}{\Delta^{2}}A\otimes
B\otimes
C}_{(g_{1})}+\underbrace{\left(\frac{1}{(z-\Delta)^{2}}-\frac{1}{\Delta^{2}}\right)2{\kappa}{\lambda}{\mu}{A}\otimes{B}\otimes{C}}_{(g_{2})}\\\\[7.22743pt]
&+&\displaystyle\underbrace{\frac{1}{(z-\Delta)^{2}}(\kappa^{2}+\lambda^{2})\mu
C}_{(g_{3})}.\end{array}$ (37)

Here $(g_{1})$ combined with term $(a)$ in (36) gives $H_{\text{targ}}$.
$(g_{2})$ and $(g_{3})$ are error terms. Now we further rearrange the error
terms as the following. We combine term $(b)$ and $(e)$ to form $E_{1}$, term
$(c)$ and $(g_{3})$ to form $E_{2}$, term $(f)$ and the factors outside the
bracket to be $E_{3}$. Rename $(g_{2})$ to be $E_{4}$. Using the identity
$({\kappa}{A}+{\lambda}{B})({A}\otimes{B})({\kappa}{A}+{\lambda}{B})=\text{sgn}(\alpha)({\kappa}{A}+{\lambda}{B})^{2}$
we combine term $(d)$ and $(h)$ along with the factors outside the bracket to
be $E_{5}$. Rename $(i)$ to be $E_{6}$ and $(j)$ to be $E_{7}$. The rearranged
self-energy expanision reads

$\begin{array}[]{ccl}\Sigma_{-}(z)&=&\displaystyle\bigg{[}\underbrace{H_{\text{else}}+\frac{2{\kappa}{\lambda}{\mu}}{\Delta^{2}}{A}\otimes{B}\otimes{C}}_{H_{\text{targ}}}+\underbrace{\left(\frac{1}{\Delta}+\frac{1}{z-\Delta}\right)({\kappa}{A}+{\lambda}{B})^{2}}_{E_{1}}\\\\[7.22743pt]
&+&\displaystyle\underbrace{\left(\frac{1}{(z-\Delta)^{2}}-\frac{1}{\Delta^{2}}\right)({\kappa}^{2}+{\lambda}^{2}){\mu}{C}}_{E_{2}}+\underbrace{\frac{1}{(z-\Delta)^{2}}({\kappa}{A}+{\lambda}{B})H_{\text{else}}({\kappa}{A}+{\lambda}{B})}_{E_{3}}\\\\[7.22743pt]
&+&\displaystyle\underbrace{\left(\frac{1}{(z-\Delta)^{2}}-\frac{1}{\Delta^{2}}\right)2{\kappa}{\lambda}{\mu}{A}\otimes{B}\otimes{C}}_{E_{4}}+\underbrace{\left(\frac{1}{(z-\Delta)^{2}}-\frac{1}{\Delta^{2}}\right)\frac{2{\kappa}{\lambda}}{\Delta}\text{sgn}(\alpha)({\kappa}{A}+{\lambda}{B})^{2}}_{E_{5}}\\\\[7.22743pt]
&-&\underbrace{\frac{1}{(z-\Delta)^{2}}\cdot\frac{4{\kappa}^{2}{\lambda}^{2}}{\Delta^{3}}({\kappa}{A}+{\lambda}{B})^{2}}_{E_{6}}\bigg{]}\otimes|0\rangle\langle{0}|_{w}+\underbrace{\sum_{k=2}^{\infty}\frac{V_{-+}V_{+}^{k}V_{+-}}{(z-\Delta)^{k+1}}}_{E_{7}}.\end{array}$
(38)

We bound the norm of each error term in the self energy expansion Eq. 38 by
substituting the definitions of $\kappa$, $\lambda$ and $\mu$ in Eq. 34 and
letting $z$ be the maximum value permitted by Theorem I.1 which is $\max
z=|\alpha|+\epsilon+\|H_{\text{else}}\|$:

$\|E_{1}\|\leq\displaystyle\frac{\max{z}{\cdot}2^{4/3}\alpha^{2/3}\Delta^{2r-1}}{\Delta-\max{z}}=\Theta(\Delta^{2r-2}),\qquad\|E_{2}\|\leq\displaystyle\frac{(2\Delta-\max{z})\max{z}}{(\Delta-\max{z})^{2}}\cdot\alpha=\Theta(\Delta^{-1})$
(39)
$\|E_{3}\|\leq\displaystyle\frac{2^{4/3}\alpha^{2/3}\Delta^{2r}\|H_{\text{else}}\|}{(\Delta-\max{z})^{2}}=\Theta(\Delta^{2r-2}),\qquad\|E_{4}\|\leq\displaystyle\frac{(2\Delta-\max{z})\max{z}}{(\Delta-\max{z})^{2}}\cdot\alpha=\Theta(\Delta^{-1})$
(40)
$\|E_{5}\|\leq\displaystyle\frac{(2\Delta-\max{z})\max{z}}{(\Delta-\max{z})^{2}}\cdot{2^{5/3}}\alpha^{4/3}\Delta^{4r-3}=\Theta(\Delta^{4r-4}),\qquad\|E_{6}\|\leq\displaystyle\frac{4\alpha^{2}\Delta^{6r-3}}{(\Delta-\max{z})^{2}}=\Theta(\Delta^{6r-5})$
(41)
$\begin{array}[]{ccl}\|E_{7}\|&\leq&\displaystyle\sum_{k=2}^{\infty}\left\|\frac{({\kappa}A+{\lambda}B)\left(H_{\text{else}}+{\mu}C+\frac{2{\kappa}{\lambda}}{\Delta}\left(1+\frac{2{\kappa}{\lambda}}{\Delta^{2}}\right)A\otimes
B\right)^{k}({\kappa}A+{\lambda}B)}{(\Delta-\max{z})^{k+1}}\right\|\\\\[7.22743pt]
&\leq&\displaystyle\frac{2^{4/3}\alpha^{2/3}\Delta^{2r}}{(\Delta-\max{z})}\sum_{k=2}^{\infty}\frac{\left(\|H_{\text{else}}\|+2^{-1/3}\alpha^{1/3}\Delta^{2-2r}+2^{1/3}\alpha^{2/3}\Delta^{2r-1}+2^{2/3}\alpha^{4/3}\Delta^{4r-3}\right)^{k}}{(\Delta-\max{z})^{k}}\\\\[7.22743pt]
&=&\displaystyle\Theta(\Delta^{\max\\{1-2r,6r-5,10r-9\\}}).\end{array}$ (42)

Now the self energy expansion can be written as

$\Sigma_{-}(z)=H_{\text{targ}}\otimes|0\rangle\langle{0}|_{w}+\Theta(\Delta^{f(r)})$

where the function $f(r)<0$ determines the dominant power in $\Delta$ from
$\|E_{1}\|$ through $\|E_{6}\|$:

$f(r)=\max\\{1-2r,6r-5\\},\quad\frac{1}{2}<r<1.$ (43)

In order to keep the error $O(\epsilon)$, it is required that
$\Delta=\Theta(\epsilon^{1/f(r)})$. To optimize the gap scaling as a function
of $\epsilon$, $f(r)$ must take the minimum value. As is shown in Fig. 5b,
when $r=3/4$, the minimum value $f(r)=-1/2$ is obtained, which corresponds to
$\Delta=\Theta(\epsilon^{-2})$. We have hence shown that the powers of
$\Delta$ in the assignments of $\kappa$, $\lambda$ and $\mu$ in Eq. 34 are
optimal for the improved gadget construction. The optimal scaling of
$\Theta(\epsilon^{-2})$ is also numerically confirmed in Fig. 4a. As one can
see, the optimized slope $\text{d}\log\Delta/\text{d}\log\epsilon^{-1}$ is
approximately 2 for small $\epsilon$.

(a)(b)

Figure 4: Comparison between our 3- to 2-body gadget with that of Oliveira and Terhal OT06 . As $\Delta$ is not explicitly assigned as a function of $\alpha$, $\|H_{\text{else}}\|$ and $\epsilon$ in OT06 , we numerically find the optimal $\Delta$ values for their constructions (marked as “[OT06]”). (a) shows the scaling of the gap $\Delta$ as a function of error tolerance $\epsilon$. (b) shows the gap $\Delta$ as a function of the desired coupling $\alpha$. For the meanings of the labels in the legend, see Fig. 2. The fixed parameters in each subplots are: (a) $\|H_{\text{else}}\|=0$, $\alpha=1$. (b) $\epsilon=0.01$, $\|H_{\text{else}}\|=0$. Note that our constructions have improved the $\Delta$ scaling for the ranges of $\alpha$ and $\epsilon$ considered.  $r$0$f(r)$0.1(2,4)(6,0) $1-2r$1$\frac{1}{2}$0.1(4,0)(6,4) $4r-3$0.1(4.666,0)(6,4) $6r-5$$1$$\frac{2}{3}$0.03(4.6666666,1.3333333)(4.666,2) 0.03(4.6666666,1.3333333)(2,1.333) $-\frac{1}{3}$ |  $r$0$f(r)$0.1(2,4)(6,0) $1-2r$1$\frac{1}{2}$0.1(4.666,0)(6,4) $6r-5$$1$$\frac{3}{4}$0.03(5,1)(5,2) 0.03(5,1)(2,1) $-\frac{1}{2}$
---|---
(a) | (b)
Figure 5: The function $f(r)$ shows the dominant power of $\Delta$ in the
error terms in the perturbative expansion. (a) When the error term $E_{4}$ in
Eq. 51, which contributes to the $4r-3$ component of $f(r)$ in Eq. 53, is not
compensated in the original construction by Oliveira and Terhal, the dominant
power of $\Delta$ in the error term $f(r)$ takes minimum value of $-1/3$,
indicating that $\Delta=\Theta(\epsilon^{-3})$ is required. (b) In the
improved construction, $\min_{r\in(1/2,1)}f(r)=-1/2$ indicating that
$\Delta=\Theta(\epsilon^{-2})$.

One natural question to ask next is whether it is possible to further improve
the gap scaling as a function of $\epsilon$. This turns out to be difficult.
Observe that the $6r-5$ component of $f(r)$ in Eq. 43 comes from $E_{6}$ and
$E_{7}$ in Eq. 38. In $E_{7}$, the $\Theta(\Delta^{6r-5})$ contribution is
attributed to the term $\frac{1}{\Delta}({\kappa}{A}+{\lambda}{B})^{2}$ in
$V_{1}$ of Eq. 31, which is intended for compensating the $2^{\text{nd}}$
order perturbative term and therefore cannot be removed from the construction.

We now let $r=3/4$ be a fixed constant and derive the lower bound for $\Delta$
such that for given $\alpha$, $H_{\text{else}}$ and $\epsilon$, the spectral
error between the effective Hamiltonian
$H_{\text{eff}}=H_{\text{targ}}\otimes|0\rangle\langle{0}|_{w}$ and
$\tilde{H}_{-}$ is within $\epsilon$. This amounts to satisfying the condition
of Theorem I.1:

$\|\Sigma_{-}(z)-H_{\text{eff}}\|\leq\epsilon.$ (44)

Define the total error $E=\Sigma_{-}(z)-H_{\text{eff}}=E_{1}+\cdots+E_{7}$.
For convenience we also define $\eta=\|H_{\text{else}}\|+2^{2/3}\alpha^{4/3}$
and $\xi=2^{-1/3}\alpha^{1/3}+2^{1/3}\alpha^{2/3}$. Then

$\begin{array}[]{ccl}\|E_{7}\|&\leq&\displaystyle\frac{2^{4/3}\alpha^{2/3}\Delta^{3/2}}{\Delta-\max{z}}\sum_{k=2}^{\infty}\frac{(\eta+\xi\Delta^{1/2})^{k}}{(\Delta-\max{z})^{k}}=\frac{2^{4/3}\alpha^{2/3}\Delta^{3/2}}{\Delta-\max{z}-(\eta+\xi\Delta^{1/2})}\left(\frac{\eta+\xi\Delta^{1/2}}{\Delta-\max{z}}\right)^{2}.\end{array}$
(45)

The upper bound for $\|E\|$ is then found by summing over Eq. 39, 40, 41 and
45:

$\begin{array}[]{ccl}\|E\|&\leq&\displaystyle\frac{\max{z}{\cdot}2^{4/3}\alpha^{2/3}\Delta^{1/2}}{\Delta-\max{z}}+\frac{(2\Delta-\max{z})\max{z}}{(\Delta-\max{z})^{2}}\cdot{2}^{4/3}\alpha^{3/2}\xi+\frac{2^{4/3}\alpha^{2/3}\Delta^{3/2}\eta}{(\Delta-\max{z})^{2}}\\\\[14.45377pt]
&+&\displaystyle\frac{2^{4/3}\alpha^{2/3}\Delta^{3/2}}{\Delta-\max{z}-(\eta+\xi\Delta^{1/2})}\left(\frac{\eta+\xi\Delta^{1/2}}{\Delta-\max{z}}\right)^{2}.\\\\[14.45377pt]
\end{array}$ (46)

By rearranging the terms in Eq. 46 we arrive at a simplified expression for
the upper bound presented below. Requiring the upper bound of $\|E\|$ to be
within $\epsilon$ gives

$\begin{array}[]{ccl}\|E\|&\leq&\displaystyle
2^{4/3}\alpha^{2/3}\frac{(\max{z}+\eta+\xi^{2})\Delta^{1/2}+\xi(\max{z}+\eta)}{\Delta-\xi\Delta^{1/2}-(\max{z}+\eta)}\leq\epsilon.\end{array}$
(47)

Eq. 47 is a quadratic constraint with respect to $\Delta^{1/2}$. Solving the
inequality gives the lower bound of $\Delta$ given in Eq. 32. Note here that
$\Delta=\Theta(\epsilon^{-2})$, which improves over the previously assumed
$\Delta=\Theta(\epsilon^{-3})$ in the literature OT06 ; KKR06 ; BDLT08 . This
bound is shown in Fig. 4b as the “analytical lower bound”. Comparison between
the analytical lower bound and the numerically optimized gap in Fig. 4b
indicates that the lower bound is relatively tight when
$\|H_{\text{else}}\|=0$.

_Comparison with Oliveira and TerhalOT06 ._ Given operators $Q$, $R$ and $T$
acting on separate spaces $\mathcal{A}$, $\mathcal{B}$ and $\mathcal{C}$
respectively, the 3- to 2-body construction in OT06 ; KKR06  approximates the
target Hamiltonian $H_{\text{targ}}=H_{\text{else}}+Q\otimes R\otimes T$. In
order to compare with their construction, however, we let
$\alpha=\|Q\|\cdot\|R\|\cdot\|T\|$ and define $Q=\alpha^{1/3}A$,
$R=\alpha^{1/3}B$ and $T=\alpha^{1/3}C$. Hence the target Hamiltonian
$H_{\text{targ}}=H_{\text{else}}+\alpha A\otimes B\otimes C$ with $A$, $B$ and
$C$ being unit-norm Hermitian operators. Introduce an ancilla qubit $w$ and
apply the penalty Hamiltonian $H=\Delta|1\rangle\langle{1}|_{w}$. In the
construction by Oliveira and Terhal OT06 , the perturbation $V$ is defined as

$V=H_{\text{else}}\otimes\openone_{w}+{\mu}C\otimes|1\rangle\langle{1}|_{w}+({\kappa}A+{\lambda}B)\otimes
X_{w}+V^{\prime}_{1}$ (48)

where the compensation term $V^{\prime}_{1}$ is

$\displaystyle
V^{\prime}_{1}=\frac{1}{\Delta}({\kappa}A+{\lambda}B)^{2}-\frac{1}{\Delta^{2}}(\kappa^{2}A^{2}+\lambda^{2}B^{2}){\mu}C.$
(49)

Comparing Eq. 49 with the expression for $V_{1}$ in Eq. 31, one observes that
$V_{1}$ slightly improves over $V^{\prime}_{1}$ by projecting 1-local terms to
$\mathcal{L}_{-}$ so that $V$ will have less contribution to $V_{+}$, which
reduces the high order error terms in the perturbative expansion. However,
this modification comes at a cost of requiring more 2-local terms in the
perturbation $V$.

From the gadget construction shown in (OT06, , Eq. 26), the equivalent choices
of the coefficients ${\kappa}$, ${\lambda}$ and ${\mu}$ are

${\kappa}=-\left(\frac{\alpha}{2}\right)^{1/3}\frac{1}{\sqrt{2}}\Delta^{r},\quad{\lambda}=\left(\frac{\alpha}{2}\right)^{1/3}\frac{1}{\sqrt{2}}\Delta^{r},\quad{\mu}=-\left(\frac{\alpha}{2}\right)^{1/3}\Delta^{2-2r}$
(50)

where $r=2/3$ in the constructions used in OT06 ; BDLT08 . In fact this value
of $r$ is optimal for the construction in the sense that it leads to the
optimal gap scaling $\Delta=\Theta(\epsilon^{-3})$. Expanding the self-energy
to $3^{\text{rd}}$ order, following a similar procedure as in (36), we have

$\begin{array}[]{ccl}\Sigma_{-}(z)&=&\displaystyle\bigg{[}\underbrace{H_{\text{else}}+\frac{2{\kappa}{\lambda}{\mu}}{\Delta^{2}}{A}\otimes{B}\otimes{C}}_{H_{\text{targ}}}+\underbrace{\left(\frac{1}{\Delta}+\frac{1}{z-\Delta}\right)({\kappa}{A}+{\lambda}{B})^{2}}_{E_{1}}\\\\[7.22743pt]
&+&\displaystyle\underbrace{\left(\frac{1}{(z-\Delta)^{2}}-\frac{1}{\Delta^{2}}\right)({\kappa}^{2}A^{2}+{\lambda}^{2}B^{2}){\mu}{C}}_{E_{2}}+\underbrace{\frac{1}{(z-\Delta)^{2}}({\kappa}{A}+{\lambda}{B})H_{\text{else}}({\kappa}{A}+{\lambda}{B})}_{E_{3}}\\\\[7.22743pt]
&+&\displaystyle\underbrace{\frac{1}{(z-\Delta)^{2}}\cdot\frac{1}{\Delta}(\kappa
A+\lambda
B)^{4}}_{E_{4}}-\underbrace{\frac{1}{(z-\Delta)^{2}}\cdot\frac{1}{\Delta^{2}}(\kappa^{2}A^{2}+\lambda^{2}B^{2})\mu(\kappa
A+\lambda B)^{2}\otimes
C}_{E_{5}}\bigg{]}\otimes|0\rangle\langle{0}|_{w}\\\\[7.22743pt]
&+&\displaystyle\underbrace{\sum_{k=2}^{\infty}\frac{V_{-+}V_{+}^{k}V_{+-}}{(z-\Delta)^{k+1}}}_{E_{6}}.\end{array}$
(51)

Similar to the derivation of Eq. 39, 40, and 41 by letting $z\mapsto\max z$,
where $\max z=|\alpha|+\epsilon+\|H_{\text{else}}\|$ is the largest value of
$z$ permitted by the Theorem I.1, and using the triangle inequality to bound
the norm, we can bound the norm of the error terms $E_{1}$ through $E_{6}$.
For example,

$\|E_{1}\|\leq\left(\frac{1}{\Delta-\max
z}-\frac{1}{\Delta}\right)2^{2}\cdot\left(\frac{\alpha}{2}\right)^{2/3}\Delta^{2r}=\Theta(\Delta^{2r-2}).$

Applying the same calculation to $E_{2},E_{3},\cdots$ we find that
$\|E_{2}\|=\Theta(\Delta^{-1})$, $\|E_{3}\|=\Theta(\Delta^{2r-2})$,
$\|E_{4}\|=\Theta(\Delta^{4r-3})$, $\|E_{5}\|=\Theta(\Delta^{4r-4})$. The norm
of the high order terms $E_{6}$ can be bounded as

$\begin{array}[]{ccl}\|E_{6}\|&\leq&\displaystyle\sum_{k=2}^{\infty}\frac{\|V_{-+}\|\cdot\|V_{+}\|^{k}\cdot\|V_{+-}\|}{(\Delta-\max(z))^{k+1}}\leq\frac{4\left(\frac{\alpha}{2}\right)^{1/3}\Delta^{2r}}{\Delta-\max(z)}\sum_{k=2}^{\infty}\left(\frac{\rho}{\Delta-\max(z)}\right)^{k}\\\\[7.22743pt]
&=&\displaystyle\frac{2^{4/3}\alpha^{2/3}\Delta^{2r}}{\Delta-\max(z)-\rho}\left(\frac{\rho}{\Delta-\max(z)}\right)^{2}=\Theta(\Delta^{2r-1+2\max\\{1-2r,2r-2\\}})=\Theta(\Delta^{\max\\{1-2r,6r-5\\}})\end{array}$
(52)

where
$\rho=\|H_{\text{else}}\|+2^{-1/3}\alpha^{1/3}\Delta^{2-2r}+2^{1/3}\alpha^{2/3}\Delta^{2r-1}$.
If we again write the self energy expansion Eq. 51 as

$\Sigma_{-}(z)=H_{\text{targ}}\otimes|0\rangle\langle{0}|_{w}+\Theta(\Delta^{f(r)}),$

the function $f(r)<0$, which determines the dominant power in $\Delta$ among
$E_{1}$ through $E_{6}$, can be found as

$f(r)=\max\\{1-2r,2r-2,4r-3,6r-5\\},\quad\frac{1}{2}<r<1.$ (53)

Similar to the discussion after Eq. 43, the optimal scaling of
$\Delta=\Theta(\epsilon^{1/f(r)})$ gives $r=\text{argmin}f(r)=2/3$, when
$f(r)=-1/3$ and $\Delta=\Theta(\epsilon^{-3})$, as is shown in Fig. 5a. Note
that the $4r-3$ component in $f(r)$, Eq. 53, comes from the error term $E_{4}$
in Eq. 51. The idea for improving the gadget construction comes from the
observation in Fig. 5a that when we add a term in $V$ to compensate for
$E_{4}$, the dominant power of $\Delta$ in the perturbation series, $f(r)$,
could admit a lower minimum as shown in Fig. 5b. In the previous calculation
we have shown that this is indeed the case and the minimum value of $f(r)$
becomes $-1/2$ in the improved case, indicating that
$\Delta=\Theta(\epsilon^{-2})$ is sufficient for keeping the error terms
$O(\epsilon)$.

##  V Creating 3-body gadget from local X

Summary. In general, terms in perturbative gadgets involve mixed couplings
(e.g. $X_{i}Z_{j}$). Although such couplings can be realized by certain gadget
constructions BL07 , physical couplings of this type are difficult to realize
in an experimental setting. However, there has been significant progress
towards experimentally implementing Ising models with transverse fields of the
type 2006cond.mat..8253H :

$H_{ZZ}=\sum_{i}\delta_{i}X_{i}+\sum_{i}h_{i}Z_{i}+\sum_{i,j}J_{ij}Z_{i}Z_{j}.$
(54)

Accordingly, an interesting question is whether we can approximate 3-body
terms such as $\alpha\cdot Z_{i}\otimes Z_{j}\otimes Z_{k}$ using a
Hamiltonian of this form. This turns out to be possible by employing a
perturbative calculation which considers terms up to $5^{\text{th}}$ order.

Similar to the 3- to 2-body reduction discussed previously, we introduce an
ancilla $w$ and apply the Hamiltonian $H=\Delta|1\rangle\langle{1}|_{w}$. We
apply the perturbation

$V=H_{\text{else}}+\mu(Z_{i}+Z_{j}+Z_{k})\otimes|1\rangle\langle{1}|_{w}+\mu\openone\otimes
X_{w}+V_{\textrm{comp}}$ (55)

where $\mu=\left(\alpha\Delta^{4}/6\right)^{1/5}$ and $V_{\textrm{comp}}$ is

$\begin{array}[]{ccl}V_{\textrm{comp}}&=&\displaystyle\frac{\mu^{2}}{\Delta}|0\rangle\langle{0}|_{w}-\left(\frac{\mu^{3}}{\Delta^{2}}+7\frac{\mu^{5}}{\Delta^{4}}\right)\left(Z_{i}+Z_{j}+Z_{k}\right)\otimes|0\rangle\langle{0}|_{w}+\frac{\mu^{4}}{\Delta^{3}}\left(3\openone+2Z_{i}Z_{j}+2Z_{i}Z_{k}+2Z_{j}Z_{k}\right).\end{array}$
(56)

To illustrate the basic idea of the $5^{\text{th}}$ order gadget, define
subspaces $\mathcal{L}_{-}$ and $\mathcal{L}_{+}$ in the usual way and define
$P_{-}$ and $P_{+}$ as projectors into these respective subspaces. Then the
second term in Eq. 55 with $\otimes|1\rangle\langle{1}|_{w}$ contributes a
linear combination $\mu Z_{i}+\mu Z_{j}+\mu Z_{k}$ to $V_{+}=P_{+}VP_{+}$. The
third term in Eq. 55 induces a transition between $\mathcal{L}_{-}$ and
$\mathcal{L}_{+}$ yet since it operates trivially on qubits 1-3, it only
contributes a constant $\mu$ to the projections $V_{-+}=P_{-}VP_{+}$ and
$V_{+-}=P_{+}VP_{-}$. In the perturbative expansion, the $5^{\text{th}}$ order
contains a term

$\frac{V_{-+}V_{+}V_{+}V_{+}V_{+-}}{(z-\Delta)^{4}}=\frac{\mu^{5}(Z_{i}+Z_{j}+Z_{k})^{3}}{(z-\Delta)^{4}}$
(57)

due to the combined the contribution of the second and third term in Eq. 55.
This yields a term proportional to $\alpha\cdot Z_{i}\otimes Z_{j}\otimes
Z_{k}$ along with some 2-local error terms. These error terms, combined with
the unwanted terms that arise at $1^{\text{st}}$ through $4^{\text{th}}$ order
perturbation, are compensated by $V_{\text{comp}}$. Note that terms at
6${}^{\textrm{th}}$ order and higher are $\Theta(\Delta^{-1/5})$. This means
in order to satisfy the gadget theorem of Kempe _et al._ ((KKR06, , Theorem
3), or Theorem I.1) $\Delta$ needs to be $\Theta(\epsilon^{-5})$. This is the
first perturbative gadget that simulates a 3-body target Hamiltonian using the
Hamiltonian Eq. 54. By rotating the ancilla space, subdivision gadgets can
also be implemented using this Hamiltonian: in the $X$ basis, $Z$ terms will
induce a transition between the two energy levels of $X$. Therefore
$Z_{i}Z_{j}$ coupling could be used for a perturbation of the form in Eq. 4 in
the rotated basis. In principle using the transverse Ising model in Eq. 54,
one can reduce some diagonal $k$-body Hamiltonian to 3-body by iteratively
applying the subdivision gadget and then to 2-body by using the 3-body
reduction gadget.

Analysis. Similar to the gadgets we have presented so far, we introduce an
ancilla spin $w$. Applying an energy gap $\Delta$ on the ancilla spin gives
the unperturbed Hamiltonian $H=\Delta|1\rangle\langle{1}|_{w}$. We then
perturb the Hamiltonian $H$ using a perturbation $V$ described in (55). Using
the same definitions of subspaces $\mathcal{L}_{+}$ and $\mathcal{L}_{-}$ as
the previous 3-body gadget, the projections of $V$ into these subspaces can be
written as

$\begin{array}[]{ccl}V_{+}&=&\displaystyle\bigg{\\{}H_{\text{else}}+\mu(Z_{1}+Z_{2}+Z_{3})+\frac{{\mu}^{4}}{\Delta^{3}}\big{[}3{\openone}+2(Z_{1}Z_{2}+Z_{1}Z_{3}+Z_{2}Z_{3})\big{]}\bigg{\\}}\otimes|1\rangle\langle{1}|_{w}\\\\[7.22743pt]
V_{-}&=&\displaystyle\bigg{\\{}H_{\text{else}}+\frac{{\mu}^{2}}{\Delta}{\openone}-\frac{{\mu}^{3}}{\Delta^{2}}(Z_{1}+Z_{2}+Z_{3}){\openone}+\frac{{\mu}^{4}}{\Delta^{3}}\big{[}3\openone+2(Z_{1}Z_{2}+Z_{1}Z_{3}+Z_{2}Z_{3})\big{]}\\\\[7.22743pt]
&&\displaystyle-\frac{7{\mu}^{5}}{\Delta^{4}}\big{(}Z_{1}+Z_{2}+Z_{3}\big{)}\bigg{\\}}\otimes|0\rangle\langle{0}|_{w}\\\\[7.22743pt]
V_{-+}&=&{\mu}{\openone}\otimes|0\rangle\langle{1}|_{w},\quad
V_{+-}={\mu}{\openone}\otimes|1\rangle\langle{0}|_{w}.\\\\[7.22743pt]
\end{array}$ (58)

The low-lying spectrum of $\tilde{H}$ is approximated by the self energy
expansion $\Sigma_{-}(z)$ below with $z\in[-\max{z},\max{z}]$ where
$\max{z}=\|H_{\text{else}}\|+|\alpha|+\epsilon$. With the choice of $\mu$
above the expression of $V_{+}$ in Eq. 58 can be written as

$V_{+}=\left(H_{\text{else}}+{\mu}(Z_{1}+Z_{2}+Z_{3})+O(\Delta^{1/5})\right)\otimes|1\rangle\langle{1}|_{w}.$
(59)

Because we are looking for the $5^{\text{th}}$ order term in the perturbation
expansion that gives a term proportional to $Z_{1}Z_{2}Z_{3}$, expand the self
energy in Eq. 3 up to $5^{\text{th}}$ order:

$\begin{array}[]{ccl}\Sigma_{-}(z)&=&\displaystyle
V_{-}\otimes|0\rangle\langle{0}|_{w}+\frac{V_{-+}V_{+-}}{z-\Delta}\otimes|0\rangle\langle{0}|_{w}+\frac{V_{-+}V_{+}V_{+-}}{(z-\Delta)^{2}}\otimes|0\rangle\langle{0}|_{w}+\frac{V_{-+}V_{+}V_{+}V_{+-}}{(z-\Delta)^{3}}\otimes|0\rangle\langle{0}|_{w}\\\\[7.22743pt]
&+&\displaystyle\frac{V_{-+}V_{+}V_{+}V_{+}V_{+-}}{(z-\Delta)^{4}}\otimes|0\rangle\langle{0}|_{w}+\sum_{k=4}^{\infty}\frac{V_{-+}V_{+}^{k}V_{+-}}{(z-\Delta)^{k+1}}\otimes|0\rangle\langle{0}|_{w}.\end{array}$
(60)

Using this simplification as well as the expressions for $V_{-}$, $V_{-+}$ and
$V_{+-}$ in Eq. 58, the self energy expansion Eq. 60 up to $5^{\text{th}}$
order becomes

$\begin{array}[]{ccl}\Sigma_{-}(z)&=&\displaystyle\underbrace{\left(H_{\text{else}}+\frac{6\mu^{5}}{\Delta^{4}}Z_{1}Z_{2}Z_{3}\right)\otimes|0\rangle\langle{0}|_{w}}_{\text{$H_{\text{eff}}$}}+\underbrace{\left(\frac{1}{\Delta}+\frac{1}{z-\Delta}\right){\mu}^{2}{\openone}\otimes|0\rangle\langle{0}|_{w}}_{\text{$E_{1}$}}\\\\[7.22743pt]
&+&\displaystyle\underbrace{\left(\frac{1}{(z-\Delta)^{2}}-\frac{1}{\Delta^{2}}\right)\mu^{3}(Z_{1}+Z_{2}+Z_{3})\otimes|0\rangle\langle{0}|_{w}}_{\text{$E_{2}$}}+\underbrace{\left(\frac{1}{\Delta^{3}}+\frac{1}{(z-\Delta)^{3}}\right)\cdot\mu^{4}\cdot(Z_{1}+Z_{2}+Z_{3})^{2}\otimes|0\rangle\langle{0}|_{w}}_{\text{$E_{3}$}}\\\\[7.22743pt]
&+&\displaystyle\underbrace{\left(\frac{1}{(z-\Delta)^{4}}-\frac{1}{\Delta^{4}}\right)7{\mu}^{5}(Z_{1}+Z_{2}+Z_{3})\otimes|0\rangle\langle{0}|_{w}}_{\text{$E_{4}$}}+\underbrace{\frac{{\mu}^{2}}{(z-\Delta)^{2}}\cdot\frac{{\mu}^{4}}{\Delta^{3}}(Z_{1}+Z_{2}+Z_{3})^{2}\otimes|0\rangle\langle{0}|_{w}}_{\text{$E_{6}$}}\\\\[7.22743pt]
&+&O(\Delta^{-2/5})+O(\|H_{\text{else}}\|\Delta^{-2/5})+O(\|H_{\text{else}}\|^{2}\Delta^{-7/5})+O(\|H_{\text{else}}\|^{3}\Delta^{-12/5})+\underbrace{\sum_{k=4}^{\infty}\frac{V_{-+}V_{+}^{k}V_{+-}}{(z-\Delta)^{k+1}}\otimes|0\rangle\langle{0}|_{w}}_{\text{$E_{7}$}}.\\\\[7.22743pt]
\end{array}$ (61)

Similar to what we have done in the previous sections, the norm of the error
terms $E_{1}$ through $E_{7}$ can be bounded from above by letting
$z\mapsto\max{z}$. Then we find that

$\begin{array}[]{ccl}\|\Sigma_{-}(z)-H_{\text{targ}}\otimes|0\rangle\langle{0}|_{w}\|&\leq&\Theta(\Delta^{-1/5})\end{array}$
(62)

if we only consider the dominant dependence on $\Delta$ and regard
$\|H_{\text{else}}\|$ as a given constant. To guarantee that
$\|\Sigma_{-}(z)-H_{\text{targ}}\otimes|0\rangle\langle{0}|_{w}\|\leq\epsilon$,
we let the right hand side of Eq. 62 to be $\leq\epsilon$, which translates to
$\Delta=\Theta(\epsilon^{-5})$.

This $\Theta(\epsilon^{-5})$ scaling is numerically illustrated (Fig. 6a).
Although in principle the $5^{\text{th}}$ order gadget can be implemented on a
Hamiltonian of form Eq. 54, for a small range of $\alpha$, the minimum
$\Delta$ needed is already large (Fig. 6b), rendering it challenging to
demonstrate the gadget experimentally with current resources. However, this is
the only currently known gadget realizable with a transverse Ising model that
is able to address the case where $H_{\text{else}}$ is not necessarily
diagonal.

(a)(b)

Figure 6: (a) The scaling of minimum $\Delta$ needed to ensure
$\|\Sigma_{-}(z)-H_{\text{eff}}\|\leq\epsilon$ as a function of
$\epsilon^{-1}$. Here we choose $\|H_{\text{else}}\|=0$, $\alpha=0.1$ and
$\epsilon$ ranging from $10^{-0.7}$ to $10^{-2.3}$. The values of minimum
$\Delta$ are numerically optimized footnote:num_op . The slope of the line at
large $\epsilon^{-1}$ is $4.97\approx{5}$, which provides evidence that with
the assignments of ${\mu}=(\alpha\Delta^{4}/6)^{1/5}$, the optimal scaling of
$\Delta$ is $\Theta(\epsilon^{-5})$. (b) The numerically optimized
footnote:num_op  gap versus the desired coupling $\alpha$ in the target
Hamiltonian. Here $\epsilon=0.01$ and $\|H_{\text{else}}\|=0$.

##  VI YY gadget

Summary. The gadgets which we have presented so far are intended to reduce the
locality of the target Hamiltonian. Here we present another type of gadget,
called “creation” gadgets BL07 , which simulate the type of effective
couplings that are not present in the gadget Hamiltonian. Many creation
gadgets proposed so far are modifications of existing reduction gadgets. For
example, the ZZXX gadget in BL07 , which is intended to simulate $Z_{i}X_{j}$
terms using Hamiltonians of the form

$\begin{array}[]{ccl}H_{ZZXX}&=&\displaystyle\sum_{i}\Delta_{i}X_{i}+\sum_{i}h_{i}Z_{i}+\sum_{i,j}J_{ij}Z_{i}Z_{j}+\sum_{i,j}K_{ij}X_{i}X_{j},\end{array}$
(63)

is essentially a 3- to 2-body gadget with the target term $A\otimes B\otimes
C$ being such that the operators $A$, $B$ and $C$ are $X$, $Z$ and identity
respectively. Therefore the analyses on 3- to 2- body reduction gadgets that
we have presented for finding the lower bound for the gap $\Delta$ are also
applicable to this ZZXX creation gadget.

Note that YY terms can be easily realized via bases rotation if single-qubit Y
terms are present in the Hamiltonian in Eq. 63. Otherwise it is not _a priori_
clear how to realize YY terms using $H_{ZZXX}$ in Eq. 63. We will now present
the first YY gadget which starts with a universal Hamiltonian of the form Eq.
63 and simulates the target Hamiltonian
$H_{\text{targ}}=H_{\text{else}}+\alpha Y_{i}Y_{j}$. The basic idea is to use
the identity $X_{i}Z_{i}=\iota Y_{i}$ where $\iota=\sqrt{-1}$ and induce a
term of the form $X_{i}Z_{i}Z_{j}X_{j}=Y_{i}Y_{j}$ at the $4^{\text{th}}$
order. Introduce ancilla qubit $w$ and apply a penalty
$H=\Delta|1\rangle\langle{1}|_{w}$. With a perturbation $V$ we could perform
the same perturbative expansion as previously. Given that the $4^{\text{th}}$
order perturbation is $V_{-+}V_{+}V_{+}V_{+-}$ up to a scaling constant. we
could let single $X_{i}$ and $X_{j}$ be coupled with $X_{w}$, which causes
both $X_{i}$ and $X_{j}$ to appear in $V_{-+}$ and $V_{+-}$. Furthermore, we
couple single $Z_{i}$ and $Z_{j}$ terms with $Z_{w}$. Then
$\frac{1}{2}(\openone+Z_{w})$ projects single $Z_{i}$ and $Z_{j}$ onto the $+$
subspace and causes them to appear in $V_{+}$. For
$H_{\text{targ}}=H_{\text{else}}+\alpha Y_{1}Y_{2}$, the full expressions for
the gadget Hamiltonian is the following: the penalty Hamiltonian
$H=\Delta|1\rangle\langle{1}|_{w}$ acts on the ancilla qubit. The perturbation
$V=V_{0}+V_{1}+V_{2}$ where $V_{0}$, $V_{1}$, and $V_{2}$ are defined as

$\begin{array}[]{ccl}V_{0}&=&\displaystyle
H_{\text{else}}+\mu({Z_{1}+Z_{2}})\otimes{|1\rangle\langle{1}|_{w}}+\mu(X_{1}-\text{sgn}(\alpha)X_{2})\otimes
X_{w}\\\\[3.61371pt]
V_{1}&=&\displaystyle\frac{2\mu^{2}}{\Delta}(\openone\otimes|0\rangle\langle{0}|_{w}+X_{1}X_{2})\\\\[3.61371pt]
V_{2}&=&\displaystyle-\frac{2\mu^{4}}{\Delta^{3}}Z_{1}Z_{2}.\end{array}$ (64)

with $\mu=(|\alpha|\Delta^{3}/4)^{1/4}$. For a specified error tolerance
$\epsilon$, we have constructed a YY gadget Hamiltonian of gap scaling
$\Delta=O(\epsilon^{-4})$ and the low-lying spectrum of the gadget Hamiltonian
captures the spectrum of $H_{\text{targ}}\otimes|0\rangle\langle{0}|_{w}$ up
to error $\epsilon$.

The YY gadget implies that a wider class of Hamiltonians such as

$\begin{array}[]{ccl}H_{ZZYY}&=&\displaystyle\sum_{i}h_{i}X_{i}+\sum_{i}\Delta_{i}Z_{i}+\sum_{i,j}J_{ij}Z_{i}Z_{j}+\sum_{i,j}K_{ij}Y_{i}Y_{j}\end{array}$
(65)

and

$\begin{array}[]{ccl}H_{XXYY}&=&\displaystyle\sum_{i}h_{i}X_{i}+\sum_{i}\Delta_{i}Z_{i}+\sum_{i,j}J_{ij}X_{i}X_{j}+\sum_{i,j}K_{ij}Y_{i}Y_{j}\end{array}$
(66)

can be simulated using the Hamiltonian of the form in Eq. 63. Therefore using
the Hamiltonian in Eq. 63 one can in principle simulate any finite-norm real
valued Hamiltonian on qubits. Although by the QMA-completeness of $H_{ZZXX}$
one could already simulate such Hamiltonian via suitable embedding, our YY
gadget provides a more direct alternative for the simulation.

Analysis.  The results in BL07  shows that Hamiltonians of the form in Eq. 63
supports universal adiabatic quantum computation and finding the ground state
of such a Hamiltonian is QMA-complete. This form of Hamiltonian is also
interesting because of its relevance to experimental implementation
2006cond.mat..8253H . Here we show that with a Hamiltonian of the form in Eq.
63 we could simulate a target Hamiltonian
$H_{\text{targ}}=H_{\text{else}}+\alpha Y_{1}Y_{2}$. Introduce an ancilla $w$
and define the penalty Hamiltonian as $H=\Delta|1\rangle\langle{1}|_{w}$. Let
the perturbation $V=V_{0}+V_{1}+V_{2}$ be

$\begin{array}[]{ccl}V_{0}&=&H_{\text{else}}+\kappa({Z_{1}+Z_{2}})\otimes{|1\rangle\langle{1}|_{w}}+\kappa(X_{1}-\text{sgn}(\alpha)X_{2})\otimes
X_{w}\\\\[3.61371pt]
V_{1}&=&2\kappa^{2}\Delta^{-1}[|0\rangle\langle{0}|_{w}-\text{sgn}(\alpha)X_{1}X_{2}]\\\\[3.61371pt]
V_{2}&=&-4\kappa^{4}\Delta^{-3}Z_{1}Z_{2}.\end{array}$ (67)

Then the gadget Hamiltonian $\tilde{H}=H+V$ is of the form in Eq. 63. Here we
choose the parameter $\kappa=(|\alpha|\Delta^{3}/4)^{1/4}$. In order to show
that the low lying spectrum of $\tilde{H}$ captures that of the target
Hamiltonian, define $\mathcal{L}_{-}=\text{span}\\{|\psi\rangle\text{ such
that }\tilde{H}|\psi\rangle=\lambda|\psi\rangle,\lambda<\Delta/2\\}$ as the
low energy subspace of $\tilde{H}$ and
$\mathcal{L}_{+}=\openone-\mathcal{L}_{-}$. Define $\Pi_{-}$ and $\Pi_{+}$ as
the projectors onto $\mathcal{L}_{-}$ and $\mathcal{L}_{+}$ respectively.

With these notations in place, here we show that the spectrum of
$\tilde{H}_{-}=\Pi_{-}\tilde{H}\Pi_{-}$ approximates the spectrum of
$H_{\text{targ}}\otimes|0\rangle\langle{0}|_{w}$ with error $\epsilon$. To
begin with, the projections of $V$ into the subspaces $\mathcal{L}_{-}$ and
$\mathcal{L}_{+}$ can be written as

$\begin{array}[]{ccl}V_{-}&=&\displaystyle\bigg{(}H_{\text{else}}+\underbrace{\frac{\kappa^{2}}{\Delta}(X_{1}-\text{sgn}(\alpha)X_{2})^{2}}_{(a)}\underbrace{-\frac{4\kappa^{4}}{\Delta^{3}}Z_{1}Z_{2}}_{(b)}\bigg{)}\otimes|0\rangle\langle{0}|_{w}\\\\[3.61371pt]
V_{+}&=&\displaystyle\left(H_{\text{else}}+\kappa(Z_{1}+Z_{2})-\frac{2\kappa^{2}}{\Delta}\text{sgn}(\alpha)X_{1}X_{2}-\frac{4\kappa^{4}}{\Delta^{3}}Z_{1}Z_{2}\right)\otimes|1\rangle\langle{1}|_{w}\\\\[3.61371pt]
V_{-+}&=&\kappa(X_{1}-\text{sgn}(\alpha)X_{2})\otimes|0\rangle\langle{1}|_{w}\\\\[3.61371pt]
V_{+-}&=&\kappa(X_{1}-\text{sgn}(\alpha)X_{2})\otimes|1\rangle\langle{0}|_{w}\end{array}$
(68)

Given the penalty Hamiltonian $H$, we have the operator valued resolvent
$G(z)=(z\openone-H)^{-1}$ that satisfies
$G_{+}(z)=\Pi_{+}G(z)\Pi_{+}=(z-\Delta)^{-1}|1\rangle\langle{1}|_{w}$. Then
the low lying sector of the gadget Hamiltonian $\tilde{H}$ can be approximated
by the perturbative expansion Eq. 3. For our purposes we will consider terms
up to the $4^{\text{th}}$ order:

$\Sigma_{-}(z)=V_{-}+\frac{1}{z-\Delta}V_{-+}V_{+-}+\frac{1}{(z-\Delta)^{2}}V_{-+}V_{+}V_{+-}+\frac{1}{(z-\Delta)^{3}}V_{-+}V_{+}V_{+}V_{+-}+\sum_{k=3}^{\infty}\frac{V_{-+}V_{+}^{k}V_{+-}}{(z-\Delta)^{k+1}}.$
(69)

Now we explain the perturbative terms that arise at each order. The
$1^{\text{st}}$ order is the same as $V_{-}$ in Eq. 68. The $2^{\text{nd}}$
order term gives

$\frac{1}{z-\Delta}V_{-+}V_{+-}=\underbrace{\frac{1}{z-\Delta}\cdot\kappa^{2}(X_{1}-\text{agn}(\alpha)X_{2})^{2}}_{(c)}\otimes|0\rangle\langle{0}|_{w}.$
(70)

At the $3^{\text{rd}}$ order, we have

$\begin{array}[]{ccl}\displaystyle\frac{1}{(z-\Delta)^{2}}V_{-+}V_{+}V_{+-}&=&\displaystyle\bigg{(}\frac{1}{(z-\Delta)^{2}}\cdot\kappa^{2}(X_{1}-\text{agn}(\alpha)X_{2})H_{\text{else}}(X_{1}-\text{sgn}(\alpha)X_{2})\\\\[3.61371pt]
&+&\displaystyle\underbrace{\frac{1}{(z-\Delta)^{2}}\frac{4\kappa^{4}}{\Delta}(X_{1}X_{2}-\text{sgn}(\alpha)\openone)}_{(d)}\bigg{)}\otimes|0\rangle\langle{0}|_{w}+O(\Delta^{-1/4}).\end{array}$
(71)

The $4^{\text{th}}$ order contains the desired YY term:

$\begin{array}[]{ccl}\displaystyle\frac{1}{(z-\Delta)^{3}}V_{-+}V_{+}V_{+}V_{+-}&=&\displaystyle\bigg{(}\underbrace{\frac{1}{(z-\Delta)^{3}}\cdot
2\kappa^{4}(X_{1}-\text{sgn}(\alpha)X_{2})^{2}}_{(e)}-\underbrace{\frac{1}{(z-\Delta)^{3}}4\kappa^{4}Z_{1}Z_{2}}_{(f)}\\\\[3.61371pt]
&+&\displaystyle\frac{4\kappa^{4}\text{sgn}(\alpha)}{(z-\Delta)^{3}}Y_{1}Y_{2}\bigg{)}\otimes|0\rangle\langle{0}|_{w}+O(\|H_{\text{else}}\|\cdot\Delta^{-3/4})+O(\|H_{\text{else}}\|^{2}\cdot\Delta^{-1/2})\end{array}$
(72)

Note that with the choice of $\kappa=(|\alpha|\Delta^{3}/4)^{1/4}$, all terms
of $5^{\text{th}}$ order and higher are of norm $O(\Delta^{-1/4})$. In the
$1^{\text{st}}$ order through $4^{\text{th}}$ order perturbations the unwanted
terms are labelled as $(a)$ through $(f)$ in Eqs. 68, 70, 71, and 72. Note how
they compensate in pairs: the sum of $(a)$ and $(c)$ is $O(\Delta^{-1/4})$.
The same holds for $(d)$ and $(e)$, $(b)$ and $(f)$. Then the self energy is
then

$\Sigma_{-}(z)=(H_{\text{else}}+\alpha
Y_{1}Y_{2})\otimes|0\rangle\langle{0}|_{w}+O(\Delta^{-1/4}).$ (73)

Let $\Delta=\Theta(\epsilon^{-4})$, then by the Gadget Theorem (I.1), the low-
lying sector of the gadget Hamiltonian $\tilde{H}_{-}$ captures the spectrum
of $H_{\text{targ}}\otimes|0\rangle\langle{0}|_{w}$ up to error $\epsilon$.

The fact that the gadget relies on $4^{\text{th}}$ order perturbation renders
the gap scaling relatively larger than it is in the case of subdivision or 3-
to 2-body reduction gadgets. However, this does not diminish its usefulness in
various applications.

## Conclusion

We have presented improved constructions for the most commonly used gadgets,
which in turn implies a reduction in the resources for the many works which
employ these current constructions. We presented the first comparison between
the known gadget constructions and the first numerical optimizations of gadget
parameters. Our analytical results are found to agree with the optimised
solutions. The introduction of our gadget which simulates YY-interactions
opens many prospects for universal adiabatic quantum computation, particularly
the simulation of physics feasible on currently realizable Hamiltonians.

## Acknowledgements

We thank Andrew Landahl for helpful comments. JDB and YC completed parts of
this study while visiting the Institute for Quantum Computing at the
University of Waterloo. RB was supported by the United States Department of
Defense. The views and conclusions contained in this document are those of the
authors and should not be interpreted as representing the official policies,
either expressed or implied, of the U.S. Government. JDB completed parts of
this study while visiting the Qatar Energy and Environment Research Institute
and would like to acknowledge the Foundational Questions Institute (under
grant FQXi-RFP3-1322) for financial support.

##  Appendix A Parallel 3- to 2-body gadget

Summary. In Sec. III we have shown that by using parallel subdivision gadgets
iteratively, one can reduce a $k$-body target term to $3$-body. We now turn
our attention to considering
$H_{\text{targ}}=H_{\text{else}}+\sum_{i=1}^{m}\alpha_{i}A_{i}\otimes
B_{i}\otimes C_{i}$, which is a sum of $m$ 3-body terms. A straightforward
approach to the reduction is to deal with the 3-body terms in series _i.e._
one at a time: apply a 3-body gadget on one term, and include the entire
gadget in the $H_{\text{else}}$ of the target Hamiltonian in reducing the next
3-body term. In this construction, $\Delta$ scales exponentially as a function
of $m$. In order to avoid that overhead, we apply all gadgets in parallel,
which means introducing $m$ ancilla spins, one for each 3-body term and
applying the same $\Delta$ onto it. This poses additional challenges as the
operator valued resolvent $G(z)$ now has multiple poles. Enumerating high
order terms in the perturbation series requires consideration of the
combinatorial properties of the bit flipping processes (Fig. 7).

If we apply the current construction OT06 ; BDLT08  of 3-body gadgets in
parallel, which requires $\Delta=\Theta(\epsilon^{-3})$, it can be shown
BDLT08  that the cross-gadget contribution is $O(\epsilon)$. However, if we
apply our improved construction of the 3- to 2-body gadget in parallel, the
perturbation expansion will contain $\Theta(1)$ cross-gadget terms that are
dependent on the commutation relations between $A_{i}$, $B_{i}$ and $A_{j}$,
$B_{j}$. Compensation terms are designed to ensure that these error terms are
suppressed in the perturbative expansion. With our improved parallel 3-body
construction, $\Delta=\Theta({\epsilon^{-2}}\text{poly}(m))$ is sufficient.

The combination of parallel subdivision with the parallel 3- to 2-body
reduction allows us to reduce an arbitrary $k$-body target Hamiltonian
$H_{\text{targ}}=H_{\text{else}}+\alpha\sigma_{1}\sigma_{2}\cdots\sigma_{k}$
to 2-body BDLT08 . In this paper we have improved both parallel 2-body and 3-
to 2-body gadgets. When numerically optimized at each iteration, our
construction requires a smaller gap than the original construction BDLT08  for
the range of $k$ concerned.

Analysis. In Sec. III we have shown that with subdivision gadgets one can
reduce a $k$-body interaction term down to 3-body. To complete the discussion
on reducing a $k$-body term to $2$-body, now we deal with reducing a 3-body
target Hamiltonian of form

$H_{\text{targ}}=H_{\text{else}}+\sum_{i=1}^{m}\alpha_{i}{A_{i}}\otimes{B_{i}}\otimes{C_{i}}$

where $H_{\text{else}}$ is a finite-norm Hamiltonian and all of $A_{i}$,
$B_{i}$, $C_{i}$ are single-qubit Pauli operators acting on one of the $n$
qubits that $H_{\text{targ}}$ acts on. Here without loss of generality, we
assume $A_{i}$, $B_{i}$ and $C_{i}$ are single-qubit Pauli operators as our
construction depends on the commutation relationships among these operators.
The Pauli operator assumption ensures that the commutative relationship can be
determined efficiently a priori.

We label the $n$ qubits by integers from 1 to $n$. We assume that in each
3-body term of the target Hamiltonian, ${A_{i}}$, ${B_{i}}$ and ${C_{i}}$ act
on three different qubits whose labels are in increasing order i.e. if we
label the qubits with integers from 1 to $n$, ${A_{i}}$ acts on qubit $a_{i}$,
${B_{i}}$ acts on $b_{i}$, ${C_{i}}$ on $c_{i}$, we assume that $1\leq
a_{i}<b_{i}<c_{i}\leq n$ must hold for all values of $i$ from 1 to $m$.

One important feature of this gadget is that the gap $\Delta$ scales as
$\Theta(\epsilon^{-2})$ instead of the common $\Theta(\epsilon^{-3})$ scaling
assumed by the other 3-body constructions in the literature KKR06 ; OT06 ;
BDLT08 .

To reduce the $H_{\text{targ}}$ to 2-body, introduce $m$ qubits labelled as
$u_{1}$, $u_{2}$, $\cdots$, $u_{m}$ and apply an energy penalty $\Delta$ onto
the excited subspace of each qubit, as in the case of parallel subdivision
gadgets presented previously. Then we have

$H=\sum_{i=1}^{m}\Delta|1\rangle\langle{1}|_{u_{i}}=\sum_{x\in\\{0,1\\}^{m}}h(x)\Delta|x\rangle\langle
x|.$ (74)

where $h(x)$ is the Hamming weight of the $m$-bit string $x$. In this new
construction the perturbation $V$ is defined as

$\begin{array}[]{ccl}V&=&\displaystyle
H_{\text{else}}+\sum_{i=1}^{m}{\mu_{i}}{C_{i}}\otimes|1\rangle\langle{1}|_{u_{i}}+\sum_{i=1}^{m}({\kappa_{i}}{A_{i}}+{\lambda_{i}}{B_{i}})\otimes
X_{u_{i}}+V_{1}+V_{2}+V_{3}\end{array}$ (75)

where $V_{1}$ is defined as

$V_{1}=\frac{1}{\Delta}\sum_{i=1}^{m}({\kappa_{i}}{A_{i}}+{\lambda_{i}}{B_{i}})^{2}-\frac{1}{\Delta^{2}}\sum_{i=1}^{m}({\kappa_{i}^{2}}+{\lambda_{i}^{2}}){\mu_{i}}{C_{i}}$
(76)

and $V_{2}$ is defined as

$V_{2}=-\frac{1}{\Delta^{3}}\sum_{i=1}^{m}({\kappa_{i}}{A_{i}}+{\lambda_{i}}{B_{i}})^{4}.$
(77)

$V_{3}$ will be explained later. Following the discussion in Sec. IV, the
coefficients ${\kappa_{i}}$, ${\lambda_{i}}$ and ${\mu_{i}}$ are defined as

${\kappa_{i}}=\text{sgn}(\alpha_{i})\left(\frac{|\alpha_{i}|}{2}\right)^{\frac{1}{3}}\Delta^{\frac{3}{4}},\quad{\lambda_{i}}=\left(\frac{|\alpha_{i}|}{2}\right)^{\frac{1}{3}}\Delta^{\frac{3}{4}},\quad{\mu_{i}}=\left(\frac{|\alpha_{i}|}{2}\right)^{\frac{1}{3}}\Delta^{\frac{1}{2}}.$
(78)

However, as we will show in detail later in this section, a close examination
of the perturbation expansion based on the $V$ in Eq. 75 shows that with
assignments of ${\kappa_{i}}$, ${\lambda_{i}}$ and ${\mu_{i}}$ in Eq. 78 if
$V$ has only $V_{1}$ and $V_{2}$ as compensation terms, the cross-gadget
contribution in the expansion causes $\Theta(1)$ error terms to arise. In
order to compensate for the $\Theta(1)$ error terms, we introduce the
compensation

$V_{3}=\sum_{i=1}^{m}\sum_{j=1,j\neq i}^{m}\bar{V}_{ij}$

into $V$ and $\bar{V}_{ij}$ is the compensation term for cross-gadget
contribution footnote:cross . Before presenting the detailed form of
$\bar{V}_{ij}$, let $s_{1}^{(i,j)}=s_{11}^{(i,j)}+s_{12}^{(i,j)}$ where

$s_{11}^{(i,j)}=\left\\{\begin{array}[]{cl}1&\text{if
}\left\\{\begin{tabular}[]{c}$[{A_{i}},{A_{j}}]\neq 0$\\\
$[{B_{i}},{B_{j}}]=0$\end{tabular}\right.\text{or
}\left\\{\begin{tabular}[]{c}$[{B_{i}},{B_{j}}]\neq 0$\\\
$[{A_{i}},{A_{j}}]=0$\end{tabular}\right.\\\
0&\text{otherwise}\end{array}\right.$ (79)
$s_{12}^{(i,j)}=\left\\{\begin{array}[]{cl}1&\text{if $[{A_{i}},{B_{j}}]\neq
0$ or $[{B_{i}},{A_{j}}]\neq 0$}\\\\[7.22743pt]
0&\text{otherwise}\end{array}\right.$ (80)

and further define $s_{2}^{(i,j)}$ as

$s_{2}^{(i,j)}=\left\\{\begin{array}[]{cl}1&\text{if $[{A_{i}},{A_{j}}]\neq 0$
and $[{B_{i}},{B_{j}}]\neq 0$}\\\\[7.22743pt]
0&\text{otherwise.}\end{array}\right.$ (81)

Then we define $\bar{V}_{ij}$ as

$\begin{array}[]{ccl}\bar{V}_{ij}&=&\displaystyle-
s_{1}^{(i,j)}\cdot\frac{1}{\Delta^{3}}({\kappa_{i}}{\kappa_{j}})^{2}{\openone}-s_{2}^{(i,j)}\bigg{(}\frac{2}{\Delta^{3}}({\kappa_{i}}{\kappa_{j}})^{2}{\openone}-\frac{2}{\Delta^{3}}{\kappa_{i}}{\kappa_{j}}{\lambda_{i}}{\lambda_{j}}{A_{i}}{A_{j}}{B_{i}}{B_{j}}\bigg{)}\end{array}$
(82)

where $s_{1}^{(i,j)}$ and $s_{2}^{(i,j)}$ are coefficients that depend on the
commuting relations between the operators in the $i$-th term and the $j$-th
term. Note that in Eq. 82, although the term $A_{i}A_{j}B_{i}B_{j}$ is
4-local, it arises only in cases where $s_{2}^{(i,j)}=1$. In this case, an
additional gadget with a new ancilla $u_{ij}$ can be introduced to generate
the 4-local term. For succinctness we present the details of this construction
in Appendix B. With the penalty Hamiltonian $H$ defined in Eq. 74, the
operator-valued resolvent (or the Green’s function) can be written as

$G(z)=\sum_{x\in\\{0,1\\}^{m}}\frac{1}{z-h(x)\Delta}|x\rangle\langle{x}|.$
(83)

Define subspaces of the ancilla register
$\mathcal{L}_{-}=\text{span}\\{|00\cdots 0\rangle\\}$ and
$\mathcal{L}_{+}=\text{span}\\{|x\rangle|x\neq 00\cdots 0\\}$. Define
${P_{-}}$ and ${P_{+}}$ as the projectors onto $\mathcal{L}_{-}$ and
$\mathcal{L}_{+}$. Then the projections of $V$ onto the subspaces can be
written as

$\begin{array}[]{ccl}V_{+}&=&\displaystyle\bigg{(}H_{\text{else}}+\frac{1}{\Delta}\sum_{i=1}^{m}({\kappa_{i}}{A_{i}}+{\lambda_{i}}{B_{i}})^{2}-\frac{1}{\Delta^{2}}\sum_{i=1}^{m}({\kappa_{i}^{2}}+{\lambda_{i}^{2}}){\mu_{i}}{C_{i}}-\frac{1}{\Delta^{3}}\sum_{i=1}^{m}({\kappa_{i}}{A_{i}}+{\lambda_{i}}{B_{i}})^{4}+\sum_{i=1}^{m}\sum_{j=1,j\neq
i}^{m}\bar{V}_{ij}\bigg{)}\otimes{P_{+}}\\\\[7.22743pt]
&+&\displaystyle\sum_{i=1}^{m}{\mu_{i}}{C_{i}}\otimes{P_{+}}|1\rangle\langle{1}|_{u_{i}}{P_{+}}+\underbrace{\sum_{i=1}^{m}({\kappa_{i}}{A_{i}}+{\lambda_{i}}{B_{i}})\otimes{P_{+}}X_{u_{i}}{P_{+}}}_{V_{f}}=V_{s}+V_{f}\\\\[7.22743pt]
V_{-+}&=&\displaystyle\sum_{i=1}^{m}({\kappa_{i}}{A_{i}}+{\lambda_{i}}{B_{i}})\otimes{P_{-}}X_{u_{i}}{P_{+}},\quad
V_{+-}=\sum_{i=1}^{m}({\kappa_{i}}{A_{i}}+{\lambda_{i}}{B_{i}})\otimes{P_{+}}X_{u_{i}}{P_{-}}\\\\[7.22743pt]
V_{-}&=&\displaystyle\bigg{(}H_{\text{else}}+\frac{1}{\Delta}\sum_{i=1}^{m}({\kappa_{i}}{A_{i}}+{\lambda_{i}}{B_{i}})^{2}-\frac{1}{\Delta^{2}}\sum_{i=1}^{m}({\kappa_{i}^{2}}+{\lambda_{i}^{2}}){\mu_{i}}{C_{i}}-\frac{1}{\Delta^{3}}\sum_{i=1}^{m}({\kappa_{i}}{A_{i}}+{\lambda_{i}}{B_{i}})^{4}+\sum_{i=1}^{m}\sum_{j=1,j\neq
i}^{m}\bar{V}_{ij}\bigg{)}\otimes{P_{-}}.\end{array}$ (84)

Here the $V_{+}$ projection is intentionally divided up into $V_{f}$ and
$V_{s}$ components. $V_{f}$ is the component of $V_{+}$ that contributes to
the perturbative expansion only when the perturbative term corresponds to
flipping processes in the $\mathcal{L}_{+}$ subspace. $V_{s}$ is the component
that contributes only when the perturbative term corresponds to transitions
that involve the state of the $m$-qubit ancilla register staying the same.

The projection of the Green’s function $G(z)$ onto $\mathcal{L}_{+}$ can be
written as

$G_{+}(z)=\sum_{x\neq 0\cdots 00}\frac{1}{z-h(x)\Delta}|x\rangle\langle{x}|.$
(85)

We now explain the self energy expansion

$\Sigma_{-}(z)=V_{-}+V_{-+}G_{+}V_{+-}+V_{-+}G_{+}V_{+}G_{+}V_{+-}+V_{-+}(G_{+}V_{+})^{2}G_{+}V_{+-}+V_{-+}(G_{+}V_{+})^{3}G_{+}V_{+-}+\cdots$
(86)

in detail term by term. The $1^{\text{st}}$ order term is simply $V_{-}$ from
Equation Eq. 84. The $2^{\text{nd}}$ order term corresponds to processes of
starting from an all-zero state of the $m$ ancilla qubits, flipping one qubit
and then flipping it back:

$\begin{array}[]{ccl}V_{-+}G_{+}V_{+-}&=&\displaystyle\frac{1}{z-\Delta}\sum_{i=1}^{m}({\kappa_{i}}{A_{i}}+{\lambda_{i}}{B_{i}})^{2}\\\\[7.22743pt]
\end{array}$ (87)

The $3^{\text{rd}}$ order term corresponds to processes of starting from an
all-zero state of the ancilla register, flipping one qubit, staying at the
same state for $V_{+}$ and then flipping the same qubit back. Therefore only
the $V_{f}$ component in $V_{+}$ in Equation Eq. 84 will contribute to the
perturbative expansion:

$\begin{array}[]{ccl}V_{-+}G_{+}V_{+}G_{+}V_{+-}&=&\displaystyle\frac{1}{(z-\Delta)^{2}}\sum_{i=1}^{m}({\kappa_{i}}{A_{i}}+{\lambda_{i}}{B_{i}})\bigg{[}H_{\text{else}}+{\mu_{i}}{C_{i}}+\frac{1}{\Delta}\sum_{j=1}^{m}({\kappa_{j}}{A_{j}}+{\lambda_{j}}{B_{j}})^{2}\\\\[7.22743pt]
&+&\displaystyle\frac{1}{\Delta^{2}}\sum_{j=1}^{m}\bigg{[}(\kappa_{j}^{2}+\lambda_{j}^{2})\mu_{j}{C_{j}}-\frac{1}{\Delta^{3}}\sum_{j=1}^{m}({\kappa_{j}}{A_{j}}+{\lambda_{j}}{B_{j}})^{4}+\sum_{j=1}^{m}\sum_{l=1,l\neq
j}^{m}\bar{V}_{jl}\bigg{]}\\\\[7.22743pt]
&&\displaystyle({\kappa_{i}}{A_{i}}+{\lambda_{i}}{B_{i}}).\\\\[7.22743pt]
\end{array}$ (88)

The $4^{\text{th}}$ order term is more involved. Here we consider two types of
transition processes (for diagrammatic illustration refer to Fig. 7):

  1. 1.

Starting from the all-zero state, flipping one of the qubits, flipping another
qubit, then using the remaining $V_{+}$ and $V_{+-}$ to flip both qubits back
one after the other (there are 2 different possible sequences, see Fig. 7a).

  2. 2.

Starting from the all-zero state of the ancilla register, flipping one of the
qubits, staying twice for the two $V_{+}$ components and finally flipping back
the qubit during $V_{+-}$ (Fig. 7b).

Therefore in the transition processes of type (1), $V_{+}$ will only
contribute its $V_{f}$ component and the detailed form of its contribution
depends on which qubit in the ancilla register is flipped. The two
possibilities of flipping the two qubits back explains why the second term in
Eq. 89 takes the form of a summation of two components. Because two qubits are
flipped during the transition, $G_{+}$ will contribute a $\frac{1}{z-2\Delta}$
factor and two $\frac{1}{z-\Delta}$ factors to the perturbative term.

In the transition processes of type (2), $V_{+}$ will only contribute its
$V_{s}$ component to the $4^{\text{th}}$ order term since the states stay the
same during both $V_{+}$ operators in the perturbative term. $G_{+}$ will only
contribute a factor of $\frac{1}{z-\Delta}$ because the Hamming weight of the
bit string represented by the state of the ancilla register is always 1. This
explains the form of the first term in Eq. 89.

$\begin{array}[]{ccl}V_{-+}(G_{+}V_{+})^{2}G_{+}V_{+-}&=&\displaystyle\frac{1}{(z-\Delta)^{3}}\sum_{i=1}^{m}({\kappa_{i}}{A_{i}}+{\lambda_{i}}{B_{i}})\bigg{[}H_{\text{else}}+{\mu_{i}}{C_{i}}+\frac{1}{\Delta}\sum_{j=1}^{m}({\kappa_{j}}{A_{j}}+{\lambda_{j}}{B_{j}})^{2}\\\\[7.22743pt]
&-&\displaystyle\frac{1}{\Delta^{2}}\sum_{j=1}^{m}(\kappa_{j}^{2}+\lambda_{j}^{2})\mu_{j}{C_{j}}-\frac{1}{\Delta^{3}}\sum_{j=1}^{m}({\kappa_{j}}{A_{j}}+{\lambda_{j}}{B_{j}})^{4}+\sum_{j=1}^{m}\sum_{l=1,l\neq
j}^{m}\bar{V}_{jl}\bigg{]}^{2}\\\\[7.22743pt]
&&({\kappa_{i}}{A_{i}}+{\lambda_{i}}{B_{i}})\\\\[7.22743pt]
&+&\displaystyle\frac{1}{(z-\Delta)^{2}(z-2\Delta)}\sum_{i=1}^{m}\sum_{j=1,j\neq
i}^{m}\bigg{[}({\kappa_{i}}{A_{i}}+{\lambda_{i}}{B_{i}})({\kappa_{j}}{A_{j}}+{\lambda_{j}}{B_{j}})\\\\[7.22743pt]
&&\makebox[132.30513pt]{}{}({\kappa_{i}}{A_{i}}+{\lambda_{i}}{B_{i}})({\kappa_{j}}{A_{j}}+{\lambda_{j}}{B_{j}})\\\\[7.22743pt]
&+&\displaystyle({\kappa_{i}}{A_{i}}+{\lambda_{i}}{B_{i}})({\kappa_{j}}{A_{j}}+{\lambda_{j}}{B_{j}})({\kappa_{j}}{A_{j}}+{\lambda_{j}}{B_{j}})({\kappa_{i}}{A_{i}}+{\lambda_{i}}{B_{i}})\bigg{]}.\\\\[7.22743pt]
\end{array}$ (89)

Although the $4^{\text{th}}$ order does not contain terms that are useful for
simulating the 3-body target Hamiltonian, our assignments of ${\kappa_{i}}$,
${\lambda_{i}}$ and ${\mu_{i}}$ values in Eq. 78 imply that some of the terms
at this order can be $\Theta(1)$. Indeed, the entire second term in Eq. 89 is
of order $\Theta(1)$ based on Eq. 78. Therefore it is necessary to study in
detail what error terms arise at this order and how to compensate for them in
the perturbation $V$. A detailed analysis on how to compensate the $\Theta(1)$
errors is presented in the Appendix B. The $5^{\text{th}}$ order and higher
terms are errors that can be reduced by increasing $\Delta$:

$\begin{array}[]{ccl}&&\displaystyle\sum_{k=3}^{\infty}V_{-+}(G_{+}V_{+})^{k}G_{+}V_{+-}.\end{array}$
(90)

At first glance, with assignments of ${\kappa_{i}}$, ${\lambda_{i}}$ and
${\mu_{i}}$ in Eq. 78, it would appear that this error term is
$\Theta(\Delta^{-1/4})$ since $\|V_{-+}\|=\Theta(\Delta^{3/4})$,
$\|V_{+-}\|=\Theta(\Delta^{3/4})$, $\|V_{+}\|=\Theta(\Delta^{3/4})$ and
$\|G_{+}\|=\Theta(\Delta^{-1})$,

$\begin{array}[]{ccl}\displaystyle\sum_{k=3}^{\infty}V_{-+}(G_{+}V_{+})^{k}G_{+}V_{+-}&\leq&\displaystyle\sum_{k=3}^{\infty}\|V_{-+}\|\cdot\|G_{+}V_{+}\|^{k}\|G_{+}\|\cdot\|V_{+-}\|\\\\[7.22743pt]
&=&\displaystyle\|V_{-+}(G_{+}V_{+})^{3}G_{+}V_{+-}\|\sum_{k=0}^{\infty}\|G_{+}V_{+}\|^{k}\\\\[7.22743pt]
&=&\displaystyle O(\Delta^{-1/4})\end{array}$ (91)

as $\sum_{k=0}^{\infty}\|G_{+}V_{+}\|^{k}=O(1)$. However, here we show that in
fact this term in Eq. 90 is $\Theta(\Delta^{-1/2})$. Note that the entire term
Eq. 90 consists of contributions from the transition processes where one
starts with a transition from the all-zero state to a state $|x\rangle$ with
$x\in\\{0,1\\}^{m}$ and $h(x)=1$. If we focus on the perturbative term of
order $k+2$:

$V_{-+}(G_{+}V_{+})^{k}G_{+}V_{+-},$

after $k$ steps. During every step one can choose to either flip one of the
ancilla qubits or stay in the same state of the ancilla register, the state of
the ancilla register will go back to a state $|y\rangle$ with
$y\in\\{0,1\\}^{m}$ and $h(y)=1$. Finally the $|1\rangle$ qubit in $|y\rangle$
is flipped back to $|0\rangle$ and we are back to the all-zero state which
spans the ground state subspace $\mathcal{L}_{-}$. Define the total number of
flipping steps to be $k_{f}$. Then for a given $k$, $k_{f}$ takes only values
from

$K(k)=\left\\{\begin{array}[]{cl}\\{k,k-2,\cdots,2\\}&\text{if $k$ is
even}\\\\[7.22743pt] \\{k-1,k-3,\cdots,2\\}&\text{if $k$ is
odd}.\end{array}\right.$ (92)

${\cal L_{-}}$${\cal L_{+}}$$\displaystyle
G_{+}\left(z\right)=\frac{1}{z-\Delta}$$\displaystyle
G_{+}\left(z\right)=\frac{1}{z-2\Delta}$$|0\,.\,.\,.\\!\\!\\!\underbrace{0}_{i}\\!\\!\\!.\,.\,.\\!\\!\\!\underbrace{0}_{j}\\!\\!\\!.\,.\,.\,0\rangle$$|0\ldots
1\ldots 0\ldots 0\rangle$$|0\ldots 1\ldots 1\ldots 0\rangle$$|0\ldots 0\ldots
1\ldots 0\rangle$$\small V_{-+}$$\small V_{+-}$$\small
V_{+-}$$\small\,V_{-+}$$\small V_{f}\,$$\small\,\,V_{f}$$\small
V_{f}\,$$\small\,\,V_{f}$

(a)

${\cal L_{-}}$${\cal L_{+}}$$\displaystyle
G_{+}\left(z\right)=\frac{1}{z-\Delta}$$|0\,.\,.\,.\\!\\!\\!\underbrace{0}_{i}\\!\\!\\!.\,.\,.\\!\\!\\!\underbrace{0}_{j}\\!\\!\\!.\,.\,.\,0\rangle$$|0\ldots
1\ldots 0\ldots 0\rangle$$|0\ldots 0\ldots 1\ldots 0\rangle$$\small
V_{-+}$$\small V_{+-}$$\small V_{+-}$$\small\,V_{-+}$$\small V_{s}$$\small
V_{s}$$\small V_{s}$$\small V_{s}$

(b)

Figure 7: Diagrams illustrating the transitions that occur at 4th order. The
two diagrams each represent a type of transition that occurs at 4th order.
Each diagram is divided by a horizontal line where below the line is
$\mathcal{L}_{-}$ space and above is $\mathcal{L}_{+}$ subspace. Each diagram
deals with a fixed pair of ancilla qubits labelled $i$ and $j$. The diagram
(a) has three horizontal layers connected with vertically going arrows.
$V_{f}$ and $V_{s}$ are both components of $V_{+}$. In fact
$V_{+}=V_{f}+V_{s}$ where $V_{f}$ is responsible for the flipping and $V_{s}$
contributes when the transition does not have flipping. At the left of each
horizontal layer lies the expression for $G_{+}(z)$, which is different for
states in $\mathcal{L}_{+}$ with different Hamming weights. The diagram (b) is
constructed in a similar fashion except that we are dealing with the type of
4th order transition where the state stays the same for two transitions in
$\mathcal{L}_{+}$, hence the $V_{s}$ symbols and the arrows going from one
state to itself. The diagram (a) reflects the type of 4th order transition
that induces cross-gadget contribution and given our gadget parameter setting,
this contribution could be $O(1)$ when otherwise compensated. The diagram (b)
shows two paths that don not interfere with each other and thus having no
cross-gadget contributions.

For the term of order $k+2$, all the transition processes that contribute non-
trivially to the term can be categorized into two types:

  1. 1.

If $x=y$, the minimum number of flipping steps is 0. The contribution of all
such processes to the $(k+2)$-th order perturbative term is bounded by
footnote:comb

$\begin{array}[]{cl}\leq&\displaystyle
m^{k_{f}}\cdot\binom{k}{k_{f}}\cdot\|V_{f}\|^{k_{f}}\cdot\|V_{s}\|^{k-k_{f}}\cdot\frac{\|V_{-+}\|\cdot\|V_{+-}\|}{(\Delta-\max(z))^{k+1}}\end{array}$
(93)

where the factor $m^{k_{f}}$ is the number of all possible ways of flipping
$k_{f}$ times, each time one of the $m$ ancilla qubits. This serves as an
upper bound for the number of transition processes that contribute non-
trivially to the perturbative term. The factor $\binom{k}{k_{f}}$ describes
the number of possible ways to choose which $(k-k_{f})$ steps among the total
$k$ steps involve the state of the ancilla register staying the same.
$\|G_{+}\|\leq\frac{1}{\Delta-\max(z)}$ is used in the upper bound.

  2. 2.

If $x\neq y$, the minimum number of flipping steps is 2. The contribution of
all such processes to the $(k+2)$-th order perturbative term is bounded by

$\begin{array}[]{cl}\leq&\displaystyle\binom{k}{k_{f}}\cdot\binom{k_{f}}{2}\cdot
2!\cdot\|V_{f}\|^{k_{f}}\|V_{s}\|^{k-k_{f}}\cdot
m^{k_{f}-2}\cdot\frac{\|V_{-+}\|\cdot\|V_{+-}\|}{(\Delta-\max(z))^{k+1}}\end{array}$
(94)

where the factor $\binom{k}{k_{f}}$ is the number of all possible ways to
choose which $(k-k_{f})$ steps among the $k$ steps should the state remain the
same. $\binom{k_{f}}{2}$ is the number of possible ways to choose from the
$k_{f}$ flipping steps the 2 minimum flips. $2!$ is for taking into account
the ordering of the 2 flipping steps. $\|G_{+}\|\leq\frac{1}{\Delta-\max(z)}$
is used in the upper bound.

For a general $m$-qubit ancilla register, there are in total $m$ different
cases of the first type of transition processes and $\binom{m}{2}$ different
cases of the second type of transition processes. Therefore we have the upper
bound to the norm of the $(k+2)$-th term (Fig. 8)

$\begin{array}[]{ccl}\|V_{-+}(G_{+}V_{+})^{k}G_{+}V_{+-}\|&\leq&\displaystyle
m\sum_{k_{f}\in
K(k)}m^{k_{f}}\binom{k}{k_{f}}\cdot\|V_{f}\|^{k_{f}}\cdot\|V_{s}\|^{k-k_{f}}\frac{\|V_{-+}\|\cdot\|V_{+-}\|}{(\Delta-\max(z))^{k+1}}\\\\[7.22743pt]
&&\displaystyle+\binom{m}{2}\sum_{k=3}^{\infty}\binom{k}{k_{f}}\cdot\binom{k_{f}}{2}\cdot
2!\cdot\|V_{f}\|^{k_{f}}\|V_{s}\|^{k-k_{f}}\cdot
m^{k_{f}-2}\cdot\frac{\|V_{-+}\|\cdot\|V_{+-}\|}{(\Delta-\max(z))^{k+1}}\\\\[7.22743pt]
&&\displaystyle=\sum_{k_{f}\in
K(k)}\left(m+\frac{m-1}{m}\right)2^{k}\cdot\frac{\|V_{-+}\|\cdot(m\|V_{f}\|)^{k_{f}}\cdot\|V_{s}\|^{k-k_{f}}\cdot\|V_{+-}\|}{(\Delta-\max(z))^{k+1}}\\\\[7.22743pt]
&&\displaystyle\leq\frac{\|V_{-+}\|\cdot\|V_{+-}\|}{\Delta-\max(z)}(m+1)\sum_{k=3}^{\infty}\left(\frac{\|V_{s}\|}{\Delta-\max(z)}\right)^{k}\sum_{k_{f}\in
K(k)}\left(m\frac{\|V_{f}\|}{\|V_{s}\|}\right)^{k_{f}}.\end{array}$ (95)

Figure 8: Numerical verification for the upper bound to the norm of the
$(k+2)$-th order perturbative term in Eq. 95. Here we use the parallel 3-body
gadget for reducing $H_{\text{targ}}=0.1X_{1}Z_{2}Z_{3}-0.2X_{1}X_{2}Z_{3}$ up
to error $\epsilon=0.01$. The gap in the gadget construction is numerically
optimized footnote:num_op . Here the calculation of the analytical upper bound
uses the result in Eq. 95. The calculation is then compared with the norm of
the corresponding perturbative term numerically calculated according to the
self-energy expansion.

Since $\|\sum_{i=1}^{m}\sum_{j=1,j\neq i}^{m}\bar{V}_{ij}\|$ is bounded by
$\frac{1}{\Delta^{3}}\sum_{i=1}^{m}\sum_{j=1,j\neq
i}^{m}8({\kappa_{i}}{\kappa_{j}})^{2}{\openone}$, from Eq. 84 we see that

$\begin{array}[]{ccl}\|V_{s}\|&\leq&\displaystyle\|H_{\text{else}}\|+2^{-1/3}\Delta^{1/2}\sum_{i=1}^{m}|\alpha_{i}|^{1/3}+2^{4/3}\Delta^{1/2}\sum_{i=1}^{m}|\alpha_{i}|^{2/3}+\sum_{i=1}^{m}|\alpha_{i}|\\\\[7.22743pt]
&&\displaystyle+2^{8/3}\sum_{i=1}^{m}|\alpha_{i}|^{4/3}+\sum_{i=1}^{m}\sum_{j=1,j\neq
i}^{m}8\cdot 2^{-4/3}|\alpha_{i}|^{2/3}|\alpha_{j}|^{2/3}\equiv
v_{s}\\\\[7.22743pt] \|V_{f}\|&\leq&\displaystyle
2^{2/3}\Delta^{3/4}\sum_{i=1}^{m}|\alpha_{i}|^{1/3}\equiv v_{f}.\end{array}$
(96)

With bounds of $\|V_{s}\|$ and $\|V_{f}\|$ in Eq. 84, the summation in
Equation Eq. 95 can be written as

$\begin{array}[]{l}\displaystyle\|\sum_{k=3}^{\infty}V_{-+}(G_{+}V_{+})^{k}G_{+}V_{+-}\|\leq\frac{\|V_{-+}\|\cdot\|V_{+-}\|}{\Delta-\max(z)}(m+1)\\\\[7.22743pt]
\displaystyle\bigg{[}\sum_{r=1}^{\infty}\left(\frac{2v_{s}}{\Delta-\max(z)}\right)^{2r+1}\sum_{s=1}^{r}\left(m\frac{v_{f}}{v_{s}}\right)^{2s}+\sum_{r=2}^{\infty}\left(\frac{2v_{s}}{\Delta-\max(z)}\right)^{2r}\sum_{s=1}^{r}\left(m\frac{v_{f}}{v_{s}}\right)^{2s}\bigg{]}.\end{array}$
(97)

To guarantee convergence of the summation in Eq. 97 we require that $\Delta$
satisfies

$\displaystyle\frac{2mv_{f}}{\Delta-\max(z)}<1$ (98) $\displaystyle
m\left(\frac{v_{f}}{v_{s}}\right)>1,$ (99)

both of which are in general satisfied. The summation in Eq. 97 can then be
written as

$\begin{array}[]{c}\displaystyle\|\sum_{k=3}^{\infty}V_{-+}(G_{+}V_{+})^{k}G_{+}V_{+-}\|\leq\frac{\|V_{-+}\|\cdot\|V_{+-}\|}{\Delta-\max(z)}\cdot\frac{\left(m\frac{v_{f}}{v_{s}}\right)^{2}}{\left(m\frac{v_{f}}{v_{s}}\right)^{2}-1}\\\\[7.22743pt]
\displaystyle\frac{\left(\frac{2mv_{f}}{\Delta-\max(z)}\right)^{2}}{1-\left(\frac{2mv_{f}}{\Delta-\max(z)}\right)^{2}}(m+1)\left[\left(\frac{2mv_{f}}{\Delta-\max(z)}\right)^{2}+\frac{2v_{s}}{\Delta-\max(z)}\right]=\Theta(\Delta^{-1/2}),\end{array}$
(100)

which shows that the high order terms are $\Theta(\Delta^{-1/2})$. This is
tighter than the crude bound $\Theta(\Delta^{-1/4})$ shown in Eq. 91. The
self-energy expansion Eq. 86 then satisfies

$\|\Sigma_{-}(z)-H_{\text{targ}}\otimes{P_{-}}\|\leq\Theta(\Delta^{-1/2})$
(101)

which indicates that $\Delta=\Theta(\epsilon^{-2})$ is sufficient for the
parallel 3-body gadget to capture the entire spectrum of
$H_{\text{targ}}\otimes{P_{-}}$ up to error $\epsilon$.

We have used numerics to verify the $\Theta(\epsilon^{-2})$ scaling, as shown
in Fig. 8. Furthermore, for a range of specified $\epsilon$, the minimum
$\Delta$ needed for the spectral error between the gadget Hamiltonian and the
target Hamiltonian is numerically found. In the optimized cases, the slope
${\rm d}\log\Delta/{\rm d}\log\epsilon^{-1}$ for the construction in BDLT08
is approximately 3, showing that $\Delta=\Theta(\epsilon^{-3})$ is the optimal
scaling for the construction in BDLT08 . For our construction both the
analytical bound and the optimized $\Delta$ scale as $\Theta(\epsilon^{-2})$
(see Fig. 9).

Figure 9: Scaling of the spectral gap $\Delta$ as a function of error
$\epsilon$ for the parallel 3-body example that is intended to reduce the
target Hamiltonian $H_{\text{targ}}=Z_{1}Z_{2}Z_{3}-X_{1}X_{2}X_{3}$ to
2-body. Here $\epsilon=0.01$. We show both numerically optimized values
(“numerical”) in our construction and the construction in BDLT08 , which is
referred to as “[BDLT08]”.

##  Appendix B Compensation for the 4-local error terms in parallel 3- to
2-body gadget

Continuing the discussion in Appendix A, here we deal with $\Theta(1)$ error
terms that arise in the $3^{\text{rd}}$ and $4^{\text{th}}$ order perturbative
expansion when $V$ in Eq. 75 is without $V_{3}$ and in so doing explain the
construction of $\bar{V}_{ij}$ in Eq. 82. From the previous description of the
$3^{\text{rd}}$ and $4^{\text{th}}$ order terms, for each pair of terms $(i)$
and $(j)$ where $i$ and $j$ are integers between 1 and $m$, let

$\begin{array}[]{ccl}M_{1}&=&({\kappa_{i}}{A_{i}}+{\lambda_{i}}{B_{i}})({\kappa_{j}}{A_{j}}+{\lambda_{j}}{B_{j}})\\\\[7.22743pt]
M_{2}&=&({\kappa_{j}}{A_{j}}+{\lambda_{j}}{B_{j}})({\kappa_{i}}{A_{i}}+{\lambda_{i}}{B_{i}})\end{array}$

and then the $\Theta(1)$ error term arising from the $3^{\text{rd}}$ and
$4^{\text{th}}$ order perturbative expansion can be written as

$\frac{1}{(z-\Delta)^{2}}\bigg{[}\frac{1}{z-2\Delta}(M_{1}^{2}+M_{2}^{2})+\left(\frac{1}{\Delta}+\frac{1}{z-2\Delta}\right)(M_{1}M_{2}+M_{2}M_{1})\bigg{]}.$
(102)

Based on the number of non-commuting pairs among ${A_{i}}$, ${A_{j}}$,
${B_{i}}$ and ${B_{j}}$, all possible cases can be enumerated as the
following:

$\begin{array}[]{ccl}\text{case
0:}&&[{A_{i}},{A_{j}}]=0,[{B_{i}},{B_{j}}]=0,[{A_{i}},{B_{j}}]=0,[{B_{i}},{A_{j}}]=0\\\\[7.22743pt]
\text{case
1:}&1.1:&[{A_{i}},{A_{j}}]=0,[{B_{i}},{B_{j}}]=0,[{A_{j}},{B_{i}}]\neq
0\\\\[7.22743pt]
&1.2:&[{A_{i}},{A_{j}}]=0,[{B_{i}},{B_{j}}]=0,[{A_{i}},{B_{j}}]\neq
0\\\\[7.22743pt] &1.3:&[{A_{i}},{A_{j}}]=0,[{B_{i}},{B_{j}}]\neq
0\\\\[7.22743pt] &1.4:&[{A_{i}},{A_{j}}]\neq
0,[{B_{i}},{B_{j}}]=0\\\\[7.22743pt] \text{case 2:}&&[{A_{i}},{A_{j}}]\neq
0,[{B_{i}},{B_{j}}]\neq 0.\end{array}$ (103)

In case 0, clearly $M_{1}=M_{2}$. Then the $\Theta(1)$ error becomes

$\frac{1}{(z-\Delta)^{2}}\left(\frac{1}{\Delta}+\frac{2}{z-2\Delta}\right)\cdot
2M_{1}^{2}=\Theta(\Delta^{-1})$

which does not need any compensation. In case 1, for example in the subcase
1.1, ${A_{j}}$ does not commute with ${B_{i}}$. Then $M_{1}$ and $M_{2}$ can
be written as

$\begin{array}[]{ccl}M_{1}&=&K+{\kappa_{j}}{\lambda_{i}}{B_{i}}{A_{j}}\\\\[7.22743pt]
M_{2}&=&K+{\kappa_{j}}{\lambda_{i}}{A_{j}}{B_{i}}\end{array}$

where $K$ contains the rest of the terms in $M_{1}$ and $M_{2}$. Furthermore,

$\begin{array}[]{c}M_{1}^{2}+M_{2}^{2}=2K^{2}-2({\kappa_{j}}{\lambda_{i}})^{2}{\openone}\\\\[7.22743pt]
M_{1}M_{2}+M_{2}M_{1}=2K^{2}+2({\kappa_{j}}{\lambda_{i}})^{2}{\openone}.\end{array}$

Hence the $\Theta(1)$ term in this case becomes

$\frac{1}{(z-\Delta)^{2}}\bigg{[}\left(\frac{1}{\Delta}+\frac{2}{z-2\Delta}\right)2K^{2}+\frac{1}{\Delta}\cdot
2({\kappa_{j}}{\lambda_{i}})^{2}{\openone}\bigg{]}$ (104)

where the first term is $\Theta(\Delta^{-1})$ and the second term is
$\Theta(1)$, which needs to be compensated. Similar calculations for cases
1.2, 1.3 and 1.4 will yield $\Theta(1)$ error with the same norm. In case 2,
define
$R={\kappa_{i}}{\lambda_{j}}{A_{i}}{B_{j}}+{\lambda_{i}}{\kappa_{j}}{B_{i}}{A_{j}}$
and
$T={\kappa_{i}}{\kappa_{j}}{A_{i}}{A_{i}}+{\lambda_{i}}{\lambda_{j}}{B_{i}}{B_{i}}$.
Then

$\begin{array}[]{c}M_{1}^{2}+M_{2}^{2}=2(R^{2}+T^{2})\\\\[7.22743pt]
M_{1}M_{2}+M_{2}M_{1}=2(R^{2}-T^{2}).\end{array}$

The $\Theta(1)$ error terms in the 3rd and 4th order perturbative expansion
becomes

$\frac{1}{(z-\Delta)^{2}}\bigg{[}\left(\frac{1}{\Delta}+\frac{2}{z-2\Delta}\right)\cdot
2R^{2}-\frac{1}{\Delta}\cdot 2T^{2}\bigg{]}$ (105)

where the first term is $\Theta(\Delta^{-1})$ and hence needs no compensation.
The second term is $\Theta(1)$. Define

$s_{0}^{(i,j)}=\left\\{\begin{array}[]{ccl}1&&\text{if case 0}\\\\[7.22743pt]
0&&\text{Otherwise}\end{array}\right.$ (106)

With the definitions of $s_{1}^{(i,j)}$ and $s_{2}^{(i,j)}$ in Eq. 79, Eq. 80
and Eq. 81, the contribution of the $i$-th and the $j$-th target terms to the
$\Theta(1)$ error in the perturbative expansion $\Sigma_{-}(z)$ becomes

$\begin{array}[]{cl}&\displaystyle
s_{0}^{(i,j)}\cdot\frac{1}{(z-\Delta)^{2}}\left(\frac{1}{\Delta}+\frac{2}{z-2\Delta}\right)\cdot
2({\kappa_{i}}{A_{i}}+{\lambda_{i}}{B_{i}})^{2}({\kappa_{j}}{A_{j}}+{\lambda_{j}}{B_{j}})^{2}\\\\[7.22743pt]
+&\displaystyle
s_{1}^{(i,j)}\cdot\frac{1}{(z-\Delta)^{2}}\bigg{[}\left(\frac{1}{\Delta}+\frac{2}{z-2\Delta}\right)\cdot
2K_{ij}^{2}+\frac{1}{\Delta}\cdot
2({\kappa_{i}}{\kappa_{j}})^{2}{\openone}\bigg{]}\\\\[7.22743pt]
+&\displaystyle
s_{2}^{(i,j)}\cdot\frac{1}{(z-\Delta)^{2}}\bigg{[}\left(\frac{1}{\Delta}+\frac{2}{z-2\Delta}\right)\cdot
2R_{ij}^{2}+\frac{1}{\Delta}\cdot
2\\{[({\kappa_{i}}{\kappa_{j}})^{2}+({\lambda_{i}}{\lambda_{j}})^{2}]{\openone}\\\\[7.22743pt]
&\displaystyle-2{\kappa_{i}}{\kappa_{j}}{\lambda_{i}}{\lambda_{j}}{A_{i}}{A_{j}}{B_{i}}{B_{j}}\\}\bigg{]}.\end{array}$
(107)

The term proportional to $s_{0}^{(i,j)}$ in Eq. 107 does not need compensation
since it is already $\Theta(\Delta^{-1})$. The term proportional to
$s_{1}^{(i,j)}$ can be compensated by the corresponding term in $\bar{V}_{ij}$
in Eq. 82 that is proportional to $s_{1}^{(i,j)}$. Similarly, the $\Theta(1)$
error term proportional to $s_{2}^{(i,j)}$ can be compensated by the term in
$\bar{V}_{ij}$ in Eq. 82 that is proportional to $s_{2}^{(i,j)}$.

Now we deal with generating the 4-local term in $\bar{V}_{ij}$. Introduce an
ancilla $u_{ij}$ and construct a gadget $\tilde{H}_{ij}=H_{ij}+V_{ij}$ such
that $H_{ij}=\Delta|1\rangle\langle{1}|_{u_{ij}}$ and the perturbation
$V_{ij}$ becomes

$V_{ij}=(\kappa_{i}A_{i}+\lambda_{j}B_{j})\otimes
X_{u_{ij}}+(\kappa_{j}A_{j}+\lambda_{i}B_{i})\otimes|1\rangle\langle{1}|_{u_{ij}}+V^{\prime}_{ij}$
(108)

where $V^{\prime}_{ij}$ is defined as

$V^{\prime}_{ij}=\frac{1}{\Delta}(\kappa_{i}A_{i}+\lambda_{j}B_{j})^{2}+\frac{1}{\Delta^{3}}\left[(\kappa_{j}^{2}+\lambda_{i}^{2})(\kappa_{i}A_{i}+\lambda_{j}B_{j})^{2}-2\kappa_{j}\lambda_{i}(\kappa_{j}^{2}+\lambda_{j}^{2})A_{j}B_{i}\right]$
(109)

The self-energy expansion $\Sigma_{-}(z)$ is now

$\Sigma_{-}(z)=\frac{1}{(z-\Delta)^{3}}4\kappa_{i}\kappa_{j}\lambda_{i}\lambda_{j}A_{i}A_{j}B_{i}B_{j}+O(\Delta^{-1/2})$

which is $O(\Delta^{-1/2})$ close to the 4-local compensation term in
$\bar{V}_{ij}$. We apply the the gadget $\tilde{H}_{ij}$ for every pair of
qubits with $s_{2}^{(i,j)}=1$. The cross-gadget contribution between the
$\tilde{H}_{ij}$ gadgets as well as those cross-gadget contribution between