††thanks: SC and PKF have contributed equally.

# Non-recursive perturbative gadgets without subspace restrictions and
applications to variational quantum algorithms

Simon Cichy Dahlem Center for Complex Quantum Systems, Freie Universität
Berlin, 14195 Berlin, Germany  Institute for Theoretical Physics, ETH Zürich,
8093 Zürich, Switzerland  Paul K. Faehrmann Dahlem Center for Complex Quantum
Systems, Freie Universität Berlin, 14195 Berlin, Germany  Sumeet Khatri Dahlem
Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin,
Germany  Jens Eisert Dahlem Center for Complex Quantum Systems, Freie
Universität Berlin, 14195 Berlin, Germany  Helmholtz-Zentrum Berlin für
Materialien und Energie, Hahn-Meitner-Platz 1, 14109 Berlin, Germany
Fraunhofer Heinrich Hertz Institute, 10587 Berlin, Germany

###### Abstract

Perturbative gadgets are a tool to encode part of a Hamiltonian, usually the
low-energy subspace, into a different Hamiltonian with favorable properties,
for instance, reduced locality. Many constructions of perturbative gadgets
have been proposed over the years. Still, all of them are restricted in some
ways: Either they apply to some specific classes of Hamiltonians, they involve
recursion to reduce locality, or they are limited to studying time evolution
under the gadget Hamiltonian, e.g., in the context of adiabatic quantum
computing, and thus involve subspace restrictions. In this work, we fill the
gap by introducing a versatile universal, non-recursive, non-adiabatic
perturbative gadget construction, without subspace restrictions, that encodes
an arbitrary many-body Hamiltonian into the low-energy subspace of a three-
body Hamiltonian. Our construction requires $rk$ additional qubits for a
$k$-body Hamiltonian comprising $r$ terms. Besides a specific gadget
construction, we also provide a recipe for constructing similar gadgets, which
can be tailored to different properties, which we discuss.

[mainsections]

##  I Introduction

The study of many-body Hamiltonians is a well-researched field in condensed
matter physics and quantum information theory. While the presence of
Hamiltonian terms acting on many qubits simultaneously can result in exciting
phenomena, in many situations, it also carries additional difficulties. Be it
due to the hardness of generating them experimentally or other limitations,
local Hamiltonians are usually simpler to deal with.

Born in the context of complexity theory for proving the QMA-completeness of
the local Hamiltonian problem [1, 2], a problem located at the interface of
the theory of quantum many-body physics and of Hamiltonian complexity, so-
called _perturbative gadgets_ can be used to reduce the locality of a given
many-body Hamiltonian. This is done by embedding it in the low-energy subspace
of a tailored, local, i.e. few-body, Hamiltonian acting on a larger Hilbert
space [3, 4]. Among the best-known constructions is the subdivision gadget
proposed by Oliveira and Terhal [4]. It employs mediator qubits to halve the
support of a given Hamiltonian term and can be recursively applied to
construct an at best three-body Hamiltonian mimicking the original $k$-body
Hamiltonian. As is typical for perturbative gadgets, such a procedure,
unfortunately, leads to an exponential increase of the interaction strengths
required for the gadget Hamiltonian to accurately mimic the low-energy
subspace of the original Hamiltonian.

A different gadget, proposed by Jordan and Farhi [5], can avoid the need for
recursion and offers a direct reduction from $k$-body to two-body
Hamiltonians, albeit with an exponential suppression of energies. However,
their direct construction is only applicable when one can restrict the
evolution of chosen initial states to predefined subspaces of the Hilbert
space, as can be done in adiabatic quantum computing, where commutation
relations guarantee the system remains in the initialized subspace.

Since such a limitation restricts the applicability of this direct $k$-to-two-
local gadget, the question arises whether there exists a direct, non-recursive
$k$-to-$k^{\prime}$-local gadget without such restrictions and whether such a
gadget could have any applications besides being a tool for proving complexity
theoretic results. After all, perturbative gadgets have so far mostly found
their application in proving hardness results for the general local
Hamiltonian problem [3, 4] or certain classes of Hamiltonians [6, 7, 8, 9, 10]
equipped with further constraints and properties.

In this work, we address these questions by proposing a direct $k$-to-three-
local gadget without the need for subspace restrictions, that is inspired by
Ref. [5] but that avoids initialization and commutation properties from
adiabatic quantum computing to achieve the same locality reduction as the
repeated subdivision procedure [4], without requiring recursive applications.
As expected from gadget constructions [11], our construction is not free from
unfavorable energy scalings, but we still explore the use of such a gadget
within gate-based quantum computing and, in particular, as a method for
reducing the locality of the cost function in variational quantum algorithms,
a setting that does not comply with the “adiabatic” restriction, or the
grouping of measurement terms. By providing a more general recipe for
constructing perturbative gadgets with similar performance guarantees and
suggesting plausible heuristics, we further hope to start a discussion about
how the trade-offs of perturbative gadgets could still be used for practical
problems.

We begin by introducing the main ideas and a historical overview of
perturbative gadgets in Section II, before focusing on a specific $k$-to-
three-local gadget and discussing guarantees on its performance in Section
III. We then generalize the gadget construction to provide a recipe for
creating custom perturbative gadgets in Section IV and discuss the nuances of
applying such gadgets in gate-based quantum computing in Section V, before
concluding with some remarks and open questions in Section VI.

##  II Perturbative gadgets in a nutshell

Authors |  Main statement
---|---
Kempe, Kitaev, Regev (KKR) [3] |  3- to 2-local gadget to prove QMA completeness of the local Hamiltonian problem. Requires restriction of the state evolution to a subspace of the Hilbert space.
Oliveira, Terhal (OT) [4] |  Subdivision gadget ($k$\- to $k/2$-local) and proof of QMA completeness of the Hamiltonian problem on a square grid. Has to be applied recursively resulting in exponential coupling strengths.
Biamonte, Love [12] |  “Realizable Hamiltonians” with a focus on using gadgets for adiabatic computing and adapting to hardware restrictions, not targeting a reduction of locality.
Bravyi, DiVicenzo, Loss, Terhal [13] |  Improvements on the OT gadget through extension to non-converging perturbative expansion, thus reducing the gap in coupling strengths
Jordan, Farhi [5] |  Direct $k$\- to $2$-local gadget through higher-order perturbation theory. Requires restriction of the state evolution to a subspace of the Hilbert space.
Cao, Babbush, Biamonte, Kais [14] |  Resource requirement improvements of some of the OT and KKR previous gadgets.
Cao [15] |  Overview of existing gadgets and improvements of the OT and KKR gadgets.
Cao, Kais [16] |  Improvement of the convergence bound for the JF gadget.
Subasi, Jarzynski [17] |  Nonperturbative gadgets for adiabatic Hamiltonian evolution.
Bausch [18] |  Augmentation of other gadget constructions and changes their energy scales by (potentially) increasing their locality by one.
Harley, Datta, Klausen, Bluhm, França, Werner, Christandl [11] |  A general framework for analog quantum simulation and unavoidable unfavorable size-dependent scalings of gadget constructions.
This work |  Direct $k$\- to $2$-local gadget without restriction to some subspace of the Hilbert space.
Table 1:  Overview of some relevant works related to perturbative gadgets. Not
included are those that apply only to a restricted subset of possible
Hamiltonian as could be topological ones.

Perturbative gadgets [3, 4, 5, 19] encode the low-energy subspace of a many-
body Hamiltonian into the low-energy subspace of a fewer-body Hamiltonian.
They make use of perturbation theory in the opposite direction than what is
more common: instead of considering the effect of some perturbation $\lambda
V$ on a well-understood Hamiltonian $H$ according to $H^{\prime}=H+\lambda V$,
perturbative gadgets provide a suitable $H$ and perturbation $V$ such that
$H^{\prime}$ is a few-body Hamiltonian that approximates the low-energy
subspace of a given, target Hamiltonian $H^{\text{target}}$, as visualized in
Figure 1. They are often accompanied by an increase in the number of required
qubits and either suppress the energy of the desired low-energy subspace or an
increase in the norm of $H^{\prime}$ compared to $H^{\text{target}}$.

In most cases, a local and simple Hamiltonian with degenerate ground space is
used as the so-called “unperturbed Hamiltonian” $H$. The degeneracy is chosen
to correspond to the dimension of the space acted upon by the target
Hamiltonian. Then, a perturbation is designed to split said degeneracy in a
way that the resulting low-energy subspace emulates the target spectrum, so
roughly

$\Pi H^{\prime}\Pi\sim H^{\text{target}},$ (1)

where $\Pi$ denotes a projector on the low-energy subspace. This statement
will later be made formal in Theorem 1.

To be explicit and clear, we use interaction weight to refer to the number of
particles acted upon by a given operator and interaction strength to refer to
the coefficient of that operator. When talking about qubits and expanding
operators in the Pauli basis, the weight of a Pauli string (a tensor product
of Pauli operators) is defined as the number of non-trivial Pauli operations
in the string. Throughout this work, we use “locality” to refer to the maximum
weight of all terms in a Hamiltonian, independently of geometry. We use the
term _local_ for Hamiltonians with fixed small weights, that is weights that
do not scale with problem size, while _global_ is reserved for Hamiltonians
with all-to-all interactions.

An overview of works related to perturbative gadgets is presented in Table 1.
Historically, perturbative gadgets were developed to prove the QMA-hardness of
the local Hamiltonian problem. The $3$-local Hamiltonian problem is known to
be QMA-complete [2] and Kempe, Kitaev, and Regev have shown that so is the
$2$-local problem by proposing the first perturbative gadget, which reduces
the locality from $3$ to $2$ [3]. Oliviera and Terhal have added to this by
showing that the $2$-local Hamiltonian problem is still QMA-complete when
restricting the interaction to a 2D square lattice, and in doing so introduced
a new perturbative gadget. This subdivision gadget reduces the locality of a
$k$-local Hamiltonian to $\lceil k/2\rceil+1$-local interactions by
introducing a single auxiliary qubit per interaction term. These kinds of
gadgets have also been considered to be used outside of the world of
complexity-theoretic analysis, but they are inherently not practical, as
discussed further in Section V.

Furthermore, the recursive use of gadgets to arrive at two-local Hamiltonians
can be avoided by a single gadget introduced by Jordan and in Ref. [5], which
encodes $k$-local Hamiltonians in $k^{\text{th}}$ order of perturbation theory
of a two-local gadget Hamiltonian. However, just like the three-to-two local
gadget, their construction relies on certain properties of the evolution of a
state under a Hamiltonian, such as provided in the adiabatic setting.

In the following years, several works proposed improvements in resource
requirements, convergence bounds, or coupling strengths [14, 15, 16, 18], as
well as introduced highly specialized gadget constructions for restricted
classes of Hamiltonians, such as for topological quantum codes and for
realizing certain parent Hamiltonians featuring intrinsic topological order
[19, 20].

There are two important things to note at this point: While all of these
gadget constructions rely on perturbation theory, they use different
techniques, ranging from perturbative expansion due to Bloch [21], which
underlies the Jordan-Farhi gadget, the Feynman-Dyson series employed in Ref.
[6] to the _Schrieffer-Wolf transformation_ [22], discussed in Ref. [16].
Furthermore, except for the so-called subdivision gadget due to Oliveira and
Terhal [4], the other gadgets are restricted to the setting of time evolution
under the Hamiltonian, which guarantees the evolution to remain in the
initialized subspaces. A non-recursive $k$-to-two-local gadget without these
restrictions is currently unknown.

Figure 1: Sketch of the main idea behind perturbative gadgets: starting from
an unperturbed Hamiltonian $H^{(0)}$ with gap $\gamma$ and degenerate ground
space, add a perturbation $V$ such that the lowest energy states resulting
from the perturbation of the ground space mimic the target Hamiltonian
$H^{\text{target}}$.

##  III A direct $k$-to-three-body gadget without subspace restriction

One of the main results of this work is the proposal of a direct, i.e., non-
recursive, three-body gadget Hamiltonian $H^{\text{gad}}$ derived from an
arbitrary $k$-body Hamiltonian $H^{\text{target}}$ that does not require any
restrictions to a subspace of the Hilbert space, inspired by the work of
Jordan and Farhi [5]. We then find that the low-energy subspace of
$H^{\text{gad}}$ mimics the low-energy subspace of $H^{\text{target}}$
(Theorem 1), implying a guarantee on the closeness of their ground states
(Corollary 1).

Figure 2: Representation of a target Hamiltonian (left) and its associated
gadget Hamiltonian, as defined in Eq. (3), for the case of $n=8$, $k=4$ and
$r=3$. Qubits that interact according to the terms of the Hamiltonian are
placed in the same colored region. Shown in the central and right-hand panels
are the contributions to the gadget Hamiltonian from two of the three four-
body terms, with the auxiliary qubits in gray and the target qubits in black.

We start by defining the gadget Hamiltonian that is the focus of our study.

######  Definition 1 (Gadget Hamiltonian).

Let $H^{\text{target}}$ be a $k$-body Hamiltonian acting on $n$ qubits, given
by

$H^{\text{target}}\coloneqq\sum\limits_{s=1}^{r}c_{s}h_{s},\quad\text{with}\quad
h_{s}=\sigma_{s,1}\otimes\sigma_{s,2}\otimes\dots\otimes\sigma_{s,k},$ (2)

where each term is a tensor product of at most $k\leq n$ single qubit
operators, with $\sigma_{s,j}=n_{X}X+n_{Y}Y+n_{Z}Z$ and
$(n_{X},n_{Y},n_{Z})\in\mathbb{R}^{3}$ a unit vector. We define the three-body
gadget Hamiltonian $H^{\text{gad}}$ corresponding to $H^{\text{target}}$,
acting on $n+rk$ qubits, as

$H^{\text{gad}}\coloneqq\sum\limits_{s=1}^{r}H^{\text{aux}}_{s}+\lambda\sum\limits_{s=1}^{r}V_{s},$
(3)

where

$\displaystyle H^{\text{aux}}_{s}$
$\displaystyle\coloneqq\sum\limits_{j=1}^{k}\frac{1}{2}\left(\mathds{1}_{s,j}-Z_{s,j}^{\text{aux}}\right)=\sum\limits_{j=1}^{k}|1\rangle\\!\langle
1|_{s,j}^{\text{aux}},$ (4) $\displaystyle V_{s}$
$\displaystyle\coloneqq\sum\limits_{j=1}^{k}\tilde{c}_{s,j}\sigma_{s,j}^{\text{target}}\otimes
X_{s,j}^{\text{aux}}\otimes X_{s,(j+1)\text{ mod }k}^{\text{aux}}$ (5)

and $\tilde{c}_{s,j}=-(-1)^{k}c_{s}$ if $j=1$ or $\tilde{c}_{s,j}=1$
otherwise. We refer to the $n$ qubits on which $H^{\text{target}}$ acts as
_target qubits_ , and the $rk$ additional qubits as _auxiliary qubits_.

In our gadget Hamiltonian, each term $H_{s}^{\text{aux}}$ acts only on the
$s^{\text{th}}$ group of auxiliary qubits, while each term $V_{s}$ acts on a
target qubit and the $s^{\text{th}}$ group of auxiliary qubits; see Fig. 2 for
a graphical depiction for a toy model.

Figure 3: Visualization of the key steps in the proof of Theorem 1. (a) For
illustrative purposes, we take as the $k$-body target Hamiltonian
$H^{\text{target}}=\bigotimes_{j=1}^{5}\sigma_{j}$, where
$\sigma_{j}\in\\{X,Y,Z\\}$ are Pauli operators, so that $k=5$. (b) The
unperturbed auxiliary Hamiltonian, given in Eq. (4), acts only on the
auxiliary qubits. (c) Acting with the perturbation $V$ in Eq. (5), at second
order, one term could result in flipping the second and last auxiliary qubits,
hence ejecting the state out of the ground space and not contributing to the
perturbative expansion. (d) At $k^{\text{th}}$ order in perturbation theory,
we obtain a non-trivial contribution acting on all target qubits
simultaneously, mimicking the target Hamiltonian, while acting trivially on
the auxiliary qubits.

The proposed gadget is heavily inspired by the gadget introduced by Jordan and
Farhi in Ref. [5], in which they rely on properties of adiabatic quantum
computing. Both their gadget and ours take advantage of a larger Hilbert space
to encode the low-energy subspace of the target Hamiltonian, so the dimension
of the ground space of the unperturbed Hamiltonian must be the same as the
space on which the target Hamiltonian acts. This point is made more explicit
in Appendix B. Jordan and Farhi start from a larger ground space of the
unperturbed Hamiltonian and reduce the dimension by restricting the region of
the Hilbert space that can be explored by initializing the system in a fixed
subspace. Remaining in this chosen subspace is then ensured by using
properties of adiabatic evolution, something that cannot be done
straightforwardly outside of the regime of adiabatic quantum computing. This
requirement, therefore, places a strong limitation on the applicability of
their construction. On the other hand, our gadget construction does not
require such a restriction to a subspace, therefore avoiding this limitation
and is applicable even to digital quantum computing and specifically to
variational quantum algorithms. We refer to Appendix F for a more detailed
discussion of why a direct application of the gadget introduced by Jordan and
Farhi is not possible in the realm of non-adiabatic quantum computing.

Similar to the results of Jordan and Farhi, we can show that the subspace of
the $2^{n}$ lowest energy eigenstates of our three-body gadget Hamiltonian in
Eq. (3) mimics that of the $k$-body target Hamiltonian. For the formal
statement, we define the following notation: Let $H$ be a Hamiltonian acting
on $n$ qubits, with spectral decomposition
$H=\sum_{j=0}^{2^{n}-1}E_{j}|\psi_{j}\rangle\\!\langle\psi_{j}|$ such that
$E_{0}\leq E_{1}\leq\dotsb\leq E_{2^{n}-1}$, we define
$H_{\text{eff}}(H,d)=\sum_{j=0}^{d-1}E_{j}|\psi_{j}\rangle\\!\langle\psi_{j}|$
to be the effective Hamiltonian corresponding to the $d$ lowest eigenvalues of
$H$.

######  Theorem 1 (Main result).

Let $H^{\text{target}}$ and $H^{\text{gad}}$ be as in Definition 1, and let
$\lambda\leq\lambda_{\text{max}}$, with
$\lambda_{\text{max}}=\frac{1}{4}\left(\sum_{s=1}^{r}|c_{s}|+r(k-1)\right)^{-1}$.
Then, there exists an $f(\lambda)=\mathcal{O}(\operatorname{poly}\lambda)$ and
$\Xi=\mathcal{O}(\operatorname{poly}k)$ such that

$H_{\text{eff}}(H^{\text{gad}},2^{n})=\frac{\lambda^{k}}{\Xi}H^{\text{target}}\otimes\left(|0\rangle\\!\langle
0|\right)^{\otimes rk}\\\ +f(\lambda)\Pi+\mathcal{O}(\lambda^{k+1}),$ (6)

where $\Pi$ is the projector onto the support of
$H_{\text{eff}}(H^{\text{gad}},2^{n})$.

Furthermore, we can provide a guarantee on the closeness of the ground states
of the target and gadget Hamiltonians.

######  Corollary 1 (Guarantees on the closeness of the ground states).

Let $H^{\text{target}}$ and $H^{\text{gad}}$ be as in Theorem 1. Then, there
exists a perturbation strength $\lambda^{*}$, with

$\lambda^{*}\leq\lambda_{\text{max}}\quad\text{ and
}\quad\lambda^{*}\leq\frac{E^{\text{target}}_{1}-E^{\text{target}}_{0}}{\Xi\|O^{\text{err}}\|},$
(7)

such that for all $\lambda\leq\lambda^{*}$ it holds that

$\left\lVert\psi_{0}-\operatorname{Tr}_{\text{aux}}[\phi_{0}]\right\rVert_{2}\leq\mathcal{O}(\lambda),$
(8)

where $\psi_{0}=|\psi_{0}\rangle\\!\langle\psi_{0}|$ and
$\phi_{0}=|\phi_{0}\rangle\\!\langle\phi_{0}|$ are in the ground spaces of
$H^{\text{target}}$ and $H^{\text{gad}}$, respectively.

In Fig. 3, we provide a visualization of the main steps in the proof of
Theorem 1, focusing on the main ideas behind these results and referring the
mathematically interested reader to the appendices. Specifically, after a
recap in Appendix A of the perturbation theory on which our results are based,
we prove Theorem 1 in Appendix B and Corollary 1 in Appendix C.

For clarity, the construction is stated for target Hamiltonians where each
term has the same Pauli weight, and for the maximal reduction: to a three-
local gadget Hamiltonian. This gadget can be generalized with respect to both
of these aspects and we show how to construct a gadget for mixed Pauli weights
in Appendix D.1 and also how to trade off target locality for reduced
resources in Appendix D.2.

##  IV A recipe for creating your own perturbative gadget

In the previous section, we presented a specific perturbative gadget
construction. However, that construction is by no means unique, because there
is some freedom in designing such gadgets. For instance, the choice of Pauli
operators in the unperturbed Hamiltonian acting on the auxiliary qubits or in
the perturbation could have been different. More generally, the general
construction of the penalization in $H^{\text{aux}}_{s}$ and of the
perturbation $V_{s}$ leaves many knobs to tweak. Especially for practical
implementations, it might be interesting to derive slightly different gadgets,
which result in similar low-energy spectra but are constructed from a
different set of operators, for instance, some that are easier to implement on
the hardware of choice.

Here, we present a more general framework for the construction of non-
recursive, non-adiabatic perturbative gadgets based on higher-order
perturbation theory that all lead to similar results as Theorem 1, with the
only notable difference being the exact form of $\Xi$ in Eq. (6).

The core idea is again to start from a well-known, unperturbed Hamiltonian
$H^{\text{aux}}$ and to perturb it with a perturbation $\lambda V$, such that
we recover the original, $k$-body target Hamiltonian at $k^{\text{th}}$ order
in perturbation theory. Since the $k^{\text{th}}$ order in perturbation theory
comes with $k$-fold applications of the perturbation $V$, we engineer the
perturbation such that only cross-terms leading to the desired result
contribute. That is if the target Hamiltonian has been cut into $k$ pieces
$O^{\text{target}}=O_{1}\otimes\ldots\otimes O_{k}$, we ensure that only the
correct $k$-fold products of $V$ survive.

To construct a perturbative gadget following a similar recipe as the one
presented in this work, we require a _penalization Hamiltonian_ $H$ and a
_perturbation operator_ $A$, both acting on a single auxiliary register of $k$
qubits. Although those are not the unperturbed Hamiltonian $H^{\text{aux}}$
and the perturbation $V$ directly, they are closely related. $H^{\text{aux}}$
will be built using instances of $H$, while the perturbation operator will be
a key component in the construction of the perturbation $V$. We further
require $H^{\text{aux}}$ to be composed of few-body terms and to have a non-
degenerate ground space to avoid the limitations of prior gadget constructions
[3, 17, 5]. That is, we need

$H=\sum_{i}h_{i},$ (9)

for some finite sum of operators $h_{i}$, each of which is few-body, such that
$H$ has a unique ground state vector, which we denote by $|GS\rangle$. We note
that the restriction on few-body terms is not strictly required for the
construction to yield the desired low-energy subspace, but for decreasing the
locality of the Hamiltonian.

Let us now argue that the operator $A$ should exhibit a product form of $k$
operators $a_{1},a_{2},\dotsc,a_{k}$, such that

$A=\prod_{j=1}^{k}a_{j},$ (10)

with the following properties:

$\displaystyle A|GS\rangle\propto|GS\rangle,$ (11) $\displaystyle\langle
GS|\prod_{\ell=1}^{m}a_{j_{\ell}}|GS\rangle=0\quad\forall~{}m<k,\,\forall~{}\\{j_{\ell}\\}\subset\\{1,2,\dotsc,k\\},$
(12) $\displaystyle
a_{j}^{2}=\mathds{1}\quad\forall~{}j\in\\{1,2,\dotsc,k\\}.$ (13)

The first condition states that the ground state of $H$ should also be an
eigenstate of $A$, while the second enforces that any partial application of
the operators $a_{j}$ results in a state orthogonal to $|GS\rangle$. These are
vital to ensure that at orders lower than $k$ in perturbation theory, the
perturbation will always expel the state out of the ground space. The final
property ensures that when the same perturbation is applied twice, it results
in a constant energy shift.

With the above properties, we can construct $H^{\text{aux}}$ and $V$ as

$\displaystyle H^{\text{aux}}$
$\displaystyle=\underbrace{\vphantom{\sum_{s=1}^{r}}\mathds{1}^{\otimes
n}}_{\mathclap{\text{target register}\hskip
7.00002pt}}\otimes\underbrace{\sum_{s=1}^{r}\mathds{1}^{\otimes(s-1)k}\otimes
H\otimes\mathds{1}^{\otimes(r-s-1)k}}_{\text{auxiliary registers}},$ (14)
$\displaystyle V$
$\displaystyle=\sum_{s=1}^{r}\sum_{j=1}^{k}\tilde{c}_{s,j}\sigma_{s,j}\otimes\mathds{1}^{\otimes(s-1)k}\otimes
a_{j}\otimes\mathds{1}^{\otimes(r-s-1)k},$ (15)

where the definition of the coefficients $\tilde{c}_{s,j}$ provides another
knob to tweak. They could be defined similarly to Definition 1 or in an
arbitrary fashion, as long as

$\prod_{j=1}^{k}\tilde{c}_{s,j}=-(-1)^{k}c_{s}$ (16)

still holds. Given these conditions, similar results as in Theorem 1 will hold
by the arguments laid out in Appendix B. Indeed, the gadget we propose is
simply a special case of

$\displaystyle h_{i}$
$\displaystyle=\frac{1}{2}(\mathds{1}-Z_{i})=|1\rangle\\!\langle 1|_{i},$
$\displaystyle i\in\\{1,2,\dotsc,k\\},$ (17) $\displaystyle a_{j}$
$\displaystyle=X_{j}\otimes X_{(j+1)\text{ mod }k},$ $\displaystyle
j\in\\{1,2,\dotsc,k\\}.$ (18)

Note that the Hamiltonian in Eq. (14) has a non-degenerate ground space when
considering only the auxiliary registers but has a $2^{n}$ degenerate ground
space when additionally considering the target qubits which it acts trivially
upon.

Furthermore, we would like to stress that any gadget constructed in this
fashion will be accompanied by a suppression of the target Hamiltonian in the
low-energy subspace by a factor of $\lambda^{k}$, therefore not avoiding a
blow-up in resource costs exponential in the reduction in the locality.

##  V On the trade-offs in using perturbative gadgets for practical
applications

Perturbative gadgets have been a useful tool in complexity theory, in
particular in the study of the QMA-completeness of the local Hamiltonian
problem [3, 4]. These successes and the locality-reducing property encourage
us to look for practical applications of these kinds of gadgets outside of the
world of complexity-theoretic analyses. The first candidate is adiabatic
computing and analog quantum simulation [12, 13, 6, 11]. Due to the
limitations of experimental setups to implement few-body couplings, these
simulations could benefit from the locality reduction to effectively study
many-body Hamiltonians while physically implementing few-body interactions.
Unfortunately, the large differences in coupling strengths pose a challenge
for experimental realizations [13, 18, 11]. In this section, we look at two
other fields that could benefit from the properties of the Hamiltonians
generated by perturbative gadgets, where gadgets might lead to improvements,
and how the aforementioned scalings result in necessary trade-offs, that are
usually unfavorable. First, we look at the issue of cost-function-dependent
barren plateaus in variational quantum algorithms. Then, we consider the
readout problem in variational quantum algorithms.

#### Cost-function-dependent barren plateaus.

_Variational quantum algorithms_ (VQAs) [23, 24, 25] are strong in the run to
find useful applications of quantum computers in the _noisy intermediate scale
quantum_ (NISQ) era [26] and are being intensively studied. These algorithms
rely on _parametrized quantum circuits_ (PQCs) to evaluate a parameter-
dependent cost function related to the expectation value of a set of
observables. An optimization algorithm, e.g., gradient descent, implemented on
a classical device is used to optimize the parameters of the PQC in order to
find the minimum of the cost function.

Two of the most prominent examples of VQAs might be the variational quantum
eigensolver [27], aimed at finding energies of Hamiltonians, and the quantum
approximate optimization algorithm [28]. One hurdle to overcome for such
algorithms to become useful are so-called barren plateaus [29, 30, 31, 32,
33]. They refer to the phenomenon where the cost-function landscape becomes
essentially flat, rendering optimization algorithms ineffective due to the
lack of measurable gradients. Many strategies for mitigating barren plateaus
have been proposed [34, 32, 35, 36, 37, 38, 39, 40, 41, 42, 43], but the
observation most appealing to us is the fact that, given two cost functions
with the same minimum but different localities, the one with reduced locality
performs better [44, 45, 46]. This dependence of the emergence of barren
plateaus on the locality of the cost function was formalized for some ansätze
in Refs. [47, 48].

Looking back at the results from Section III, our gadget enables a generic
procedure for any cost function written as the expectation value of a
Hamiltonian to find an equivalent $3$-local cost function. This new cost
function has the same minimum (Corollary 1) as the target cost function and
has provably non-vanishing gradients (due to Ref. [48, Theorem 2]).

Upon first inspection, the problem of cost-function-locality-dependent barren
plateaus seems to be solved, but one needs to take a step back and remember
the original problem. Barren plateaus are an issue because exponentially
vanishing gradients require an exponential number of measurements on a quantum
device to resolve the gradients. This experimental cost means that such
procedures are not scalable. Although on the surface our proposal produces
gradients that can be computed efficiently, finding the minimum of the
_effective_ gadget Hamiltonian might become hard. Indeed, let us consider the
extreme case of a global cost function, i.e., an $n$-local cost function. In
this setting, from Theorem 1, the contribution of the target Hamiltonian is
suppressed as $\lambda^{n}$. In the end, the features of interest from the
target Hamiltonian might become exponentially small. In other words, the
optimization can successfully reach a minimum of the gadget cost function, but
with no guarantees of it being a good solution to the target problem.

Not all is lost, and we show some successful simulations in Appendix G. Our
gadget-induced cost function could be used as an initialization strategy.
Indeed, even if the target Hamiltonian is exponentially suppressed in the
effective low-energy subspace, each of the terms of the perturbation in gadget
Hamiltonian contains some part of the target Hamiltonian. It could be that
using our gadget provides a useful path to reach a region of the target cost
function that is outside of the regime plagued by barren plateaus.
Furthermore, previous works on perturbative gadgets argue that restricting to
the regime where the perturbative expansion converges is not necessarily
justified [13]. In our case, that means that it could be beneficial to choose
a perturbation parameter $\lambda$ larger than the bound for which our
analytical results hold, thus increasing the contribution of the target
Hamiltonian. This idea is supported by the results of our numerical
simulations. Interpreting this perturbation factor as a hyperparameter of the
model, one could take inspiration from classical machine learning and
implement a schedule of slowly decreasing $\lambda$, having strong
contributions at the beginning and high precision at the end. These heuristics
will however need to be confirmed by larger experiments than those we could
perform or by further theoretical studies. An extensive description of the
problem of cost-function-dependent barren plateaus and of the attempt to use
perturbative gadgets, complemented with numerical simulations, can be found in
Appendix E.

#### Reducing measurement bases for readout.

Another, albeit more pessimistic example of possible trade-offs using
perturbative gadgets is the construction of a gadget aimed at exploiting the
commutation structure of the gadget Hamiltonian.

As for the gadget introduced in Eq. (3), by first measuring all auxiliary
qubits in the Pauli-$Z$ basis, we are able to estimate $H^{\textrm{aux}}$.
Then, consecutively measuring all auxiliary qubits in the Pauli-$X$ basis and
simultaneously all target qubits in one of the three Pauli bases, we are able
to estimate all of the $V_{s}$ terms. Consequently, only four different
measurements are required to obtain an unbiased estimator of the energy of the
gadget Hamiltonian.

Going one step further, we could design a new gadget that decomposes each term
of the Hamiltonian into their Pauli-$X$, Pauli-$Y$, and Pauli-$Z$ parts and
use each part in a single perturbation term. That would lead to a gadget that
reconstructs the original term in the third order of perturbation theory and
thereby reduces the complexity of the gadget.

In case the locality is of no importance, we can also reduce the number of
terms in the gadget Hamiltonian and the qubit overhead. Through a different
definition of the part of the perturbation in the gadget Hamiltonian that acts
on the auxiliary register, we can achieve only a logarithmic qubit overhead,
as shown in more detail in Appendix H.

However, we still end up facing the same challenge as before: While we are
able to efficiently estimate the energy of the gadget Hamiltonian, that is not
the quantity we are interested in. Instead, we want to measure the energy of
the target Hamiltonian, which is suppressed by $\lambda^{3}$ and will, due to
the implicit dependence of $\lambda$ on the number of terms in the target
Hamiltonian, lead to an unfavorable scheme compared to simply measuring each
term of the Hamiltonian by itself. The only potential use case for such a
gadget would then be a setting where it is excessively more expensive to
change the measurement setting than to evaluate the circuit.

##  VI Summary and outlook

Perturbative gadgets are a powerful tool that can be used to show equivalences
between Hamiltonians of different localities. They have led to advances in
quantum complexity theory, addressing problems that originate from studies of
quantum many-body systems in rigorous condensed matter theory, and have been
considered tools to facilitate feasible implementations in experimental
settings. They have also been explored as tools to devise schemes of quantum
simulations of systems that are natively too difficult to tackle, say, quantum
systems featuring certain kinds of intrinsic topological order [19, 49]. At
the same time, perturbative gadgets are quite often accompanied by unfavorable
trade-offs in interaction strengths, recursions, or limitations to settings
allowing for subspace restrictions, bringing into question their use for
practical applications [11].

In this work, we have proposed a new type of perturbative gadget that jointly
lifts the requirements on subspace restrictions and recursions but cannot
circumvent the problem of impractical interaction strengths. It achieves the
same locality reduction as the subdivision gadget from Oliveira and Terhal
[4], but has a direct formulation in higher-orders of perturbation theory as
does the gadget from Jordan and Farhi [5], without requiring to restrict the
evolution of the system to a subspace of the Hilbert space. In doing so, we
observe that each of these constructions is a special case and demonstrate how
to generalize our construction to a larger class of gadgets.

Furthermore, we turn towards the setting of variational quantum algorithms,
where the locality of cost functions can be of great interest and thus benefit
from generic procedures producing Hamiltonians with the same ground states but
reduced locality.

We note that locality versus energy scale trade-offs in using perturbative
gadgets may still be impractical outside of theoretical considerations and
therefore leave the question of their practicality wide open. Circumventing
the need for subspace restrictions and recursions does, however, broaden their
scope and therefore opens up new directions of exploration for finding
practical applications. It might be interesting to consider the question of
how imposing restrictions on the target Hamiltonian might allow us to improve
the resource requirements of our gadget construction. In the same flavor as
gadgets for topological quantum codes, there might be classes of Hamiltonians
for which the effective Hamiltonian can be retrieved at a lower perturbation
order. Such a development would trade off universality for performance, an
idea established in the area of variational quantum algorithms and beyond.

#### Author contributions.

The project has been conceived by PKF. The theoretical analysis has been
developed by SC, PKF, and SK, and the numerical demonstrations have been
developed by SC under the supervision of PKF and SK. JE has supported research
and development. All authors have contributed to scientific discussions and to
the writing of the manuscript.

#### Acknowledgements.

We thank Johannes Jakob Meyer, Jakob Kottmann, and Lennart Bittel for helpful
discussions and for providing feedback on an early version of the manuscript.
Financial support has been provided by the BMWK (PlanQK, EniQmA), the QuantERA
(HQCC), the BMBF (Hybrid), the Munich Quantum Valley (K-8), and the Einstein
Foundation (Einstein Research Unit on Quantum Devices).

#### Code availability.

The numerical simulations were performed using PennyLane [50] and the code is
available here.

## References

  * Kitaev  _et al._ [2002] A. Kitaev, A. Shen, and M. Vyalyi,  _Classical and Quantum Computation_, Graduate Studies in Mathematics, Vol. 47 (American Mathematical Society, 2002).
  * Kempe and Regev [2003] J. Kempe and O. Regev, 3-local Hamiltonian is QMA-complete, Quantum Inf. Comput. 3, 258 (2003).
  * Kempe  _et al._ [2006] J. Kempe, A. Kitaev, and O. Regev, The complexity of the local Hamiltonian problem, SIAM J. Comp. 35, 1070 (2006).
  * Oliveira and Terhal [2005] R. Oliveira and B. M. Terhal, The complexity of quantum spin systems on a two-dimensional square lattice, arXiv:quant-ph/0504050 (2005).
  * Jordan and Farhi [2008] S. P. Jordan and E. Farhi, Perturbative gadgets at arbitrary orders, Phys. Rev. A 77, 062329 (2008).
  * Cubitt  _et al._ [2018] T. S. Cubitt, A. Montanaro, and S. Piddock, Universal quantum Hamiltonians, Proc. Natl. Acad. Sci. U.S.A.. 115, 9497 (2018).
  * Bravyi and Hastings [2017] S. Bravyi and M. Hastings, On complexity of the quantum Ising model, Commun. Math. Phys. 349, 1 (2017).
  * Zhou and Aharonov [2021] L. Zhou and D. Aharonov, Strongly universal Hamiltonian simulators, arXiv:2102.02991 (2021).
  * Piddock and Montanaro [2018] S. Piddock and A. Montanaro, Universal qudit Hamiltonians, arXiv:1802.07130 (2018).
  * Piddock and Bausch [2020] S. Piddock and J. Bausch, Universal translationally-invariant Hamiltonians, arXiv:2001.08050 (2020).
  * Harley  _et al._ [2023] D. Harley, I. Datta, F. R. Klausen, A. Bluhm, D. S. França, A. H. Werner, and M. Christandl, Going beyond gadgets: The importance of scalability for analogue quantum simulators, arXiv:2306.13739 (2023).
  * Biamonte and Love [2008] J. D. Biamonte and P. J. Love, Realizable Hamiltonians for universal adiabatic quantum computers, Phys. Rev. A 78, 012352 (2008).
  * Bravyi  _et al._ [2008] S. Bravyi, D. P. DiVincenzo, D. Loss, and B. M. Terhal, Quantum simulation of many-body Hamiltonians using perturbation theory with bounded-strength interactions, Phys. Rev. Lett. 101, 070503 (2008).
  * Cao  _et al._ [2015] Y. Cao, R. Babbush, J. Biamonte, and S. Kais, Hamiltonian gadgets with reduced resource requirements, Phys. Rev. A 91, 012315 (2015).
  * Cao [2016] Y. Cao, Combinatorial algorithms for perturbation theory and application on quantum computing, Open Access Dissertations (2016).
  * Cao and Kais [2017] Y. Cao and S. Kais, Efficient optimization of perturbative gadgets, Quant. Inf. Comp. 17, 779 (2017).
  * Subaşı and Jarzynski [2016] Y. Subaşı and C. Jarzynski, Nonperturbative embedding for highly nonlocal Hamiltonians, Phys. Rev. A 94, 012342 (2016).
  * Bausch [2020] J. Bausch, Perturbation gadgets: Arbitrary energy scales from a single strong interaction, Annales Henri Poincaré 21, 81 (2020).
  * Brell  _et al._ [2011] C. G. Brell, S. T. Flammia, S. D. Bartlett, and A. C. Doherty, Toric codes and quantum doubles from two-body Hamiltonians, New J. Phys. 13, 053039 (2011).
  * Ocko and Yoshida [2011] S. A. Ocko and B. Yoshida, Nonperturbative gadget for topological quantum codes, Phys. Rev. Lett. 107, 250502 (2011).
  * Bloch [1958] C. Bloch, Sur la théorie des perturbations des états liés, Nucl. Phys. 6, 329 (1958).
  * Bravyi  _et al._ [2011] S. Bravyi, D. P. DiVincenzo, and D. Loss, Schrieffer–Wolff transformation for quantum many-body systems, Ann. Phys. 326, 2793 (2011).
  * Cerezo  _et al._ [2021a] M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. J. Coles, Variational quantum algorithms, Nature Rev. Phys. 3, 625 (2021a).
  * Bharti  _et al._ [2022] K. Bharti, A. Cervera-Lierta, T. H. Kyaw, T. Haug, S. Alperin-Lea, A. Anand, M. Degroote, H. Heimonen, J. S. Kottmann, T. Menke, W.-K. Mok, S. Sim, L.-C. Kwek, and A. Aspuru-Guzik, Noisy intermediate-scale quantum algorithms, Rev. Mod. Phys. 94, 015004 (2022).
  * McClean  _et al._ [2016] J. R. McClean, J. Romero, R. Babbush, and A. Aspuru-Guzik, The theory of variational hybrid quantum-classical algorithms, New J. Phys. 18, 023023 (2016).
  * Preskill [2018] J. Preskill, Quantum Computing in the NISQ era and beyond, Quantum 2, 79 (2018).
  * Peruzzo  _et al._ [2014] A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’Brien, A variational eigenvalue solver on a photonic quantum processor, Nature Comm. 5, 4213 (2014).
  * Farhi  _et al._ [2014] E. Farhi, J. Goldstone, and S. Gutmann, A quantum approximate optimization algorithm, arXiv:1411.4028 (2014).
  * McClean  _et al._ [2018] J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, Barren plateaus in quantum neural network training landscapes, Nature Comm. 9, 4812 (2018).
  * Wang  _et al._ [2021] S. Wang, E. Fontana, M. Cerezo, K. Sharma, A. Sone, L. Cincio, and P. J. Coles, Noise-induced barren plateaus in variational quantum algorithms, Nature Comm. 12, 6961 (2021).
  * Ortiz Marrero  _et al._ [2021] C. Ortiz Marrero, M. Kieferová, and N. Wiebe, Entanglement-induced barren plateaus, PRX Quantum 2, 040316 (2021).
  * Holmes  _et al._ [2022] Z. Holmes, K. Sharma, M. Cerezo, and P. J. Coles, Connecting ansatz expressibility to gradient magnitudes and barren plateaus, PRX Quantum 3, 010313 (2022).
  * Martín  _et al._ [2023] E. C. Martín, K. Plekhanov, and M. Lubasch, Barren plateaus in quantum tensor network optimization, Quantum 7, 974 (2023).
  * Grant  _et al._ [2019] E. Grant, L. Wossnig, M. Ostaszewski, and M. Benedetti, An initialization strategy for addressing barren plateaus in parametrized quantum circuits, Quantum 3, 214 (2019).
  * Volkoff and Coles [2021] T. Volkoff and P. J. Coles, Large gradients via correlation in random parameterized quantum circuits, Quant. Sc. Tech. 6, 025008 (2021).
  * Wiersema  _et al._ [2021] R. Wiersema, C. Zhou, J. F. Carrasquilla, and Y. B. Kim, Measurement-induced entanglement phase transitions in variational quantum circuits, arXiv:2111.08035 (2021).
  * Mele  _et al._ [2022] A. A. Mele, G. B. Mbeng, G. E. Santoro, M. Collura, and P. Torta, Avoiding barren plateaus via transferability of smooth solutions in Hamiltonian Variational Ansatz, Physical Review A 106, L060401 (2022).
  * Skolik  _et al._ [2021] A. Skolik, J. R. McClean, M. Mohseni, P. van der Smagt, and M. Leib, Layerwise learning for quantum neural networks, Quant. Mach. Int. 3, 5 (2021).
  * Kieferova  _et al._ [2021] M. Kieferova, O. M. Carlos, and N. Wiebe, Quantum generative training using Rényi divergences, arXiv:2106.09567 (2021).
  * Dborin  _et al._ [2022] J. Dborin, F. Barratt, V. Wimalaweera, L. Wright, and A. G. Green, Matrix product state pre-training for quantum machine learning, Quant. Sc. Tech. 7, 035014 (2022).
  * Liu  _et al._ [2022] X. Liu, G. Liu, J. Huang, and X. Wang, Mitigating barren plateaus of variational quantum eigensolvers, arXiv:2205.13539 (2022).
  * Sack  _et al._ [2022] S. H. Sack, R. A. Medina, A. A. Michailidis, R. Kueng, and M. Serbyn, Avoiding barren plateaus using classical shadows, PRX Quantum 3, 020365 (2022).
  * Kiani  _et al._ [2022] B. T. Kiani, G. D. Palma, M. Marvian, Z.-W. Liu, and S. Lloyd, Learning quantum data with the quantum Earth mover’s distance, Quant. Sc. Tech. 7, 045002 (2022).
  * Khatri  _et al._ [2019] S. Khatri, R. LaRose, A. Poremba, L. Cincio, A. T. Sornborger, and P. J. Coles, Quantum-assisted quantum compiling, Quantum 3, 140 (2019).
  * LaRose  _et al._ [2019] R. LaRose, A. Tikku, E. O’Neel-Judy, L. Cincio, and P. J. Coles, Variational quantum state diagonalization, npj Quant. Inf. 5, 57 (2019).
  * Bravo-Prieto  _et al._ [2019] C. Bravo-Prieto, R. LaRose, M. Cerezo, Y. Subasi, L. Cincio, and P. J. Coles, Variational quantum linear solver, arXiv:1909.05820 (2019).
  * Cerezo  _et al._ [2021b] M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles, Cost function dependent barren plateaus in shallow parametrized quantum circuits, Nature Comm. 12, 1791 (2021b).
  * Uvarov and Biamonte [2021] A. V. Uvarov and J. D. Biamonte, On barren plateaus and cost function locality in variational quantum algorithms, J. Phys. A 54, 245301 (2021).
  * Wille  _et al._ [2019] C. Wille, R. Egger, J. Eisert, and A. Altland, Simulating topological tensor networks with Majorana qubits, Phys. Rev. B 99, 115117 (2019).
  * Bergholm  _et al._ [2022] V. Bergholm, J. Izaac, M. Schuld, C. Gogolin, S. Ahmed, V. Ajith, M. S. Alam, G. Alonso-Linaje, B. AkashNarayanan, A. Asadi, J. M. Arrazola, U. Azad, S. Banning, C. Blank, T. R. Bromley, B. A. Cordier, J. Ceroni, A. Delgado, O. Di Matteo, A. Dusko, T. Garg, D. Guala, A. Hayes, R. Hill, A. Ijaz, T. Isacsson, D. Ittah, S. Jahangiri, P. Jain, E. Jiang, A. Khandelwal, K. Kottmann, R. A. Lang, C. Lee, T. Loke, A. Lowe, K. McKiernan, J. J. Meyer, J. A. Montañez-Barrera, R. Moyard, Z. Niu, L. J. O’Riordan, S. Oud, A. Panigrahi, C.-Y. Park, D. Polatajko, N. Quesada, C. Roberts, N. Sá, I. Schoch, B. Shi, S. Shu, S. Sim, A. Singh, I. Strandberg, J. Soni, A. Száva, S. Thabet, R. A. Vargas-Hernández, T. Vincent, N. Vitucci, M. Weber, D. Wierichs, R. Wiersema, M. Willmann, V. Wong, S. Zhang, and N. Killoran, PennyLane: Automatic differentiation of hybrid quantum-classical computations, arXiv:1811.04968 (2022).
  * Anschuetz and Kiani [2022] E. R. Anschuetz and B. T. Kiani, Beyond Barren Plateaus: Quantum Variational Algorithms Are Swamped With Traps, Nature Communications 13, 7760 (2022).
  * Bittel and Kliesch [2021] L. Bittel and M. Kliesch, Training variational quantum algorithms Is NP-hard, Phys. Rev. Lett. 127, 120502 (2021).
  * Elben  _et al._ [2023] A. Elben, S. T. Flammia, H.-Y. Huang, R. Kueng, J. Preskill, B. Vermersch, and P. Zoller, The randomized measurement toolbox, Nature Reviews Physics 5, 9 (2023).
  * Huang  _et al._ [2020] H.-Y. Huang, R. Kueng, and J. Preskill, Predicting many properties of a quantum system from very few measurements, Nature Phys. 16, 1050 (2020).
  * Litinski [2019] D. Litinski, A game of surface codes: Large-scale quantum computing with lattice surgery, Quantum 3, 128 (2019).

[mainsections]

Appendix for “Non-recursive perturbative gadgets without subspace restrictions
and applications to variational quantum algorithms”

[appendices] [appendices]l1

##  Appendix A Review of perturbation theory

In this section, we briefly summarize relevant results from perturbation
theory. In particular, we closely follow the presentation in Ref. [21] for
obtaining a general perturbative expansion, which we need for the Proof of
Theorem 1 in Appendix B.

###  A.1 Definitions

The goal of perturbation theory is to calculate the effect of a small
perturbation $V$ of strength $\lambda\geq 0$ on a known, unperturbed
Hamiltonian $H^{(0)}$. In particular, the goal is to study the Hamiltonian

$H=H^{(0)}+\lambda V$ (19)

and to determine its low-energy eigenvalues and corresponding eigenvectors as
a function of $\lambda$. To this end, suppose that $H^{(0)}$ and $V$ act on a
$D$-dimensional Hilbert space. Let $E_{0}^{(0)}$ be the lowest eigenenergy of
$H^{(0)}$, and let

$\mathcal{E}^{(0)}\coloneqq\textrm{span}\left\\{|\varphi\rangle\in\mathbb{C}^{D}:H^{(0)}|\varphi\rangle=E^{(0)}_{0}|\varphi\rangle\right\\}$
(20)

be the corresponding $d$-dimensional (degenerate) ground space of $H^{(0)}$,
$d\leq D$. We let $\\{|j\rangle\in\mathbb{C}^{D}\\}_{j=1}^{d}$ denote an
orthonormal basis for $\mathcal{E}^{(0)}$. We also let
$|\psi_{1}\rangle,|\psi_{2}\rangle,\dotsc,|\psi_{d}\rangle\in\mathbb{C}^{D}$
be the perturbed orthonormal eigenvector (i.e., the eigenvectors of $H$)
corresponding to the $d$-dimensional subspace $\mathcal{E}^{(0)}$, such that

$H|\psi_{j}\rangle=\widetilde{E}_{j}|\psi_{j}\rangle\quad\forall~{}j\in\\{1,2,\dotsc,d\\},$
(21)

where $\widetilde{E}_{j}$ are the energies corresponding to
$|\psi_{j}\rangle$. For the rest of this section, we are concerned with the
shifted energies $E_{j}\coloneqq\widetilde{E}_{j}-E_{0}^{(0)}$. We also let

$\mathcal{E}\coloneqq\text{span}\left\\{|\psi_{j}\rangle\in\mathbb{C}^{D}:j\in\\{1,2,\dotsc,d\\}\right\\}$
(22)

be the $d$-dimensional subspace spanned by the vectors
$|\psi_{1}\rangle,|\psi_{2}\rangle,\dotsc,|\psi_{d}\rangle$. We assume
throughout that the subspaces $\mathcal{E}^{(0)}$ and $\mathcal{E}$ are not
orthogonal, meaning that there does not exist a vector in $\mathcal{E}^{(0)}$
that is orthogonal to all vectors in $\mathcal{E}$, and vice versa. This
condition can be guaranteed if the perturbation strength is not too high [21].

Our specific goal in this section is to determine a perturbative expansion of
$H$ in the $d$-dimensional subspace $\mathcal{E}$, i.e., we seek a
perturbative expansion of the _effective Hamiltonian_

$H_{\text{eff}}(H,d)\coloneqq\sum_{j=1}^{d}E_{j}|\psi_{j}\rangle\\!\langle\psi_{j}|.$
(23)

Note that this is nothing more than the projection of the Hamiltonian $H$ onto
the subspace $\mathcal{E}$, followed by a constant shift of $E_{0}^{(0)}$.

Let $P_{0}$ be the projector onto $\mathcal{E}^{(0)}$. We can thus write
$H^{(0)}$ as

$H^{(0)}=E_{0}^{(0)}P_{0}+Q,$ (24)

where $Q$ satisfies $P_{0}Q=QP_{0}=0$. Let us also define $|\alpha_{j}\rangle$
to be the (non-normalized) state vectors reflecting the projections of the
perturbed eigenstates onto the subspace $\mathcal{E}^{(0)}$, i.e.,

$|\alpha_{j}\rangle\coloneqq P_{0}|\psi_{j}\rangle.$ (25)

Note that these vectors are not necessarily orthonormal. But they are linearly
independent, as we now prove.

######  Lemma 1 (Linear independence).

Under the assumption that the vector spaces $\mathcal{E}^{(0)}$ and
$\mathcal{E}$ are not orthogonal, the vectors defined in Eq. (25) are linearly
independent. Consequently, there exist vectors
$|\widetilde{\alpha}_{j}\rangle$, $j\in\\{1,2,\dotsc,d\\}$, such that
$\langle\alpha_{j}|\widetilde{\alpha}_{j^{\prime}}\rangle=\delta_{j,j^{\prime}}$
for all $j,j^{\prime}\in\\{1,2,\dotsc,d\\}$ and

$P_{0}=\sum_{j=1}^{d}|\alpha_{j}\rangle\\!\langle\widetilde{\alpha}_{j}|=\sum_{j=1}^{d}|\widetilde{\alpha}_{j}\rangle\\!\langle\alpha_{j}|.$
(26)

###### Proof.

Consider the equation
$c_{1}|\alpha_{1}\rangle+c_{2}|\alpha_{2}\rangle+\dotsb+c_{d}|\alpha_{d}\rangle=0$,
where $c_{1},c_{2},\dotsc,c_{d}\in\mathbb{C}$. Using the definition of
$|\alpha_{j}\rangle$, we obtain

$P_{0}\left(c_{1}|\psi_{1}\rangle+c_{2}|\psi_{2}\rangle+\dotsb+c_{d}|\psi_{d}\rangle\right)=0.$
(27)

Now, because $\mathcal{E}^{(0)}$ and $\mathcal{E}$ are non-orthogonal, it
follows that the vector
$c_{1}|\psi_{1}\rangle+c_{2}|\psi_{2}\rangle+\dotsb+c_{d}|\psi_{d}\rangle$ is
not in the orthogonal complement of $\mathcal{E}^{(0)}$, which means that it
must be equal to the zero vector. Consequently, because the vectors
$|\psi_{j}\rangle$ are linearly independent, we have that
$c_{1}=c_{2}=\dotsb=c_{d}=0$. Hence, because the numbers
$c_{1},c_{2},\dotsc,c_{d}$ were arbitrary, we conclude that the vectors
$|\alpha_{j}\rangle$ are linearly independent.

Now, consider the operator
$T\coloneqq\sum_{j=1}^{d}|\alpha_{j}\rangle\\!\langle j|$, which can be
thought of as a matrix whose columns are equal to the vectors
$|\alpha_{j}\rangle$. In particular, note that $|\alpha_{j}\rangle=T|j\rangle$
for all $j\in\\{1,2,\dotsc,d\\}$. Linear independence of the vectors
$|\alpha_{j}\rangle$ implies that $T$ is invertible. (Here, and throughout
this section, by _inverse_ we mean the Moore-Penrose pseudo-inverse, which is
the inverse on the support of a linear operator.) Hence, letting

$|\widetilde{\alpha}_{j}\rangle\coloneqq(T^{-1})^{\dagger}|j\rangle,\quad\forall~{}j\in\\{1,2,\dotsc,d\\},$
(28)

we find that

$\langle\alpha_{j}|\widetilde{\alpha}_{j^{\prime}}\rangle=\langle
j|T^{\dagger}(T^{-1})^{\dagger}|j^{\prime}\rangle=\langle
j|j^{\prime}\rangle=\delta_{j,j^{\prime}}\quad\forall~{}j,j^{\prime}\in\\{1,2,\dotsc,d\\},$
(29)

as required.

Finally, using Eq. (28) and the fact that $T|j\rangle=|\alpha_{j}\rangle$ for
all $j\in\\{1,2,\dotsc,d\\}$, we find that both
$\sum_{j=1}^{d}|\alpha_{j}\rangle\\!\langle\widetilde{\alpha}_{j}|$ and
$\sum_{j=1}^{d}|\widetilde{\alpha}_{j}\rangle\\!\langle\alpha_{j}|$ are equal
to the identity operator for the subspace $\mathcal{E}^{(0)}$, which is
precisely equal to the projection $P_{0}$. This completes the proof. ∎

######  Lemma 2 (Invertibility).

Consider the two linear operators

$\displaystyle\mathcal{U}$
$\displaystyle\coloneqq\sum_{j=1}^{d}|\psi_{j}\rangle\\!\langle\widetilde{\alpha}_{j}|,$
(30) $\displaystyle\mathcal{A}$ $\displaystyle\coloneqq\lambda
P_{0}V\mathcal{U}.$ (31)

The operator $\mathcal{U}$ is invertible on the subspace $\mathcal{E}$, and

$\mathcal{U}\mathcal{A}\mathcal{U}^{-1}=H_{\text{eff}}(H,d)=\sum_{j=1}^{d}E_{j}|\psi_{j}\rangle\\!\langle\psi_{j}|.$
(32)

###### Proof.

First of all, note that

$\mathcal{U}|\alpha_{j}\rangle=|\psi_{j}\rangle\quad\forall~{}j\in\\{1,2,\dotsc,d\\},$
(33)

which holds due to Lemma 1. Next, using Eq. (28), we find that
$\mathcal{U}=\sum_{j=1}^{d}|\psi_{j}\rangle\\!\langle j|T^{-1}=ST^{-1}$, where
$S\coloneqq\sum_{j=1}^{d}|\psi_{j}\rangle\\!\langle j|$. Since the vectors
$|\psi_{j}\rangle$ are linearly independent, the operator $S$ is invertible.
Furthermore, because the vectors $|\psi_{j}\rangle$ are orthonormal,
$S^{-1}=S^{\dagger}=\sum_{j=1}^{d}|j\rangle\\!\langle\psi_{j}|$. Therefore,
the inverse of $\mathcal{U}$ exists and is equal to
$\mathcal{U}^{-1}=TS^{\dagger}$. Next, using Eq. (24), we have that

$P_{0}(\lambda V)=P_{0}(H-E_{0}^{(0)}P_{0}-Q)=P_{0}H-E_{0}^{(0)}P_{0},$ (34)

so that

$\mathcal{A}=P_{0}H\mathcal{U}-E_{0}^{(0)}P_{0}\mathcal{U}.$ (35)

However, using Eq. (26), we find that $P_{0}\mathcal{U}=P_{0}$, which means
that

$\mathcal{A}=P_{0}H\mathcal{U}-E_{0}^{(0)}P_{0}.$ (36)

For this reason, because $\mathcal{U}\mathcal{U}^{-1}$ is equal to the
projection onto the subspace $\mathcal{E}$, we obtain

$\displaystyle\mathcal{U}\mathcal{A}\mathcal{U}^{-1}$
$\displaystyle=\mathcal{U}P_{0}H\mathcal{U}\mathcal{U}^{-1}-E_{0}^{(0)}\mathcal{U}P_{0}\mathcal{U}^{-1}$
(37)
$\displaystyle=\mathcal{U}P_{0}\sum_{j=1}^{d}\widetilde{E}_{j}|\psi_{j}\rangle\\!\langle\psi_{j}|-E_{0}^{(0)}\mathcal{U}P_{0}\mathcal{U}^{-1}$
$\displaystyle=\sum_{j=1}^{d}\widetilde{E}_{j}|\psi_{j}\rangle\\!\langle\psi_{j}|-E_{0}^{(0)}\mathcal{U}P_{0}\mathcal{U}^{-1}.$

Finally, using Eq. (26), along with Eq. (33) and the fact that
$\langle\widetilde{\alpha}_{j}|\mathcal{U}^{-1}=\langle
j|T^{-1}TS^{\dagger}=\langle\psi_{j}|$, we find that

$\mathcal{U}P_{0}\mathcal{U}^{-1}=\sum_{j=1}^{d}\mathcal{U}|\alpha_{j}\rangle\\!\langle\widetilde{\alpha}_{j}|\mathcal{U}^{-1}=\sum_{j=1}^{d}|\psi_{j}\rangle\\!\langle\psi_{j}|.$
(38)

Therefore,

$\mathcal{U}\mathcal{A}\mathcal{U}^{-1}=\sum_{j=1}^{d}(\widetilde{E}_{j}-E_{0}^{(0)})|\psi_{j}\rangle\\!\langle\psi_{j}|=\sum_{j=1}^{d}E_{j}|\psi_{j}\rangle\\!\langle\psi_{j}|,$
(39)

as required. ∎

###  A.2 Perturbative expansion of $\mathcal{U}$

We now derive a perturbative expansion for $\mathcal{U}$, from which we obtain
an expansion for $\mathcal{A}$, which will allow us to obtain a perturbative
expansion for the effective Hamiltonian $H_{\text{eff}}(H,d)$ via Eq. (32).
Crucial to obtaining the perturbative expansion of $\mathcal{U}$ is the
following fact.

######  Lemma 3 (Towards a perturbative expansion).

The linear operator $\mathcal{U}$ defined in Eq. (30) satisfies

$\mathcal{U}=P_{0}+A^{-1}Q_{0}\lambda(V\mathcal{U}-\mathcal{U}V\mathcal{U}),$
(40)

where $Q_{0}\coloneqq\mathds{1}-P_{0}$ and $A\coloneqq
E^{(0)}_{0}\mathds{1}-H^{(0)}$.

###### Proof.

From Eq. (21), we have that

$\left(H-E^{(0)}_{0}\mathds{1}\right)|\psi_{j}\rangle=E_{j}|\psi_{j}\rangle\quad\forall~{}j\in\\{1,2,\dotsc,d\\}.$
(41)

Multiplying both sides of this equation from the left by $P_{0}$ gives us

$\displaystyle P_{0}(H-E_{0}^{(0)}\mathds{1})|\psi_{j}\rangle$
$\displaystyle=P_{0}E_{j}|\psi_{j}\rangle,$ (42) $\displaystyle\Rightarrow
P_{0}(H^{(0)}+\lambda V-E_{0}^{(0)}\mathds{1})|\psi_{j}\rangle$
$\displaystyle=E_{j}|\alpha_{j}\rangle,$ (43) $\displaystyle\Rightarrow\lambda
P_{0}V|\psi_{j}\rangle$ $\displaystyle=E_{j}|\alpha_{j}\rangle,$ (44)

for all $j\in\\{1,2,\dotsc,d\\}$, where to obtain the right-hand side of the
second line we used Eq. (25). Now, multiplying both sides of the last line by
$\mathcal{U}$ gives us

$\displaystyle\lambda\mathcal{U}P_{0}V|\psi_{j}\rangle$
$\displaystyle=E_{j}\mathcal{U}|\alpha_{j}\rangle,$ (45)
$\displaystyle\Rightarrow\lambda\mathcal{U}V|\psi_{j}\rangle$
$\displaystyle=E_{j}|\psi_{j}\rangle,$ (46)

for all $j\in\\{1,2,\dotsc,d\\}$, where to obtain the left-hand side of the
last line we used the fact that $\mathcal{U}P_{0}=\mathcal{U}$, which can be
straightforwardly verified using Eq. (26). For the right-hand side of the last
line, we used Eq. (33) the fact that
$\mathcal{U}|\alpha_{j}\rangle=|\psi_{j}\rangle$ for all
$j\in\\{1,2,\dotsc,d\\}$. Using Eq. (41), we find that Eq. (46) can be written
as

$\displaystyle\lambda\mathcal{U}V|\psi_{j}\rangle=(H^{(0)}-E_{0}^{(0)}\mathds{1})|\psi_{j}\rangle$
(47)
$\displaystyle\Rightarrow(H-E_{0}^{(0)}\mathds{1}-\lambda\mathcal{U}V)|\psi_{j}\rangle=0,$
(48)

for all $j\in\\{1,2,\dotsc,d\\}$. Multiplying the last line by
$\langle\widetilde{\alpha}_{j}|$ from the right leads to

$(H-E_{0}^{(0)}\mathds{1}-\lambda\mathcal{U}V)|\psi_{j}\rangle\\!\langle\widetilde{\alpha}_{j}|=0\quad\forall~{}j\in\\{1,2,\dotsc,d\\}.$
(49)

Summing over all $j\in\\{1,2,\dotsc,d\\}$ therefore leads to

$(H-E_{0}^{(0)}\mathds{1}-\lambda\mathcal{U}V)\mathcal{U}=0,$ (50)

which is equivalent to

$\left(E^{(0)}_{0}\mathds{1}-H^{(0)}\right)\mathcal{U}=\lambda
V\mathcal{U}-\lambda\mathcal{U}V\mathcal{U}.$ (51)

Letting $Q_{0}\coloneqq\mathds{1}-P_{0}$ be the projector onto the span of the
excited states of $H^{(0)}$, we have

$\mathcal{U}=P_{0}\mathcal{U}+Q_{0}\mathcal{U},$ (52)

which means that

$\displaystyle\left(E^{(0)}_{0}\mathds{1}-H^{(0)}\right)\mathcal{U}$
$\displaystyle=\left(E^{(0)}_{0}\mathds{1}-H^{(0)}\right)(P_{0}\mathcal{U}+Q_{0}\mathcal{U})$
(53)
$\displaystyle=0+\left(E^{(0)}_{0}\mathds{1}-H^{(0)}\right)Q_{0}\mathcal{U},$

leading to

$\left(E^{(0)}_{0}\mathds{1}-H^{(0)}\right)Q_{0}\mathcal{U}=\lambda
V\mathcal{U}-\lambda\mathcal{U}V\mathcal{U}.$ (54)

Next, using the fact that $P_{0}\mathcal{U}=P_{0}$, we obtain

$\begin{split}Q_{0}(V\mathcal{U}-\mathcal{U}V\mathcal{U})&=(\mathds{1}-P_{0})(V\mathcal{U}-\mathcal{U}V\mathcal{U})\\\
&=V\mathcal{U}-\mathcal{U}V\mathcal{U}+P_{0}(\mathcal{U}V\mathcal{U}-V\mathcal{U})\\\
&=V\mathcal{U}-\mathcal{U}V\mathcal{U}.\end{split}$ (55)

Then, because $H^{(0)}-E^{(0)}_{0}\mathds{1}$ has a well defined inverse on
$\mathcal{E}^{(0)\perp}$, we can write

$Q_{0}\mathcal{U}=\left(E^{(0)}_{0}\mathds{1}-H^{(0)}\right)^{-1}Q_{0}\lambda(V\mathcal{U}-\mathcal{U}V\mathcal{U}).$
(56)

Inserting this result into Eq. (52) yields

$\mathcal{U}=P_{0}\mathcal{U}+\left(E^{(0)}_{0}\mathds{1}-H^{(0)}\right)^{-1}Q_{0}\lambda(V\mathcal{U}-\mathcal{U}V\mathcal{U}),$
(57)

which simplifies to

$\mathcal{U}=P_{0}+\left(E^{(0)}_{0}\mathds{1}-H^{(0)}\right)^{-1}Q_{0}\lambda(V\mathcal{U}-\mathcal{U}V\mathcal{U}),$
(58)

as required. ∎

We have, therefore, obtained the governing equation for $\mathcal{U}$. This
equation is well suited for expansion in powers of $\lambda$ and can be
expanded as

$\mathcal{U}=\sum\limits_{m=0}^{\infty}\mathcal{U}^{(m)},$ (59)

with $\mathcal{U}^{(m)}$ being the $m^{\text{th}}$-order term. Substituting
$\mathcal{U}$ into Eq. (40) gives the recurrence relations

$\displaystyle\mathcal{U}^{(0)}$ $\displaystyle=P_{0},$ (60)
$\displaystyle\mathcal{U}^{(m)}$
$\displaystyle=A^{-1}Q_{0}\lambda\left(V\mathcal{U}^{(m-1)}-\sum\limits_{p=1}^{m-1}\mathcal{U}^{(p)}V\mathcal{U}^{(m-p-1)}\right),$
(61)

with $A=E^{(0)}_{0}\mathds{1}-H^{(0)}$.

Figure 4: Visual representation of the allowed set of indices in the expansion
of $\mathcal{U}$ as proposed by Bloch in Ref. [21]. All allowed diagrams are
shown for $m\in\\{1,2,3\\}$ and additionally, one not contributing diagram for
$m=2$ since it goes below the diagonal (it does not fulfill the third property
in Eq. (64)).

Let

$S^{\ell}\coloneqq\begin{cases}-P_{0}\quad&\text{if }\ell=0,\\\
A^{-\ell}Q_{0}&\text{if }\ell>0.\end{cases}$ (62)

Then,

$\mathcal{U}^{(m)}=\lambda^{m}{\sum}^{\prime}S^{\ell_{1}}VS^{\ell_{2}}V\dots
VS^{\ell_{n}}VP_{0},$ (63)

where the sum is over all sets of indices $\\{\ell_{i}\\}_{i=1}^{m}$ that
fulfill the following conditions [21]:

$\displaystyle\ell_{i}\geq 0\quad\forall~{}i\in\\{1,\dotsc,m\\},$ (64)
$\displaystyle\ell_{1}+\dots+\ell_{m-1}=m,$ (65)
$\displaystyle\ell_{1}+\dots+\ell_{p}\geq
p\quad\forall~{}p\in\\{1,\dotsc,m-1\\}.$ (66)

######  Lemma 4 (Explicit form of terms).

For $\ell>0$, the terms $S^{\ell}$ defined in Eq. (62) are given by

$S^{\ell}=\sum_{j\neq 0}(E_{0}^{(0)}-E_{j}^{(0)})^{-\ell}P_{j}\quad(\ell>0),$
(67)

where $P_{j}$ is the spectral projection of $H^{(0)}$ corresponding to the
energy $E_{j}^{(0)}$.

###### Proof.

To obtain this result, we use the fact that

$H^{(0)}=E_{0}^{(0)}P_{0}+\sum_{j\neq 0}E_{j}^{(0)}P_{j},\quad
P_{0}+\sum_{j\neq 0}P_{j}=\mathds{1}.$ (68)

This implies that

$E_{0}^{(0)}\mathds{1}-H^{(0)}=\sum_{j\neq 0}(E_{0}^{(0)}-E_{j}^{(0)})P_{j},$
(69)

which in turn implies that

$A^{-\ell}=(E_{0}^{(0)}\mathds{1}-H^{(0)})^{-\ell}=\sum_{j\neq
0}(E_{0}^{(0)}-E_{j}^{(0)})^{-\ell}P_{j},$ (70)

and because this is supported entirely on the orthogonal complement of the
ground space of $H^{(0)}$, we have that $A^{-\ell}Q_{0}=A^{-\ell}$, proving
the desired result. ∎

From the expansion of $\mathcal{U}$, we can write the expansion of
$\mathcal{A}$ as

$\mathcal{A}=\sum\limits_{m=1}^{\infty}\mathcal{A}^{(m)}$ (71)

with

$\mathcal{A}^{(m)}=\lambda^{m}{\sum}^{\prime\prime}P_{0}VS^{\ell_{1}}VS^{\ell_{2}}V\dots
VS^{\ell_{m-1}}VP_{0},$ (72)

with the sum over all sets of $m-1$ indices $\\{\ell_{i}\\}_{i=1}^{m-1}$ such
that

$\displaystyle\ell_{i}\geq 0\quad\forall~{}i\in\\{1,2,\ldots,m-1\\},$ (73)
$\displaystyle\ell_{1}+\dots+\ell_{m-1}=m-1\geq 0,$ (74)
$\displaystyle\ell_{1}+\dots+\ell_{p}\geq
p\quad\forall~{}p\in\\{1,\dotsc,m-2\\}.$ (75)

Finally, using Eq. (32), the perturbative expansion of $H_{\text{eff}}(H,d)$,
up to $m^{\text{th}}$ order in perturbation theory, is

$H_{\text{eff}}(H,d)=\mathcal{U}\mathcal{A}^{(\leq
m)}\mathcal{U}^{-1}+\mathcal{O}(\lambda^{m+1}),\quad\mathcal{A}^{(\leq
m)}\coloneqq\sum_{j=1}^{m}\mathcal{A}^{(j)}.$ (76)

As shown in Ref. [21] (see also Ref. [5, Appendix B]), the following condition
is sufficient to guarantee convergence of this perturbative expansion:

$\|\lambda V\|<\frac{\gamma}{4},$ (77)

where $\gamma$ is the gap between $E_{0}^{(0)}$ and the energy of the first
excited state of $H^{(0)}$. We note that this bound is not tight [16] and that
significantly larger $\lambda$ might still lead to similar results, even
outside of the regime in which the perturbative expansion converges [13, 18].

##  Appendix B Proof of Theorem 1

In this section, we show how to get from Definition 1 to Theorem 1 using the
expansion presented in the previous section. In particular, we analyze what
the obtained formulas in Appendix A imply for the construction of the novel
perturbative gadget introduced in Definition 1, and thereby prove Theorem 1.
The proof also serves as the groundwork for the extensions presented in
Appendix D and the generalization in Section IV.

For convenience, let us recall the definition of our gadget Hamiltonian from
Definition 1. Given a $k$-body target Hamiltonian $H^{\text{target}}$ acting
on a Hilbert space $\mathcal{H}^{\text{target}}$ with
$\operatorname{dim}(\mathcal{H}^{\text{target}})=2^{n}$, the associated gadget
Hamiltonian is

$H^{\text{gad}}\coloneqq\sum\limits_{s=1}^{r}H^{\text{aux}}_{s}+\lambda\sum\limits_{s=1}^{r}V_{s},$
(78)

where

$\displaystyle H^{\text{aux}}_{s}$
$\displaystyle\coloneqq\sum\limits_{j=1}^{k}\frac{1}{2}\left(\mathds{1}_{s,j}-Z_{s,j}^{\text{aux}}\right)=\sum\limits_{j=1}^{k}|1\rangle\\!\langle
1|_{s,j}^{\text{aux}},$ (79) $\displaystyle V_{s}$
$\displaystyle\coloneqq\sum\limits_{j=1}^{k}\tilde{c}_{s,j}\sigma_{s,j}^{\text{target}}\otimes
X_{s,j}^{\text{aux}}\otimes X_{s,(j+1)\text{ mod }k}^{\text{aux}}$ (80)

and $\tilde{c}_{s,j}=-(-1)^{k}c_{s}$ if $j=1$ or $\tilde{c}_{s,j}=1$
otherwise. We consider
$\sigma_{s,j}\in\left\\{\hat{\boldsymbol{n}}\cdot\boldsymbol{\sigma}:\hat{\boldsymbol{n}}\in\mathds{R}^{3},\,\hat{\boldsymbol{n}}\cdot\hat{\boldsymbol{n}}=1,\,\boldsymbol{\sigma}=(X,Y,Z)\right\\}$.
We refer to the Hilbert spaces of each of the auxiliary registers as
$\mathcal{H}^{\text{aux}}_{s}$, where
$\operatorname{dim}(\mathcal{H}^{\text{aux}}_{s})=2^{k}$. The complete Hilbert
space acted upon by our gadget Hamiltonian is thus

$\mathcal{H}^{\text{total}}\simeq\mathcal{H}^{\text{target}}\otimes\mathcal{H}^{\text{aux}}_{1}\otimes\ldots\otimes\mathcal{H}^{\text{aux}}_{r}.$
(81)

Our goal in this section is to use the perturbative expansion of the previous
section, by taking $H^{(0)}\equiv\sum_{s=1}^{r}H_{s}^{\text{aux}}$ and
$V\equiv\sum_{s=1}^{r}V_{s}$, and showing that

$H_{\text{eff}}(H^{\text{gad}},2^{n})=aH^{\text{target}}\otimes|\phi_{0}\rangle\\!\langle\phi_{0}|+b\Pi+O_{\text{err}},$
(82)

where $\Pi$ is the projector onto the low-energy subspace of $H^{\text{gad}}$,
$|\phi_{0}\rangle\in\mathcal{H}^{\text{aux}}$ is a state vector, $a$ is a
scaling factor, and $b$ is a shift on the whole subspace of interest. We
remark that the above equation is in accordance with [18, Definition 11],
which provides a general definition of what it means for one Hamiltonian to
mimic another Hamiltonian in its low-energy subspace.

Figure 5: Illustration of the different relevant qubit registers in the
construction of the gadget Hamiltonian for the case of $n=5$, $k=4$, and
$r=2$. Shown are the two target Hamiltonian terms $h_{1}$ and $h_{2}$ on the
five-qubit target register on the left with the corresponding single-qubit
operators $\sigma_{s,j}$. On the right are the two four-qubit auxiliary
registers, and two of the $a^{(s)}_{j}$ operators displayed on each. As
displayed for $\sigma_{2,3}$, the indices $(s,j)$ for operators on the target
register should always be understood by referring to $h_{s}$. Indeed,
$\sigma_{2,3}$ acts on qubit $4$. On the other hand, the indices for operators
on the auxiliary qubits are more straightforward: $X_{2,3}$ is a Pauli $X$ on
the third qubit of the second register.

###  B.1 Useful properties

For illustrative purposes, and to help in some coming steps of the derivation,
let us write down the lowest-order terms of the expansion of $\mathcal{A}$
from Eq. (72) explicitly. This is

$\displaystyle\mathcal{A}^{(1)}$ $\displaystyle=$ $\displaystyle\lambda
P_{0}VP_{0},$ (83) $\displaystyle\mathcal{A}^{(2)}$ $\displaystyle=$
$\displaystyle\lambda^{2}P_{0}VS^{1}VP_{0},$ (84)
$\displaystyle\mathcal{A}^{(3)}$ $\displaystyle=$
$\displaystyle\lambda^{3}P_{0}VS^{1}VS^{1}VP_{0}+\lambda^{3}P_{0}VS^{2}VS^{0}VP_{0}.$
(85)

Let us consider a few properties of the construction defined in Definition 1,
which we use below. First of all, note that the gadget Hamiltonian is three-
body by construction. Then, the unperturbed Hamiltonian acting solely on the
auxiliary registers can be rewritten as

$H^{\text{aux}}=\sum\limits_{s=1}^{r}\sum\limits_{j=1}^{k}|1\rangle\\!\langle
1|_{s,k}$ (86)

and its ground state is the computational basis state vector
$|0\rangle^{\otimes rk}$ with corresponding eigenvalue $0$. Consequently, the
ground space of the unperturbed Hamiltonian is given by

$\mathcal{E}^{(0)}=\textrm{span}\left\\{|\varphi\rangle\otimes|0\rangle^{\otimes
rk}:|\varphi\rangle\in\mathcal{H}^{\text{target}}\right\\},$ (87)

with the corresponding projector

$P_{0}=\mathds{1}^{\otimes n}\otimes\left(|0\rangle\\!\langle
0|\right)^{\otimes rk},$ (88)

whose support is $2^{n}$-dimensional, as for the original target Hamiltonian.
Furthermore, the energy of any state in the computational basis is given by
the Hamming weight of the state with respect to the auxiliary register.
Lastly, let us define

$a^{(s)}_{j}\coloneqq X_{s,j}^{\text{aux}}\otimes X_{s,(j+1)\text{ mod
}k}^{\text{aux}}$ (89)

as the parts of the perturbation from Eq. (80) acting on the auxiliary
registers. Then, these operators fulfill the useful relations

$\left[a^{(s)}_{i},a^{(p)}_{j}\right]=0\quad\forall~{}i,j,s,p,\qquad\prod_{j=1}^{k}a^{(s)}_{j}=\bigotimes_{j=1}^{k}X_{s,j}^{2}=\mathds{1}^{\otimes
k}\quad\forall~{}s.$ (90)

The first is a direct consequence of having only Pauli-$X$ operators in the
construction of $a^{(s)}_{j}$. The second is due to the fact that the
operators $a_{j}^{(s)}$ are constructed in a cyclic manner and the fact that
the Pauli-$X$ operator squares to the identity.

###  B.2 Simplified target Hamiltonian

Now, let us first consider the simplified example of a target Hamiltonian
comprising only a single term with unit norm, that is

$H^{\text{target}}=\sigma_{1}\sigma_{2}\ldots\sigma_{k}.$ (91)

For this case, we can omit the subscript $s$. The corresponding gadget
Hamiltonian is then given by

$H^{\text{gad}}=H^{\text{aux}}+\lambda V$ (92)

with

$H^{\text{aux}}=\sum\limits_{j=1}^{k}\frac{1}{2}(\mathds{1}-Z_{j})$ (93)

and

$V=\sum\limits_{j=1}^{k}\left(-(-1)^{k}\right)^{\delta_{1j}}\sigma_{j}\otimes
X_{j}\otimes X_{(j+1)\text{ mod }k}.$ (94)

The $2^{k}$-dimensional unperturbed ground space is

$\mathcal{E}^{(0)}=\textrm{span}\left\\{|\varphi\rangle^{\text{target}}\otimes|0\rangle^{\otimes
k}:|\varphi\rangle\in\mathcal{H}^{\text{target}}\right\\}.$ (95)

The projector on the unperturbed ground space can consequently be written as

$P_{0}=\mathds{1}^{\otimes k}\otimes\left(|0\rangle\\!\langle
0|\right)^{\otimes k}.$ (96)

First, let us look at the auxiliary part of the Hamiltonian to understand its
effect. It can be interpreted as a penalization on flipped qubits: each term
has a $0$ contribution if the affected qubit is in the $|0\rangle$ state but
has a penalty of $1$ if the qubit is in $|1\rangle$. The gap is then
$\gamma=1$ and taking into account that $\|V\|=k$, the convergence of the
expansion in Eq. (63) is guaranteed for $\lambda\leq\frac{1}{4k}$.

Let us now study the first terms in the expansion of $\mathcal{A}$ from Eq.
(72), i.e.,

$\mathcal{A}^{(\leq 2)}=\lambda P_{0}VP_{0}+\lambda^{2}P_{0}VS^{1}VP_{0}.$
(97)

Every term of this expansion is sandwiched between two projectors $P_{0}$. The
only terms with a non-trivial contribution are then those that take a state
from $\mathcal{E}^{(0)}$ and return it to $\mathcal{E}^{(0)}$, i.e., those
that leave the auxiliary register in the all-zero state. That is not the case
for $\mathcal{A}^{(1)}$ in which the application of a single term of the
perturbation $V$ necessarily kicks the state out of the ground space by
flipping two auxiliary qubits. Consequently, $\mathcal{A}^{(1)}=0$. For
$\mathcal{A}^{(2)}$, each term of the first $V$ excites the system to a state
with two flipped auxiliary qubits. The only contribution from $S^{1}$ is then
due to the projector on the second excited subspace $P_{2}$ with corresponding
eigenenergy $E^{(0)}_{2}=2$. This gives the denominator in $S^{1}$, resulting
in

$\mathcal{A}^{(\leq 2)}=-\frac{\lambda^{2}}{2}P_{0}V^{2}P_{0}.$ (98)

Now, let us examine $V^{2}$. This two-fold application of the perturbation $V$
has to act on the same two qubits, flipping them back to their original state.
All cross-terms in

$\begin{split}V^{2}&=\sum\limits_{i,j=1}^{k}\sigma_{i}\sigma_{j}\otimes
a_{i}a_{j}\\\ &=\sum\limits_{i,j=1}^{k}\sigma_{i}\sigma_{j}\otimes
X_{i}X_{(i+1)\text{ mod }k}X_{j}X_{(j+1)\text{ mod }k},\end{split}$ (99)

with $i\neq j$, do not contribute since some of the Pauli-$X$ operators on
auxiliary qubits survive and leave the state outside of $\mathcal{E}^{(0)}$.
For visualization, we refer to Fig. 3(c). Additionally, for $i=j$, and even on
the target register, the terms that do contribute are necessarily squared
operators and thus only identities:

$\sum\limits_{j=1}^{k}\sigma_{j}^{2}\otimes\left(X_{j}X_{(j+1)\text{ mod
}k}\right)^{2}=\sum\limits_{j=1}^{k}\mathds{1}=k\mathds{1}.$ (100)

Altogether, we have that

$\mathcal{A}^{(\leq 2)}=-\frac{\lambda^{2}k}{2}P_{0}.$ (101)

Figure 6: Illustration of the interplay of $V$ and $S^{\ell}$ in
$\mathcal{A}$. Shown are some possible contributions to $\alpha_{4}$ in the
case of seven qubits; see Eq. (102). Displayed are two choices of indices
$\ell_{i}$ fulfilling (73) and some terms from $V^{4}$ that starting from a
state in $\mathcal{E}^{(0)}$ return to $\mathcal{E}^{(0)}$ for each choice. At
each step of application of $S^{\ell_{i}}V$, the state is changed by $V$ by
flipping two qubits, and $S^{\ell_{i}}$ weights the resulting state by a power
of the inverse of the energy or $0$.

Similarly, for the next orders in the perturbative expansion, each pair of
flipped auxiliary qubits has to be flipped back by the same operator in order
to result in a non-zero contribution. For this to be true, $m$ is only allowed
to take even values, and the perturbation is always applied as
$P_{0}V^{m}P_{0}\propto P_{0}$. That means that all contributions below order
$k$ are proportional to $P_{0}$ and thus

$\mathcal{A}^{(\leq
k-1)}=\left(\sum\limits_{m=0}^{k-1}\alpha_{m}\lambda^{m}\right)P_{0}.$ (102)

Here, $\alpha_{m}$ is a coefficient depending on the number of combinations of
$m$ excitations returning a state to $\mathcal{E}^{(0)}$, and the
corresponding energy penalties picked up along the way, which is independent
of $\lambda$. To strengthen the intuition on the construction of $\alpha_{m}$
we refer to Fig. 6, which displays a few examples of terms that do and do not
contribute.

A different behavior can be first observed at $k^{\text{th}}$ order in
perturbation theory. There, by Eq. (90), we can construct terms acting $k$
times on the auxiliary register as $\prod_{j=1}^{k}a_{j}=\mathds{1}^{\otimes
k}$. In other words, all qubits from the auxiliary register are flipped twice
and thus returned to $\mathcal{E}^{(0)}$, while each qubit in the target
register is acted upon only once by the corresponding $\sigma_{j}$. This
results in all elements from $H^{\text{target}}$ being applied to the target
register, yielding

$\mathcal{A}^{(k)}=-(-\lambda)^{k}\sum_{\boldsymbol{\ell}}\frac{1}{\xi_{\boldsymbol{\ell}}}P_{0}\left(-(-1)^{k}\sigma_{1}\sigma_{2}\dots\sigma_{k}\otimes\mathds{1}^{\otimes
k}\right)P_{0}=\lambda^{k}\sum_{\boldsymbol{\ell}}\frac{1}{\xi_{\boldsymbol{\ell}}}P_{0}\left(H^{\text{target}}\otimes\mathds{1}^{\otimes
k}\right)P_{0}.$ (103)

The sum over $\boldsymbol{\ell}$ is over all possible permutations in the
application order of the $\left(\sigma_{j},\ a_{j}\right)$ pairs, while
$\xi_{\boldsymbol{\ell}}=\prod_{i=1}^{k}E_{\ell_{i}}$ is the factor
originating from the corresponding energy penalties
$E_{\ell_{i}}=\|H^{\text{aux}}a_{\ell_{i}}\ldots
a_{\ell_{0}}|0\rangle^{\otimes k}\|_{2}$. Defining

${\Xi}^{-1}\coloneqq\sum_{\boldsymbol{\ell}}\frac{1}{\xi_{\boldsymbol{\ell}}},$
(104)

the full expansion of $\mathcal{A}$ up to $k^{\text{th}}$ order in
perturbation theory considering all possible combinations can then be written
as

$\begin{split}\mathcal{A}^{(\leq
k)}&=f(\lambda)P_{0}+\frac{\lambda^{k}}{\Xi}P_{0}\left(H^{\text{target}}\otimes\mathds{1}^{\otimes
k}\right)P_{0}\\\
&=f(\lambda)P_{0}+\frac{\lambda^{k}}{\Xi}H^{\text{target}}\otimes(|0\rangle\\!\langle
0|)^{\otimes k}.\end{split}$ (105)

Applying these results to Eq. (76) yields

$\begin{split}H_{\text{eff}}(H^{\text{gad}},2^{n})&=\mathcal{U}f(\lambda)P_{0}\mathcal{U}^{-1}+\mathcal{U}\left[\frac{\lambda^{k}}{\Xi}H^{\text{target}}\otimes(|0\rangle\\!\langle
0|)^{\otimes k}+\mathcal{O}(\lambda^{k+1})\right]\mathcal{U}^{-1}\\\
&=f(\lambda)\Pi+\frac{\lambda^{k}}{\Xi}H^{\text{target}}\otimes(|0\rangle\\!\langle
0|)^{\otimes k}+\mathcal{O}(\lambda^{k+1}),\end{split}$ (106)

where $\mathcal{U}P_{0}\mathcal{U}^{-1}=\Pi$ is the projector onto the support
of $H_{\text{eff}}(H^{\text{gad}},2^{n})$. Similarly to Ref. [5], we used the
fact that the operators $\mathcal{U}$ on both sides leave the second term
remains unaffected up to errors of order $\mathcal{O}(\lambda^{k+1})$.

###  B.3 General case

For the general case stated in Definition 1, the argument is similar, with the
exception that one has to bear in mind that there are now $r$ auxiliary
registers of $k$ qubits each. There are then more cross-terms in the powers of
$V$ and Eq. (99) becomes

$V^{2}=\sum\limits_{s,p=1}^{r}\sum\limits_{i,j=1}^{k}\tilde{c}_{s,i}c_{p,j}\sigma_{s,i}\sigma_{p,j}\otimes
X_{s,i}X_{s,i+1}X_{p,j}X_{p,j+1}.$ (107)

Similarly, only terms with $s=p$ and $i=j$ contribute. More contributions
appear from all possible combinations of the different terms in the powers of
$V$, but in the end, Eq. (102) still holds: All non-zero contributions to
$\mathcal{A}$ at orders lower than $k$ are proportional to $P_{0}$.

At $k^{\text{th}}$ order in perturbation theory, the non-trivial terms appear
when acting $k$ times on a single auxiliary register, since Eq. (90) only
holds when all operators operate on the same register $s$.

On the target register, it produces a contribution of the form
$\prod_{j=1}^{k}\tilde{c}_{s,j}\sigma_{s,1}\sigma_{s,2}\dots\sigma_{s,k}=-(-1)^{k}c_{s}h_{s}$.
Considering all possible cross terms of this kind emerging from $V^{k}$ leads
to similar terms for each auxiliary register, yielding

$\begin{split}\mathcal{A}^{(\leq
k)}&=f(\lambda)P_{0}+\sum_{s=1}^{r}\frac{\lambda^{k}}{\Xi}P_{0}\left(c_{s}h_{s}\otimes\mathds{1}^{\otimes
k}_{s}\right)P_{0}\\\
&=f(\lambda)P_{0}+\frac{\lambda^{k}}{\Xi}P_{0}\left(\sum_{s=1}^{r}c_{s}h_{s}\otimes\mathds{1}^{\otimes
k}_{s}\right)P_{0}\\\
&=f(\lambda)P_{0}+\frac{\lambda^{k}}{\Xi}P_{0}\left(H^{\text{target}}\otimes\mathds{1}^{\otimes
rk}\right)P_{0}.\end{split}$ (108)

Applying these results to Eq. (76) results in

$\begin{split}H_{\text{eff}}(H^{\text{gad}},2^{n})&=\mathcal{U}f(\lambda)P_{0}\mathcal{U}^{-1}+\mathcal{U}\left[\frac{\lambda^{k}}{\Xi}P_{0}\left(H^{\text{target}}\otimes\mathds{1}^{\otimes
rk}\right)P_{0}+\mathcal{O}(\lambda^{k+1})\right]\mathcal{U}^{-1}\\\
&=f(\lambda)\Pi+\frac{\lambda^{k}}{\Xi}H^{\text{target}}\otimes(|0\rangle\\!\langle
0|)^{\otimes rk}+\mathcal{O}(\lambda^{k+1}),\end{split}$ (109)

which is what we have been aiming for. Furthermore, by Eq. (77), we need to
upper bound the perturbation strength $\lambda$ by $\gamma/(4\lVert V\rVert)$.
For the presented gadget we have $\gamma=1$ and $\lVert
V\rVert\leq\left(\sum_{s=1}^{r}|c_{s}|+r(k-1)\right)$ by the triangle
inequality and the fact that the operator norm of Pauli operators is equal to
one. Although not tight, we can thus upper bound $\lambda$ by

$\lambda\leq\frac{1}{4\left(\sum_{s=1}^{r}|c_{s}|+r(k-1)\right)},$ (110)

concluding the proof of Theorem 1.

##  Appendix C Proof of Corollary 1

Corollary 1 results from a direct application of Eq. (6) for sufficiently
small $\lambda$. Since $f(\lambda)\Pi$ is a constant shift on the whole
subspace of interest, the eigenstates of
$H_{\text{eff}}\left(H^{\text{gad}},2^{n}\right)$ and
$H_{\text{eff}}\left(H^{\text{gad}},2^{n}\right)-f(\lambda)\Pi$ are identical,
and all energy gaps preserved. We can then rewrite Eq. (6) as

$\widetilde{H}_{\text{eff}}(H^{\text{gad}},2^{n},f(\lambda))=\frac{\lambda^{k}}{\Xi}H^{\text{target}}\otimes\left(|0\rangle\\!\langle
0|\right)^{\otimes rk}+\lambda^{k+1}O^{\text{err}},$ (111)

with
$\widetilde{H}_{\text{eff}}\left(H^{\text{gad}},2^{n},f(\lambda)\right)\coloneqq
H_{\text{eff}}\left(H^{\text{gad}},2^{n}\right)-f(\lambda)\Pi$ and
$\|O^{\text{err}}\|\in\mathcal{O}(1)$. Since the error shifts any eigenvalue
by at most $\|\lambda^{k+1}O^{\text{err}}\|$, choosing $\lambda$ such that

$\|\lambda^{k+1}O^{\text{err}}\|\leq{\lambda^{k}}(E^{\text{target}}_{1}-E^{\text{target}}_{0})/{\Xi},$
(112)

where $E_{0}^{\text{target}}$ and $E_{1}^{\text{target}}$ are the ground and
first-excited energies, respectively, of $H^{\text{target}}$, ensures that the
ground space of the right-hand side of Eq. (111) remains separated from the
first excited subspace. Considering that the spectrum of $H^{\text{target}}$
is independent of $\lambda$, we are always able to find a sufficiently small
$\lambda$, whose upper bound is given by

$\lambda\leq\frac{E^{\text{target}}_{1}-E^{\text{target}}_{0}}{\Xi\|O^{\text{err}}\|},$
(113)

concluding the proof.

##  Appendix D Extensions of the locality gadget construction

###  D.1 Extension to mixed Pauli weights

The gadget presented in Definition 1 seems to be restricted to the case in
which all terms $h_{s}$ of the target Hamiltonian act non-trivially on the
same number of qubits, namely, that they all act non-trivially on exactly $k$
qubits. Here, we want to argue that such a restriction, although useful to
simplify the derivations and formulas, is not necessary. We can also consider
the case of a Hamiltonian $H^{\text{target}}$ whose terms $h_{s}$ are not all
acting non-trivially on the same number of qubits, i.e.,

$H^{\text{target}}=\sum\limits_{s=1}^{r}c_{s}h_{s}\quad\text{with}\quad
h_{s}=\bigotimes\limits_{j=1}^{k_{s}}\sigma_{s,j}$ (114)

where $k_{s}$ and $k_{s^{\prime}}$ may be different. Let us, therefore, define
$k=\max_{s}k_{s}$. This means that all terms $h_{s}$ act non-trivially on at
most $k$ qubits.

First of all, one should note that no step of the derivation in Appendix B
actually relies on the fact that $\sigma_{s,j}$ is a linear combination of the
Pauli operators $X,Y,Z$. What has been leveraged, on the other hand, is that
without loss of generality and to simplify the derivation, we can assume the
property $\sigma_{s,j}^{2}=\mathds{1}$. In other words, nothing prohibits us
from extending this definition to include identity terms, such that
$\sigma_{s,j}\in\left\\{\hat{\boldsymbol{n}}\cdot\boldsymbol{\sigma}:\hat{\boldsymbol{n}}\in\mathds{R}^{3},\,\hat{\boldsymbol{n}}\cdot\hat{\boldsymbol{n}}=1,\,\boldsymbol{\sigma}=(X,Y,Z)\right\\}\bigcup\\{\mathds{1}\\}$.
We can therefore redefine the gadget from Eq. (3) such that
$H^{\text{aux}}_{s}$ stays as in Definition 1, but the perturbation changes to

$V_{s}=\sum\limits_{j=1}^{k_{s}}\tilde{c}_{s,j}\sigma_{s,j}^{\text{target}}\otimes
X_{s,j}^{\text{aux}}\otimes X_{s,(j+1)\text{ mod
}k}^{\text{aux}}+\sum\limits_{j=k_{s}+1}^{k}X_{s,j}^{\text{aux}}\otimes
X_{s,(j+1)\text{ mod }k}^{\text{aux}}.$ (115)

With this change, even terms with $k_{s}<k$ will only contribute at
$k^{\text{th}}$ order in perturbation theory, and we recover our main result
even for Hamiltonians of the form presented in Eq. (114).

###  D.2 Extension to arbitrary target locality

Having extended the use of our gadget to target Hamiltonians whose terms act
non-trivially on different numbers of qubits, we can also extend it for
arbitrary target locality. For now, let us assume again that all terms $h_{s}$
act non-trivially on exactly $k$ qubits. Reducing the locality to a value
lower than three is out of reach for our gadget construction. However, we can
construct gadget Hamiltonians with localities between three and $k$ that lead
to the same overall result as Theorem 1. Doing so might seem to be a counter-
productive goal at first, but such constructions will require fewer additional
qubits and might thus be useful when it comes to practical implementations.
After all, the three-body perturbative gadget introduced here requires $rk$
additional qubits. We start by discussing the simpler case in which $k$ is
divisible by $k^{\prime}-2$, where $k^{\prime}$ is the target locality, and
then extend the findings to the general case.

If, for instance, one chooses the target locality to be four instead of three,
Eq. (80) can be changed to

$V_{s}=\sum\limits_{j=1}^{k/2}\tilde{c}_{s,j}\sigma_{s,2j-1}^{\text{target}}\otimes\sigma_{s,2j}^{\text{target}}\otimes
X_{s,j}^{\text{aux}}\otimes X_{s,(j+1)\text{ mod }k/2}^{\text{aux}}.$ (116)

Each perturbation term now acts on two target qubits instead of one, halving
the order in perturbation theory at which the target Hamiltonian is recovered
and would consequently only require $r\frac{k}{2}$ auxiliary qubits to obtain
a result equivalent to Eq. (6).

In general, we can construct a gadget with an arbitrary target locality
between three and $k$ by acting on more target qubits at once in each term of
the perturbation. If the original target Hamiltonian is $k$-body and the
target locality of $H^{\text{gad}}$ is $k^{\prime}$, the resulting gadget
construction requires $\frac{k}{k^{\prime}-2}$ auxiliary qubits for each term
of the target Hamiltonian. Two of the $k^{\prime}$ operators of the tensor
product have to be the pair of Pauli-$X$ operators on the auxiliary register
and the rest can be populated with the corresponding Pauli operators from
$h_{s}$.

The statements above assume that $\frac{k}{k^{\prime}-2}$ is equal to an
integer; now let us look at the case where this is not the case. Let us define
$k^{\top}=\lceil\frac{k}{k^{\prime}-2}\rceil$ and
$k^{\perp}=\lfloor\frac{k}{k^{\prime}-2}\rfloor$. Using the insights from
Appendix D.1, we can lift the divisibility requirement and can construct a
$k^{\prime}$-body gadget Hamiltonian with the perturbation given by

$V_{s}=\sum\limits_{j=1}^{k^{\perp}}\tilde{c}_{s,j}\bigotimes_{\ell=1}^{k^{\prime}-2}\sigma_{s,(j-1)(k^{\prime}-2)+\ell}^{\text{target}}\otimes
X_{s,j}^{\text{aux}}\otimes X_{s,(j+1)\text{ mod
}k^{\top}}^{\text{aux}}+\tilde{c}_{s,k^{\perp}+1}\bigotimes_{\mathclap{m=(k^{\perp}-1)(k^{\prime}-2)+1}}^{k}\sigma_{s,m}^{\text{target}}\otimes
X_{s,k^{\perp}}^{\text{aux}}\otimes X_{s,(k^{\perp}+1)\text{ mod
}k^{\top}}^{\text{aux}}.$ (117)

The last term may act on less than $k^{\prime}-2$ target qubits but the paired
$X$ operator ensures that the only contribution is the one _acting_ $k$ times
on the target register with $k_{s}$ Pauli operators and $k-k_{s}$ identities.

When $k^{\perp}={k}/({k^{\prime}-2})$, the final term does not contribute and
we recover the divisible case. Otherwise, the last term implements the
remaining operators of the target term $h_{s}$. For a target Hamiltonian whose
terms act non-trivially on $k$ qubits simultaneously and a targeted locality
of the gadget Hamiltonian of $k^{\prime}$, the number of required auxiliary
qubits is $k^{\top}r$.

##  Appendix E Can perturbative gadgets help address the barren plateau
problem?

In this section, we provide an in-depth study of our results when applying
perturbative gadgets in the context of gate-based quantum computing, in
particular in the context of variational quantum algorithms. One might ask if
and why one would even need a perturbative gadget without constraints of
adiabaticity. After all, digital, gate-based quantum computing is not
restricted by existing couplings due to the design of more intricate gate
decompositions and the freedom of constructing arbitrary gates from universal
gate sets. Although finding practical uses in general gate-based computations
is as of yet an open problem, one fruitful application could be in the context
of _variational quantum algorithms (VQAs)_ [23, 24, 25], which are based upon
measurements of a Hamiltonian expanded in the Pauli basis and for which it was
shown that the Hamiltonian’s locality, both in the sense of geometric locality
and few-body terms, can play a role in their performance [47, 48].

VQAs rely upon _parametrized quantum circuits_ (PQCs) to evaluate a parameter-
dependent cost function related to the expectation value of a set of
observables and are greatly discussed in the setting of _noisy intermediate
scale quantum (NISQ)_ devices [26]. The probably simplest setting is that of
the _variational quantum eigensolver_ (VQE) [27], which refers to the case
where the cost function is equal to the expectation value of a Hamiltonian
$H^{\text{target}}$, i.e.,

$C^{\text{target}}(\boldsymbol{\theta})=\operatorname{Tr}\\!\left[H^{\text{target}}U(\boldsymbol{\theta})\rho
U(\boldsymbol{\theta})^{\dagger}\right],$ (118)

for some initial state $\rho$, e.g., one given by the state vector $|00\dots
0\rangle\\!\langle 00\dots 0|$, and quantum circuit ansatz
$\boldsymbol{\theta}\mapsto U(\boldsymbol{\theta})$. Solving the problem
corresponds to estimating the ground state energy and associated ground state
vector of $H^{\text{target}}$ by classically optimizing the parameters
$\boldsymbol{\theta}$ and employing a quantum device to evaluate the
aforementioned cost function.

A significant obstacle in the successful optimization is the presence of so-
called _barren plateaus_ , which reflect the phenomenon that the variance of
gradients of the cost function with respect to the variational parameters
decays exponentially in the number of qubits of the PQC. First discussed for
the hardware-efficient ansatz with a polynomial number of layers in Ref. [29],
the emergence of barren plateaus has been observed in other settings as well
[30, 31, 32, 33] and hinders the optimization procedure due to the therefore
exponential number of required measurement samples. Scalable VQAs thus rely on
practical mitigation strategies.

Existing approaches build upon improving initialization strategies [34], using
correlated gates or restricted parameter spaces [32, 35], intermediate
measurements [36], the transferability of smooth solutions [37], layerwise
learning [38], pre-optimization [39, 40], different types of ansätze [41],
classical shadows [42], or alternative loss landscapes [43].

Furthermore, in Refs. [44, 45, 46], it has surprisingly been found that for
large system sizes and circuit depths a _local_ cost function, i.e., a cost
function defined by a few-body Hamiltonian, results in more effective
optimization compared to a _global_ cost function, i.e., a cost function
defined by a many-body Hamiltonian, and that global cost functions exhibit
vanishing gradients for large system sizes already at constant circuit depths.
The concept of such _cost-function-dependent_ barren plateaus was formalized
in Refs. [47, 48], in which it has been further shown that local cost
functions can still be optimized even for circuits of logarithmic depth.

Inspired by these findings, a natural question to ask is whether we can
_localize_ any given cost function, and thus avoid cost-function-dependent
barren plateaus in the corresponding optimization landscape. For the problems
considered in Refs. [44, 45, 46], the local cost function corresponding to the
problem could be defined essentially by inspection of the global cost
function. However, this is not necessarily possible in general and motivates
us to open the discussion on whether perturbative gadgets could help extend
results on the non-existence of barren plateaus for local cost functions to
non-local ones.

###  E.1 A reduction from $k$-body to three-body cost functions

Applying the above-presented gadget to substitute cost functions of the form
in (118), allows us to use Theorem 1 and Corollary 1 to conclude the following
about VQAs: Given a cost function as in Eq. (118), we can replace the $k$-body
Hamiltonian $H^{\text{target}}$ with the three-body gadget Hamiltonian
$H^{\text{gad}}$ from Definition 1, such that finding the minimum of the
gadget Hamiltonian will bring us close to the low-energy subspace of the
target Hamiltonian, and thus the minimum of the original cost function.

Furthermore, by _localizing_ the original cost function, we obtain cost
functions with provably non-vanishing gradients as shown in Refs. [48, 47].
Specifically, they prove that the corresponding gradients decrease at most
polynomially in the number of qubits for the same ansatz of a logarithmic
depth. Thus, via Ref. [48, Theorem 2], we obtain the following result:

######  Corollary 2 (Bound to the variance of the gradient of the cost
function).

Consider the local cost function
$C^{\text{gad}}(\boldsymbol{\theta})=\operatorname{Tr}[H^{\text{gad}}U(\boldsymbol{\theta})\rho
U(\boldsymbol{\theta})^{\dagger}]$ defined by the gadget Hamiltonian in
Definition 1, where $U(\boldsymbol{\theta})$ is the unitary corresponding to
an alternating layered ansatz with $L$ layers, with each block of the ansatz
drawn independently from a local unitary 2-design. Then, the variance of the
gradient of the cost function is bounded from below by

$\text{Var}\\!\left[\frac{\partial
C^{\text{gad}}(\boldsymbol{\theta})}{\partial\boldsymbol{\theta}_{\nu}}\right]\geq\Omega\left(\mathrm{poly}\left(3^{-L}\right)\right),$
(119)

where $\nu$ denotes the subset of parameters the gradient is evaluated for. We
are thus guaranteed non-vanishing gradients for logarithmic circuit depths,
i.e., for $L=\mathcal{O}(\log n)$.

In Fig. 7, we present a proof-of-principle numerical demonstration of non-
vanishing gradients. At this point, we would like to point out that simply
having non-vanishing gradients does not imply successful optimization, i.e.,
trainability. Although the converse is true, one should, in general, be
careful when implying trainability from the existence of gradients. Take, for
example, the Hamiltonian
$H=H^{\text{global}}\otimes\mathds{1}+\mathds{1}^{\otimes(n-1)}\otimes Z$. The
vanishing gradients of the first, global term would effectively result in only
the second term contributing to the gradients. That is, if $H^{\text{global}}$
is a prototypical global observable afflicted by barren plateaus, it will
barely contribute to the magnitude of the gradients. Consequently, the circuit
will effectively be trained on the other, local, term
$\mathds{1}^{\otimes(n-1)}\otimes Z$, which has measurable gradients. In the
end, one will successfully implement the gradient descent algorithm to a
minimum, but only of the local part, and not of the full Hamiltonian. In other
words, the total cost function has measurable gradients, but these non-
vanishing gradients do not help with the actual optimization problem.

Our gadget has gradients that do not vanish exponentially and a ground state
that is close to the target solution. Unfortunately, it is not enough to fully
avoid the core issue behind barren plateaus: the exponential increase in the
number of required measurements. For the extreme case of $k=n$, the magnitude
of the contribution of the target Hamiltonian in the effective Hamiltonian, or
in other words the degeneracy splitting mentioned in Fig. 1, is suppressed
exponentially by $\lambda^{n}$. For the results from perturbation theory to
hold, $\lambda$ has to be chosen to be small (see Theorem 1), further
amplifying this problem. As a result, when reaching the low-energy subspace of
the gadget Hamiltonian and therefore entering the regime described by the
effective Hamiltonian, one would in practice need an exponentially increasing
number of measurements to resolve the nuances in the cost function and find
the global minimum. While we can guarantee a vanishing error in the limit of
$\lambda\rightarrow 0$ and that all terms of the gadget Hamiltonian contribute
to the gradient, the main contributions to the gradients would be essentially
those corresponding to reaching the unperturbed ground space, i.e., some state
vector $|\psi\rangle=|\phi\rangle\otimes|0\rangle^{\otimes rk}$. Therefore,
actually finding the ground state of the gadget Hamiltonian might be
prohibitively hard. However, this hardness can be present even for cost
functions without barren plateaus, as discussed in detail in Refs. [51, 52].
Moreover, for numerical proof-of-principle demonstrations, we find that
leaving the strict regime of perturbation strengths corresponding to
theoretical guarantees can help the optimization performance as shown in
Appendix G.

For large $\lambda$ we do not have such strong analytical guarantees but allow
for larger contributions with respect to the perturbative terms. Our training
simulations reflect these insights as we obtain different behaviors for
different perturbation strengths. These observations are aligned with previous
works on perturbative gadgets that have also found it beneficial to increase
the perturbation strength, including increasing it to values outside the
regime of convergence of perturbation theory [13, 18]. Practical
implementations might thus benefit highly from treating the perturbation
strength $\lambda$ as a hyperparameter during optimization.

It is worth noting that while using the proposed gadget Hamiltonian requires
$rk$ additional qubits and comprises $2rk$ terms instead of $r$, there exists
a simple, optimal measurement scheme for estimating its expectation value,
relying on only four different measurement-basis settings, inspired by Refs.
[53, 54]. First, by measuring all auxiliary qubits in the Pauli-$Z$ basis, we
are able to estimate $H^{\textrm{aux}}$. Then, consecutively measuring all
auxiliary qubits in the Pauli-$X$ basis and simultaneously all target qubits
in one of the three Pauli bases, we are able to estimate all terms $V_{s}$.

Figure 7: Demonstration of the theoretical guarantee from Corollary 2. We take
as our global cost function the one in Eq. (118), defined by the target
Hamiltonian $H^{\text{target}}=\bigotimes_{i=1}^{n}Z_{i}$, and we use an
alternating layered ansatz with different circuit depths. Shown is the
variance of the gradient of this global cost function (dark pink), the local
cost function based on our three-body gadget Hamiltonian from Definition 1
(blue), and a similar local cost function defined by a four-body gadget
Hamiltonian (turquoise) presented in Appendix D.

##  Appendix F Inapplicability of the gadget by Jordan and Farhi for
variational algorithms

The perturbative gadget proposed by Jordan and Farhi [5] relies strongly on
the restriction of the allowed Hilbert space in which the state of the system
can evolve. To be specific, in the language of Section IV, their gadget has a
penalization Hamiltonian, as in Eq. (9), of the form $H=\sum_{1\leq
i_{1}<i_{2}\leq k}h_{i_{1},i_{2}}$, with

$h_{i_{1},i_{2}}=\frac{1}{2}(\mathds{1}-Z_{i_{1}}\otimes Z_{i_{2}}),$ (120)

and the perturbation operator $A$ in Eq. (10) is such that

$a_{j}=X_{j},\quad j\in\\{1,2,\dotsc,k\\}.$ (121)

However, since the ground space of their penalization Hamiltonian is two-
dimensional and given by $\mathrm{span}\left\\{|0\rangle^{\otimes k},\
|1\rangle^{\otimes k}\right\\}$, they have to enforce that the state of the
system remains in the $+1$ eigenspace of the $A=X^{\otimes k}$ operator,
thereby reducing the system to a one-dimensional ground state vector
$|GS\rangle=|GHZ\rangle=({1}/{\sqrt{2}})\left(|0\rangle^{\otimes
k}+|1\rangle^{\otimes k}\right)$. With this additional restriction, which can
be fulfilled naturally in adiabatic quantum computing by initializing the
auxiliary registers in GHZ states, it is easy to check that $X^{\otimes k}$
fulfills all properties stated in Eq. (11). Unfortunately, this restriction is
not possible outside of the adiabatic regime, and their gadget construction is
consequently not applicable to our problem at hand.

However, let us now consider what happens when one cannot use initialization
and adiabatic restriction to ensure a reduction of the reachable Hilbert
space. The unperturbed ground space of their penalization Hamiltonian $H$ in
Eq. (120) is

$\mathcal{E}^{(0)}=\operatorname{span}\left\\{|\varphi\rangle^{\text{target}}\bigotimes_{s=1}^{r}|\phi\rangle^{\text{aux}}_{s}:|\varphi\rangle\in\mathcal{H}^{\text{target}},\,|\phi\rangle\in\operatorname{span}\left\\{|0\rangle^{\otimes
k},\ |1\rangle^{\otimes k}\right\\}\right\\}$ (122)

and the corresponding projector is

$P_{0}=\mathds{1}\otimes\left(|0\rangle\\!\langle 0|^{\otimes
k}+|1\rangle\\!\langle 1|^{\otimes k}\right)^{\otimes
r}=\mathds{1}\otimes\Pi_{0}^{\otimes r}.$ (123)

The fact that the dimension of $\mathcal{E}^{(0)}$ is not the same as the
dimension of the target Hilbert space makes a considerable difference in Eq.
(108), where the shifted contributions become

$\frac{\lambda^{k}}{\Xi}P_{0}\left(\sum\limits_{s=1}^{r}c_{s}h_{s}\otimes
X^{\otimes k}_{s}\right)P_{0}.$ (124)

Using the fact that

$\Pi_{0}=|GHZ_{+}\rangle\\!\langle GHZ_{+}|+|GHZ_{-}\rangle\\!\langle
GHZ_{-}|$ (125)

with

$|GHZ_{\pm}\rangle=\frac{1}{\sqrt{2}}\left(|0\rangle^{\otimes
k}\pm|1\rangle^{\otimes k}\right),$ (126)

results in

$\smash[b]{\frac{\lambda^{k}}{\Xi}\sum\limits_{s=1}^{r}}c_{s}h_{s}\otimes\Pi_{0}^{\otimes
s-1}\otimes(|GHZ_{+}\rangle\\!\langle GHZ_{+}|-|GHZ_{-}\rangle\\!\langle
GHZ_{-}|)\otimes\Pi_{0}^{\otimes r-s}.$ (127)

In other words, the effective Hamiltonian on the low-energy subspace of the
gadget Hamiltonian is composed of a mixture of positive and negative
contributions from each term as $\pm h_{s}$ is associated with different
projectors on the different auxiliary registers. This prevents us from
recovering the desired tensor-product structure between target and auxiliary
registers with $H^{\text{target}}$ required to use this construction in
practice, for our purposes; see also Ref. [18, Definition 11].

##  Appendix G Numerical simulations of the application of the gadget for
variational quantum algorithms

To show how one can use the proposed gadget construction, we have studied its
performance on the toy model $H^{\text{target}}=Z_{1}Z_{2}\dots Z_{n}$. This
specific example has already been used in the study of cost-function-dependent
barren plateaus [32]. Furthermore, a single global Pauli string is the
simplest example on which we can apply our gadget, and that needs the least
amount of resources. Indeed, we require $2n$ qubits to generate the
corresponding cost function, while any additional global Hamiltonian term
would imply $n$ additional qubits. With this choice, having in mind the
scaling of classical simulations, we can show the functioning of the gadget
for the largest possible number of target qubits. The purpose of our
simulation is to demonstrate Theorem 1 and Corollary 1; therefore, we
performed exact, state-vector simulations, which are not subject to the
considerations of exponential circuit evaluations presented previously. We
used a layered ansatz as done in Refs. [29, 32]. While this ansatz does not
fulfill the exact conditions of Corollary 2, it allows a comparison with
previous works on the topic.

###  G.1 Methods for gradient variance computations

Figure 8: Circuit ansatz used for the PQC implemented in the simulations of
the use of our perturbative gadget for VQE. Each layer is composed of randomly
chosen Pauli rotations on each qubit followed by controlled Pauli-$Z$ gates in
a chain pattern.

As shown in Fig. 7, the variances of the gradients of the energy for the
target Hamiltonian decay exponentially, while those of the gadget Hamiltonian
seem to decay subexponentially. The exponential scaling is more obvious when
using linear-log axes, but the current log-log choice puts emphasis on the
polynomial scaling of the curves for the gadget cost functions. Indeed, with
this choice of axes, a polynomial scaling results in a straight line which
seems to fit the data points well. Although the presented regime does not show
a clear advantage, the visible trend hints towards a crossover at larger qubit
numbers that are out of reach for our classical simulator.

For these results, we have used the parameter on the $n^{\text{th}}$ qubit of
the first layer when evaluating the variances. For the target Hamiltonian,
this corresponds to the last qubit it acts upon, while it corresponds to the
last qubit of the target register for the gadget Hamiltonian. Based on the
asymmetry of the gadget Hamiltonian with respect to the target and auxiliary
registers, choosing the parameter related to the last qubit of the target
register within the first layer guarantees a contribution of all Hamiltonian
terms at any depth. However, we stress that the found trend is expected to be
similar for all parameter choices, as indicated by Corollary 2.

###  G.2 Training simulations

Figure 9: Training simulations using the gadget construction $H^{\text{gad}}$
introduced in Definition 1 as cost to optimize the global Hamiltonian
$H^{\text{target}}=Z^{\otimes 5}$. Each of the 30 runs is plotted in a light
color while the more dark lines are the average over all runs. We employ an
alternating layered ansatz on ten layers that is trained on $H^{\text{gad}}$
(blue). Furthermore, we evaluate the energy of
$H^{\text{target}}\otimes\mathds{1}$ (red) by measuring the expectation value
of the target Hamiltonian for the output state of the circuit trained on the
gadget Hamiltonian, hence tracing out the auxiliary part. While the
theoretical guarantees of Theorem 1 only hold for
$\lambda\leq\lambda_{\text{max}}$, this bound is not tight and we observe
improved training for larger values. We thus propose treating $\lambda$ as an
additional hyperparameter.

Additionally to the gradient variance simulations, we have simulated gradient-
based optimization of $H^{\text{gad}}$ while monitoring the expectation value
of $H^{\text{target}}$ for different values of $\lambda$ as shown in Fig. 9.
From Theorem 1, we know that when successfully reaching the global minimum of
the expectation value of the gadget Hamiltonian, we can expect the output
state to converge to a state close to the ground state of $H^{\text{target}}$.
It has to be pointed out, however, that the subtleties of the low-energy part
of the spectrum are exponentially suppressed in $\lambda$, which can result in
slow optimizations or even exponential requirements in the presence of noise.
This can be seen in our experiments as the optimization stagnates for
perturbation strengths within the range of validity of our theoretical
results. Nevertheless, we have successfully obtained minimizations of the
expectation value of the target Hamiltonian for large values of
$\lambda>\lambda_{\text{max}}$ within a reasonable number of iterations. We
thus propose using the interaction strength $\lambda$ as an additional
hyperparameter and starting with larger values and reducing it later on for
improved accuracy and faster training. Furthermore, we note that the qubit
ordering has an impact on the practical performance and that a different
ordering has been employed for the variances and training plots. Further
details are discussed in Appendix G.3.

Note that these training simulations are to be seen as proof-of-principle
demonstrations, since, in the simulated regime, even the original, global
Hamiltonian can be optimized. Also, since the proposed gadget requires several
times the number of qubits that the global Hamiltonian would, we quickly
escape the realm of system sizes that can be efficiently simulated
classically. Still, the scalings of our gadget construction remain compatible
with the NISQ regime and could be a tool added to the arsenal of techniques
for optimizing cost functions on near-term devices that are otherwise plagued
by the barren plateau phenomenon.

###  G.3 Performance improvements through qubit reordering

Figure 10: Two possible qubit orderings and the resulting simulations for the
case of $n=5$, $k=4$, and $r=2$ (as in Fig. 5). Panel (a) is the corresponding
simulation to Fig. 9 but using the basic ordering. Panels (b) and (c) show
said ordering (used in Fig. 7) and the improved one (used in Fig. 9)
respectively. For each, first is the distribution of the 13 qubits into the
three registers (left), then the terms from the target Hamiltonian and the
qubits they act on (center), and finally a selection of the terms composing
the gadget Hamiltonian (right). In contrast with Fig. 5, we abandoned the
circular layout and use a linear one to match the usual representation of the
qubit register in a quantum computing circuit.

Until this point, we focused more on the conceptual message of using
perturbative gadgets in VQAs to overcome cost-function-dependent barren
plateaus and less on practical details relevant to their actual
implementation. One of them is the qubit ordering in the joint register of the
quantum computer or simulator. While our main theorems do not depend on the
geometry of the quantum circuit, the couplings in the constructed gadget
Hamiltonian do have a particular structure. Considering the state generated at
the end of the PQC and the nearest-neighbor coupling of each layer of the used
ansatz in combination with shallow circuit depths, it is reasonable to assume
that the ordering of the qubits in a one-dimensional, joint register will have
an effect. Qubits coupled by the target Hamiltonian should probably be more
entangled than those that are not coupled. We have thus explored different
layouts of the target and auxiliary qubit registers with the goal of keeping
coupled qubits closer.

First, let us discuss the straightforward qubit ordering used for the
simulation results in Fig. 7. As shown in Fig. 10(b), the qubits have been
added to the total register as they appear in the gadget construction. That
is, first the target register and then one auxiliary register after the other.
The resulting coupling terms $\sigma_{s,j}^{\text{target}}\otimes
X_{s,j}^{\text{aux}}\otimes X_{s,(j+1)\text{ mod }k}^{\text{aux}}$ are then
divided with the target qubit being far from the two corresponding auxiliary
qubits. Training simulations in this setting (Fig. 10 (a) ) were mostly
successful, but in some instances ended up maximizing the target cost function
instead of minimizing it.

Since the coupling graph resulting from $H^{\text{gad}}$ does not allow for a
one-dimensional distribution such that only nearest-neighbor qubits are
coupled, we settled for putting at least one of the relevant auxiliary qubits
close to the target qubit. To do so, we interleave the registers such that the
first auxiliary qubit in $\sigma_{s,j}^{\text{target}}\otimes
X_{s,j}^{\text{aux}}\otimes X_{s,(j+1)\text{ mod }k}^{\text{aux}}$ is added
between the corresponding target qubit and the next target qubit. Due to the
cyclic nature of the gadget construction, the second auxiliary qubit will be
placed in the neighborhood of the following target qubit. A simple example of
this is presented in Fig. 10 (c). With this new ordering, we obtained the
results shown in Fig. 9. The comparison of the convergence properties of the
training simulations in both settings provides numerical evidence of the role
of qubit ordering when it comes to practical implementations of the introduced
methods. First, the average convergence speed visibly improves when using the
new ordering. Second, the better ordering does not exhibit any runs that
maximize the target Hamiltonian as found for the first one, which could be
attributed to the local minima of the gadget cost function. Although this
reordering does not pretend to be optimal but rather a first proposal, we
could show for our example that considering the order of the qubits in
combination with the structure of the minimized cost function can lead to
clear improvements in the performance of VQAs in practical settings.

##  Appendix H A gadget for reducing measurement bases in the Hamiltonian
readout problem

The gadget discussed so far is a gadget tuned for maximally reducing the
locality of the gadget Hamiltonian. There, we have also noted, that the energy
of such a gadget construction can be estimated using only four measurement
settings. This motivates the construction of a different gadget minimizing the
resource overheads. Such a gadget is presented here. Furthermore, since such a
gadget can be expressed in four layers of mutually commuting terms, it could
also be applicable to the fault-tolerant setting, where layers of mutually
commuting $T$-gates can be executed in parallel by increasing the number of
qubits [55].

###  H.1 Gadget definition

The gadget itself is constructed as follows: Let $H^{\text{target}}$ be an
arbitrary Hamiltonian represented using $r$ differently weighted tensor
products of Pauli operators, such that

$H^{\text{target}}=\sum_{s=1}^{r}c_{s}H_{s}=\sum_{s=1}^{r}c_{s}H_{s}^{X}H_{s}^{Y}H_{s}^{Z},$
(128)

where each individual Pauli-word is decomposed into its Pauli-$X$, Pauli-$Y$,
and Pauli-$Z$ part, e.g.,

$\displaystyle H_{1}=$ $\displaystyle X_{1}Y_{2}X_{3}Z_{4},$ (129)
$\displaystyle H_{1}^{X}=$ $\displaystyle X_{1}X_{3},$ (130) $\displaystyle
H_{1}^{Y}=$ $\displaystyle Y_{2},$ (131) $\displaystyle H_{1}^{Z}=$
$\displaystyle Z_{4}.$ (132)

Then, we choose our gadget Hamiltonian to be

$H^{\text{gad}}=H^{\text{aux}}+\lambda V$ (133)

with

$H^{\text{aux}}=-\sum_{i=1}^{q}Z_{i}$ (134)

acting as the unperturbed Hamiltonian on the $q$ auxiliary qubits and

$\lambda
V=\lambda\sum_{s=1}^{r}\sum_{A\in\\{X,Y,Z\\}}\tilde{c}_{s}H_{s}^{A}\otimes
V_{s,A}^{\text{aux}}$ (135)

its perturbation. Since the goal is that products of $V_{s,A}^{\text{aux}}$
only become the identity if the corresponding product of $H_{s}^{A}$ is one of
the target terms, we introduce

$\tau_{i}^{X}=X_{i-1}\qquad\tau_{i}^{Y}=X_{i}\qquad\tau_{i}^{Z}=X_{i-1}X_{i}$
(136)

for $X$ being the Pauli-$X$ operators acting on the auxiliary qubits.

The idea is to construct the terms $V_{s,A}^{\text{aux}}$ as products of some
$\tau_{i}^{A}$ such that their product only results in the identity if we have
$V_{s}^{X}V_{s}^{Y}V_{s}^{Z}$. To do so, we define $M$ to be the set of all
subsets of $\\{1,2,\dots,q/2\\}$ with an odd number of entries sorted with
respect to their cardinality. There are

$\sum_{k\text{ odd}}^{q}\binom{q}{k}=2^{q-1}$ (137)

many such sets. Then, constructing the perturbations $V_{s,A}^{\text{aux}}$
for the term $H_{s}^{A}$ using the set $M_{s}$, we define

$V_{s,A}^{\text{aux}}=\prod_{i\in M_{s}}\tau_{2i}^{A}$ (138)

and

$\tilde{c}_{s}=\sqrt[3]{c_{s}|M_{s}|^{2}}.$ (139)

The ground state of $H^{\text{aux}}$ is given by $|0\rangle^{\otimes k}$.
Since the action of the perturbation is not immediately apparent, it is
worthwhile to inspect it more closely. Imagine a system with $q=10$ auxiliary
qubits $a_{1},\dots,a_{q}$. There, the individual $V_{i,A}^{\text{aux}}$ are
chosen in the fashion of table 2:

|  | $a_{1}$ | $a_{2}$ | $a_{3}$ | $a_{4}$ | $a_{5}$ | $a_{6}$ | $a_{7}$ | $a_{8}$ | $a_{9}$ | $a_{10}$
---|---|---|---|---|---|---|---|---|---|---|---
$V_{1,X}^{\text{aux}}$ | $=\tau_{2}^{X}$ | $X$ | $\mathds{1}$ |  |  |  |  |  |  |  |
$V_{1,Y}^{\text{aux}}$ | $=\tau_{2}^{Y}$ | $\mathds{1}$ | $X$ |  |  |  |  |  |  |  |
$V_{1,Z}^{\text{aux}}$ | $=\tau_{2}^{Z}$ | $X$ | $X$ |  |  |  |  |  |  |  |
$V_{2,X}^{\text{aux}}$ | $=\tau_{4}^{X}$ |  |  | $X$ | $\mathds{1}$ |  |  |  |  |  |
$V_{3,X}^{\text{aux}}$ | $=\tau_{6}^{X}$ |  |  |  |  | $X$ | $\mathds{1}$ |  |  |  |
$\vdots$ |  |  |  |  |  |  |  | $\ddots$ |  |  |
$V_{6,X}^{\text{aux}}$ | $=\tau_{2}^{X}\tau_{4}^{X}\tau_{6}^{X}$ | $X$ | $\mathds{1}$ | $X$ | $\mathds{1}$ | $X$ | $\mathds{1}$ |  |  |  |
$V_{7,X}^{\text{aux}}$ | $=\tau_{2}^{X}\tau_{4}^{X}\tau_{8}^{X}$ | $X$ | $\mathds{1}$ | $X$ | $\mathds{1}$ |  |  | $X$ | $\mathds{1}$ |  |
$\vdots$ |  |  |  |  |  |  |  |  |  | $\ddots$ |
$V_{16,X}^{\text{aux}}$ | $=\prod_{i=1}^{5}\tau_{2i}^{X}$ | $X$ | $\mathds{1}$ | $X$ | $\mathds{1}$ | $X$ | $\mathds{1}$ | $X$ | $\mathds{1}$ | $X$ | $\mathds{1}$
Table 2: Exemplary assignments for the perturbation acting on ten auxiliary
qubits for a computational Hamiltonian comprising 16 terms.

In this fashion, we have that
$V_{s}^{X}V_{s^{\prime}}^{Y}V_{s^{\prime\prime}}^{Z}=\mathds{1}$ only if
$s=s^{\prime}=s^{\prime\prime}$. In any other case, due to the perturbative
expansion, the product does not contribute to the effective Hamiltonian. Since
there are two auxiliary qubits required as a unit, we obtain a qubit overhead
of $q\geq 2(\log_{2}(r)+1)$. Here, we note that this perturbation structure is
only one example and that more compact versions requiring fewer qubits might
exist.

###  H.2 Mathematical analysis

The perturbation of $H^{\text{aux}}$ by $\lambda V$ results in a global energy
shift and a splitting of the degeneracy of the ground space, mimicking
$H^{\text{target}}$ and leading to the following result:

######  Theorem 2 (Mathematical analysis).

Given $H^{\text{gad}}$ acting on $n$ target and $q$ auxiliary qubits as
defined above and $\lambda<1/2\lVert V\rVert$ with the operator norm
$\lVert...\rVert$, $H_{\text{eff}}(H^{\text{gad}},d)$ will mimic
$H^{\text{target}}$ at third order in perturbation theory with respect to
$\lambda$, specifically

$H_{\text{eff}}(H^{\text{gad}},2^{n})=\Delta\Pi+\lambda^{3}H^{\text{target}}\otimes
P_{+}+\mathcal{O}(\lambda^{4}),$ (140)

where $\Delta$ is a constant energy shift and $P_{+}=|0\rangle\\!\langle
0|^{\otimes q}$ denotes the operator projecting all auxiliary qubits onto
their ground state and $\Pi$ the projector on the support of
$H_{\text{eff}}(H^{\text{gad}},2^{k})$.

###### Proof.

The fundamentals of the perturbative expansion are presented above in Appendix
A, identical to those also used in Appendix B. Consequently, the expansion
converges if

$\lVert\lambda V\rVert<\frac{\gamma}{4},$ (141)

with $\gamma$ being equal to the smallest energy gap of $H^{\text{aux}}$,
i.e., $\gamma=2$ for $H^{\text{gad}}$ leading to the condition that

$\lambda\leq\frac{1}{2\lVert V\rVert}.$ (142)

Let us now start by identifying nonzero terms in every order of perturbation
theory. Since (see Eq. (72)) all terms are sandwiched by
$P_{0}=\mathds{1}\otimes P_{+}$ operators projecting the system onto the
ground space $\mathcal{E}^{(0)}$ of $H^{\text{aux}}$, all terms vanish that do
not take a state from $\mathcal{E}^{(0)}$ and return it to
$\mathcal{E}^{(0)}$. For the perturbation introduced in Equation (135), this
is equivalent to saying that no combination of terms of $V$ resulting in an
auxiliary space unequal to $|0\rangle^{\otimes q}$ will survive. Consequently,
there will be no surviving terms in the first order of perturbation theory.

The terms in second order originate from $V^{2}$ and belong to one of the
following two categories: either they vanish because they excite the auxiliary
space in two different ways not returning the state to $\mathcal{E}^{(0)}$ or
they are squares of individual terms that survive since Pauli operators square
to the identity. The latter are responsible for the constant energy shift
$\Delta$.

In analogy, all third-order terms vanish except for those of the form
$V_{s}^{X}V_{s}^{Y}V_{s}^{Z}$ resulting in a degeneracy splitting caused by
the application of $H_{s}^{X}H_{s}^{Y}H_{s}^{Z}$ on the original system,
because only a combination of $\tau_{s}^{X}$, $\tau_{s}^{Y}$, and
$\tau_{s}^{Z}$ will yield $|0\rangle^{\otimes q}\in\mathcal{E}^{(0)}$ on the
auxiliary register after the perturbation. There are six possible permutations
of these three perturbations, and the perturbation corresponding to the
Pauli-$Z$ string can happen first, second or last, resulting in different
energy penalties. Applying $V_{i}^{Z}$ first or last will result in one
intermediate state with a penalty of $4\lvert M_{s}\rvert$ and one with a
penalty of $2\lvert M_{s}\rvert$, whereas applying the $V_{i}^{Z}$
perturbation in the middle results in both intermediate states having a
penalty of $2\lvert M_{s}\rvert$. Furthermore, from the sum in Eq. (72), only
the case $(\ell_{1},\ell_{2})=(1,1)$ contributes, and not $(2,0)$. Including
the corresponding combinatorial factors we find

$\displaystyle H_{\text{eff}}(H^{\text{gad}},2^{n})^{(3)}$
$\displaystyle=\sum_{s=1}^{r}\frac{1}{\lvert
M_{s}\rvert^{2}}\Bigg{(}2\underbrace{\frac{1}{(-2)(-2)}}_{V_{i}^{Z}\text{
second}}+4\underbrace{\frac{1}{(-4)(-2)}}_{V_{i}^{Z}\text{ first or
last}}\Bigg{)}\tilde{c}_{s}^{3}\lambda^{3}H_{s}^{X}H_{s}^{Y}H_{s}^{Z}\otimes
P_{+}$ $\displaystyle=\lambda^{3}\sum_{s=1}^{r}c_{s}H_{s}\otimes
P_{+}=\lambda^{3}H^{\text{target}}\otimes P_{+}.$ (143)

∎

The striking feature of these types of gadgets is, that their Hamiltonian can
be grouped into four sums of qubitwise commuting Pauli operators, which can
therefore be estimated using only four measurement bases:

$H^{\text{gad}}=\underbrace{-\sum_{i=1}^{q}\mathds{1}\otimes
Z_{i}}_{\mathds{1}_{\text{target}}\otimes
Z_{\text{aux}}}+\underbrace{\lambda\sum_{s=1}^{r}\tilde{c}_{s}H_{s}^{X}\otimes
V_{s,X}^{\text{aux}}}_{X_{\text{target}}\otimes
X_{\text{aux}}}+\underbrace{\lambda\sum_{s=1}^{r}\tilde{c}_{s}H_{s}^{Y}\otimes
V_{s,Y}^{\text{aux}}}_{Y_{\text{target}}\otimes
X_{\text{aux}}}+\underbrace{\lambda\sum_{s=1}^{r}\tilde{c}_{s}H_{s}^{Z}\otimes
V_{s,Z}^{\text{aux}}}_{Z_{\text{target}}\otimes X_{\text{aux}}}.$ (144)

However, as mentioned above, the scaling in $\lambda$ is unfavorable except
for settings in which it is excessively expensive to change measurement
settings but cheap to evaluate a circuit given a chosen setting.