# Going Beyond Gadgets: The Importance of Scalability for Analogue Quantum Simulators

Dylan Harley, Ishaun Datta, Frederik Ravn Klausen, Andreas Bluhm, Albert Werner, Matthias Christandl, Daniel Stilck França

► To cite this version:

Dylan Harley, Ishaun Datta, Frederik Ravn Klausen, Andreas Bluhm, Albert Werner, et al., Going Beyond Gadgets: The Importance of Scalability for Analogue Quantum Simulators. 2024. [hal-04386725]

HAL Id: hal-04386725

https://hal.science/hal-04386725v1

Preprint submitted on 11 Jan 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Going Beyond Gadgets: The Importance of Scalability for Analogue Quantum Simulators

Dylan Harley¹, Ishaun Datta², Frederik Ravn Klausen¹, Andreas Bluhm¹,³, Daniel Stilck França¹,⁴, Albert Werner¹, and Matthias Christandl¹

¹Department of Mathematical Sciences, University of Copenhagen, Universitetsparken 5, 2100 Copenhagen, Denmark

²Stanford University, 450 Serra Mall, Stanford, CA 94305, USA

⁴Univ Lyon, ENS Lyon, UCBL, CNRS, Inria, LIP, F-69342, Lyon Cedex 07, France

³Univ. Grenoble Alpes, CNRS, Grenoble INP, LIG, 38000 Grenoble, France

August 15, 2023

## Abstract

We propose a theoretical framework for analogue quantum simulation to capture the full scope of experimentally realisable simulators, motivated by a set of fundamental criteria first introduced by Cirac and Zoller. Our framework is consistent with Hamiltonian encodings used in complexity theory, is stable under noise, and encompasses a range of possibilities for experiment, such as the simulation of open quantum systems and overhead reduction using Lieb-Robinson bounds. We discuss the requirement of scalability in analogue quantum simulation, and in particular argue that simulation should not involve interaction strengths that grow with the size of the system. We develop a general framework for gadgets used in Hamiltonian complexity theory, which may be of interest independently of analogue simulation, and in particular prove that size-dependent scalings are unavoidable in Hamiltonian locality reduction. However, if one allows for an additional resource of engineered dissipation, we demonstrate a scheme that circumvents the locality reduction no-go theorem using the quantum Zeno effect. Our gadget framework opens the door to formalise and resolve long-standing open questions about gadgets. We conclude with a discussion on universality results in analogue quantum simulation.
# Contents

## 1 Introduction 4

1.1 Background 4

1.2 Overview and motivation for work 4

1.3 Criteria for quantum computation and analogue quantum simulation 5

1.4 Existing theoretical work 6

## 2 Framework 8

2.1 Definition 8

2.2 Justification and applications 10

## 3 Modular encodings and gadgets 14

3.1 Overview 14

3.2 A general definition for gadgets 14

3.3 Energy scaling is inevitable for gadgets 16

3.4 Gadgets from the quantum Zeno effect 17

3.5 Outlook on universality for analogue quantum simulators 20

## 4 Conclusion 21

## References 22

### A General gadgets 25

A.1 Existing constructions 25

A.2 "Exact" 3-to-2 gadget 27

A.3 Combining gadgets 28

### B Proofs 30

B.1 Qutrit-to-qubit energy scaling 30

B.2 Gadget characterisation 32

B.2.1 The gadget property from gadgets 33

B.2.2 Gadgets from the gadget property 33

B.3 Gadget energy scaling 39

B.4 Gadget combination 40

B.4.1 Combination of general gadgets 40
<table><tr><td>B.4.2 Combination of low-energy gadgets</td><td>43</td></tr><tr><td>B.4.3 Ground-state estimation with bounded-strength low-energy gadgets</td><td>46</td></tr><tr><td>B.5 Measurement gadgets</td><td>48</td></tr><tr><td>B.5.1 Measurement gadgets in isolation</td><td>48</td></tr><tr><td>B.5.2 Trotter errors</td><td>49</td></tr><tr><td>B.5.3 Measurement gadgets with other terms</td><td>50</td></tr></table>
# 1 Introduction

## 1.1 Background

In the decades since Feynman’s famous 1981 talk “Simulating physics with computers” that formulated and popularised the idea of what we now call a quantum simulator [Fey82], there has been a proliferation of increasingly sophisticated quantum devices (see for example [GAN14, ALGTS$^{+}$19] for reviews). The simulation of quantum systems remains a particularly promising application of quantum technologies owing to its classical intractability and the possibilities of attaining quantum advantage on near-term hardware, both digital [CMN$^{+}$18] and analogue [TRC22].

The generic problem of quantum simulation is as follows: one is given a state $ρ$, a Hamiltonian $H$, and an observable $O$. The task is to determine how the measured values of $O$ change as $ρ$ evolves under $H$.

From here there are two main approaches: digital and analogue. A digital quantum simulator uses discrete time steps to calculate the evolution of a system under the Hamiltonian $H$ through a series of quantum gates [Llo96]. This method provides the greatest control and flexibility for quantum simulation problems, and over recent decades there has been extensive development of algorithms for this task [BCK15, BCC$^{+}$15, LC17, LC19], and in particular optimisations for applications to quantum chemistry [HWBT15, BBMC20]. Despite this, and experimental progress [LHN$^{+}$11, BLK$^{+}$15, HMR$^{+}$18, NCP$^{+}$20], useful and scalable digital simulations still lie out of reach for NISQ technology [Pre18] that lacks fault-tolerance.

By contrast, an analogue quantum simulator encodes the Hamiltonian $H$ into a better-controlled laboratory Hamiltonian $H'$, such that the dynamics of the $H'$ system reveal properties of the dynamics of $H$. Instead of a sequence of quantum gates, the simulation in this regime takes place through the natural time evolution of the laboratory system. The aim of analogue quantum simulation is not to precisely calculate the time-evolved state, but instead to provide qualitative insight into the time evolution of observables in the system. Such simulators do not require individual qubit control, which constitutes a major advantage for near-term hardware, on which individual gates incur a significant noise penalty. On the other hand, this approach suffers the disadvantage of poor flexibility: the laboratory system may only be capable of implementing a relatively small family of Hamiltonians. Nevertheless, experimental setups can be tailored for a variety of tasks, from spin systems [JZ05, GTHC$^{+}$15, PCK$^{+}$21] to quantum chemistry [ALGTS$^{+}$19, MC23].

Presently, there exist hundreds of analogue quantum simulators realised on a diversity of experimental platforms [GB17, MW21, NA16], some of which have already demonstrated hundreds of interacting sites [EWL$^{+}$21], pushing them beyond the frontier of classical simulability [ABC$^{+}$21]. For some analogue simulators, this already constitutes a kind of quantum advantage over any available classical computers [DBK$^{+}$22].

## 1.2 Overview and motivation for work

Unlike the digital case, analogue quantum simulation is relatively under-explored from the theoretical perspective (notable exceptions include [CMP18, AZ18, ZA21], which we address in this work). Despite extensive study of Hamiltonian complexity theory (see Section 1.4), abstract complexity-theoretic results generally do not reflect experimental possibilities for analogue quantum simulators. In particular, constructions for universal Hamiltonian simulators [CMP18] often require high-degree polynomial, or even exponential, scalings for interaction strengths with respect to the system size.

In Section 1.3 we discuss the Cirac-Zoller criteria [CZ12] for analogue quantum simulators and the necessity for an additional size-independence requirement, for which we provide a candidate
definition. In Section 1.4 we review existing theoretical work and combine the conclusions of these sections to motivate a new definition for analogue quantum simulation in Section 2. In Section 2.2 we verify that our definition is suitable for noisy simulators, is in a sense consistent with the notion of simulation defined in [CMP18], and demonstrate applications which are not captured by the latter.

In Section 3, we generalise gadget constructions used extensively in Hamiltonian complexity theory [KKR06, OT08, BH17]. Armed with a general definition, we argue that gadget locality reduction techniques necessarily require scaling interaction strengths with the system size. This has significant consequences for the applicability of universal simulation results to experimental systems, which we discuss in Section 3.5.

## 1.3 Criteria for quantum computation and analogue quantum simulation

In a review of the prospective possibilities of quantum computing [DiV00] the author provided a set of requirements, now known as the DiVincenzo criteria, designed to serve as a full specification for implementations of universal quantum computers. These are summarised in Fig. 1.

<table><caption>Figure 1: A summary of the DiVincenzo and Cirac-Zoller criteria.</caption><thead><tr><th>The DiVincenzo criteria for quantum computation [DiV00]</th><th>The Cirac-Zoller criteria for quantum simulation [CZ12]</th></tr></thead><tbody><tr><td>(A) A scalable physical system with well-characterised qubits.</td><td>(I) A system of bosons/fermions confined in a region of space, containing a large number of degrees of freedom.</td></tr><tr><td>(B) The ability to initialise the state of the qubits to a simple fiducial state, such as |000...⟩.</td><td>(II) The ability to approximately prepare a known quantum state — ideally pure.</td></tr><tr><td>(C) Long relevant decoherence times, much longer than the gate operation time.</td><td>(III) The ability to engineer and adjust the values of a set of interactions between the particles, and possibly external fields or a reservoir.</td></tr><tr><td>(D) A "universal" set of quantum gates.</td><td>(IV) The capability to measure the system, either on specific sites or collectively.</td></tr><tr><td>(E) A qubit-specific measurement capability.</td><td>(V) A procedure for increasing confidence in the results of the simulation.</td></tr></tbody></table>

As well as concretely providing the experimentalist with a necessary set of criteria to aim towards, the sufficiency of the DiVincenzo criteria provides the theorist with a canonical yardstick to judge the applicability of their protocol to idealised quantum hardware. It is therefore important that such requirements reflect exactly what can be expected from quantum technology in the long term, neither excluding feasible technologies nor including unfeasible procedures.

A similar set of criteria for analogue quantum simulators is discussed in [CZ12], also summarised in Fig. 1. These are all natural requirements to ask of a quantum simulator, but it is noteworthy that (III) does not provide any restriction on the interactions that one should expect the simulator to include. This leads to a problem which does not arise for the DiVincenzo criteria: whereas a quantum computer can approximate arbitrary $k$-qubit gates from the compact set $U((C^2)^{\otimes k})$ of
unitary transformations relatively cheaply due to the Solovay-Kitaev theorem [Kit97], the task of
an analogue quantum simulator is to implement $k$-qudit interactions from the unbounded set of
possible Hamiltonians Herm(((keit)$^{\otimes}$k). The ability to realise arbitrarily strong interactions on a
physical device is clearly an impossibility.

Thus, the key extra criterion which we demand of an analogue quantum simulator is that the
encoding of the target Hamiltonian should be size-independent. Concretely, if the Hamiltonian
$H$ to be encoded consists of local interactions $(h_i)_{i=1}^m$ on $n$ sites then the encoding of individual
terms should not depend, for instance by polynomial scaling of interaction strengths, on the size
of the physical system $n$. In particular, we argue that methods for practical analogue quantum
simulation must respect a limit on the interaction strengths of the simulator Hamiltonian. The
strongest interactions should be bounded by some constant fixed by physical limitations, and the
weakest interactions should be similarly bounded from below (since sufficiently weak interactions
will be overwhelmed by noise in the simulator). We summarise this requirement with the following
qualitative definition:

**Definition 1** (Size-independent simulation). We say that an analogue quantum simulation is size-independent if the simulation of a *n*-site Hamiltonian can be implemented scalably with *n*. By this, we mean that the number of qubits used in the simulation should grow no faster than linearly in *n*, and the interaction strengths necessary should remain $\Theta(1)$.<fnref n="1" />

In addition to the physical limits of a simulator, there is philosophical motivation to be suspicious
of analogue quantum simulation procedures which require interaction strengths that scale with the
system size. A many-body Hamiltonian is inherently a modular object, and an analogue quantum
simulation should reflect this. The addition of a few qubits and local interactions to one end of the
physical system should require an analogous action on the simulator — it should not require the
adjustment of every other interaction in the system. Compare this to a civil engineer “simulating”
their bridge design by building a model: if the density of the bricks they use to build the model
must, for some reason, scale polynomially with the length of their bridge, then their modelling
procedure is clearly flawed and inevitably limited in its capabilities. This is not what analogue
simulation, classical or quantum, should look like.

Moreover, encoding interactions independently has quantitative benefits; as noted in [CMP18], for
a suitably “local” Hamiltonian encoding, local errors on the simulator system will correspond to
local errors on the target system. For NISQ hardware, this represents an extremely useful way to
mitigate the negative effects of a noisy simulation: rather than random scrambling, noise can be
viewed as the manifestation of physically reasonable noisy effects on the target system.

Finally, studying the power of Hamiltonians subject to interaction energies that are constant in
system size is well-motivated in its own right, from the perspective of Hamiltonian complexity. For
example, [AZ18] show that restriction to such Hamiltonians will necessarily sacrifice some sense of
universality of the simulator. Earlier results in Hamiltonian complexity theory [BDLT08], however,
show that in many cases it is still possible to simulate ground state energies up to an extensive
error.

**1.4 Existing theoretical work**

Much of the existing theoretical work on analogue quantum simulation has been motivated by the
complexity of the local Hamiltonian problem [KSV02]. We say that a Hamiltonian $H$ on the space

<footnote n="1">¹It is worth noting that further formalisation is required to make this definition robust. For example, suppose we are given a Hamiltonian $H = h_1 + h_2$ where $\|h_1\|, \|h_2\| = O(n^{-1})$, which violates the size-independence requirement. One could simply define $h'_1 = h_1 + K$, $h'_2 = h_2 - K$, for some $K = \Theta(1)$, and then $H = h'_1 + h'_2$ can be written in a form which does not obviously violate Definition 1. To exclude such possibilities, we could impose an additional requirement that $H$ is given in a canonical form, such as that described by [WW22].</footnote>
of $n$ qubits $\mathcal{H} = (\mathbb{C}^2)^{\otimes n}$ is $k$-local if it can be written as $H = \sum_{j=1}^N h_j$, where each of the terms $h_j$ acts on at most $k$ of the qubit sites. We consider the $h_j$ individual interactions in the Hamiltonian and make reference to the interaction hypergraph, whose vertices are qubits and whose (hyper)edges are interactions (joining the qubits on which they act), illustrated in Fig. 2.

<figure><img src="image_2.png" /><figcaption>Figure 2: A Hamiltonian $H$ on 4 qubits, and its associated interaction hypergraph. The Hamiltonian consists of a 3-local and a 2-local term, so we say that $H$ is 3-local.</figcaption></figure>

Informally, the $k$-local Hamiltonian problem asks whether the ground state energy of a $k$-local Hamiltonian is less than $a$, or greater than $b$, for some real numbers $a < b$ separated by a suitably large gap. This problem lies in the QMA complexity class: the natural quantum analogue to the classical NP, containing problems whose solutions can be efficiently verified (but not necessarily found) on a quantum computer.

**Definition 2** ($k$-local Hamiltonian problem). The $k$-local Hamiltonian problem is the promise problem which takes as its input a $k$-local Hamiltonian $H = \sum_{j=1}^N h_j$ on the space of $n$ qubits $\mathcal{H} = (\mathbb{C}^2)^{\otimes n}$, where $N = \text{poly}(n)$, and for each $j$ we have $\|h_j\| \le \text{poly}(n)$ and $h_j$ is specified by $O(\text{poly}(n))$ bits.

Given $a < b$ with $b - a > 1/\text{poly}(n)$, let $\lambda_0(H)$ denote the lowest eigenvalue of $H$. Then the output should distinguish between the cases

* Output 0: The ground state energy of $H$ has $\lambda_0(H) \le a$.

* Output 1: The ground state energy of $H$ has $\lambda_0(H) \ge b$.

Through the Feynman-Kitaev circuit-to-Hamiltonian construction [KSV02], it was established that the 5-local Hamiltonian problem is QMA-complete, and subsequent works optimising the construction [KR03] and using gadget techniques [KKR06] reduced this further to show the QMA-completeness of the 2-local Hamiltonian problem. Various further optimisations have been found to refine the problem and further restrict the family of allowed Hamiltonians (see for example [HNN13, CM16]); indeed hardness results have been shown to hold even under the significant restriction to 1-dimensional translationally invariant systems [GI09]. QMA-completeness is closely related to a notion of universality for simulators; an equivalence was proved in [KPBC22].

The constructions involved in the aforementioned results contain Hamiltonian interaction strengths which scale polynomially, or exponentially, with system size. Such Hamiltonians are infeasible for an analogue simulator, as discussed in Section 1.3. A notable exception to this is [BDLT08], in which the authors use the Schrieffer-Wolff transformation to show that bounded-strength interactions are sufficient for one to reproduce the ground-state energy of the original Hamiltonian up to an extensive error.

As much of this Hamiltonian simulation literature focuses on specific complexity-theoretic problems, comparatively little work has been done to actually define a mathematical framework for analogue quantum simulation to be used in experiment. Notable recent work in this direction includes [CMP18], in which the authors study methods of encoding Hamiltonians via a map $\mathcal{E}_{\text{obs}}: \text{Herm}(\mathcal{H}) \to \text{Herm}(\mathcal{H}')$, which satisfy the natural requirement of preserving the spectrum of
observables. Additionally, in the case that $\mathcal{H} = \bigotimes_{i=1}^n \mathcal{H}_i$ is a space of many sites, they introduce the further notion of local encodings, which map local observables in $\mathcal{H}$ to local observables in $\mathcal{H}' = \bigotimes_{i=1}^{n'} \mathcal{H}_i'$. The authors arrive at the following definition.

**Definition 3** (Local Hamiltonian encoding [CMP18]). A local Hamiltonian encoding is a map $\mathcal{E}_{\text{obs}}: \text{Lin}(\bigotimes_{i=1}^n \mathcal{H}_i) \to \text{Lin}(\bigotimes_{i=1}^n \mathcal{H}_i')$ of the form

$$ \mathcal{E}_{\text{obs}}(M) = V(M \otimes P + \bar{M} \otimes Q)V^{\dagger}, $$

where $P$ and $Q$ are locally distinguishable<fnref n="2" /> orthogonal projectors on an ancillary space $\mathcal{A} = \bigotimes_{i=1}^n \mathcal{A}_i$, and $V = \bigotimes_{i=1}^n V_i$ where $V_i \in \text{Isom}(\mathcal{H}_i \otimes \mathcal{A}_i, \mathcal{H}_i')$ for all $i$.

Generally, we consider the case of rank($P$) > 0 (referred to as *standard* in [CMP18]), for which one can define a corresponding state encoding

$$ \mathcal{E}_{\text{state}}(\rho) = V(\rho \otimes \tau)V^{\dagger}, \qquad (1) $$

where $\tau$ is a state on $\mathcal{A}$ satisfying $P\tau = \tau$.

Moreover, the authors define the following notion of simulation, which relaxes the requirements of locality and allows for some error in the simulated eigenvalues.

**Definition 4** ((Δ, η, ε)-simulation [CMP18]). A Hamiltonian $H' \in \text{Herm}(\mathcal{H}') = \text{Herm}(\bigotimes_{i=1}^n \mathcal{H}_i')$ is said to (Δ, η, ε)-simulate a Hamiltonian $H \in \text{Herm}(\mathcal{H}) = \text{Herm}(\bigotimes_{i=1}^n \mathcal{H}_i)$ if there exists a local encoding (Definition 3) $\mathcal{E}_{\text{obs}}(M) = V(M \otimes P + \bar{M} \otimes Q)V^{\dagger}$ such that

(i) There exists an encoding $\tilde{\mathcal{E}}_{\text{obs}}(M) = \tilde{V}(M \otimes P + \bar{M} \otimes Q)\tilde{V}^{\dagger}$ (where $\tilde{V} \in \text{Isom}(\mathcal{H} \otimes \mathcal{A}, \mathcal{H}')$ need not have a tensor product structure as in Definition 3) such that $\|V - \tilde{V}\| \le \eta$ and $\tilde{\mathcal{E}}_{\text{obs}}(\mathbb{I}) = P_{\le \Delta(H')}$ is the projection onto the low-energy ($\le \Delta$) subspace of $H'$, and

(ii) $\|P_{\le \Delta(H')}H'P_{\le \Delta(H')} - \tilde{\mathcal{E}}_{\text{obs}}(H)\| \le \varepsilon$.

This approach (later generalised in [AC22]) provides an elegant framework to capture a notion of one Hamiltonian fully simulating another. However, we believe that this regime does not capture the scope of possibilities for analogue quantum simulation experiments. On one hand, the formalism requires the entire physics of the target system to be encoded into the low-energy subspace of a simulator — this rules out simulators which only simulate part of the target system, or in a different subspace. On the other hand, the formalism is too broad in the sense that it does not prohibit unrealistically scaling interaction strengths in violation of Definition 1.

# 2 Framework

## 2.1 Definition

The generic task of an analogue quantum simulator is to estimate the dynamics of observables in a system $\mathcal{H}$ under the evolution of a target Hamiltonian $H$, up to some maximum time $t_{\text{max}}$. In particular, it is not always necessary to simulate the entire target system in arbitrary configurations: it may be convenient to restrict to a particular subset of initial states $\Omega_{\text{state}}$, for example lying in a subspace invariant under the Hamiltonian or corresponding to the states which can be reliably prepared by the simulator, and similarly to a particular subset of observables of interest $\Omega_{\text{obs}}$. We

<footnote n="2">²Projectors $P, Q \in \text{Proj}(\otimes_i \mathcal{A}_i)$ are locally distinguishable if, for all $i$, there exist orthogonal projectors $P_i, Q_i \in \text{Proj}(\mathcal{A}_i)$ such that $(P_i \otimes \mathbb{I})P = P$ and $(Q_i \otimes \mathbb{I})Q = Q$.</footnote>
<figure><img src="image_3.png" /><figcaption>Figure 3: The general procedure of analogue quantum simulation as described by Definition 5.</figcaption></figure>

denote by $\mathcal{H}'$ the Hilbert space corresponding to the simulator system, and for $t \in [0, t_{\max}]$ we write $T_t: D(\mathcal{H}') \to D(\mathcal{H}')$ for the family of time evolution quantum channels implemented by the simulator, where $D(\mathcal{H}')$ is the set of density matrices on $\mathcal{H}'$. This approach, in which we view simulations in terms of individual observables rather than the entire Hamiltonian, has been considered in earlier work [KS17, BCSF21, TRC22].

The minimal requirement for a simulator is that it should approximate the expectation values of the elements of $\Omega_{\text{obs}}$. That is, $\text{tr}[Oe^{-iHt}\rho e^{iHt}]$ should be close to $\text{tr}[O'T_t(\rho')]$ for all $\rho \in \Omega_{\text{state}}$ and $O \in \Omega_{\text{obs}}$, where $\rho'$ and $O'$ are some encoded versions of the states and operators respectively. Notice that, in principle, the experimentalist could be using a completely different simulator for each choice of $\rho$ and $O$, with $\mathcal{H}'$ a space large enough to contain all of them and by encoding $\rho$ into several copies. However, this would violate the size-independence requirement of Definition 1 if $\Omega_{\text{obs}}$ and $\Omega_{\text{state}}$ both do not only contain $O(1)$ elements. Furthermore, it is natural to consider analogue quantum simulators as machines taking quantum, rather than classical, input — possibly prepared by another experiment — which cannot be cloned. For this reason, we assume that the state encoding takes the form of a quantum channel $\mathcal{E}_{\text{state}}: D(\mathcal{H}) \to D(\mathcal{H}')$. Correspondingly, to accommodate for quantum outputs, we require the observable encoding $O \mapsto O'$ to be a unital and completely positive map $\mathcal{E}_{\text{obs}}: \text{Herm}(\mathcal{H}) \to \text{Herm}(\mathcal{H}')$. This perspective sets analogue quantum simulators apart from the framework of digital quantum computation, for which fault-tolerant architectures require both inputs and outputs to be classical.

This definition is still sufficiently versatile to capture the simulation of global observables that are a sum of local parts $O = \sum_k O_k$ (a task, for example, useful for variational quantum algorithms [CAB+21]), in the following way. Often the $O_k$ cannot be simultaneously measured due to non-commutativity relations or experimental limitations. The simplest approach to estimating $O$ is to run many simulations, measuring one of the $O_k$ each time (this process can be sped up by combining simultaneously measurable terms [MRBAG16]), and summing the average results.

The above discussion leads us to the following definition, which is illustrated by Fig. 3.

**Definition 5 (Analogue quantum simulation).** Given a set of states $\Omega_{\text{state}}$ on a Hilbert space $\mathcal{H}$, a normalised set of observables $\Omega_{\text{obs}}$ (i.e. $\|O\| = 1$ for all $O \in \Omega_{\text{obs}}$, where $\| \cdot \|$ denotes the operator norm), a time $t_{\max} > 0$, a Hamiltonian $H \in \text{Herm}(\mathcal{H})$, and $\varepsilon > 0$, we say that a family of quantum channels $T_t: D(\mathcal{H}') \to D(\mathcal{H}')$, for $t \in [0, t_{\max}]$ simulates $H$ with respect to $\Omega_{\text{state}}$ and $\Omega_{\text{obs}}$ with accuracy $\varepsilon$ if there exists

1. A state encoding quantum channel $\mathcal{E}_{\text{state}}: D(\mathcal{H}) \to D(\mathcal{H}')$ which maps states to the simulator Hilbert space $\mathcal{H}'$,
2. An observable encoding, given by a unital and completely positive map $\mathcal{E}_{\text{obs}} : \text{Herm}(\mathcal{H}) \to \text{Herm}(\mathcal{H}')$,

such that

$$ \left| \text{tr}[\mathcal{E}_{\text{obs}}(O)(T_t \circ \mathcal{E}_{\text{state}})(\rho)] - \text{tr}[O(e^{-i t H} \rho e^{i t H})]\right| \le \varepsilon, \quad (2) $$

for all $\rho \in \Omega_{\text{state}}$, $O \in \Omega_{\text{obs}}$, and $t \in [0, t_{\text{max}}]$.

Our use of a Hamiltonian $H$ for the target system is mostly for simplicity; the simulation of more general dynamics, of open quantum systems for example, can be defined analogously, with the target Hamiltonian $H$ replaced by any generator of a quantum dynamical semigroup [GKS76, Lin76]. It should be noted also that Definition 5 could equivalently have been phrased in terms of a set of POVMs rather than observables $\Omega_{\text{obs}}$. We use the latter for convenience in relating our work to other results.

By the triangle inequality, (2) holds for any convex combination of the states and observables in $\Omega_{\text{state}}$ and $\Omega_{\text{obs}}$ respectively, so we could without loss of generality assume that the two sets are convex to begin with.

Often the simulation channels $T_t$ in Definition 5 are taken simply as time evolution under some simulator Hamiltonian $H' \in \text{Herm}(\mathcal{H}')$, but it is useful to consider a more general case. Firstly, this allows one to directly account for, and possibly exploit, dissipative errors in the experimental setup [VWC09]. Secondly, it enables the possibility of a more complicated simulation experiment, for example involving intermediate measurements. Moreover, it is important to allow the simulation of open quantum systems for our definition to be consistent with (III). Despite the generality afforded by Definition 5, we emphasise that experimentally practical simulations should be size-independent as in Definition 1. That is, the implementation of $T_t$ should not require engineering a system of size which grows more than linearly in $n$, or boundlessly scaling interaction energies.

## 2.2 Justification and applications

In this section, we discuss some basic applications of our notion of analogue quantum simulation in the sense we have introduced in Definition 5. Firstly, we give an example of a trivial but illustrative situation in which encoding qudits into qubits incurs an unavoidable cost for low-energy encodings, but which is not an issue in our framework. We then demonstrate the robustness of the definition under noise, and show that it is consistent with the existing notion of simulation given in Definition 4. Finally, we note how Lieb-Robinson bounds can be used to reduce the overhead of simulating local observables.

### Qudits to qubits

To motivate this example, we first notice that the requirement in [CMP18] (Definition 4) that the simulator Hamiltonian should reproduce the target dynamics in its low-energy subspace is too strong for some practical situations. As observed by the authors, this can require the simulator to use strong interactions to “push” unwanted states out of the low-energy subspace. Proposition 6 provides a formal proof of this fact in the context of encoding a simple qutrit Hamiltonian into qubits.

Here we consider qutrits with individual state spaces $\mathbb{C}^3$ spanned by a basis $\{|\downarrow\rangle, |0\rangle, |\uparrow\rangle\}$. We write $P_0^{(j)} = |0\rangle\langle 0|$ and $P_\uparrow^{(j)} = |\uparrow\rangle\langle\uparrow|$, where the superscript indicates that the projectors act on the $j$th qutrit.
<figure><img src="image_4.png" /><figcaption>Figure 4: (Left) The original non-interacting qutrits have on-site energy levels 0,1,1. (Right) The $(\Delta, \eta, \epsilon)$-simulation, in this case sending each qutrit into two qubits, leads to approximately the same on-site energy levels, but the extra state must be given an energy above $\Delta$. (This illustration is a simplification; in principle the simulator sites $\mathcal{H}'_i$ can interact.)</figcaption></figure>

**Proposition 6.** Let $\mathcal{H} = (\mathbb{C}^3)^{\otimes n}$ be the space of $n$ qutrits acted on by the Hamiltonian

$$H_n = \sum_{j=1}^{n} (P_0^{(j)} + P_{\uparrow}^{(j)}).$$

Suppose $H'_n = \sum_{j=1}^K h'_j$ is a $k$-local Hamiltonian on $\mathcal{H}' = (\mathbb{C}^2)^{\otimes m}$, where $m = O(n^{1+\alpha})$, for $\alpha \in [0, 1]$ and $k = O(1)$. Assume the interaction hypergraph of $H'_n$ has degree bounded by $d = O(1)$.

If $H'_n$ is a $(\Delta, \eta, \epsilon)$-simulation for $H_n$ in the sense of Definition 4, for $\eta \in [0, 1)$ and $\epsilon \ge 0$, then

$$\max_j \|h'_j\| = \Omega(n^{1-\alpha}(1-\eta^2)). \qquad (3)$$

(Proof in Appendix B.1)

From (3) we see that simulating this simple system with a low-energy encoding, an interaction hypergraph of bounded degree, and bounded locality, requires either the qubit count or interaction energy (or a mixture) to scale unfeasibly with $n$: a violation of the requirements of Definition 1. The proof of this fact follows from a dimension-counting argument, since the state space of the qutrits cannot be surjectively encoded into the qubit simulator, see Fig. 4. In contrast, the simulation task is trivial in our framework given in Definition 5 because the low-energy encoding requirement is relaxed.

Letting $H_n = \sum_{j=1}^n (P_0^{(j)} + P_{\uparrow}^{(j)})$ as in Proposition 6, we can simulate all observables under $H_n$ on $\mathcal{H}' = \bigotimes_{j=1}^n (\mathbb{C}^2 \otimes \mathbb{C}^2)$ via any isometry

$$V : \mathbb{C}^3 \to \mathbb{C}^2 \otimes \mathbb{C}^2,$$

encoding each qutrit into two qubits. To realise a simulator in the sense of Definition 5, we let

$$\mathcal{E}_{\text{state}} : \rho \mapsto V^{\otimes n} \rho (V^{\otimes n})^{\dagger}, \quad \mathcal{E}_{\text{obs}} : O \mapsto V^{\otimes n} O (V^{\otimes n})^{\dagger},$$

and

$$T_t = e^{-it\mathcal{E}_{\text{obs}}(H_n)}(\cdot)e^{it\mathcal{E}_{\text{obs}}(H_n)},$$

which is just time evolution under a 2-local Hamiltonian with bounded strength interactions.
## Noisy analogue simulators

Suppose we have quantum channels $T_t$, for $t \in [0, t_{max}]$ which simulate some $H \in \text{Herm}(\mathcal{H})$ with respect to $\Omega_{\text{state}}$ and $\Omega_{\text{obs}}$ up to accuracy $\varepsilon$ as in Definition 5, corresponding to encoding maps $\mathcal{E}_{\text{state}}$ and $\mathcal{E}_{\text{obs}}$.

In practice, the experimental setup will suffer from noise in the steps of state preparation, evolution, and measurement. This will correspond to noisy versions of the above maps, which we denote by $\tilde{T}_t$, $\tilde{\mathcal{E}}_{\text{state}}$, and $\tilde{\mathcal{E}}_{\text{obs}}$. For any $O \in \Omega_{\text{obs}}$, $\rho \in \Omega_{\text{state}}$, we may bound the additional error in observable expectation values incurred by the noisy maps by

$$ \begin{aligned} & |\text{tr}[\mathcal{E}_{\text{obs}}(O)(T_t \circ \mathcal{E}_{\text{state}})(\rho)] - \text{tr}[\tilde{\mathcal{E}}_{\text{obs}}(O)(\tilde{T}_t \circ \tilde{\mathcal{E}}_{\text{state}}(\rho))]| \\ &= |\text{tr}[O(\mathcal{E}_{\text{obs}}^* \circ T_t \circ \mathcal{E}_{\text{state}} - \tilde{\mathcal{E}}_{\text{obs}}^* \circ \tilde{T}_t \circ \tilde{\mathcal{E}}_{\text{state}})(\rho)]| \\ &\le \|\mathcal{E}_{\text{obs}}^* \circ T_t \circ \mathcal{E}_{\text{state}} - \tilde{\mathcal{E}}_{\text{obs}}^* \circ \tilde{T}_t \circ \tilde{\mathcal{E}}_{\text{state}}\|_{1 \to 1} \\ &\le \|\mathcal{E}_{\text{obs}}^* - \tilde{\mathcal{E}}_{\text{obs}}^*\|_{1 \to 1} + \|T_t - \tilde{T}_t\|_{1 \to 1} + \|\mathcal{E}_{\text{state}} - \tilde{\mathcal{E}}_{\text{state}}\|_{1 \to 1}, \end{aligned} $$

where $\| \cdot \|_{1 \to 1}$ denotes the one-to-one norm $\|\Lambda\|_{1 \to 1} = \sup_{\rho} \|\Lambda(\rho)\|_1$ (defined as the induced trace norm in [Wat18], for example — note that this is in particular upper bounded by the diamond norm). Hence the noisy simulator $\tilde{T}_t$ also simulates $H$ with respect to $\Omega_{\text{state}}$ and $\Omega_{\text{obs}}$, up to error

$$ \varepsilon' \le \varepsilon + \sup_t \|T_t - \tilde{T}_t\|_{1 \to 1} + \|\mathcal{E}_{\text{state}} - \tilde{\mathcal{E}}_{\text{state}}\|_{1 \to 1} + \|\mathcal{E}_{\text{obs}}^* - \tilde{\mathcal{E}}_{\text{obs}}^*\|_{1 \to 1}. $$

## Local Hamiltonian simulation in a subspace

Suppose that $H'$ is a $(\Delta, \eta, \varepsilon)$-simulation of $H$ as defined by [CMP18] (Definition 4), corresponding to encodings $\mathcal{E}_{\text{state}}$ and $\mathcal{E}_{\text{obs}}$, with the projector $Q = 0$. Here we show that the time evolution channel under $H', (\cdot) \mapsto e^{-itH'}(\cdot)e^{itH'}$ gives a simulation in our sense, Definition 5.

We make use of the following lemmas. Lemma 7 ensures that measurement and time evolution are consistent with the encodings of Definition 4, and Lemma 8 bounds the error of $(\Delta, \eta, \varepsilon)$-simulations under time evolution.

**Lemma 7** ([CMP18], Proposition 4). If $\mathcal{E}_{\text{state}}$ and $\mathcal{E}_{\text{obs}}$ are encodings as in Definition 4 and (1), then for all observables $O$ and states $\rho$ on the target system $\mathcal{H}$,

$$ \text{tr}[\mathcal{E}_{\text{obs}}(O)\mathcal{E}_{\text{state}}(\rho)] = \text{tr}[O\rho]. $$

Moreover if the encoding is standard (rank($P$) > 0 in Definition 4) then

$$ e^{-i\mathcal{E}_{\text{obs}}(H)t}\mathcal{E}_{\text{state}}(\rho)e^{i\mathcal{E}_{\text{obs}}(H)t} = \mathcal{E}_{\text{state}}(e^{-iHt}\rho e^{iHt}). $$

**Lemma 8** ([CMP18], Proposition 28). Let $H'$ be a $(\Delta, \eta, \varepsilon)$-simulation of $H$ in the sense of Definition 4 corresponding to encodings $\mathcal{E}_{\text{obs}}$, $\mathcal{E}_{\text{state}}$. If $\rho'$ is a state in the simulator system $\mathcal{H}'$ satisfying $\mathcal{E}_{\text{obs}}(\mathcal{I})\rho' = \rho'$, then for all $t$

$$ \|e^{-iH't}\rho'e^{iH't} - e^{-i\mathcal{E}_{\text{obs}}(H)t}\rho'e^{i\mathcal{E}_{\text{obs}}(H)t}\|_{1} \le 2\varepsilon t + 4\eta. $$
Combining these lemmas, we see that for any observable O and state $\rho$ on $\mathcal{H}$,

$$ 
\begin{aligned}
& \left| \operatorname{tr}[\mathcal{E}_{\text{obs}}(O)e^{-iH't}\mathcal{E}_{\text{state}}(\rho)e^{iH't}] - \operatorname{tr}[Oe^{-iHt}\rho e^{iHt}] \right| \\
& = \left| \operatorname{tr}[\mathcal{E}_{\text{obs}}(O)(e^{-iH't}\mathcal{E}_{\text{state}}(\rho)e^{iH't} - e^{-i\mathcal{E}_{\text{obs}}(H)t}\mathcal{E}_{\text{state}}(\rho)e^{i\mathcal{E}_{\text{obs}}(H)t})] \right| \\
& \le \|O\|(2\varepsilon t + 4\eta).
\end{aligned}
$$

Hence the channels $T_t : \rho' \mapsto e^{-iH't}\rho'e^{iH't}$, for $t \in [0, t_{\max}]$ simulate H in the sense of Definition 5 with respect to any $\Omega_{\text{state}}$ and $\Omega_{\text{obs}}$, up to error

$$ \varepsilon' \le 2\varepsilon t_{\max} + 4\eta. $$

This provides some consistency between existing work and our notion of simulation; we have shown that evolution under a simulator Hamiltonian in the sense of [CMP18] constitutes an analogue quantum simulator in our framework given by Definition 5.

## Short-time simulation with Lieb-Robinson bounds

One advantage of only requiring the simulation of a particular set of observables $\Omega_{\text{obs}}$ in Definition 5, as opposed to reproducing the entire physical system, is that one can take advantage of the limited spread of correlations for short-time dynamics [LR72]. The idea of exploiting Lieb-Robinson bounds to reduce necessary hardware overhead has already been considered for the study of many-body quantum states on quantum computers [KS17, BCSF21], and more recently in the setting of analogue simulators [TRC22]. We explain here how the latter fits into our framework.

Consider the case of a Hamiltonian $H_n$ on a $d$-dimensional lattice of $n$ qubits $\mathcal{H} \cong (\mathbb{C}^2)^{\otimes n}$, such that

$$ H_n = \sum_{x=1}^{n} h_x, $$

where the $h_x$ is a nearest-neighbour local interaction with $\|h_x\| \le 1$, translated to position $x$ in the lattice, so that $H_n$ is translationally invariant.

If one is only interested in simulating the finite-time dynamics of a few local observables $\Omega_{\text{obs}}$ which are contained within a small neighbourhood of the origin, starting from a state $\rho = |0\rangle\langle 0|^{\otimes n}$, then it is sufficient (up to exponentially small error) to simulate a far smaller subsystem, corresponding to the Lieb-Robinson light cone, as in Fig. 5. This situation is studied in [TRC22], in particular for the thermodynamic limit $n \to \infty$.

Let $H_m = \sum_{y=1}^m h_y$ be the simulator Hamiltonian, defined identically to $H_n$ but on a lattice of size $m < n$, $\mathcal{H}' \cong (\mathbb{C}^2)^{\otimes m}$. We encode $\rho$ and O simply by restricting them to the smaller subsystem. Then a simulation of an observable $O \in \Omega_{\text{obs}}$ up to accuracy $\varepsilon$, satisfying

$$ \left| \operatorname{tr}[Oe^{-iH_{nt}}\rho e^{iH_{nt}}] - \operatorname{tr}[\mathcal{E}_{\text{obs}}(O)e^{-iH_{mt}}\mathcal{E}_{\text{state}}(\rho)e^{iH_{mt}}] \right| \le \varepsilon, $$

can be accomplished in the large-$n$ regime for all $t \in [0, t_{\max}]$ if one takes $m = O(\log^d(1/\varepsilon) + t^d)$ (see [TRC22, Lemma 1]).
<figure><img src="image_5.png" /><figcaption>Figure 5: Simulation of a 1-dimensional spin system under a Hamiltonian $H$ for time $t$. In theory, the system extends infinitely, but to estimate the value of a local observable $O$ it is only necessary to simulate a subsystem corresponding to the Lieb-Robinson light cone.</figcaption></figure>

# 3 Modular encodings and gadgets

## 3.1 Overview

In this section, we focus on the case of a simulator channel $T_l$ given by time evolution under a local simulator Hamiltonian $H'$, which should reproduce the dynamics of the local target Hamiltonian $H = \sum_i H_i$. In light of the size-independence requirement of Definition 1, it is natural to encode each $H_i$ term separately into some term $H'_i$, but systematically doing so is a non-trivial task: we need the encoded terms to interact with each other in a way which mimics the original system.

This problem can be tackled using perturbative gadgets. Perturbative gadgets were initially introduced by [KKR06] as a means of proving QMA-completeness of the 2-local Hamiltonian problem by reduction from the 3-local case [KR03], and have since been used extensively in the field of Hamiltonian complexity theory. In this work, we especially focus on the use of gadgets for Hamiltonian locality reduction, though it should be noted that perturbative gadgets can also be used to simplify the structure of the interaction hypergraph [OT08] and in general to reduce Hamiltonians to more restrictive families of interactions [BL08, SV09, CM16]. Moreover, beyond Hamiltonian complexity-theoretic results, gadgets can be tailored to improve the performance of variational quantum algorithms [CFKE22].

In this work, we introduce a formalism which we argue encompasses any attempt at gadgetisation, in a sense which we make precise (Definition 9), in order to prove general properties of such constructions. Note that our approach, and the $(\eta, \varepsilon)$ accuracy parameters, are closely related to those used in the definitions of simulation in [CMP18] and [BH17]. We refine the approach of the latter by generalising to a potentially non-perturbative regime and by considering the feature of “combining well” with other interactions as a generic requirement for gadgets. We use these results to argue that any size-independent encoding of a Hamiltonian $H$ into another $H'$ cannot reduce the locality of interactions (for example, reducing a 3-local Hamiltonian to a 2-local Hamiltonian).

## 3.2 A general definition for gadgets

The setup is as follows: we consider a large system $\mathcal{H} = \bigotimes_{i=1}^n \mathcal{H}_i$, within which a local interaction $H \in \text{Herm}(\mathcal{H})$ acts on a subsystem of $O(1)$ sites. With the introduction of a small ancillary system $\mathcal{A}$, we aim to replace $H$ by some “gadget” $H' \in \text{Herm}(\mathcal{H} \otimes \mathcal{A})$, which acts on $O(1)$ sites in $\mathcal{H}$ and $\mathcal{A}$.

A simulator Hamiltonian in the sense of Definition 5 need not necessarily capture the entire spectrum of its target Hamiltonian. In this case, however, we are thinking of $H$ as a single interaction in
a larger system, and as such we cannot generally assume that its eigenspaces will be preserved under time evolution. Therefore, we require as a minimum that $H'$ should (when restricted to some subspace defined by a projector $P'$) approximately reproduce the full spectrum of $H$. Moreover, for $H'$ to be a useful gadget, it must combine well with other Hamiltonian terms acting on $\mathcal{H}$. That is to say, there should exist $P' \in \text{Proj}(\mathcal{H} \otimes \mathcal{A})$ such that $P'(H' + H_{\text{else}} \otimes \mathbb{I})P'$ approximates the spectrum of $H + H_{\text{else}}$, for any $H_{\text{else}} \in \text{Herm}(\mathcal{H})$ (see Fig. 6). We formalise this with the following definition.

**Definition 9** (($\zeta, \varepsilon$)-gadget property). Given a Hamiltonian $H \in \text{Herm}(\mathcal{H})$ acting on a system $\mathcal{H} = \otimes_{i=1}^n \mathcal{H}_i$, and $H' \in \text{Herm}(\mathcal{H} \otimes \mathcal{A})$ for $\mathcal{A}$ an ancillary system, we say that $(H', \mathcal{A})$ satisfies the $(\zeta, \varepsilon)$-gadget property for $H$ if there exists $P' \in \text{Proj}(\mathcal{H} \otimes \mathcal{A})$, $\tilde{P} \in \text{Proj}(\mathcal{A}) \setminus \{0\}$ such that, for any $H_{\text{else}} \in \text{Herm}(\mathcal{H})$, there exists a unitary $\tilde{U}_{H_{\text{else}}} \in \text{U}(\mathcal{H} \otimes \mathcal{A})$ with

$$ \| P'(H' + H_{\text{else}} \otimes \mathbb{I})P' - \tilde{U}_{H_{\text{else}}}((H + H_{\text{else}}) \otimes \tilde{P})\tilde{U}_{H_{\text{else}}}^{\dagger} \| \le \varepsilon + \zeta \|H_{\text{else}}\|. $$

<figure><img src="image_6.png" /><figcaption>Figure 6: An example of a mediator gadget. The (blue) 3-local interaction is replaced by a set of 2-local terms with an ancillary site. Crucially, the other (red) terms in the original Hamiltonian are unchanged, allowing the encoding to take place term-by-term.</figcaption></figure>

In other words, $(H', \mathcal{A})$ satisfies the $(\zeta, \varepsilon)$-gadget property for $H$ if, when restricted a subspace defined by $P'$, $H' + H_{\text{else}} \otimes \mathbb{I}$ approximates the spectrum of $H + H_{\text{else}}$ up to error $\varepsilon + \zeta \|H_{\text{else}}\|$. Notice that $\tilde{P}$ is almost arbitrary; its rank determines the multiplicity of each eigenvalue of $H + H_{\text{else}}$ in the simulator system, but otherwise it can be rotated by $\tilde{U}_{H_{\text{else}}}$, which rotates the eigenvectors of $(H + H_{\text{else}}) \otimes \tilde{P}$ approximately onto those of $P'(H' + H_{\text{else}} \otimes \mathbb{I})P'$.

As noted in [CMP18], there are two distinct types of gadgets used in literature:

* **Mediator gadgets**, in which ancillary qubits are inserted between logical qubits to mediate interactions, and

* **Subspace gadgets**, in which single logical qubits are encoded into several physical qubits, restricted to a two-dimensional subspace by strong interactions.

**Definition 9** encompasses the former, but not the latter. Qualitatively this is because whereas mediator gadgets replace interactions, subspace gadgets replace entire qubits, including all of the interactions they take part in. It would be possible to extend our formalism to subspace gadgets, by restricting the range of $H_{\text{else}}$ in **Definition 9** to terms which do not interact with the target qubit. We do not consider this here, however, for brevity and because subspace gadgets do not reduce the locality of interactions, which is our primary motivation for this section.

Although **Definition 9** is a natural requirement, it is not convenient to work with due to the appearance of the general $H_{\text{else}}$ acting on the entire of $\mathcal{H}$, upon which $\tilde{U}$ depends. The following alternative definition does not suffer from this problem.

**Definition 10** (($\eta, \varepsilon$)-gadget). Let $H \in \text{Herm}(\mathcal{H})$ be a Hamiltonian on a Hilbert space $\mathcal{H}$, and let $\mathcal{A}$ be an ancillary Hilbert space. For $H' \in \text{Herm}(\mathcal{H} \otimes \mathcal{A})$, we say that $(H', \mathcal{A})$ is a $(\eta, \varepsilon)$-gadget for
$H$ if there exists $P \in \mathrm{Proj}(\mathcal{A}) \setminus \{0\}$ and $U \in U(\mathcal{H} \otimes \mathcal{A})$ such that

$$ \|U - \mathbb{I}\| \le \eta, \quad \|P'H'P' - U(H \otimes P)U^\dagger\| \le \varepsilon, $$

where $P' = U(\mathbb{I} \otimes P)U^\dagger \in \mathrm{Proj}(\mathcal{H} \otimes \mathcal{A})$.

The advantage of Definition 10 is that it is stated in terms of a “local” rather than global property. Assuming that $H, H', P'$ act on only $O(1)$ sites in $\mathcal{H}$ and $\mathcal{A}$, we can without loss of generality restrict to this significantly smaller subspace to check whether $H'$ is a gadget. This is in contrast with Definition 9, which requires us to in principle consider interactions over the full $n$-site space in order to check the gadget property.

To motivate the use of Definition 10, we show that the above notions are in correspondence; things that look like gadgets are always gadgets, and vice-versa. This is formalised by the following two theorems.

**Theorem 11** (($\eta, \varepsilon$)-gadgets have the ($\zeta, \varepsilon$)-gadget property). Suppose that $(H', \mathcal{A})$ is a $(\eta, \varepsilon)$-gadget for $H$. Then $(H', \mathcal{A})$ satisfies the ($\zeta, \varepsilon$)-gadget property for $H$, where $\zeta = O(\eta)$.

(Proof in Appendix B.2.1)

**Theorem 12** (The ($\zeta, \varepsilon$)-gadget property requires a ($\eta, \varepsilon$)-gadget). Suppose that $(H', \mathcal{A})$ satisfies the ($\zeta, \varepsilon$)-gadget property for $H$, where $H, H'$, and $P'$ act on $O(1)$ sites in $\mathcal{H} = \otimes_{i=1}^n \mathcal{H}_i$. Then $(H', \mathcal{A})$ is a ($\eta, \varepsilon'$)-gadget for $H$, where $\eta = O(\varepsilon) + O(\zeta^{\frac{1}{2}})$ and $\varepsilon' = O(\varepsilon) + O(\zeta)$.

(Proof in Appendix B.2.2)

The roles of the $\eta$ and $\varepsilon$ parameters are to bound the error in the eigenvectors and eigenvalues respectively. Roughly speaking, $\eta$ quantifies how well the gadget combines with other terms, and $\varepsilon$ quantifies the spectral error of the gadget in isolation. A good gadget requires both of these parameters to be small. In Appendix A.2 we present a 3-to-2 local gadget which is an extreme case of this, with $\varepsilon = 0$ at the cost of a large $\eta$ error.

Prior work in Hamiltonian complexity theory has focused on gadgetisation in the context of ground state estimation [KR03, CM16, BH17] or simulation in a low energy subspace [CMP18]; as a result, a case of particular relevance is when $P'$ projects onto the low-energy subspace of $H'$. For $\Delta \in \mathbb{R}$, we write $P_{\le \Delta(H')}$ for the projector onto the span of the eigenvectors of $H'$ with eigenvalues in the range $(-\infty, \Delta]$.

**Definition 13** (($\Delta, \eta, \varepsilon$)-gadget). Let $H \in \mathrm{Herm}(\mathcal{H})$ be a Hamiltonian on a Hilbert space $\mathcal{H}$, and let $\mathcal{A}$ be an ancillary Hilbert space. For $H' \in \mathrm{Herm}(\mathcal{H} \otimes \mathcal{A})$, we say that $(H', \mathcal{A})$ is a ($\Delta, \eta, \varepsilon$)-gadget for $H$ if there exists $P \in \mathrm{Proj}(\mathcal{A}) \setminus \{0\}$, and $U \in U(\mathcal{H} \otimes \mathcal{A})$ such that $P_{\le \Delta(H')} = U(\mathbb{I} \otimes P)U^\dagger$, and

$$ \|U - \mathbb{I}\| \le \eta, \quad \|P_{\le \Delta(H')}H'P_{\le \Delta(H')} - U(H \otimes P)U^\dagger\| \le \varepsilon. $$

In other words, the pair $(H', \mathcal{A})$ satisfy Definition 10, in the special case where we can use $P' = P_{\le \Delta(H')}$.

Notice that Definition 13 imposes a significantly stronger requirement on $H'$ than Definition 10; a priori there is no reason to expect that there will exist any choice of $P$ and $U$ such that $P_{\le \Delta(H')} = U(\mathbb{I} \otimes P)U^\dagger$. Definitions 10 and 13 are sufficient to guarantee desirable combination properties (see Appendix A.3), and are satisfied by widely-used constructions (see Appendix A.1).

## 3.3 Energy scaling is inevitable for gadgets

Here we present the main result of the section: general locality reduction gadgets cannot exist without unfavourably scaling energies. This result holds in the most general setting of ($\eta, \varepsilon$)-gadgets
(Definition 10), and hence follows even from the relaxed $(\zeta, \varepsilon)$-gadget property of Definition 9.

**Theorem 14 (Gadget energy scaling).** Let $\mathcal{H} = (\mathbb{C}^2)^{\otimes k}$ be the space of $k = O(1)$ qubits, and let $H$ be the $k$-fold tensor product of Pauli $Z$ operators with strength $J > 0$,

$$H = J \bigotimes_{i=1}^{k} Z_i .$$

Suppose $(H', \mathcal{A})$ is a $(\eta, \varepsilon)$-gadget for $H$ for $H'$ a $k'$-local Hamiltonian, where $k' < k$.

Then, provided $\varepsilon < 2^{-k'} J$, the gadget must have energy scale $\|H'\| \ge \frac{2^{-k'} J - \varepsilon}{\eta} = \Omega(\eta^{-1})$.

(Proof in Appendix B.3)

The method of proof is simple, and very likely does not provide an optimal lower bound for $\|H'\|$, due to the lack of any dependence on $k$. We expect that such dependence should be present; any approach which iteratively lowers the locality of an interaction from $k$-local to 2-local will accumulate scalings from each round of gadgetisation, but this does not rule out a more direct approach. Existing methods to reduce locality, such as the subdivision and 3-to-2 gadgets of [OT08] (described in Appendix A.1) and the higher-order gadgets of [JF08, CFKE22], give scalings that suggest that any $k$-to-2-local gadget construction should require energies which scale exponentially in $k$. The question of whether such exponential scaling is the best possible was first raised in [BDLT08], and is still unresolved. Using the formalism introduced here, this problem can be precisely stated, and optimisation of Theorem 14 may provide a negative result. Furthermore, we expect that it may be possible to answer similar questions about gadget energy scaling in other cases, for example in simplifying the structure of an interaction graph or reducing to smaller families of interactions.

The significance of Theorem 14 is that it essentially rules out a size-independent (Definition 1) simulation of a $k$-local Hamiltonian $H$ by another $k'$-local Hamiltonian $H'$ for $k' < k$, for the following reason. Any “modular” encodings require the use of term-by-term gadgets, which must each satisfy the $(\zeta, \varepsilon)$-gadget property (Definition 9) with $\zeta, \eta = O(n^{-1})$ to guarantee that they can be combined (since the rest of the Hamiltonian will have $\|H_{else}\| = O(n)$). By Theorem 12, this requires the use of $(\eta, \varepsilon)$-gadgets (Definition 10) with $\eta = O(n^{-1/2})$, and by Theorem 14 this will require interactions which scale at least as $\Omega(n^{1/2})$.

A couple of notes on gadget energy scalings in existing work: [Bau20] gives a method to reduce the exponential or doubly-exponential scaling in perturbative Hamiltonians to polynomial scaling, and in [CN15] the authors present gadgets whose interaction strengths do not grow with accuracy. However, both cases violate size-independence (Definition 1) in other ways such as polynomial scaling in the number of simulator qubits or instead shrinking the interaction strengths.

## 3.4 Gadgets from the quantum Zeno effect

In this section, we demonstrate an alternative approach for reducing the locality of an interaction in a Hamiltonian — a task for which Theorem 14 establishes the need for energies which scale with the size of the system, when conventional gadgets are used. The construction presented here, however, uses the freedom afforded by the general simulation channel $T_t$ in Definition 5 to take advantage of an additional resource: dissipation.

We will see that, despite some impractical features, this approach offers an improvement in scalings over the conventional gadget techniques discussed earlier in the section. Additionally, this construction captures a key feature of our framework for analogue simulators given in Definition 5
in contrast with existing work: we define simulators in terms of their dynamic behaviour, rather than in terms of the properties of static Hamiltonians.

For the process we describe here, we repeatedly refer to “measurement” for conceptual simplicity when talking about probabilities, but this terminology is somewhat misleading; we do not record or use the outcome.

## Construction

Let $H \in \text{Herm}(\mathcal{H})$ be a single interaction in a many-body system, which we intend to simulate. As before, we will introduce an ancillary qubit $\mathcal{A} \cong \mathbb{C}^2$, and evolve under a Hamiltonian $H' \in \text{Herm}(\mathcal{H} \otimes \mathcal{A})$, but now we supplement the natural time evolution with regular projective measurements on the $\mathcal{A}$ system at time intervals of $\delta t$. By the quantum Zeno effect [MS77], this forces the $\mathcal{A}$ system to stay in the $|0\rangle$ state with high probability, meanwhile simulating the desired interaction on the $\mathcal{H}$ system.

The following result, Proposition 15, provides a formal construction for the measurement-based gadgets described above. Qualitatively, this result tells us that if we evolve $|\psi\rangle \otimes |0\rangle$ for time $\delta t$ under the simulator Hamiltonian $H'$, and then measure the ancillary qubit, we will obtain a ‘1’ result with probability $O((\delta t)^3)$ (corresponding to an amplitude of $O((\delta t)^{3/2})$). In the more likely case that we obtain ‘0’, the post-measurement state (on the $\mathcal{H}$ space) is $e^{-i\delta tH} |\psi\rangle$, for some new Hamiltonian $H$, up to error $O((\delta t)^2)$. By repeating this process $t/\delta t$ times, we will hence obtain a state $e^{-i\delta tH} |\psi\rangle + O(t(\delta t))$ on the $\mathcal{H}$ space if ‘0’ is measured in every round of measurement. The probability of a measurement error in this process scales as $t(\delta t)^2$, hence can be controlled provided that $\delta t = O(t^{-1/2})$.

**Proposition 15.** For a Hilbert space $\mathcal{H}$ and an ancillary qubit $\mathcal{A} = \mathbb{C}^2$, let $H' \in \text{Herm}(\mathcal{H} \otimes \mathcal{A})$ be a Hamiltonian given by

$$H' = H_{\mathbb{I}} \otimes \mathbb{I} + H_X \otimes X + H_{|1\rangle\langle 1|} \otimes |1\rangle\langle 1|,$$

for some $H_{\mathbb{I}}, H_X, H_{|1\rangle\langle 1|} \in \text{Herm}(\mathcal{H})$ depending on a small parameter $\delta t$ such that $\|H_{\mathbb{I}}\| = O(1)$, $\|H_X\| = O((\delta t)^{-1/2})$, and $\|H_{|1\rangle\langle 1|}\| = O((\delta t)^{-1})$ with $H_{|1\rangle\langle 1|}^2 = \omega^2\mathbb{I}$, $\omega = \frac{2\pi}{\delta t}$.

Then, for any $|\psi\rangle \in \mathcal{H}$,

$$e^{-i\delta tH'} (|\psi\rangle \otimes |0\rangle) = (e^{-i\delta tH} |\psi\rangle + O((\delta t)^2)) \otimes |0\rangle + O((\delta t)^{3/2}) \otimes |1\rangle,$$

where

$$H = H_{\mathbb{I}} - \omega^{-2} H_X H_{|1\rangle\langle 1|} H_X.$$

(Proof in Appendix B.5)

This provides a new 3-to-2-local gadget for Pauli strings. For example, we can set $H_{\mathbb{I}} = -Z_1$, $H_X = \sqrt{\omega/2}(Z_2 + Z_3)$, $H_{|1\rangle\langle 1|} = -\omega Z_1$; this yields a 2-local Hamiltonian $H'$ simulating the 3-local interaction $H = Z_1 \otimes Z_2 \otimes Z_3$. More generally, given three commuting Pauli strings $A_a, B_b, C_c$, we can set $H_{\mathbb{I}} = -A_a$, $H_X = \sqrt{\omega/2}(B_b+C_c)$, $H_{|1\rangle\langle 1|} = -\omega A_a$ to simulate the interaction $H = A_a \otimes B_b \otimes C_c$. This procedure may be used to simulate a $k$-local Pauli string using a ($\lceil k/3 \rceil + 1$)-local Hamiltonian.

Although Proposition 15 shows that evolution and repeated measurements under $H'$ reproduce the dynamics of $H$, it is also important to guarantee that it can be combined with other interactions, as discussed in Section 3.2. Proposition 16 provides the necessary result for this, by verifying that the conclusions of Proposition 15 also hold when an additional term $H_{\text{else}} \in \text{Herm}(\mathcal{H})$ is added to both the target and simulator Hamiltonian.
**Proposition 16.** Let $H_{else} = \sum_i h_i$ be a k-local Hamiltonian on $\mathcal{H} = \otimes_i \mathcal{H}_i$ such that $\|h_i\| = O(1)$, and whose interaction graph has a degree bounded by an $O(1)$ constant.

Introduce an ancillary qubit $\mathcal{A} = \mathbb{C}^2$, and let $H' \in \text{Herm}(\mathcal{H} \otimes \mathcal{A})$ be a Hamiltonian given by

$$H' = H_{\mathbb{I}} \otimes \mathbb{I} + H_X \otimes X + H_{|1\rangle\langle 1|} \otimes |1\rangle\langle 1|,$$

for some $H_{\mathbb{I}}$, $H_X$, $H_{|1\rangle\langle 1|} \in \text{Herm}(\mathcal{H})$ depending on a small parameter $\delta t$ such that $\|H_{\mathbb{I}}\| = O(1)$, $\|H_X\| = O((\delta t)^{-1/2})$, and $\|H_{|1\rangle\langle 1|}\| = O((\delta t)^{-1})$ with $H_{|1\rangle\langle 1|}^2 = \omega^2 \mathbb{I}$, $\omega = \frac{2\pi}{\delta t}$. Assume that $H_{\mathbb{I}}$, $H_X$, and $H_{|1\rangle\langle 1|}$ act on $O(1)$ sites in $\mathcal{H}$.

Then, for any $|\psi\rangle \in \mathcal{H}$,

$$e^{-i\delta t(H'+H_{else}\otimes\mathbb{I})}(|\psi\rangle \otimes |0\rangle) = (e^{-i\delta t(H+H_{else})} |\psi\rangle + O((\delta t)^2)) \otimes |0\rangle + O((\delta t)^{3/2}) \otimes |1\rangle,$$

where

$$H = H_{\mathbb{I}} - \omega^{-2} H_X H_{|1\rangle\langle 1|} H_X.$$

(Proof in Appendix B.5)

The significance of Proposition 16 is that the errors do not depend on the size of the system through $\|H_{else}\|$, due to bounds we place on the Trotter error in the expansion $e^{-i\delta t(H+H_{else})} \approx e^{-i\delta tH}e^{-i\delta tH_{else}}$.

## Discussion and comparison to conventional gadgets

Given the result of Proposition 16, we can now describe how the measurement gadget construction fits into our framework of analogue quantum simulation described in Definition 5.

Given a Hamiltonian $H = Z_1 \otimes Z_2 \otimes Z_3 + H_{else}$ on $n$ qubits $\mathcal{H} = (\mathbb{C}^2)^{\otimes n}$, with $H_{else} \in \text{Herm}(\mathcal{H})$ satisfying the requirements of Proposition 16, we fix some $\delta t > 0$ and define the simulator space $\mathcal{H}' = \mathcal{H} \otimes \mathcal{A}$, where $\mathcal{A} = \mathbb{C}^2$. Let $H' \in \text{Herm}(\mathcal{H}')$ be given by

$$H' = -Z_1 \otimes \mathbb{I} + \sqrt{\frac{\omega}{2}}(Z_2 + Z_3) \otimes X - \omega Z_1 \otimes |1\rangle\langle 1|,$$

where $\omega = \frac{2\pi}{\delta t}$. Define the state and observable encodings $\mathcal{E}_{\text{state}}$ and $\mathcal{E}_{\text{obs}}$ by

$$\mathcal{E}_{\text{state}}(\rho) = \rho \otimes |0\rangle\langle 0|, \quad \mathcal{E}_{\text{obs}}(O) = O \otimes \mathbb{I},$$

and define channels $E_{\delta t}, M : D(\mathcal{H}') \to D(\mathcal{H}')$ by

$$E_{\delta t}(\rho') = e^{-i\delta t(H'+H_{else}\otimes\mathbb{I})} \rho' e^{i\delta t(H'+H_{else}\otimes\mathbb{I})}, \\ M(\rho') = \text{tr}_{\mathcal{A}}[\rho'(\mathbb{I} \otimes |0\rangle\langle 0|)] \otimes |0\rangle\langle 0| + \text{tr}_{\mathcal{A}}[\rho'(\mathbb{I} \otimes |1\rangle\langle 1|)] \otimes |1\rangle\langle 1|,$$

so that $E_{\delta t}$ corresponds to evolution under the Hamiltonian $H' + H_{else}$ for time $\delta t$, and $M$ corresponds to a measurement of the $\mathcal{A}$ system. Then, for all $t$, define the time evolution channel

$$T_t = (M \circ E_{\delta t}) \circ (M \circ E_{\delta t}) \circ \dots \circ (M \circ E_{\delta t}),$$

containing $\lfloor t/\delta t \rfloor$ copies of $(M \circ E_{\delta t})$. This evolution is described by Fig. 7. The content of Proposition 16 tells us that

$$(T_t \circ \mathcal{E}_{\text{state}})(\rho) = (e^{-itH} \rho e^{itH} + O(t\delta t)) \otimes |0\rangle\langle 0| + O(t(\delta t)^2) \otimes |1\rangle\langle 1|,$$
<figure><img src="image_7.png" /><figcaption>Figure 7: Time-evolution with a measurement gadget for the simulation of an interaction H with a gadget Hamiltonian H'.</figcaption></figure>

and hence for any observable $O \in \text{Herm}(\mathcal{H})$ with $\|O\| = 1$,

$$ \text{tr}[\mathcal{E}_{\text{obs}}(T_t \circ \mathcal{E}_{\text{state}})(\rho)] = \text{tr}[Oe^{-itH}\rho e^{itH}] + O(t\delta t). $$

The channels $T_t$ therefore simulate $H$ (in the sense of Definition 5) with respect to any states $\Omega_{\text{state}}$ and normalised observables $\Omega_{\text{obs}}$, up to accuracy $\epsilon > 0$ and maximum time $t_{\text{max}}$, provided that one chooses $\delta t = O(\epsilon t_{\text{max}}^{-1})$. Therefore we require interaction strengths and measurement frequency which scale as $J = O(\epsilon^{-1}t_{\text{max}})$ — note that this does not depend on $n$, the size of the system.

We can compare these scalings with those obtained if we were to use conventional gadgets. Suppose we have a $(\eta, \epsilon)$-gadget in the sense of Definition 10, with $\eta = O(n^{-1}\epsilon)$ to ensure an absolute error of $O(\epsilon)$ when combined with a Hamiltonian of order $n$, comparable with the above construction. By Theorem 14, this must involve energy scalings of $J = \Omega(\epsilon^{-1}n)$ (and even without Theorem 14, a low-energy $(\Delta, \eta, \epsilon)$-gadget as in Definition 13 would require energies scaling as $\Omega(n)$ to ensure that unwanted states are sufficiently penalised). In fact, this is likely not the optimal bound; the best known 3-to-2 gadget construction (see Appendix A.1) requires energy scales of $O(\epsilon^{-3}+\eta^{-3})$, which in this case would require interaction strengths scaling as $J = O((\epsilon^{-1}n)^3)$. Even if the system size is restricted via Lieb-Robinson bounds as described in Section 2.2 to set $n = O(\log^d(1/\epsilon) + t_{\text{max}}^d)$ (where $d$ is the dimension of the system), the measurement-based gadget still provides an improvement.

Despite this advantage, the measurement gadget construction involves repeated instantaneous decoherence of the ancillary qubit at precise time intervals without disturbing the rest of the system, and may still require large (albeit non-scaling) interaction strengths. Moreover, if $N_{\text{gad}}$ such gadgets were used in parallel, we expect (though do not calculate here) that an additional overhead of at least $\delta t = O((t_{\text{max}}N_{\text{gad}})^{-1/2})$ would be necessary to control the probability of measuring a 1 at any of the ancillary sites. Nonetheless, the construction provides a marked improvement in scalings over existing gadgets for a single 3-local term in a Hamiltonian, and gives some positive clues as to the ways in which simulators might take advantage of more general possibilities for channels allowed by Definition 5.

## 3.5 Outlook on universality for analogue quantum simulators

In analogy to universal quantum computation, one may consider the notion of universality for quantum simulators. Roughly speaking: given a family $\mathcal{F} = \{H_m\}$ of Hamiltonians, when is $\mathcal{F}$ universal, in some sense of being able to simulate the dynamics of all other Hamiltonians?
Precise definitions of universality have been provided by [CMP18, ZA21]. These, and subsequent
works [PB20, PM21, KPBC20, KPBC22], have characterised several such universal families $\mathcal{F}$.
The proofs of these results often involve perturbative gadgets (as in Definition 13) as a central
ingredient for reducing general Hamiltonians to simple families. Constructions can also make
use of sophisticated techniques involving mapping between analogue and digital problems [ZA21,
KPBC20], which incur interaction strengths scaling (at least polynomially) with $n$.

As discussed in Section 3.3, the use of gadgets may in fact necessitate unfavourable energy scalings, which creates a barrier for Hamiltonian locality reduction in the size-independent regime. Although our gadget construction with intermediate measurements in Section 3.4 demonstrates how the more general simulation procedures afforded by our notion of simulation (Definition 5) may be leveraged to provide some improvement, this still falls short of completely size-independent simulation as in Definition 1. Further limitations for practical Hamiltonian simplification procedures come from [AZ18], in which the authors show that the reduction of local Hamiltonians with dense interaction hypergraphs to simulator Hamiltonians with sparse interaction hypergraphs is generally impossible without introducing scalings in interaction strengths. This result holds even with their weaker requirement of gap-simulation, in which the simulator needs only to replicate the ground and first excited energies of the system.

These results suggest that we cannot expect to talk about a simple class of practical analogue
quantum simulators which can mimic the physics of all other Hamiltonians in any sense resembling
previous universality results. In fact, we argue that this should not be expected; if a notion of
simulation renders almost all simple Hamiltonian families universal, then it is unlikely to capture
the actual capabilities of experimentally realistic simulators. On the other hand, our definition of
simulation leads to a new notion of universality, not phrased in terms of the static classification of
Hamiltonians but rather the dynamics of observable quantities. Such a notion could take advantage
of the generality afforded by our definition of simulation channels, as well as take into account the
constraints of size-independence for realisable systems. We expect that in this regime a resource
theory for simulation should arise, relating the capabilities of simulators with a preorder analogously
to the theory of SLOCC state transformations [DVC00, WDGC13] or tensor network representation
[CLS$^+$23].

# 4 Conclusion

In this work, we have presented a new definition for analogue quantum simulators, Definition 5, which provides a general theoretical setting to study experimentally realisable simulations. We argue that a requirement of scalability (Definition 1) is necessary for this task. Our framework emphasises the broad dynamical possibilities of experiments, and we have shown how this may be leveraged to provide improvements on other notions of simulation in Section 2.2 and Section 3.4. Our work stands in contrast to existing literature (reviewed in Section 1.4) which has typically focused on analogue simulation in the context of Hamiltonian complexity theory, using perturbative gadget constructions to make general statements about universality. To describe this, we have produced general definitions for gadgets (Definition 10 and Definition 13) motivated by a natural requirement (Definition 9), and with these in hand we have shown that gadgets require unavoidable scalings of interaction strengths in the setting of locality reduction in Theorem 14, posing an obstacle for experimental realisations. We argue that a more general notion of simulation (such as Definition 5), tempered by scalability requirements, is necessary to provide a clear description of the computational power and possibilities of analogue quantum simulators.
Acknowledgements

We acknowledge financial support from the Novo Nordisk Foundation (Grant No. NNF20OC0059939 'Quantum for Life'), the European Research Council (ERC Grant Agreement No. 81876) and VILLUM FONDEN via the QMATH Centre of Excellence (Grant No.10059). I.D. gratefully acknowledges Harriet Apel for generously offering insights and guidance during fruitful discussions at the early stages of this work. I.D. also thanks QMATH, especially M.C., A.W., and Lise Nielsen, for their hospitality during his research visit to KU. Finally, thanks is due to Prof. Adam Bouland, without whom I.D.'s visit would not have been possible.

References

[ABC$^{+21}$] Ehud Altman, Kenneth R. Brown, Giuseppe Carleo, Lincoln D. Carr, Eugene Demler, Cheng Chin, Brian DeMarco, Sophia E. Economou, Mark A. Eriksson, Kai-Mei C. Fu, et al. Quantum simulators: Architectures and opportunities. *PRX Quantum*, 2(1):017003, 2021.

[AC22] Harriet Apel and Toby Cubitt. A mathematical framework for quantum Hamiltonian simulation and duality. *arXiv preprint arXiv:2208.11941*, 2022.

[ALGTS$^{+19}$] Javier Argüello-Luengo, Alejandro González-Tudela, Tao Shi, Peter Zoller, and J. Ignacio Cirac. Analogue quantum chemistry simulation. *Nature*, 574(7777):215-218, 2019.

[AZ18] Dorit Aharonov and Leo Zhou. Hamiltonian sparsification and gap-simulations. *arXiv preprint arXiv:1804.11084*, 2018.

[Bau20] Johannes Bausch. Perturbation gadgets: Arbitrary energy scales from a single strong interaction. In *Annales Henri Poincaré*, volume 21, pages 81-114. Springer, 2020.

[BBMC20] Bela Bauer, Sergey Bravyi, Mario Motta, and Garnet Kin-Lic Chan. Quantum algorithms for quantum chemistry and quantum materials science. *Chemical Reviews*, 120(22):12685-12717, 2020.

[BCC$^{+15}$] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Simulating Hamiltonian dynamics with a truncated Taylor series. *Physical Review Letters*, 114(9):090502, 2015.

[BCK15] Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In *2015 IEEE 56th Annual Symposium on Foundations of Computer Science*, pages 792-809. IEEE, 2015.

[BCSF21] Johannes Borregaard, Matthias Christandl, and Daniel Stilck França. Noise-robust exploration of many-body quantum states on near-term quantum devices. *npj Quantum Information*, 7(1):45, 2021.

[BDL11] Sergey Bravyi, David P. DiVincenzo, and Daniel Loss. Schrieffer-Wolff transformation for quantum many-body systems. *Annals of Physics*, 326(10):2793-2826, 2011.

[BDLT08] Sergey Bravyi, David P. DiVincenzo, Daniel Loss, and Barbara M. Terhal. Quantum simulation of many-body Hamiltonians using perturbation theory with bounded-strength interactions. *Physical Review Letters*, 101(7):070503, 2008.

[BH17] Sergey Bravyi and Matthew Hastings. On complexity of the quantum Ising model. *Communications in Mathematical Physics*, 349(1):1-45, 2017.

[Bha13] Rajendra Bhatia. *Matrix analysis*, volume 169. Springer Science and Business Media, 2013.

[BL08] Jacob D. Biamonte and Peter J. Love. Realizable Hamiltonians for universal adiabatic quantum computers. *Physical Review A*, 78(1):012352, 2008.

[BLK$^{+15}$] Rami Barends, L. Lamata, Julian Kelly, L. García-Álvarez, Austin G. Fowler, A. Megrant, Evan Jeffrey, Ted C. White, Daniel Sank, Josh Y. Mutus, et al. Digital quantum simulation of fermionic models with a superconducting circuit. *Nature Communications*, 6(1):7654, 2015.

[CAB$^{+21}$] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. Variational quantum algorithms. *Nature Reviews Physics*, 3(9):625-644, 2021.
[CFKE22] Simon Cichy, Paul K. Faehrmann, Sumeet Khatri, and Jens Eisert. A perturbative gadget for delaying the onset of barren plateaus in variational quantum algorithms. arXiv preprint arXiv:2210.03099, 2022.

[CLS$^{+23}$] Matthias Christandl, Vladimir Lysikov, Vincent Steffan, Albert H. Werner, and Freek Witteveen. The resource theory of tensor networks. arXiv preprint arXiv:2307.07394, 2023.

[CM16] Toby Cubitt and Ashley Montanaro. Complexity classification of local Hamiltonian problems. SIAM Journal on Computing, 45(2):268-316, 2016.

[CMN$^{+18}$] Andrew M. Childs, Dmitri Maslov, Yunseong Nam, Neil J. Ross, and Yuan Su. Toward the first quantum simulation with quantum speedup. Proceedings of the National Academy of Sciences, 115(38):9456-9461, 2018.

[CMP18] Toby S. Cubitt, Ashley Montanaro, and Stephen Piddock. Universal quantum Hamiltonians. Proceedings of the National Academy of Sciences, 115(38):9497-9502, 2018.

[CN15] Yudong Cao and Daniel Nagaj. Perturbative gadgets without strong interactions. Quantum Information and Computation, 15(13-14):1197-1222, 2015.

[CST$^{+21}$] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu. Theory of Trotter error with commutator scaling. Physical Review X, 11(1):011020, 2021.

[CZ12] J. Ignacio Cirac and Peter Zoller. Goals and opportunities in quantum simulation. Nature Physics, 8(4):264-266, 2012.

[DBK$^{+22}$] Andrew J. Daley, Immanuel Bloch, Christian Kokail, Stuart Flannigan, Natalie Pearson, Matthias Troyer, and Peter Zoller. Practical quantum advantage in quantum simulation. Nature, 607(7920):667-676, 2022.

[DiV00] David P. DiVincenzo. The physical implementation of quantum computation. Fortschritte der Physik: Progress of Physics, 48(9-11):771-783, 2000.

[DK69] Chandler Davis and William M. Kahan. Some new bounds on perturbation of subspaces. Bulletin of the American Mathematical Society, 75(4):863-868, 1969.

[DK70] Chandler Davis and William Morton Kahan. The rotation of eigenvectors by a perturbation. III. SIAM Journal on Numerical Analysis, 7(1):1-46, 1970.

[DVC00] Wolfgang Dür, Guifre Vidal, and J. Ignacio Cirac. Three qubits can be entangled in two inequivalent ways. Physical Review A, 62(6):062314, 2000.

[EWL$^{+21}$] Sepehr Ebadi, Tout T. Wang, Harry Levine, Alexander Keesling, Giulia Semeghini, Ahmed Omran, Dolev Bluvstein, Rhine Samajdar, Hannes Pichler, Wen Wei Ho, et al. Quantum phases of matter on a 256-atom programmable quantum simulator. Nature, 595(7866):227-232, 2021.

[Fey82] Richard P. Feynman. Simulating physics with computers. International Journal of Theoretical Physics, 21(6-7):467-488, 1982.

[GAN14] Iulia M. Georgescu, Sahel Ashhab, and Franco Nori. Quantum simulation. Reviews of Modern Physics, 86(1):153, 2014.

[GB17] Christian Gross and Immanuel Bloch. Quantum simulations with ultracold atoms in optical lattices. Science, 357(6355):995-1001, 2017.

[GI09] Daniel Gottesman and Sandy Irani. The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 95-104. IEEE, 2009.

[GKS76] Vittorio Gorini, Andrzej Kossakowski, and Ennackal Chandy George Sudarshan. Completely positive dynamical semigroups of n-level systems. Journal of Mathematical Physics, 17(5):821-825, 1976.

[GTHC$^{+15}$] Alejandro González-Tudela, C.-L. Hung, Darrick E. Chang, J. Ignacio Cirac, and H. J. Kimble. Sub-wavelength vacuum lattices and atom-atom interactions in two-dimensional photonic crystals. Nature Photonics, 9(5):320-325, 2015.

[HMR$^{+18}$] Cornelius Hempel, Christine Maier, Jonathan Romero, Jarrod McClean, Thomas Monz, Heng Shen, Petar Jurcevic, Ben P. Lanyon, Peter Love, Ryan Babbush, et al. Quantum chemistry calculations on a trapped-ion quantum simulator. Physical Review X, 8(3):031022, 2018.
[HNN13] Sean Hallgren, Daniel Nagaj, and Sandeep Narayanaswami. The local Hamiltonian problem on a line with eight states is QMA-complete. *Quantum Information and Computation*, 13(9-10):721-750, 2013.

[HWBT15] Matthew B. Hastings, Dave Wecker, Bela Bauer, and Matthias Troyer. Improving quantum algorithms for quantum chemistry. *Quantum Information and Computation*, 15(1-2):1-21, 2015.

[JF08] Stephen P. Jordan and Edward Farhi. Perturbative gadgets at arbitrary orders. *Physical Review A*, 77(6):062329, 2008.

[JZ05] Dieter Jaksch and Peter Zoller. The cold atom Hubbard toolbox. *Annals of Physics*, 315(1):52-79, 2005.

[Kit97] A. Yu Kitaev. Quantum computations: algorithms and error correction. *Russian Mathematical Surveys*, 52(6):1191, 1997.

[KKR06] Julia Kempe, Alexei Kitaev, and Oded Regev. The complexity of the local Hamiltonian problem. *SIAM Journal on Computing*, 35(5):1070-1097, 2006.

[KPBC20] Tamara Kohler, Stephen Piddock, Johannes Bausch, and Toby Cubitt. Translationally invariant universal quantum Hamiltonians in 1D. In *Annales Henri Poincaré*, pages 1-32. Springer, 2020.

[KPBC22] Tamara Kohler, Stephen Piddock, Johannes Bausch, and Toby Cubitt. General conditions for universality of quantum Hamiltonians. *PRX Quantum*, 3(1):010308, 2022.

[KR03] Julia Kempe and Oded Regev. 3-local Hamiltonian is QMA-complete. *Quantum Information and Computation*, 3(3):258-264, 2003.

[KS17] Isaac H. Kim and Brian Swingle. Robust entanglement renormalization on a noisy quantum computer. *arXiv preprint arXiv:1711.07500*, 2017.

[KSV02] Alexei Yu Kitaev, Alexander Shen, and Mikhail N. Vyalyi. *Classical and quantum computation*. American Mathematical Society, 2002.

[LC17] Guang Hao Low and Isaac L. Chuang. Optimal Hamiltonian simulation by quantum signal processing. *Physical Review Letters*, 118(1):010501, 2017.

[LC19] Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by qubitization. *Quantum*, 3:163, 2019.

[LHN$^{+11}$] Ben P. Lanyon, Cornelius Hempel, Daniel Nigg, Markus Müller, Rene Gerritsma, F. Zähringer, Philipp Schindler, Julio T. Barreiro, Markus Rambach, Gerhard Kirchmair, et al. Universal digital quantum simulation with trapped ions. *Science*, 334(6052):57-61, 2011.

[Lin76] Goran Lindblad. On the generators of quantum dynamical semigroups. *Communications in Mathematical Physics*, 48:119-130, 1976.

[Llo96] Seth Lloyd. Universal quantum simulators. *Science*, 273(5278):1073-1078, 1996.

[LR72] Elliott H. Lieb and Derek W. Robinson. The finite group velocity of quantum spin systems. *Communications in Mathematical Physics*, 28:251-257, 1972.

[MC23] Daniel Malz and J. Ignacio Cirac. Few-body analog quantum simulation with Rydberg-dressed atoms in optical lattices. *PRX Quantum*, 4(2):020301, 2023.

[MRBAG16] Jarrod R. McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik. The theory of variational hybrid quantum-classical algorithms. *New Journal of Physics*, 18(2):023023, 2016.

[MS77] Baidyanath Misra and E. C. George Sudarshan. The Zeno's paradox in quantum theory. *Journal of Mathematical Physics*, 18(4):756-763, 1977.

[MW21] M. Morgado and S. Whitlock. Quantum simulation and computing with Rydberg-interacting qubits. *AVS Quantum Science*, 3(2), 2021.

[NA16] Changsuk Noh and Dimitris G. Angelakis. Quantum simulations and many-body physics with light. *Reports on Progress in Physics*, 80(1):016401, 2016.

[NCP$^{+20}$] Yunseong Nam, Jwo-Sy Chen, Neal C. Pisenti, Kenneth Wright, Conor Delaney, Dmitri Maslov, Kenneth R. Brown, Stewart Allen, Jason M. Amini, Joel Apisdorf, et al. Ground-state energy estimation of the water molecule on a trapped-ion quantum computer. *npj Quantum Information*, 6(1):33, 2020.
[OT08] Roberto Oliveira and Barbara M. Terhal. The complexity of quantum spin systems on a two-dimensional square lattice. *Quantum Information and Computation*, 8(10):900-924, 2008.

[PB20] Stephen Piddock and Johannes Bausch. Universal translationally-invariant Hamiltonians. *arXiv preprint arXiv:2001.08050*, 2020.

[PCK$^{+}$21] Avikar Periwal, Eric S. Cooper, Philipp Kunkel, Julian F. Wienand, Emily J. Davis, and Monika Schleier-Smith. Programmable interactions and emergent geometry in an array of atom clouds. *Nature*, 600(7890):630-635, 2021.

[PM17] Stephen Piddock and Ashley Montanaro. The complexity of antiferromagnetic interactions and 2D lattices. *Quantum Information and Computation*, 17(7-8):636-672, 2017.

[PM21] Stephen Piddock and Ashley Montanaro. Universal qudit Hamiltonians. *Communications in Mathematical Physics*, 382:721-771, 2021.

[Pre18] John Preskill. Quantum computing in the NISQ era and beyond. *Quantum*, 2:79, 2018.

[SV09] Norbert Schuch and Frank Verstraete. Computational complexity of interacting electrons and fundamental limitations of density functional theory. *Nature physics*, 5(10):732-735, 2009.

[TRC22] Rahul Trivedi, Adrian Franco Rubio, and J. Ignacio Cirac. Quantum advantage and stability to errors in analogue quantum simulators. *arXiv preprint arXiv:2212.04924*, 2022.

[VWC09] Frank Verstraete, Michael M. Wolf, and J. Ignacio Cirac. Quantum computation and quantum-state engineering driven by dissipation. *Nature Physics*, 5(9):633-636, 2009.

[Wat18] John Watrous. *The Theory of Quantum Information*. Cambridge University Press, 2018.

[WDGC13] Michael Walter, Brent Doran, David Gross, and Matthias Christandl. Entanglement polytopes: multiparticle entanglement from single-particle information. *Science*, 340(6137):1205-1208, 2013.

[WW22] Henrik Wilming and Albert H. Werner. Lieb-Robinson bounds imply locality of interactions. *Physical Review B*, 105(12):125101, 2022.

[ZA21] Leo Zhou and Dorit Aharonov. Strongly universal Hamiltonian simulators. *arXiv preprint arXiv:2102.02991*, 2021.

# A General gadgets

## A.1 Existing constructions

Lemmas 4-7 in [BH17] can be naturally adapted to give several constructions for $(\Delta, \eta, \varepsilon)$ gadgets, which we use to demonstrate that Definition 10 encompasses commonly-used techniques. In the following we take $\mathcal{H}' = \mathcal{H} \otimes \mathcal{A}$, and $\mathcal{A} \cong \mathbb{C}^2$. For $V$ an operator on $\mathcal{H}'$ we write it in block-diagonal form with respect to the basis of $\mathcal{A}$ as

$$V = \begin{pmatrix} V_{00} & V_{01} \\ V_{10} & V_{11} \end{pmatrix},$$

where, for instance, $V_{00} = (\mathbb{I} \otimes \langle 0 |)V(\mathbb{I} \otimes | 0 \rangle)$.

**Lemma 17** (First-order gadgets, adapted from [BH17]). Suppose $H \in \text{Herm}(\mathcal{H})$ and $V \in \text{Herm}(\mathcal{H}')$ are such that

$$\|H - V_{00}\| \le \frac{\varepsilon}{2}.$$

Then $H' = \Delta H_0 + V$ defines a $(O(\Delta), \eta, \varepsilon)$-gadget for $H$, where $H_0 = \mathbb{I} \otimes |1\rangle\langle 1|$, provided that $\Delta \ge O(\varepsilon^{-1}\|V\|^2 + \eta^{-1}\|V\|)$.
<figure><img src="image_8.png" /><figcaption>Figure 8: Interaction hypergraphs of a 2-system interaction before (left) and after (right) the use of the subdivision gadget.</figcaption></figure>

**Lemma 18** (Second-order gadgets, adapted from [BH17]). Let $H \in \text{Herm}(\mathcal{H})$, and suppose $V^{(1)}, V^{(0)} \in \text{Herm}(\mathcal{H}')$ are such that $\|V^{(1)}\|, \|V^{(0)}\| \le \Lambda$, $V_{10}^{(0)} = V_{01}^{(0)} = V_{00}^{(1)} = 0$, and

$$ \|H - V_{00}^{(0)} + V_{01}^{(1)}V_{10}^{(1)}\| \le \frac{\varepsilon}{2}. $$

Then $H' = \Delta H_0 + \Delta^{\frac{1}{2}}V^{(1)} + V^{(0)}$ is a $(O(\Delta), \eta, \varepsilon)$-gadget for $H$, where $H_0 = \mathbb{I} \otimes |1\rangle\langle 1|$, if

$$ \Delta \ge O(\varepsilon^{-2}\Lambda^6 + \eta^{-2}\Lambda^2). $$

**Lemma 19** (Third-order gadgets, adapted from [BH17]). Let $H \in \text{Herm}(\mathcal{H})$, and suppose $V^{(2)}, V^{(1)}, V^{(0)} \in \text{Herm}(\mathcal{H}')$ are such that $\|V^{(2)}\|, \|V^{(1)}\|, \|V^{(0)}\| \le \Lambda$, $V_{10}^{(1)} = V_{01}^{(1)} = V_{00}^{(0)} = 0$, $V_{01}^{(0)} = 0$,

$$ \|H - V_{00}^{(0)} - V_{01}^{(2)}V_{11}^{(2)}V_{10}^{(2)}\| \le \frac{\varepsilon}{2}, \quad \text{and} \quad V_{00}^{(1)} = V_{01}^{(2)}V_{10}^{(2)}. $$

Then $H' = \Delta H_0 + \Delta^{\frac{2}{3}}V^{(2)} + \Delta^{\frac{1}{3}}V^{(1)} + V^{(0)}$ is a $(O(\Delta), \eta, \varepsilon)$-gadget for $H$, where $H_0 = \mathbb{I} \otimes |1\rangle\langle 1|$, if

$$ \Delta \ge O(\varepsilon^{-3}\Lambda^{12} + \eta^{-3}\Lambda^3). $$

We illustrate the application of these lemmas to our definition with the following ubiquitous gadgets from [OT08]:

## Subdivision gadget

Given a target Hamiltonian $H = A \otimes B \in \text{Herm}(\mathcal{H}_A \otimes \mathcal{H}_B)$, the subdivision gadget on $\mathcal{H}_A \otimes \mathcal{H}_B \otimes \mathcal{H}_C$ (where $\mathcal{H}_C \cong \mathbb{C}^2$) is defined by

$$ H' = \Delta H_0 + \Delta^{\frac{1}{2}}V^{(1)} + V^{(0)}, $$

where

$$ \begin{align*} H_0 &= \mathbb{I} \otimes \mathbb{I} \otimes |1\rangle\langle 1|, \\ V^{(1)} &= \frac{1}{\sqrt{2}}(-A \otimes \mathbb{I} + \mathbb{I} \otimes B) \otimes X, \\ V^{(0)} &= \frac{1}{2}(A^2 \otimes \mathbb{I} + \mathbb{I} \otimes B^2) \otimes \mathbb{I}. \end{align*} $$

Then by Lemma 18 we see that, for sufficiently large $\Delta$, $(H', \mathcal{H}_C)$ defines a $(O(\Delta), \eta, \varepsilon)$-gadget for $H$ (see Fig. 8).
<figure><img src="image_9.png" /><figcaption>Figure 9: Interaction hypergraphs of a 3-system interaction before (left) and after (right) the use of the 3-to-2 gadget.</figcaption></figure>

### 3-to-2 gadget

Given a target Hamiltonian $H = A \otimes B \otimes C \in \text{Herm}(\mathcal{H}_A \otimes \mathcal{H}_B \otimes \mathcal{H}_C)$, the 3-to-2 local gadget on $\mathcal{H}_A \otimes \mathcal{H}_B \otimes \mathcal{H}_C \otimes \mathcal{H}_D$ (where $\mathcal{H}_D \cong \mathbb{C}^2$) is defined by

$$H' = \Delta H_0 + \Delta^{\frac{2}{3}} V^{(2)} + \Delta^{\frac{1}{3}} V^{(1)} + V^{(0)},$$

where

$$ \begin{aligned} H_0 &= \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes |1\rangle\langle 1|, \\ V^{(2)} &= \frac{1}{\sqrt{2}}(-A \otimes \mathbb{I} + \mathbb{I} \otimes B) \otimes \mathbb{I} \otimes X - \mathbb{I} \otimes \mathbb{I} \otimes C \otimes |1\rangle\langle 1|, \\ V^{(1)} &= \frac{1}{2}(-A \otimes \mathbb{I} + \mathbb{I} \otimes B)^2 \otimes \mathbb{I} \otimes \mathbb{I}, \\ V^{(0)} &= \frac{1}{2}(A^2 \otimes \mathbb{I} + \mathbb{I} \otimes B^2) \otimes C \otimes \mathbb{I}. \end{aligned} $$

By Lemma 19 we see that, for sufficiently large $\Delta$, $(H', \mathcal{H}_D)$ defines a $(O(\Delta), \eta, \varepsilon)$-gadget for $H$ (see Fig. 9).

### A.2 "Exact" 3-to-2 gadget

We provide the following example to illustrate the importance of the $\eta$ parameter as a quantifier of how well a gadget combines with other terms.

Let $H = A \otimes B \otimes C \in \text{Herm}((\mathbb{C}^2)^{\otimes 3})$ be a 3-qubit interaction, and diagonalise $A, B$, and $C$ as

$$A = \lambda_0^A |0\rangle\langle 0| + \lambda_1^A |1\rangle\langle 1|, \quad B = \lambda_0^B |0\rangle\langle 0| + \lambda_1^B |1\rangle\langle 1|, \quad C = \lambda_0^C |0\rangle\langle 0| + \lambda_1^C |1\rangle\langle 1|.$$

Let $H' \in \text{Herm}((\mathbb{C}^2)^{\otimes 4})$ be defined as

$$ \begin{aligned} H' = & \lambda_0^B (A - \lambda_0^A \mathbb{I}) \otimes \mathbb{I} \otimes \mathbb{I} \otimes C \\ & + \lambda_1^B \mathbb{I} \otimes (A - \lambda_0^A \mathbb{I}) \otimes \mathbb{I} \otimes C \\ & + \lambda_0^A \mathbb{I} \otimes \mathbb{I} \otimes B \otimes C, \end{aligned} $$

and let $P' \in \text{Proj}((\mathbb{C}^2)^{\otimes 4})$ be

$$P' = (\mathbb{I} \otimes |0\rangle\langle 0| \otimes |0\rangle\langle 0| + |0\rangle\langle 0| \otimes \mathbb{I} \otimes |1\rangle\langle 1|) \otimes \mathbb{I}.$$

Then in fact the restriction of $H'$ to the image of $P'$ exactly reproduces the spectrum of $H$. This hence defines a 3-to-2 $(\eta, 0)$-gadget — or a $(\Delta, \eta, 0)$-gadget, if one adds a term of the form $O(\Delta)(\mathbb{I} - P')$ to $H'$. The caveat is that this gadget has a large $\eta$ parameter, and hence it does not combine well with other interactions. For instance, in Definition 10 we might take $P = |0\rangle\langle 0| \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I}$, and $U = (\mathbb{F} \otimes |0\rangle\langle 0| + \mathbb{I} \otimes \mathbb{I} \otimes |1\rangle\langle 1|) \otimes \mathbb{I}$, where $\mathbb{F}$ is the two-qubit swapping operator. This gives $\eta = 2$.
<figure><img src="image_10.png" /><figcaption>Figure 10: Effect of the “exact” 3-to-2 gadget on an interaction hypergraph. The (blue) 3-local interaction between A, B, and C is replaced by a series of (blue) 2-local interactions, where the A site has been split into two sites A₁ and A₂. However after this process, the 2-local interaction (red) between A and another qubit E is replaced by two 3-local interactions between E, A₁, B and E, A₂, B. Compare this with Fig. 9, for which additional interactions on qubit A will remain on qubit A of the gadgetised Hamiltonian without any need for adjustment.</figcaption></figure>

The construction of $H'$ can be thought of as splitting the A qubit into two qubits (see Fig. 10), and controlling whether the first or second qubit is excited depending on the value of the B qubit. Therefore, if the full Hamiltonian contains another interaction term which acts on the A site in $H$, then the locality of this term will be increased under the gadgetisation procedure. Such a gadget cannot be used to systematically reduce the locality of a Hamiltonian with many interactions.

### A.3 Combining gadgets

The following results show that gadgets satisfying Definition 10 or Definition 13 can be systematically combined as desired. Our techniques and proofs extend prior work [BDLT08, OT08, PM17], using the convenient formalism of the direct rotation [BDL11]. The scalings of the parameters $\eta', \varepsilon'$ are not necessarily optimal, though they sufficient for application to the subdivision and 3-to-2 gadget constructions exhibited in Appendix A.1.

We summarise the setup below, which will be used throughout the following results.

**Setup 20.** Let $H \in \text{Herm}(\mathcal{H})$ be a Hamiltonian on $n$ sites, $\mathcal{H} = \otimes_{i=1}^n \mathcal{H}_i$. Assume $H = \sum_{i=1}^N H_i$, where $N = O(n)$, such that each $H_i$ acts on at most $k = O(1)$ of the sites $\mathcal{H}_i$, and each site participates in at most $d = O(1)$ interactions. Assume also that $H$ has bounded interaction strengths, that is, $\|H_i\| \le J$ for all $i$.

In the below propositions we consider gadgets $(H'_i, \mathcal{A}_i)$ for $H_i$, with $U_i, P_i$, and $P'_i$ defined as in Definition 10, for each $i$. Assume that $\mathcal{A}_i$ consists of $O(1)$ ancillary sites and that $H'_i$ is a local Hamiltonian consisting of $O(1)$ interactions, such that

$$ \|H'_i\| \le J', \quad \|(\mathbb{I} \otimes P_i)H'_i(\mathbb{I} \otimes P_i^{\perp})\| \le J'_O. $$

Firstly, we state the main result: that gadgets as in Definition 10 may be systematically combined to produce new gadgets.

**Proposition 21** (Parallel $(\eta, \varepsilon)$-gadget combination). Let $H = \sum_i H_i$ be as in Setup 20, and suppose that each $(H'_i, \mathcal{A}_i)$ defines a $(\eta, \varepsilon)$-gadget for $H_i$.

Define

$$ H' = \sum_i H'_i \in \text{Herm} (\mathcal{H} \otimes (\otimes_i \mathcal{A}_i)). $$

Then $(H', \otimes_i \mathcal{A}_i)$ is a $(\eta', \varepsilon')$-gadget for $H$, where

$$ \varepsilon' = O(n\varepsilon + n\eta J + n\eta^3 J'_O + n\eta^4 J'), \quad \eta' = O(n\eta). $$

(Proof in Appendix B.4.1)
For completeness, we also prove a similar result that $(\Delta, \eta, \varepsilon)$-gadgets can be combined to create a new $(\Delta', \eta', \varepsilon')$-gadget. It follows from Proposition 21 that the combination of many $(\Delta, \eta, \varepsilon)$-gadgets defines a $(\eta', \varepsilon')$-gadget, however it still remains to show that the projector $P'$ in the sense of Definition 10 may be taken as a low-energy projector $P_{\le \Delta'(H')}$.

**Proposition 22** (Parallel $(\Delta, \eta, \varepsilon)$-gadget combination). Let $H = \sum_i H_i$ be as in Setup 20, and suppose that each $(H'_i, A_i)$ defines a $(\Delta, \eta, \varepsilon)$-gadget for $H_i$, where

$$ \Delta \ge \frac{\|H\| + J + N(\varepsilon + 2J\eta)}{\frac{1}{4} - 2\eta} = O(nJ), \qquad (4) $$

and assume that the scaling of $\eta$ with $n$ is bounded as

$$ \eta = o(n^{-\frac{1}{2}}), \qquad (5) $$

and moreover that, for large $J'$,

$$ n\varepsilon + n\eta J + n\eta^3 J'_O + n\eta^4 J' = o(J'), \quad J' = O(\Delta). \qquad (6) $$

Define

$$ H' = \sum_i H'_i \in \mathrm{Herm}(\mathcal{H} \otimes (\otimes_i A_i)). $$

Then $(H', \otimes_i A_i)$ is a $(\Delta', \eta', \varepsilon')$-gadget for $H$, where

$$ \Delta' = \frac{1}{2}\Delta, \quad \varepsilon' = O(n\varepsilon + n\eta J + n\eta^3 J'_O + n\eta^4 J'), \quad \eta' = O(n\eta). $$

(Proof in Appendix B.4.2)

For an example of how these conditions can be satisfied, consider the case of combining many of the 3-to-2 gadgets described in Appendix A.1. Setting $J = 1$ for convenience, we have $J' = \Theta(\Delta)$, $J'_O = \Theta(\Delta^{2/3})$, and $\varepsilon, \eta = O(\Delta^{-1/3})$. The errors $\varepsilon'$ and $\eta'$ both grow as $O(n\Delta^{-1/3})$, so a good gadget will require $\Delta = \Omega(n^3)$. A direct computation verifies that this condition also ensures that (4-6) are satisfied. Hence reduction from a 3-local to 2-local Hamiltonian in this way requires interaction strengths to scale as $n^3$.

To combine $(\Delta, \eta, \varepsilon)$ gadgets using Proposition 22 requires the unappealing conditions of (4)-(5), which explicitly require the gadget energies to scale with $n$. In fact, as noted by [BDLT08], the regime of bounded-strength interactions does still allow approximation of the ground state energy of $H$ — the caveat being that the errors are extensive. Below is a generalisation of their main result.

**Theorem 23** (Ground state energy estimation with $(\Delta, \eta, \varepsilon)$-gadgets, generalising [BDLT08], Theorem 1). Let $H = \sum_i H_i$ be as in Setup 20, and suppose that each $(H'_i, A_i)$ defines a $(\Delta, \eta, \varepsilon)$-gadget for $H_i$.

Define

$$ H' = \sum_i H'_i \in \mathrm{Herm}(\mathcal{H} \otimes (\otimes_i A_i)). $$

Then the ground state energies of $H$ and $H'$ satisfy

$$ |\lambda_0(H) - \lambda_0(H')| = O(n\varepsilon + n\eta J + n\eta^3 J'_O + n\eta^4 J'). $$

(Proof in Appendix B.4.3)
# B Proofs

## B.1 Qutrit-to-qubit energy scaling

Here we prove Proposition 6. The idea is simple: by encoding a qutrit into a set of qubits, we must end up with an “unused” state in the qubit system, since the encoding cannot be surjective by dimension counting. Since the $(\Delta, \eta, \varepsilon)$ simulation requires all simulated states to lie in the low-energy subspace of the simulator, this implies that the unused qubit states must lie in the high-energy (above $\Delta$) subspace.

In the proof below, we start with the encoded ground state $\rho_0$, and construct a state $\rho_1$ which differs only from $\rho_0$ only in one set of qubits in which it is in such an “unused” state. The similarity of the states and their differences in energies lead to the requirement for strong interactions.

In this proof, and subsequent sections, we make frequent use of the following standard result from matrix analysis (see for instance [Bha13, Corollary III.2.6]).

**Lemma 24** (Weyl's Perturbation Theorem). Let $A, B \in \text{Herm}(\mathcal{H})$ be Hermitian matrices, with spectra $\lambda_0 \le \lambda_1 \le \dots$ and $\mu_0 \le \mu_1 \le \dots$ respectively. Then

$$ \max_j |\lambda_j - \mu_j| \le \|A - B\|. $$

*Proof of Proposition 6.* Write $\mathcal{H} = \bigotimes_{i=1}^n \mathcal{H}_i$, where $\mathcal{H}_i = \mathbb{C}^3$ is a single qutrit site. By Definition 4, we have two encodings $\mathcal{E}_{\text{obs}}$ and $\tilde{\mathcal{E}}_{\text{obs}}$ of the form (using that $H$ is real to set $Q = 0$ without loss of generality)

$$ \mathcal{E}_{\text{obs}}(M) = V(M \otimes P)V^{\dagger}, \quad \tilde{\mathcal{E}}_{\text{obs}}(M) = \tilde{V}(M \otimes P)\tilde{V}^{\dagger}, $$

where $P$ is a projector on the ancillary space $\mathcal{A}$, and $V, \tilde{V}$ are both isometries $\mathcal{H} \otimes \mathcal{A} \to \mathcal{H}'$. These encodings satisfy the properties:

* $\mathcal{E}_{\text{obs}}$ is a local encoding, in the sense that $\mathcal{A} = \bigotimes_{i=1}^n \mathcal{A}_i$ and $V = \bigotimes_{i=1}^n V_i$ where $V_i: \mathcal{H}_i \otimes \mathcal{A}_i \to \mathcal{H}_i'$. Here we write $\mathcal{H}_i' \cong (\mathbb{C}^2)^{\otimes m_i}$ for the set of $m_i$ qubits into which qutrit $i$ is encoded. Note $\sum_i m_i = m$.

* $\tilde{\mathcal{E}}_{\text{obs}}$ satisfies

$$ \tilde{\mathcal{E}}_{\text{obs}}(\mathbb{I}) = \tilde{V}(\mathbb{I} \otimes P)\tilde{V}^{\dagger} = P_{\le \Delta(H_n')}, $$

where $P_{\le \Delta(H_n')}$ is the low-energy (below $\Delta$) projector for $H_n'$, and

$$ \|P_{\le \Delta(H_n')} H_n' P_{\le \Delta(H_n')} - \tilde{\mathcal{E}}_{\text{obs}}(H_n)\| \le \varepsilon. \quad (7) $$

* $\mathcal{E}_{\text{obs}}$ and $\tilde{\mathcal{E}}_{\text{obs}}$ are close, in the sense that

$$ \|V - \tilde{V}\| \le \eta. $$

Now we define a state $\tau \in \text{span}(P)$ and define a state encoding (as in (1))

$$ \tilde{\mathcal{E}}_{\text{state}}(\rho) = \tilde{V}(\rho \otimes \tau)\tilde{V}^{\dagger}. $$

Let $\rho_0 = \tilde{\mathcal{E}}_{\text{state}}(|\downarrow\rangle\langle\downarrow|^{\otimes n})$ be the encoded ground state of $H_n$, which by definition satisfies

$$ P_{\le \Delta(H_n')} \rho_0 = \rho_0, \quad \tilde{\mathcal{E}}_{\text{obs}}(H_n) \rho_0 = 0. $$
Hence we can bound the energy of $\rho_0$ under $H'_n$ by

$$
\begin{align*}
\operatorname{tr}[H'_n \rho_0] &= \operatorname{tr}[P_{\le \Delta(H'_n)} H'_n P_{\le \Delta(H'_n)} \rho_0] \\
&= \operatorname{tr}[(P_{\le \Delta(H'_n)} H'_n P_{\le \Delta(H'_n)} - \tilde{\mathcal{E}}_{\operatorname{obs}}(H_n)) \rho_0] \\
&\le \| P_{\le \Delta(H'_n)} H'_n P_{\le \Delta(H'_n)} - \tilde{\mathcal{E}}_{\operatorname{obs}}(H_n) \| \\
&\le \varepsilon. \tag{8}
\end{align*}
$$

Now without loss of generality we assume that $m_1 = \min_i m_i$. Notice that $V_1 : \mathcal{H}_1 \otimes \mathcal{A}_1 \to \mathcal{H}'_1$
cannot be surjective, since

$$
\dim(\mathcal{H}_1 \otimes \mathcal{A}_1) = 3 \dim \mathcal{A}_1 \neq 2^{m_1}.
$$

We can therefore choose some pure state $\psi = |\psi\rangle\langle\psi|$ in $\mathcal{H}'_1$ which is orthogonal to the image of $V_1$, and define

$$
\rho_1 = \psi \otimes \operatorname{tr}_1[\rho_0] \in \operatorname{Lin}(\mathcal{H}'),
$$

Where tr₁ denotes the partial trace over the H'₁ system. This satisfies V†ρ₁ = ρ₁V = 0, so we have

$$
\begin{align*}
\operatorname{tr}[P_{\le \Delta(H'_n)} \rho_1] &= \operatorname{tr}[(\mathbb{I} \otimes P) \tilde{V}^\dagger \rho_1 \tilde{V}] \\
&\le \operatorname{tr}[\tilde{V}^\dagger \rho_1 \tilde{V}] \\
&= \operatorname{tr}[(\tilde{V} - V)^\dagger \rho_1 (\tilde{V} - V)] \\
&\le \|(\tilde{V} - V)(\tilde{V} - V)^\dagger\| \\
&\le \eta^2,
\end{align*}
$$

from which we deduce that

$$
\operatorname{tr}[H'_n \rho_1] \ge \Delta \operatorname{tr}[(\mathbb{I} - P_{\le \Delta(H'_n)}) \rho_1] - \varepsilon \operatorname{tr}[P_{\le \Delta(H'_n)} \rho_1] \ge \Delta(1 - \eta^2) - \varepsilon \eta^2,
$$

using that the smallest eigenvalue of $H'_n$ is at least $-\varepsilon$, by (7) and Lemma 24. Therefore, using (8),

$$
\operatorname{tr}[H'_n(\rho_1 - \rho_0)] \ge \Delta(1 - \eta^2) - \varepsilon(1 + \eta^2). \quad (9)
$$

On the other hand, by expanding $H'_n$ we can write

$$
\operatorname{tr}[H'_n(\rho_1 - \rho_0)] = \sum_{j=1}^{K} \operatorname{tr}[h'_j(\rho_1 - \rho_0)]. \qquad (10)
$$

Notice that if $h'_j$ acts trivially on $\mathcal{H}'_1$, that is $h'_j = \mathbb{I}_1 \otimes \tilde{h}_j$, then

$$
\begin{align*}
\operatorname{tr}[h'_j(\rho_1 - \rho_0)] &= \operatorname{tr}[(\mathbb{I}_1 \otimes \tilde{h}_j)(\psi \otimes \operatorname{tr}_1 \rho_0 - \rho_0)] \\
&= \operatorname{tr}_1[\psi] \operatorname{tr}_{2,3,...}[\tilde{h}_j \operatorname{tr}_1[\rho_0]] - \operatorname{tr}[(\mathbb{I} \otimes \tilde{h}_j)\rho_0] \\
&= 0.
\end{align*}
$$

Hence the only non-zero contributions to (10) come from $j$ in the set

$$
I_1 = \{1 \le j \le K \mid h'_j \text{ acts non-trivially on } \mathcal{H}'_1\}.
$$

So (10) can be bounded by

$$
\operatorname{tr}[H'_n(\rho_1 - \rho_0)] = \sum_{j \in I_1} \operatorname{tr}[h'_j(\rho_1 - \rho_0)] \le 2|I_1| \max_{j \in I_1} \|h'_j\|, \quad (11)
$$

using the Hölder inequality for Schatten p-norms.
Now notice that, since the largest eigenvalue of $H_n$ is $n$, and the encoding $\tilde{\mathcal{E}}_{\text{obs}}$ preserves spectra, we have

$$ \|\tilde{\mathcal{E}}_{\text{obs}}(H_n)\| = \|H_n\| = n, $$

so by (7) and Lemma 24

$$ \|P_{\le \Delta(H'_n)} H'_n P_{\le \Delta(H'_n)}\| \ge n - \varepsilon. $$

Hence, by the definition of $P_{\le \Delta(H'_n)}$, we must have $\Delta > n - \varepsilon$. Combining this fact with (9) and (11), we deduce that

$$ \max_{j \in I_1} \|h'_j\| > \frac{1}{2|I_1|} ((n - \varepsilon)(1 - \eta^2) - \varepsilon(1 + \eta^2)). $$

Finally, note that $m_1 \le m/n = O(n^\alpha)$ and $|I_1| \le dm_1$, so for large $n$ we have the desired scaling

$$ \max_{j \in I_1} \|h'_j\| \ge \Omega(n^{1-\alpha}(1-\eta^2)). $$

<figure><img src="image_11.png" /></figure>

## B.2 Gadget characterisation

In this section, we give the proofs of Theorems 11 and 12. The former is quite simple, but the latter requires several preparatory lemmas. In particular, we will make heavy use of the direct rotation — for a detailed introduction see [BDL11]. We summarise the basic definitions and properties here without proof.

### The direct rotation

Consider two states $|\psi\rangle$, $|\phi\rangle$ lying in some Hilbert space $\mathcal{H} \cong \mathbb{C}^N$. There are many unitary matrices $U \in U(\mathcal{H})$ which rotate between these states (that is, $U|\psi\rangle = |\phi\rangle$), but a particularly natural choice is the unitary $U_{\psi \to \phi}$ which rotates only within the subspace spanned by $|\psi\rangle$ and $|\phi\rangle$. Defining the reflections $R_{\psi} = \mathbb{I} - 2|\psi\rangle\langle\psi|$ and $R_{\phi} = \mathbb{I} - 2|\phi\rangle\langle\phi|$, we can write

$$ U_{\psi \to \phi} = \sqrt{R_{\phi} R_{\psi}}, $$

assuming it is well-defined. This is the direct rotation from $|\psi\rangle$ to $|\phi\rangle$.

This construction can be generalised to rotations between subspaces:

**Definition 25 (Direct rotation).** Let $\mathcal{P}$ and $\mathcal{Q}$ be linear subspaces of equal dimension corresponding to orthogonal projectors $P$ and $Q$ respectively. Define

$$ R_{\mathcal{P}} = \mathbb{I} - 2P, \quad R_{\mathcal{Q}} = \mathbb{I} - 2Q, $$

then direct rotation between $\mathcal{P}$ and $\mathcal{Q}$ is

$$ U_{\mathcal{P} \to \mathcal{Q}} = \sqrt{R_{\mathcal{Q}} R_{\mathcal{P}}}, $$

where the square root is taken with a branch cut along the negative axis and such that $\sqrt{1} = 1$. This is well-defined whenever $\|P - Q\| < 1$.

Then $U_{\mathcal{P} \to \mathcal{Q}}$ satisfies

$$ U_{\mathcal{P} \to \mathcal{Q}} P U_{\mathcal{P} \to \mathcal{Q}}^{\dagger} = Q. $$

Moreover, as shown in [BDL11], the direct rotation may be written in terms of its generator: an anti-Hermitian operator $S = -S^{\dagger}$ which can be chosen so that $U_{\mathcal{P} \to \mathcal{Q}} = e^S$, with $\|S\| < \pi/2$ and
which is off-diagonal with respect to both P and Q:

$$PSP = (\mathbb{I} - P)S(\mathbb{I} - P) = QSQ = (\mathbb{I} - Q)S(\mathbb{I} - Q) = 0.$$

Notice that, writing $S = i \operatorname{diag}(\theta_1, \theta_2, \dots, \theta_n)$ for $\theta_j \in (-\pi/2, \pi/2)$, we have

$$\|U_{P \to Q} - \mathbb{I}\| = \max_j |2 \sin(\theta_j/2)|, \quad \|S\| = \max_j |\theta_j|,$$

and hence

$$\|S\| \le \frac{\pi}{2\sqrt{2}} \|U_{P \to Q} - \mathbb{I}\|. \qquad (12)$$

### B.2.1 The gadget property from gadgets

*Proof of Theorem 11.* This follows directly from the definition, since for any $H_{else} \in \operatorname{Herm}(\mathcal{H})$, we have

$$\|P'(H' + H_{else} \otimes \mathbb{I})P' - U((H + H_{else}) \otimes P)U^{\dagger}\| \\ \le \|P'H'P' - U(H \otimes P)U^{\dagger}\| + \|P'(H_{else} \otimes \mathbb{I})P' - U(H_{else} \otimes P)U^{\dagger}\|.$$

The first term is bounded by $\varepsilon$ by definition, and the second term can be bounded using

$$\|P'(H_{else} \otimes \mathbb{I})P' - U(H_{else} \otimes P)U^{\dagger}\| \\ = \|(\mathbb{I} \otimes P)U^{\dagger}(H_{else} \otimes \mathbb{I})U(\mathbb{I} \otimes P) - H_{else} \otimes P\| \\ \le 2\eta\|H_{else}\|.$$

Hence Definition 9 is satisfied, putting $\tilde{P} = P$ and $\tilde{U}_{H_{else}} := U$ for all $H_{else}$.

### B.2.2 Gadgets from the gadget property

The proof of Theorem 12 requires Lemma 26, a basic linear algebra fact which we prove here for convenience. Two projectors P and Q commute if and only if they are simultaneously diagonalisable, in which case PQP is also a projector. This lemma says that this is also true in the approximate setting: $[P, Q]$ is small if and only if PQP is close to some projector $\tilde{P}$.

**Lemma 26.** Let $P, Q \in \operatorname{Proj}(\mathcal{H})$ be projectors, and define

$$f(P, Q) := \min_{\tilde{P} \in \operatorname{Proj}(\mathcal{H})} \|PQP - \tilde{P}\|.$$

Then

$$\|[P, Q]\| = \sqrt{f(P, Q) - f(P, Q)^2}.$$

*Proof of Lemma 26.* Write P and Q in the block-diagonal basis of P, so that

$$P = \begin{pmatrix} \mathbb{I} & 0 \\ 0 & 0 \end{pmatrix}, \quad Q = \begin{pmatrix} A & B \\ B^{\dagger} & C \end{pmatrix},$$

for some matrices A, B, C. The requirement $Q \in \operatorname{Proj}(\mathcal{H})$ implies that $BB^{\dagger} = A(\mathbb{I} - A)$. We have

$$PQP = \begin{pmatrix} A & 0 \\ 0 & 0 \end{pmatrix}.$$
Let {$\lambda_j$}$_j$ be the eigenvalues of A; notice that these satisfy $0 \le \lambda_j \le 1$, since $0 \le PQP \le Q$. Then $f(P, Q)$ is given by

$$f(P, Q) = \max_j \left( \min\{|\lambda_j|, |1 - \lambda_j|\} \right). \qquad (13)$$

To see why (13) holds, note that the upper bound on $f$ follows by constructing $\tilde{P}$ to have the same eigenvectors as $PQP$, but with each eigenvalue replaced by either 0 or 1 depending on which is closer. The lower bound follows from Lemma 24.

Now we can compute

$$-[P, Q]^2 = \begin{pmatrix} BB^\dagger & 0 \\ 0 & B^\dagger B \end{pmatrix},$$

hence

$$\|[P, Q]\|^2 = \|[P, Q]^2\| = \|BB^\dagger\| = \|A(I - A)\| = \max_j |\lambda_j||1 - \lambda_j|. \qquad (14)$$

Note that the maximising $j$ in (13) and (14) must be the same (the functions $\min\{|\lambda|, |1 - \lambda|\}$ and $|\lambda||1 - \lambda|$ are both maximised by the $\lambda_j$ closest to $1/2$), hence we can deduce

$$\|[P, Q]\|^2 = f(P, Q)(1 - f(P, Q)),$$

which gives the result.

In order to obtain the correct unitary $U$ in Definition 10, the proof of Theorem 12 requires constructing rotations between eigenspaces of different operators. The Davis-Kahan $\sin \theta$ theorem below provides a bound on the size of these rotations. This is also used in the proof of Proposition 22.

**Lemma 27** (Davis-Kahan $\sin \theta$ theorem [DK69]). Let $A, B \in \text{Herm}(\mathcal{H})$, and take $P_A, P_B \in \text{Proj}(\mathcal{H})$ projectors of equal rank which block-diagonalise $A$ and $B$ respectively, so that

$$A = P_A A P_A + P_A^\perp A P_A^\perp, \quad B = P_B B P_B + P_B^\perp B P_B^\perp.$$

Assume $\alpha, \beta \in \mathbb{R}$ and $\lambda_{\text{gap}}$ are such that

$$\text{spec}(A|_{P_A \mathcal{H}}) \subset [\alpha, \beta], \quad \text{spec}(B|_{P_B^\perp \mathcal{H}}) \subset \mathbb{R} \setminus (\alpha - \lambda_{\text{gap}}, \beta + \lambda_{\text{gap}}).$$

Then the direct rotation $U \in \text{U}(\mathcal{H})$ from $P_A$ to $P_B$ satisfies

$$\|U - I\| \le \frac{\sqrt{2}}{\lambda_{\text{gap}}} \|(B - A)P_A\|.$$

*Proof of Lemma 27.* The statement found in [DK69] is phrased in terms of a matrix $\Theta_0 = \text{diag}(\theta_1, \theta_2, \dots, \theta_n)$, where the eigenvalues (possibly excluding some 1's) of $U$ are given by $e^{i\theta_j}$ and $\pi/2 \ge \theta_1 \ge \theta_2 \ge \dots \ge \theta_n$. Specifically, the authors give the following result:

$$\lambda_{\text{gap}} \| \sin \Theta_0 \| \le \|(B - A)P_A\|.$$

To recover our restatement of the theorem, we use the identity $|1 - e^{i\theta}| = |2\sin(\theta/2)|$ to deduce that

$$\|U - I\| = |2 \sin(\theta_1/2)| \le \sqrt{2} |\sin \theta_1| = \sqrt{2} \|\sin \Theta_0\|.$$

The following lemmas from [BDLT08] are used extensively in the rest of the gadget proofs. They provide bounds on a series expansion of $e^S He^{-S}$, for $S$ small and anti-Hermitian, in particular
showing that

$$e^S H e^{-S} = H + [S, H] + \frac{1}{2!}[S, [S, H]] + \frac{1}{3!}[S, [S, [S, H]]] + \dots$$

**Lemma 28** (Lemma 1 from [BDLT08]). Let $S$ be an anti-Hermitian operator. Define a superoperator $\mathrm{ad}_S$ such that $\mathrm{ad}_S(X) = [S, X]$, and let $\mathrm{ad}_S^k$ be the $k$-fold composition of $\mathrm{ad}_S$, with $\mathrm{ad}_S^0(X) = X$. For any operator $H$ define $r_0(H) = \|e^S H e^{-S}\| = \|H\|$, $r_1(H) = \|e^S H e^{-S} - H\|$, and

$$r_k(H) = \|e^S H e^{-S} - \sum_{p=0}^{k-1} \frac{1}{p!} \mathrm{ad}_S^p(H)\|, \quad k \ge 2.$$

Then for all $k \ge 0$ one has

$$r_k(H) \le \frac{1}{k!} \|\mathrm{ad}_S^k(H)\|.$$

**Lemma 29** (Lemma 2 from [BDLT08]). Let $S = \sum_i S_i$ and $H = \sum_j H_j$ be any $O(1)$-local operators acting on $n$ qubits with interaction strengths $J_S$ and $J_H$ respectively (i.e. $\|S_i\| \le J_S$ and $\|H_j\| \le J_H$ for all $i$ and $j$). Let each qubit be acted on non-trivially by $O(1)$ terms in both $S$ and $H$. Then, for any $k = O(1)$,

$$\| \mathrm{ad}_S^k(H) \| = O(n J_S^k J_H).$$

These lemmas provide us with the necessary tools to prove Theorem 12.

*Proof of Theorem 12.* The idea of the proof is as follows.

By Definition 9, we have

$$\|P'(H' + H_{\text{else}} \otimes \mathbb{I})P' - \tilde{U}_{H_{\text{else}}}((H + H_{\text{else}}) \otimes \tilde{P})\tilde{U}_{H_{\text{else}}}^{\dagger}\| \le \varepsilon + \zeta \|H_{\text{else}}\|, \quad (15)$$

for any $H_{\text{else}} \in \text{Herm}(\mathcal{H})$.

1. First we consider (15) the case where $H_{\text{else}}$ dominates the expression, and argue that that $P'$ is “almost” a projector $\mathbb{I} \otimes P$ on $\mathcal{A}$.

2. Next, by setting $H_{\text{else}} = 0$ in (15), we observe that $P'H'P'$ has approximately the same spectrum as $H \otimes P$.

3. By setting $H_{\text{else}} = -H$ in (15), we argue that $P'H'P' \approx H \otimes P$.

4. Using steps 2 and 3, and Lemma 27, we construct a rotation $U$ such that $\|P'H'P' - U(H \otimes P)U^{\dagger}\| \le \varepsilon$, by inductively rotating each eigenspace.

Here we start step 1. Assume that $\|H_{\text{else}}\| = 1$, and let $\lambda > 0$. Then putting $H_{\text{else}} \mapsto \lambda H_{\text{else}}$ in (15) yields

$$\|P'(H_{\text{else}} \otimes \mathbb{I})P' - \tilde{U}_{\lambda H_{\text{else}}} (H_{\text{else}} \otimes \tilde{P}) \tilde{U}_{\lambda H_{\text{else}}}^{\dagger}\| \le \zeta + O(\lambda^{-1}),$$

for large $\lambda$, which in particular, by Lemma 24, implies that $P'(H_{\text{else}} \otimes \mathbb{I})P'$ has the same spectrum as $H_{\text{else}} \otimes \tilde{P}$, up to error $\zeta$. (That is, the $k$th smallest eigenvalue, counted with multiplicity, of $P'(H_{\text{else}} \otimes \mathbb{I})P'$, differs from that of $H_{\text{else}} \otimes \tilde{P}$ by an absolute error of at most $\zeta$.)

In particular, if $H_{\text{else}} = Q \in \text{Proj}(\mathcal{H})$ is a projection, then so is $P'(Q \otimes \mathbb{I})P'$ (up to spectral error $\zeta$). Hence by Lemma 26, we have

$$\|[P', Q \otimes \mathbb{I}]\| \le \sqrt{\zeta}.$$

Without loss of generality we may assume that $\dim \mathcal{H} = K = O(1)$, by disregarding all the systems on which $H$, $H'$, and $P'$ do not act. So by writing $H_{\text{else}}$ as a linear combination of at most $K$ projections, we have

$$\|[P', H_{\text{else}} \otimes \mathbb{I}]\| \le \pi K \sqrt{\zeta},$$
for all $H_{else} \in \text{Herm}(\mathcal{H})$ with $\|H_{else}\| \le \pi$.

Therefore, for any $V \in \text{U}(\mathcal{H})$, we can write $V = e^{iH_{else}}$ for some $H_{else}$ as above, and then by Lemma 28,

$$ \|(V \otimes \mathbb{I})P'(V^\dagger \otimes \mathbb{I}) - P'\| \le \pi K \sqrt{\zeta}. $$

Integrating over all $V \in \text{U}(\mathcal{H})$ using the Haar measure (normalised with $\int dV = 1$) yields

$$ \left\| \int dV (V \otimes \mathbb{I}) P'(V^\dagger \otimes \mathbb{I}) - P' \right\| \le \pi K \sqrt{\zeta}, $$

but

$$ \int dV (V \otimes \mathbb{I}) P'(V^\dagger \otimes \mathbb{I}) = K^{-1} \mathbb{I}_{\mathcal{H}} \otimes \text{tr}_{\mathcal{H}}[P'], $$

hence

$$ \|P' - \mathbb{I}_{\mathcal{H}} \otimes K^{-1} \text{tr}_{\mathcal{H}}[P']\| \le \pi K \sqrt{\zeta}. $$

In particular, this implies that $K^{-1} \text{tr}_{\mathcal{H}}[P']$ has spectrum in $[-\pi K \sqrt{\zeta}, \pi K \sqrt{\zeta}] \cup [1 - \pi K \sqrt{\zeta}, 1 + \pi K \sqrt{\zeta}]$ (where for sufficiently small $\zeta$ there will be a gap), so there exists a projector $P \in \text{Proj}(\mathcal{A})$ such that

$$ \|P' - \mathbb{I} \otimes P\| \le \pi K \sqrt{\zeta}. $$

Now we can apply Lemma 27, using $A = P_A = P'$, $B = P_B = \mathbb{I} \otimes P$, and $\lambda_{gap} = 1$. Then for $\zeta$ small enough, the direct rotation $W$ from $\mathbb{I} \otimes P$ to $P'$ satisfies

$$ P' = W(\mathbb{I} \otimes P)W^{\dagger}, \quad \|W - \mathbb{I}\| \le \sqrt{2\pi K \sqrt{\zeta}}, \qquad (16) $$

which completes step 1. Without loss of generality we can now adjust the $\tilde{U}_{H_{else}}$ so that $\tilde{P} = P$. Hence for all $H_{else} \in \text{Herm}(\mathcal{H})$ we have

$$ \|P'(H' + H_{else})P' - \tilde{U}_{H_{else}}((H + H_{else}) \otimes P)\tilde{U}_{H_{else}}^{\dagger}\| \le \varepsilon + \zeta \|H_{else}\|. $$

With the above expression, we can begin steps 2 and 3. Putting $H_{else} = 0$, this becomes

$$ \|P'H'P' - \tilde{U}(0)(H \otimes P)\tilde{U}^{\dagger}(0)\| \le \varepsilon, \qquad (17) $$

and putting $H_{else} = -H$ we have

$$ \|P'H'P' - P'(H \otimes \mathbb{I})P'\| \le \varepsilon + \zeta \|H\|. \qquad (18) $$

Moreover, by (16) we can bound

$$ \begin{aligned} \|P'(H \otimes \mathbb{I})P' - H \otimes P\| &= \|W(\mathbb{I} \otimes P)W^{\dagger}(H \otimes \mathbb{I})W(\mathbb{I} \otimes P)W^{\dagger} - H \otimes P\| \\ &= \|(W - \mathbb{I})(\mathbb{I} \otimes P)W^{\dagger}(H \otimes \mathbb{I})W(\mathbb{I} \otimes P)W^{\dagger} \\ &\quad + (\mathbb{I} \otimes P)(W^{\dagger} - \mathbb{I})(H \otimes \mathbb{I})W(\mathbb{I} \otimes P)W^{\dagger} \\ &\quad + (H \otimes P)(W - \mathbb{I})(\mathbb{I} \otimes P)W^{\dagger} \\ &\quad + (H \otimes P)(W^{\dagger} - \mathbb{I})\| \\ &\le 4\|H\| \cdot \|W - \mathbb{I}\| \\ &\le 4\sqrt{2\pi K \sqrt{\zeta}}\|H\|. \end{aligned} \qquad (19) $$

Combining (18) and (19), we complete step 3:

$$ \|P'H'P' - H \otimes P\| \le \varepsilon + (\zeta + 4\sqrt{2\pi K \sqrt{\zeta}})\|H\| := \delta. \qquad (20) $$

Now we begin step 4. Let $H^{(0)} = H \otimes P$. Write the eigenvalues of this operator as $\{\lambda_k\}_{k=1}^{M+1}$, where
$\lambda_1 = 0$ and $0 < \lambda_2 < \dots < \lambda_{M+1}$ are the $M$ distinct eigenvalues of $H$. If $H$ has any non-positive eigenvalues, then we shift both $H$ and $H'$ by a $O(1)$ factor of the identity for the duration of the proof; notice that Definition 9 then still holds up to a redefined $\varepsilon$ which does not affect the conclusions of this theorem. We define

$$ \lambda_{\text{gap}} = \min_{j \neq k} |\lambda_j - \lambda_k|, $$

which is $O(1)$ since $H$ acts on $O(1)$ sites, and does not scale with $\eta$ or $\varepsilon$. Let $\mathcal{P}_k$ be the eigenspace of $H^{(0)}$ corresponding to $\lambda_k$.

We also diagonalise $P'H'P'$ — see Fig. 11. By (17) and Weyl's inequality we can write the eigenvalues as $\{\mu_k^{(i_k)}\}$ such that

$$ |\mu_k^{(i_k)} - \lambda_k| \le \varepsilon, \quad \text{for all } i_k, \text{ and for all } k. $$

Let $\mathcal{P}'_k$ be the eigenspace of $P'H'P'$ corresponding to the eigenvalues $\{\mu_k^{(i_k)}\}_{i_k}$, which by (17) satisfies $\dim \mathcal{P}'_k = \dim \mathcal{P}_k$ for $\varepsilon$ sufficiently small. Note that for $j \neq k$ we have

$$ |\mu_j^{(i_j)} - \lambda_k| \ge \lambda_{\text{gap}} - \varepsilon. $$

We aim to construct a unitary operator which rotates all of the $\mathcal{P}_i$ onto the $\mathcal{P}'_i$ eigenspaces. We do this by induction, defining $W^{(k)}$ to be a unitary operator which performs these rotations for $i = 1, \dots, k$. Moreover the define $H^{(k)} = W^{(k)}H^{(0)}(W^{(k)})^\dagger$ to be the version of $H \otimes P$ whose first $k$ eigenspaces have been rotated in this way. We will use bounds on the direct rotation provided by Lemma 27; we will see that the direct rotations are be well-defined for sufficiently small $\eta$ and $\varepsilon$.

The inductive construction we use will bound the rotations by $\|W^{(k)} - \mathbb{I}\| \le \omega_k$, where

$$ \omega_k = \frac{\delta}{2\|H\|} \left( \left[ 1 + \frac{2\sqrt{2}\|H\|}{\lambda_{\text{gap}} - \varepsilon} \right]^k - 1 \right). $$

<figure><img src="image_12.png" /><figcaption>Figure 11: The degenerate eigenvalues of $H \otimes P$ are approximated by eigenvalues of $P'H'P'$ up to error $\varepsilon$, corresponding to eigenspaces $\mathcal{P}'_i$. We construct a unitary operator which rotates the eigenspaces $\mathcal{P}_i$ onto the $\mathcal{P}'_i$</figcaption></figure>

We now inductively define the $H^{(k)} \in \text{Herm}(\mathcal{H} \otimes \mathcal{A})$ and $W^{(k)} \in \text{U}(\mathcal{H} \otimes \mathcal{A})$ as described above. For the base case, we see that clearly $H^{(0)}$ satisfies the conditions with the trivial $W^{(0)} = \mathbb{I}$.
For the inductive step, suppose we are given $H^{(k-1)}$ and $W^{(k-1)}$. Notice that

$$ \| P' H' P' - H^{(k-1)} \| \le \delta + 2\omega_{k-1} \| H \|, \qquad (21) $$

using (20) and the bound $\|W^{(k-1)} - \mathbb{I}\| \le \omega_{k-1}$. Hence, applying Lemma 27 to $(P'H'P')|_{\oplus_{j \ge k} \mathcal{P}'_j}$, and $H^{(k-1)}|_{\oplus_{j \ge k} \mathcal{P}'_j}$, we may construct the direct rotation $V^{(k)}$ on $\oplus_{j \ge k} \mathcal{P}'_j$ which maps from $W^{(k-1)}\mathcal{P}_k(W^{(k-1)})^\dagger$ to $\mathcal{P}'_k$, and which satisfies

$$ \begin{aligned} \|V^{(k)} - \mathbb{I}\| &\le \frac{\sqrt{2}}{\lambda_{\text{gap}} - \varepsilon} \|(P'H'P')|_{\oplus_{j \ge k} \mathcal{P}'_j} - (H^{(k-1)})|_{\oplus_{j \ge k} \mathcal{P}'_j} \| \\ &\le \frac{\sqrt{2}}{\lambda_{\text{gap}} - \varepsilon} (\delta + 2\omega_{k-1} \|H\|) . \end{aligned} $$

For the above step, it is necessary to verify that the direct rotation is well-defined. If it were not, then there would be a nonzero vector $|\psi\rangle \in W^{(k-1)}\mathcal{P}(W^{(k-1)})^\dagger \cap (\mathcal{P}'_k)^\perp$. Then, by the definition of these subspaces,

$$ \langle \psi | P' H' P' | \psi \rangle \ge \lambda_{k+1} - \varepsilon \ge \lambda_k + (\lambda_{\text{gap}} - \varepsilon) , \quad \langle \psi | H^{(k-1)} | \psi \rangle = \lambda_k , $$

which would imply that

$$ \| P' H' P' - H^{(k-1)} \| \ge \lambda_{\text{gap}} - \varepsilon . $$

By (21), this is prohibited for sufficiently small $\eta$ and $\varepsilon$ — so we can safely assume that the direct rotation is well-defined.

Now we can let

$$ W^{(k)} = (\mathbb{I}_{\oplus_{j<k} \mathcal{P}'_j} \oplus V^{(k)}) W^{(k-1)} , $$

and

$$ H^{(k)} = W^{(k)} H^{(0)} (W^{(k)})^{\dagger} , $$

which satisfies

$$ \|W^{(k)} - \mathbb{I}\| \le \omega_{k-1} + \frac{\sqrt{2}}{\lambda_{\text{gap}} - \varepsilon} (\delta + 2\omega_{k-1} \|H\|) = \omega_k . $$

After $M+1$ inductive steps, we have constructed the operator

$$ H^{(M+1)} = W^{(M+1)}(H \otimes P)(W^{(M+1)})^{\dagger} , $$

whose $\lambda_k$-eigenspace is $\mathcal{P}'_k$ for all $k$. Hence

$$ \| P' H' P' - W^{(M+1)}(H \otimes P)(W^{(M+1)})^{\dagger} \| \le \varepsilon . $$

Moreover, since $H'$ has no zero eigenvalues (since otherwise we shifted by a factor of the identity), we are guaranteed that the null space of $H \otimes P$ is exactly that of $(\mathbb{I} \otimes P)$, and the null space of $P'H'P'$ is exactly that of $P'$. Hence by construction of $W^{(M+1)}$,

$$ P' = W^{(M+1)}(\mathbb{I} \otimes P)(W^{(M+1)})^{\dagger} . $$

We have therefore shown that $(H', \mathcal{A})$ is a gadget in the sense of Definition 10, using $U = W^{(M+1)}$, with accuracy $\varepsilon$ (possibly with an additional $O(\eta)$ if shifting of $H'$ was necessary earlier in the proof) and $\eta = O(\varepsilon) + O(\sqrt{\zeta})$ given explicitly by

$$ \eta = \omega_{M+1} = \frac{1}{2\|H\|} \left[ \left( \frac{2\sqrt{2}}{\lambda_{\text{gap}} - \varepsilon} \|H\| + 1 \right)^M - 1 \right] [\varepsilon + (\zeta + 4\sqrt{2}\pi K \sqrt{\zeta}) \|H\|] . $$
## B.3 Gadget energy scaling

In this section, we prove Theorem 14. Firstly, we introduce the notion of a k-local function, which can be thought of as a classical k-local observable on a state space $\{0, 1\}^n$.

**Definition 30 (k-local function).** Let $f: \{0, 1\}^n \to \mathbb{R}$ be a function. We say that $f$ is k-local if it can be written as a sum of functions

$$f(x_1, x_2, \dots, x_n) = \sum_i f_i(x_1, x_2, \dots, x_n),$$

where the $f_i: \{0, 1\}^n \to \mathbb{R}$ each depend on at most k of their inputs.

The following simple lemmas show that there exist k-local functions which cannot be approximated well by k'-local functions for $k' < k$.

**Lemma 31.** Let $f$ be a k-local function on $n$ inputs. Then $\mathcal{R}f: \{0, 1\}^{n-1} \to \mathbb{R}$, defined by

$$\mathcal{R}f(x_1, \dots, x_{n-1}) = f(x_1, \dots, x_{n-1}, 0) - f(x_1, \dots, x_{n-1}, 1)$$

is $(k-1)$-local.

*Proof of Lemma 31.* Decomposing $f = \sum_i f_i$ as in Definition 30, note that any $f_i$ which does not depend on $x_n$ has $\mathcal{R}f_i = 0$. Moreover, any $f_i$ which does depend on $x_n$ depends on at most $(k-1)$ other inputs, hence $\mathcal{R}f_i$ is $(k-1)$-local. ■

**Lemma 32.** Let $k > k' > 0$. There exists a k-local function $f: \{0, 1\}^n \to \mathbb{R}$ with $\max_{x \in \{0, 1\}^n} |f(x)| \le 1$ such that for any k'-local function $g: \{0, 1\}^n \to \mathbb{R}$,

$$\max_{x \in \{0, 1\}^n} |f(x) - g(x)| \ge 2^{-k'}.$$

*Proof of Lemma 32.* For any $r \ge 1$, we can define $\mathcal{R}^r f: \{0, 1\}^{n-r} \to \mathbb{R}$ by

$$\mathcal{R}^r f(x_1, \dots, x_{n-r}) = \sum_{x_{n-r+1}, \dots, x_n \in \{0,1\}} (-1)^{\sum_{j=1}^r x_{n-r+j}} f(x_1, \dots, x_n). \quad (22)$$

Applying Lemma 31 inductively, note that $\mathcal{R}^r f$ is $(k-r)$-local. In particular, $\mathcal{R}^{k'} g$ is constant for any k'-local $g$.

Let $\tilde{f}: \{0, 1\}^{n-k'} \to \mathbb{R}$ be the $(k-k')$-local function given by

$$\tilde{f}(x_1, \dots, x_{n-k'}) = (-1)^{\sum_{i=1}^{k-k'} x_i}. \quad (23)$$

Then define

$$f(x_1, \dots, x_n) = \begin{cases} \tilde{f}(x_1, \dots, x_{n-k'}) & \text{if } x_{n-k'+1} = \dots = x_n = 0 \\ 0 & \text{otherwise} \end{cases}.$$

Note that $\mathcal{R}^{k'} f = \tilde{f}$. Since $\tilde{f}$ can take values $\pm 1$ yet $\mathcal{R}^{k'} g$ is constant, there must exist $y \in \{0, 1\}^{n-k'}$ such that

$$|\mathcal{R}^{k'} f(y) - \mathcal{R}^{k'} g(y)| \ge 1,$$
and hence, expanding $\mathcal{R}^{k'}f(y)$ and $\mathcal{R}^{k'}g(y)$ using (22) into $2^{k'}$ terms of $f$ and $g$, we must have

$$ \max_{x \in \{0,1\}^n} |f(x) - g(x)| \ge 2^{-k'}. $$

Note that Lemma 32 uses a single illustrative function given by (23) (which appears in the proof of Theorem 14), but a similar argument could apply to most $k$-local functions; the vector space of $k$-local functions has a higher dimension than that of $k'$-local functions.

The following proof uses the intuition from Lemma 32 to argue that the target $k$-local term cannot be reproduced by a $k'$-local Hamiltonian.

**Proof of Theorem 14.** By Definition 10, we have $U \in U(\mathcal{H} \otimes \mathcal{A})$ and $P \in \text{Proj}(\mathcal{A})$ such that

$$ \|U - \mathbb{I}\| \le \eta, \quad \|P'H'P' - U(H \otimes P)U^{\dagger}\| \le \varepsilon, \quad \text{where } P' = U(\mathbb{I} \otimes P)U^{\dagger}. $$

For any given $x \in \{0,1\}^k$, define $|\psi_x\rangle \in \mathcal{H}$ to be the pure state whose $i$th qubit is in the state $|x_i\rangle$. Moreover let $|\phi\rangle \in \mathcal{A}$ be some state satisfying $P|\phi\rangle = |\phi\rangle$. Then define functions $F, f: \{0,1\}^k \to \mathbb{R}$ by

$$ \begin{aligned} F(x) &= \text{tr}[H|\psi_x\rangle\langle\psi_x|], \\ f(x) &= \text{tr}[H'(|\psi_x\rangle\langle\psi_x| \otimes |\phi\rangle\langle\phi|)]. \end{aligned} $$

Notice that $F$ and $f$ are $k$- and $k'$-local respectively, and by Lemma 32 there exists some $y \in \{0,1\}^k$ such that

$$ |F(y) - f(y)| \ge 2^{-k'} J. $$

On the other hand, for all $x \in \{0,1\}^k$ we have

$$ \begin{aligned} |F(x) - f(x)| &= |\text{tr}[(H \otimes P)(|\psi_x\rangle\langle\psi_x| \otimes |\phi\rangle\langle\phi|)] - \text{tr}[H'(|\psi_x\rangle\langle\psi_x| \otimes |\phi\rangle\langle\phi|)]| \\ &\le \|(\mathbb{I} \otimes P)H'(\mathbb{I} \otimes P) - H \otimes P\| \\ &= \|P'UH'U^{\dagger}P' - U(H \otimes P)U^{\dagger}\| \\ &\le \varepsilon + \|P'(H' - UH'U^{\dagger})P'\| \\ &\le \varepsilon + 2\eta\|H'\|. \end{aligned} $$

Hence we must have scaling

$$ \|H'\| \ge \frac{2^{-k'} J - \varepsilon}{2\eta}, $$

as required.

## B.4 Gadget combination

### B.4.1 Combination of general gadgets

Here we introduce some preparatory lemmas before proving Proposition 21.

The first lemma allows us to immediately reduce gadgets to the case that $U$ (in Definition 10) is a direct rotation, defined in Definition 25. This allows us to write $U = e^S$ for $S$ the generator of the direct rotation — the off-diagonal properties of $S$ will simplify calculations considerably.
**Lemma 33.** Suppose $(H', A)$ is a $(\eta, \varepsilon)$-gadget for $H$, where $\eta < \sqrt{2}$. Let $\tilde{\varepsilon} = \varepsilon + 4\eta\|H\|$.

Then $(H', A)$ is also a $(\eta, \tilde{\varepsilon})$-gadget for $H$, where the unitary $U$ in Definition 10 can be assumed to be the direct rotation $W$ [BDL11] between the subspaces defined by $(\mathbb{I} \otimes P)$ and $P'$.

*Proof of Lemma 33.* By Definition 10 we have $U$ such that

$$P' = U(\mathbb{I} \otimes P)U^{\dagger}, \quad \|U - \mathbb{I}\| \le \eta.$$

As noted in [DK70], the direct rotation $W$ between $(\mathbb{I} \otimes P)$ and $P'$ minimises $\|W - \mathbb{I}\|$ subject to the first equality above, hence we have

$$P' = W(\mathbb{I} \otimes P)W^{\dagger}, \quad \|W - \mathbb{I}\| \le \eta.$$

So

$$\begin{aligned} \|P'H'P' - W(H \otimes P)W^{\dagger}\| &\le \varepsilon + \|U(H \otimes P)U^{\dagger} - W(H \otimes P)W^{\dagger}\| \\ &\le \varepsilon + \|U(H \otimes P)U^{\dagger} - H \otimes P\| \\ &\quad + \|W(H \otimes P)W^{\dagger} - H \otimes P\| \\ &\le \varepsilon + 4\eta\|H\|. \end{aligned}$$

A gadget $H'$ for $H$ as in Definition 10 has $\|P'H'P'\| \le \|H\| + \varepsilon$ by definition, however outside the span of $P'$ there are no bounds on $H'$. For $\eta$ small, $P'$ will be close to the projector $\mathbb{I} \otimes P$. The following lemma provides a bound for $H'$ when instead restricted to the span of $\mathbb{I} \otimes P$.

**Lemma 34.** Suppose $(H', A)$ is a $(\eta, \varepsilon)$-gadget for $H$, with $U$, $P'$, and $P$ as in Definition 10, and where $U$ is the direct rotation between $(\mathbb{I} \otimes P)$ and $P'$. Assume $\|H'\| \le J'$, and

$$\|(\mathbb{I} \otimes P)H'(\mathbb{I} \otimes P^{\perp})\| \le J'_{O}.$$

Then

$$\|(\mathbb{I} \otimes P)H'(\mathbb{I} \otimes P)\| \le \|H\| + O(\varepsilon + \eta J'_{O} + \eta^2 J').$$

*Proof of Lemma 34.* Let $S$ be the generator of the direct rotation $U$, so that $\|S\| = O(\eta)$ (see (12)) satisfies

$$P' = e^S (\mathbb{I} \otimes P) e^{-S}.$$

Hence

$$\|(\mathbb{I} \otimes P)H'(\mathbb{I} \otimes P)\| \le \|(\mathbb{I} \otimes P)(e^{-S}H'e^S - H')(\mathbb{I} \otimes P)\| + \|P'H'P'\|.$$

By Definition 10, we have $\|P'H'P'\| \le \|H\| + \varepsilon$, and using Lemma 28 we can bound the first term as

$$\|(\mathbb{I} \otimes P)(e^{-S}H'e^S - H')(\mathbb{I} \otimes P)\| \le \|(\mathbb{I} \otimes P)[S, H')(\mathbb{I} \otimes P)\| + O(\eta^2 J').$$

Furthermore, since $S$ is off-diagonal with respect to $(\mathbb{I} \otimes P)$ we have

$$\|(\mathbb{I} \otimes P)[S, H')(\mathbb{I} \otimes P)\| \le O(\eta J'_{O}),$$

completing the proof.

We now have the necessary tools to prove the gadget combination result Proposition 21. We are provided with the gadgets $(H'_i, A_i)$ for each of the $H_i$ (corresponding to $U_i, P_i, P'_i$ as in Definition 10),
which immediately suggest using $P = \otimes_i P_i$ for the gadget $H' = \sum_i H'_i$ for $H = \sum_i H_i$. It is not immediately clear what unitary $U$, and hence projector $P'$, should be used here, since the $U_i$ do not necessarily commute so cannot be naïvely composed. The direct rotation provides a natural choice, however; writing $U_i = e^{S_i}$ for all $i$, we can choose $U = e^{\sum_i S_i}$. The content of the proof is just a long computation to verify that this choice indeed satisfies the gadget definition.

The following proof is a generalisation of that in [BDLT08], in which similar techniques are used.

**Proof of Proposition 21.** We begin by reducing to the case of the direct rotation. By Lemma 33, we may replace $\varepsilon$ with

$$ \tilde{\varepsilon} = \varepsilon + 4\eta J = O(\varepsilon + \eta J), $$

and hence assume that each gadget $(H'_i, A_i)$ uses the direct rotation $U_i = e^{S_i}$. Specifically, there exists $P_i \in \mathrm{Proj}(A_i)$ such that

$$ \|(\mathbb{I} \otimes P_i)e^{-S_i} H'_i e^{S_i} (\mathbb{I} \otimes P_i) - H_i \otimes P_i\| \le \tilde{\varepsilon}, \quad (24) $$

where $S_i$ is the generator of the direct rotation between the projectors $\mathbb{I} \otimes P_i$ and $P'_i := e^{S_i} (\mathbb{I} \otimes P_i) e^{-S_i}$. We have $\|S_i\| \le O(\eta)$ and $S_i$ is an anti-Hermitian operator which is block off-diagonal with respect to the projectors $\mathbb{I} \otimes P_i$ and $P'_i$ [BDL11].

We define the operators

$$ P := \otimes_i P_i \in \mathrm{Proj}(\otimes_i A_i), \quad S = \sum_i S_i. $$

We now use the triangle inequality along with Lemmas 28-29 to bound

$$ \begin{aligned} & \|(\mathbb{I} \otimes P)e^{-S} H' e^{S} (\mathbb{I} \otimes P) - H \otimes P\| \\ & \le \sum_i \|(\mathbb{I} \otimes P)(H'_i - [S, H'_i] + \frac{1}{2}[S, [S, H'_i]]) - \frac{1}{6}[S, [S, [S, H'_i]]]\| (\mathbb{I} \otimes P) \\ & \quad - H_i \otimes P\| + O(n\eta^4 J'). \end{aligned} $$

Now we bound the terms in the norm separately, using that $S_j$ is block-off-diagonal with respect to $(\mathbb{I} \otimes P_j)$, and that $(\mathbb{I} \otimes P_j)$ commutes with $H'_k$ and $S_k$ if $j \ne k$.

* $(\mathbb{I} \otimes P)[S, H'_i](\mathbb{I} \otimes P):$

Expanding $S = \sum_j S_j$, notice that $(\mathbb{I} \otimes P)[S_j, H'_i](\mathbb{I} \otimes P) = 0$ whenever $j \ne i$, since then we can commute $(\mathbb{I} \otimes P_j)$ past $H'_i$. Hence

$$ (\mathbb{I} \otimes P)[S, H'_i](\mathbb{I} \otimes P) = (\mathbb{I} \otimes P)[S_i, H'_i](\mathbb{I} \otimes P). $$

* $(\mathbb{I} \otimes P)[S, [S, H'_i]](\mathbb{I} \otimes P):$

Note that if $j \ne k$, then

$$ (\mathbb{I} \otimes P)[S_j, [S_k, H'_i]](\mathbb{I} \otimes P) = 0, $$

since at least one of them must be also different to $i$. Then, for instance if $j \ne i$, we can commute $(\mathbb{I} \otimes P_j)$ past $H'_i$ and $S_k$. Hence it remains to consider terms of the form

$$ (\mathbb{I} \otimes P)[S_j, [S_j, H'_i]](\mathbb{I} \otimes P). $$

In this case, if $j \ne i$, then we have

$$ \begin{aligned} \|(\mathbb{I} \otimes P)[S_j, [S_j, H'_i]](\mathbb{I} \otimes P)\| & \le 4 \|S_j\|^2 \|(\mathbb{I} \otimes P_i) H'_i (\mathbb{I} \otimes P_i)\| \\ & \le O(\eta^2 J + \eta^3 J'_O + \eta^4 J'), \end{aligned} $$
using Lemma 34. Hence

$$ (\mathbb{I} \otimes P)[S, [S, H'_i]](\mathbb{I} \otimes P) = (\mathbb{I} \otimes P)[S_i, [S_i, H'_i]](\mathbb{I} \otimes P) + O(\eta^2 J + \eta^3 J'_O + \eta^4 J') . $$

• $(\mathbb{I} \otimes P)[S, [S, [S, H'_i]]](\mathbb{I} \otimes P):$

Here we consider terms of the form $(\mathbb{I} \otimes P)[S_j, [S_k, [S_l, H'_i]]](\mathbb{I} \otimes P)$ in various situations. Firstly, note that if none of $j, k, l$ are equal to $i$ then we can commute $(\mathbb{I} \otimes P_i)$ into the commutator to obtain

$$ \begin{aligned} \|(\mathbb{I} \otimes P)[S_j, [S_k, [S_l, H'_i]]](\mathbb{I} \otimes P)\| &\le 8\|S_j\|\|S_k\|\|S_l\|\|(\mathbb{I} \otimes P_i)H'_i(\mathbb{I} \otimes P_i)\| \\ &\le O(\eta^3 J + \eta^4 J'_O + \eta^5 J') , \end{aligned} $$

by Lemma 34, neglecting the $O(\eta^2\eta)$ term.

If exactly two of the $j, k, l$ are equal to $i$ ($k = l = i \ne j$, say), then we can commute $(\mathbb{I} \otimes P_j)$ past the other terms to kill the $S_j$ term, and the expression vanishes.

If exactly one of the $j, k, l$ is equal to $i$, then by commuting $(\mathbb{I} \otimes P_i)S_i = S_i(\mathbb{I} \otimes P_i^\perp)$, we arrive at

$$ \begin{aligned} \|(\mathbb{I} \otimes P)[S_j, [S_k, [S_l, H'_i]]](\mathbb{I} \otimes P)\| &\le O(\eta^3)\|(\mathbb{I} \otimes P_i^\perp)H'_i(\mathbb{I} \otimes P_i)\| \\ &= O(\eta^3 J'_O) . \end{aligned} $$

Hence

$$ (\mathbb{I} \otimes P)[S, [S, [S, H'_i]]](\mathbb{I} \otimes P) = (\mathbb{I} \otimes P)[S_i, [S_i, [S_i, H'_i]]](\mathbb{I} \otimes P) \\ + O(\eta^3 J + \eta^3 J'_O + \eta^5 J') . $$

So putting the above bounds together and applying Lemma 28, we obtain

$$ \begin{aligned} \|(\mathbb{I} \otimes P)e^{-S} H' e^S (\mathbb{I} \otimes P) - H \otimes P\| &\le \sum_i \|(\mathbb{I} \otimes P)e^{-S_i} H'_i e^{S_i} (\mathbb{I} \otimes P) - H_i \otimes P\| \\ &\quad + O(n\eta^2 J + n\eta^3 J'_O + n\eta^4 J') \\ &\le O(n\varepsilon + n\eta J + n\eta^3 J'_O + n\eta^4 J') , \end{aligned} \quad (25) $$

where the last inequality follows because the $H'_i$ are gadgets for the $H_i$.

Noting also that $\|e^S - \mathbb{I}\| = O(n\eta)$, this completes the proof that $(H', A)$ is a $(\eta', \varepsilon')$-gadget for $H$ as required.

<figure><img src="image_13.png" /></figure>

### B.4.2 Combination of low-energy gadgets

Having proved Proposition 21, we know that the $H'$ from Proposition 22 is an $(\eta', \varepsilon')$-gadget for $H$ in the sense of Definition 10. It remains to prove that it is in fact a $(\Delta', \eta', \varepsilon')$-gadget, which requires replacing the projector $\tilde{P} = e^S(\mathbb{I} \otimes P)e^{-S}$ in (25) by a low-energy projector $P_{\le \Delta'(H')}$. This requires the use of the following corollary to the Davis-Kahan sin $\theta$ theorem (Lemma 27).

**Lemma 35.** Let $A \in \text{Herm}(\mathcal{H})$, and let $P \in \text{Proj}(\mathcal{H})$ be a projector of the same rank as $P_{\le \Delta(A)}$, where $P_{\le \Delta(A)} \in \text{Proj}(\mathcal{H})$ is the projector onto the eigenvectors of $A$ with eigenvalues less than $\Delta$. Suppose that $\|PAP\| \le \lambda$.
Then, for any $\Delta > \lambda$, the direct rotation $U \in U(\mathcal{H})$ from $P$ to $P_{\le \Delta(A)}$ satisfies

$$ \|U - \mathbb{I}\| \le \frac{\sqrt{2}}{\Delta - \lambda} \|P^{\perp}AP\|. $$

**Proof of Lemma 35.** Follows from Lemma 27 using $A \mapsto PAP$, $B \mapsto A$. ■

**Proof of Proposition 22.** By Proposition 21, we have

$$ \tau := \|(\mathbb{I} \otimes P)e^{-S}H'e^{S}(\mathbb{I} \otimes P) - H \otimes P\| \le O(n\varepsilon + n\eta J + n\eta^3 J'_O + n\eta^4 J'). $$

Letting $\tilde{P} = e^{S}(\mathbb{I} \otimes P)e^{-S}$ and the triangle inequality, this gives

$$ \|\tilde{P}H'\tilde{P}\| \le \|H\| + \tau. \qquad (26) $$

We seek to use Lemma 35 to argue that $\tilde{P}$ is “close to” $P_{\le \Delta'(H)}$. To do this, we start by bounding $\|\tilde{P}H'\tilde{P}^{\perp}\|$. We have

$$ \begin{aligned} \|\tilde{P}H'\tilde{P}^{\perp}\| &= \|(\mathbb{I} \otimes P)e^{-S}H'e^{S}(\mathbb{I} \otimes P^{\perp})\| \\ &\le \sum_{i} \|(\mathbb{I} \otimes P)e^{-S}H'_{i}e^{S}(\mathbb{I} \otimes P^{\perp})\|, \end{aligned} \qquad (27) $$

by the triangle inequality. For each $i$, we define $\tilde{H}_i = e^{-S_i}H'_i e^{S_i}$. Note that this operator is block diagonal in the basis of the projector $(\mathbb{I} \otimes P_i)$, in which $S_i$ is block off-diagonal. Note also that each $\tilde{H}_i$ acts on $O(1)$ sites. Now we can write

$$ \|\tilde{P}H'\tilde{P}^{\perp}\| \le \sum_{i} \|(\mathbb{I} \otimes P)e^{-S}e^{S_i}\tilde{H}_i e^{-S_i}e^{S}(\mathbb{I} \otimes P^{\perp})\|. $$

From here we use Lemma 28 to expand

$$ e^{S_i} \tilde{H}_i e^{-S_i} = \tilde{H}_i + [S_i, \tilde{H}_i] + R_i, $$

where $R_i$ acts on $O(1)$ sites, and by Lemma 29 we can bound $\|R_i\| = O(J'\eta^2)$. Hence

$$ \begin{aligned} e^{-S}e^{S_i}\tilde{H}_i e^{-S_i}e^{S} = \tilde{H}_i &+ [S_i, \tilde{H}_i] + R_i \\ & - [S, \tilde{H}_i + [S_i, \tilde{H}_i] + \frac{1}{2}[S_i, [S_i, \tilde{H}_i]] + R_i] \\ & + \tilde{R}_i, \end{aligned} $$

where the remainder $\tilde{R}_i$ is similarly obtained by Lemmas 28-29 with $\|\tilde{R}_i\| = O(J\eta^2)$. Then, using that $S_i$, $\tilde{H}_i$, and $R_i$ each act on $O(1)$ sites, we can estimate

$$ e^{-S}e^{S_i}\tilde{H}_i e^{-S_i}e^{S} = \tilde{H}_i - \sum_{j \neq i} [S_j, \tilde{H}_i] + O(J'\eta^2). $$

But note that, if $j \neq i$, then $[S_j, \tilde{H}_i]$ is block-diagonal with respect to $(\mathbb{I} \otimes P_k)$ for all $k$. Hence

$$ (\mathbb{I} \otimes P)e^{-S}e^{S_i}\tilde{H}_i e^{-S_i}e^{S}(\mathbb{I} \otimes P^{\perp}) = O(J\eta^2), $$

and so, inserting into (27), we have

$$ \|\tilde{P}H'\tilde{P}^{\perp}\| := \omega = O(nJ'\eta^2). \qquad (28) $$
Now we show that the restriction of $H'$ to the image of $\tilde{P}^{\perp}$ has high-energy eigenvalues. Let $|\psi_{\mathcal{H}}\rangle \otimes |\psi_{A_i}\rangle \in \mathcal{H} \otimes A_i$. We consider the expression $((\langle\psi_{\mathcal{H}}| \otimes \langle\psi_{A_i}|)H'_i(|\psi_{\mathcal{H}}\rangle \otimes |\psi_{A_i}\rangle))$ in two cases:

• Case 1: $|\psi_{A_i}\rangle \in P_i A_i$

Then

$$ \begin{aligned} & (\langle\psi_{\mathcal{H}}| \otimes \langle\psi_{A_i}|)H'_i(|\psi_{\mathcal{H}}\rangle \otimes |\psi_{A_i}\rangle) \\ & \geq (\langle\psi|_{\mathcal{H}} \otimes \langle\psi_{A_i}|)P_{\leq\Delta(H'_i)}H'_i P_{\leq\Delta(H'_i)}(|\psi_{\mathcal{H}}\rangle \otimes |\psi_{A_i}\rangle) \\ & \geq (\langle\psi|_{\mathcal{H}} \otimes \langle\psi_{A_i}|)e^{S_i}(H_i \otimes P_i)e^{-S_i}(|\psi_{\mathcal{H}}\rangle \otimes |\psi_{A_i}\rangle) - \varepsilon \\ & \geq \langle\psi_{\mathcal{H}}| H_i |\psi_{\mathcal{H}}\rangle - (\varepsilon + 2J\eta). \end{aligned} $$

• Case 2: $|\psi_{A_i}\rangle \in P_i^{\perp} A_i$

Then

$$ \begin{aligned} & (\langle\psi_{\mathcal{H}}| \otimes \langle\psi_{A_i}|)H'_i(|\psi_{\mathcal{H}}\rangle \otimes |\psi_{A_i}\rangle) \\ & \geq \Delta(\langle\psi_{\mathcal{H}}| \otimes \langle\psi_{A_i}|)P_{>\Delta(H'_i)}(|\psi_{\mathcal{H}}\rangle \otimes |\psi_{A_i}\rangle) \\ & = \Delta((\langle\psi_{\mathcal{H}}| \otimes \langle\psi_{A_i}|)e^{S_i}(\mathbb{I} \otimes P_i^{\perp})e^{-S_i}(|\psi_{\mathcal{H}}\rangle \otimes |\psi_{A_i}\rangle)) \\ & \geq \Delta(1 - 2\eta) \\ & \geq \langle\psi_{\mathcal{H}}| H_i |\psi_{\mathcal{H}}\rangle, \end{aligned} $$

using that $\Delta(1 - 2\eta) \geq J$ for large enough $n$, as $\Delta = \Theta(nJ)$ by assumption.

Now consider any $|\psi\rangle \in \mathcal{H} \otimes (\otimes_i A_i)$ of the form

$$ |\psi\rangle = e^S |\psi_{\mathcal{H}}\rangle \otimes (\otimes_i |\psi_{A_i}\rangle), $$

where $P_j |\psi_{A_j}\rangle = 0$ for at least one value of $j$. Note that such states span the image of $\tilde{P}^{\perp}$. Then

$$ \begin{aligned} \langle\psi| \tilde{P}^{\perp} H' \tilde{P}^{\perp} |\psi\rangle &= \sum_i \langle\psi| H'_i |\psi\rangle \\ &\geq \sum_{i \neq j} (\langle\psi_{\mathcal{H}}| H_i |\psi_{\mathcal{H}}\rangle - \varepsilon - 2J\eta) + \Delta(1 - 2\eta) \\ &\geq \langle\psi_{\mathcal{H}}| H |\psi_{\mathcal{H}}\rangle - (N-1)(\varepsilon + 2J\eta) - J + \Delta(1 - 2\eta) \\ &\geq \Delta(1 - 2\eta) - (\|H\| + J + N(\varepsilon + 2J\eta)) \\ &\geq \frac{3}{4}\Delta, \end{aligned} \quad (29) $$

where we have used the condition (4).

Now let $\tilde{H} := \tilde{P}H'\tilde{P} + \tilde{P}^{\perp}H'\tilde{P}^{\perp}$, so that $\|H' - \tilde{H}\| = O(nJ'\eta^2)$ by (28). Based on (26) and (29), we know that

$$ \text{spec} \tilde{H} \subset [-(\|H\| + \tau), \|H\| + \tau] \cup [\frac{3}{4}\Delta, \infty), \quad (30) $$

corresponding to low- and high-energy projectors $\tilde{P}$ and $\tilde{P}^{\perp}$ respectively. Notice that, for sufficiently large $n$, by condition (5), we will have $\omega < \frac{1}{2}\Delta - (\|H\| + \tau)$, and hence

$$ \text{spec} \tilde{H} \subset (-\infty, \frac{1}{2}\Delta - \omega] \cup [\frac{3}{4}\Delta, \infty), $$

once again corresponding to subspaces defined by $\tilde{P}$ and $\tilde{P}^{\perp}$. Now, by Eq. (28) and Lemma 24, we see that the full Hamiltonian $H'$ has a $(\leq \frac{1}{2}\Delta)$-low energy subspace with the same dimension as
the rank of $\tilde{P}$, and moreover

$$ \text{spec} H' \subset (-\infty, \|H\| + \omega] \cup [\frac{3}{4}\Delta - \omega, \infty). $$

Now set $\Delta' = \Delta/2$. Notice that $\|\tilde{P} - P_{\le \Delta'(H')}\| < 1$, since otherwise there would be a state of energy less than $\Delta'$ in the image of $\tilde{P}^{\perp}$, which is disallowed by (30). So the direct rotation $W \in U(\mathcal{H} \otimes \mathcal{A})$ from $\tilde{P}$ to $P_{\le \Delta'(H')}$ is well-defined, and by Lemma 35

$$ \|W - \mathbb{I}\| \le \frac{\sqrt{2}}{\frac{1}{2}\Delta - \|H\| - \tau} \omega. $$

Note that (4) in particular implies that $\Delta \ge 4\|H\|$, so $\frac{1}{2}\Delta - \|H\| \ge \frac{1}{4}\Delta = \Omega(\Delta)$. By (6), this will dominate the relatively small $\tau$ term, so using (28) and that $\Delta = \Omega(J')$ we have

$$ \|W - \mathbb{I}\| = O(n\eta^2). $$

We can write $W$ in terms of its anti-Hermitian and off-diagonal generator $X$, $W = e^X$, where $\|X\| = O(n\eta^2)$ by (12). Then

$$ P_{\le \Delta'(H')} = U(\mathbb{I} \otimes P)U^{\dagger}, $$

where $U = e^X e^S$. Note that

$$ \begin{aligned} \|U - \mathbb{I}\| &\le \|e^X (e^S - \mathbb{I})\| + \|e^X - \mathbb{I}\| \\ &\le \|S\| + \|X\| \\ &= O(n\eta) + O(n\eta^2) = O(n\eta). \end{aligned} $$

It remains to bound find $\varepsilon'$ to achieve a bound of the form

$$ \|P_{\le \Delta'(H')} H' P_{\le \Delta'(H')} - U(H \otimes P) U^{\dagger}\| \le \varepsilon'. $$

Using (26) and the triangle inequality we have

$$ \|P_{\le \Delta'(H')} H' P_{\le \Delta'(H')} - U(H \otimes P) U^{\dagger}\| \le \|\tilde{P}(e^{-X} H' e^X - H') \tilde{P}\| + \tau, $$

and the first term can be bounded using Lemma 28 by

$$ \begin{aligned} \|\tilde{P}(e^{-X} H' e^X - H') \tilde{P}\| &\le \|\tilde{P}[X, H'] \tilde{P}\| + \frac{1}{2}\|[X, [X, H']]\| \\ &\le 2\|X\| \cdot \|\tilde{P} H' \tilde{P}^{\perp}\| + 2\|X\|^2 \cdot \|H'\| \\ &\le O(n^3 J' \eta^4). \end{aligned} $$

In the second inequality we have used that $X$ is off-diagonal with respect to $\tilde{P}$, and in the third inequality we have used (28) to bound $\|\tilde{P} H' \tilde{P}^{\perp}\|$. Hence

$$ \varepsilon' = O(n\varepsilon + n\eta J + n\eta^3 J'_O + n^3\eta^4 J'). $$

### B.4.3 Ground-state estimation with bounded-strength low-energy gadgets

The following proof of Theorem 23 is a simple corollary of Proposition 21, and generalises the proof of [BDLT08] Theorem 1.
Proof of Theorem 23. For the first part of this proof, we seek to put a lower bound on the individual gadgets $H'_i$. We write

$$H'_i = P_{\le \Delta(H'_i)} H'_i P_{\le \Delta(H'_i)} + P_{> \Delta(H'_i)} H'_i P_{> \Delta(H'_i)},$$

and consider the high- and low-energy parts separately.

For the low-energy part, we can apply the gadget definition (Definition 10) to write

$$\|P_{\le \Delta(H'_i)} H'_i P_{\le \Delta(H'_i)} - H_i \otimes P_i\| \le \varepsilon + \|e^{S_i}(H_i \otimes P_i)e^{-S_i} - H_i \otimes P_i\| \\ \le O(\varepsilon + \eta J),$$

using Lemma 28, and hence

$$P_{\le \Delta(H'_i)} H'_i P_{\le \Delta(H'_i)} \ge H_i \otimes P_i + O(\varepsilon + \eta J). \quad (31)$$

For the high-energy part, we first notice that since the spectrum of $P_{> \Delta(H'_i)} H'_i P_{> \Delta(H'_i)}$ lies in $(\Delta, \infty)$, where $\Delta \ge \|H_i\| - \varepsilon$, and so

$$P_{> \Delta(H'_i)} H'_i P_{> \Delta(H'_i)} \ge P_{> \Delta(H'_i)} (H_i \otimes \mathbb{I}) P_{> \Delta(H'_i)} + O(\varepsilon).$$

Furthermore, we can approximate the RHS of this expression by

$$\|P_{> \Delta(H'_i)}(H_i \otimes \mathbb{I}) P_{> \Delta(H'_i)} - H_i \otimes P_i^{\perp}\| \\ = \|e^{S_i}(\mathbb{I} \otimes P_i^{\perp})e^{-S_i}(H_i \otimes \mathbb{I})e^{S_i}(\mathbb{I} \otimes P_i^{\perp})e^{-S_i} - H_i \otimes P_i^{\perp}\| \\ \le O(\eta J),$$

by applying Lemma 28. Hence

$$P_{> \Delta(H'_i)} H'_i P_{> \Delta(H'_i)} \ge H_i \otimes P_i^{\perp} + O(\varepsilon + \eta J). \quad (32)$$

Summing (31) and (32) for all $i$, we obtain

$$H' = \sum_i H'_i \ge \sum_i (H_i \otimes \mathbb{I} + O(\varepsilon + \eta J)) = H \otimes \mathbb{I} + O(n\varepsilon + n\eta J),$$

and so the ground state energy of $H'$ must satisfy

$$\lambda_0(H') \ge \lambda_0(H) + O(n\varepsilon + n\eta J). \quad (33)$$

Now notice that the restriction of $H'$ to a subspace can only increase $\lambda_0$, so<fnref n="3" />

$$\lambda_0(H') = \lambda_0(e^{-S} H' e^{S}) \le \lambda_0((\mathbb{I} \otimes P)e^{-S} H' e^{S}(\mathbb{I} \otimes P)),$$

so by Proposition 21 we have

$$\lambda_0(H') \le \lambda_0(H) + O(n\varepsilon + n\eta J + n\eta^3 J'_O + n\eta^4 J'). \quad (34)$$

Combining (33)-(34) gives the desired result.

<footnote n="3">³Here, as in [BDLT08], we abuse notation slightly: in the expression $\lambda_0((\mathbb{I} \otimes P)e^{-S} H' e^{S}(\mathbb{I} \otimes P))$, we implicitly take the ground state of the restriction of $e^{-S} H' e^{S}$ to the image of $(\mathbb{I} \otimes P)$.</footnote>
## B.5 Measurement gadgets

### B.5.1 Measurement gadgets in isolation

Here we first prove Proposition 15. This follows from direct calculation, by Taylor expanding the expression $e^{-i\delta t H'}$ and identifying the leading order terms in $\delta t$. This approach is complicated by the fact that $H'$ itself consists of terms that are $O((\delta t)^{-1})$ and $O((\delta t)^{-1/2})$, but the task is simplified since we only need to calculate the time evolution of states of the form $|\psi\rangle \otimes |0\rangle$.

*Proof of Proposition 15.* First, notice that the requirement $H_{|1\rangle\langle1|}^2 = \omega^2 \mathbb{I}$ implies that

$$e^{-i\delta t H_{|1\rangle\langle1|}} = \mathbb{I}, \quad H_{|1\rangle\langle1|}^{-1} = \omega^{-2} H_{|1\rangle\langle1|}. \qquad (35)$$

Now we expand $e^{-i\delta t H'}$:

$$e^{-i\delta t H'} = \sum_{k \ge 0} \frac{(-i\delta t)^k}{k!} (H_{\mathbb{I}} \otimes \mathbb{I} + H_X \otimes X + H_{|1\rangle\langle1|} \otimes |1\rangle\langle1|)^k. \qquad (36)$$

We can expand out this expression so that each term is a product of $a$ factors of $H_{\mathbb{I}} \otimes \mathbb{I}$, $b$ factors of $H_X \otimes X$, and $c$ factors of $H_{|1\rangle\langle1|}$, for some $a, b, c \in \mathbb{N}$. Such a term is accompanied by $(\delta t)^{a+b+c}$, to give a total order of $(\delta t)^{a+\frac{1}{2}b}$ (using that $\|H_X\| = O((\delta t)^{-1/2})$ and $\|H_{|1\rangle\langle1|}\| = O((\delta t)^{-1})$). There are eight cases producing terms of order $O((\delta t)^{3/2})$ and lower, which we enumerate in Fig. 12.

<table><caption>Figure 12: Enumeration of possible cases for the values of $a, b, c$ giving rise to terms of order $O((\delta t)^{3/2})$ and lower in (36). We denote $N_+ = \{1, 2, \dots\}$ and $N = \{0, 1, 2, \dots\}$.</caption><thead><tr><th>Case</th><th>a</th><th>b</th><th>c</th><th>Order</th></tr></thead><tbody><tr><td>1</td><td>0</td><td>0</td><td>0</td><td>O(1)</td></tr><tr><td>2</td><td>0</td><td>0</td><td>N<sub>+</sub></td><td></td></tr><tr><td>3</td><td>0</td><td>1</td><td>N</td><td>O((δt)<sup>1/2</sup>)</td></tr><tr><td>4</td><td>1</td><td>0</td><td>0</td><td>O(δt)</td></tr><tr><td>5</td><td>1</td><td>0</td><td>N<sub>+</sub></td><td></td></tr><tr><td>6</td><td>0</td><td>2</td><td>N</td><td></td></tr><tr><td>7</td><td>1</td><td>1</td><td>N</td><td>O(t<sup>3/2</sup>)</td></tr><tr><td>8</td><td>0</td><td>3</td><td>N</td><td></td></tr></tbody></table>

In particular, we are interested in the block-elements $(\mathbb{I} \otimes \langle 0 |) e^{-i\delta t H'} (\mathbb{I} \otimes |0\rangle)$ and $(\mathbb{I} \otimes \langle 1 |) e^{-i\delta t H'} (\mathbb{I} \otimes |0\rangle)$, since the other blocks in $e^{-i\delta t H'}$ will annihilate states of the form $|\psi\rangle \otimes |0\rangle$.

* $(\mathbb{I} \otimes \langle 0 |) e^{-i\delta t H'} (\mathbb{I} \otimes |0\rangle)$:

Note that each factor of $H_X \otimes X$ flips the ancillary qubit $\mathcal{A}$, whereas each factor of $H_{|1\rangle\langle1|} \otimes |1\rangle\langle1|$ annihilates states with the ancillary qubit in state $|0\rangle$. As a result, the only contributions to $(\mathbb{I} \otimes \langle 0 |) e^{-i\delta t H'} (\mathbb{I} \otimes |0\rangle)$ from Fig. 12 are those such that $b$ is even. Moreover, $c$ can only be nonzero if $b$ is at least 2 (so that the factors of $H_{|1\rangle\langle1|} \otimes |1\rangle\langle1|$ can be sandwiched between two $H_X \otimes X$ factors). This restricts us to cases 1, 4, and 6, so

$$(\mathbb{I} \otimes \langle 0 |) e^{-i\delta t H'} (\mathbb{I} \otimes |0\rangle) = \mathbb{I} - i\delta t H_{\mathbb{I}} + \sum_{k \ge 2} \frac{(-i\delta t)^k}{k!} H_X H_{|1\rangle\langle1|}^{k-2} H_X + O((\delta t)^2).$$
Furthermore, the sum can be simplified to

$$ 
\begin{aligned}
\sum_{k \ge 2} \frac{(-i\delta t)^k}{k!} H_X H_{|1\rangle\langle 1|}^{k-2} H_X &= H_X H_{|1\rangle\langle 1|}^{-2} \left( \sum_{k \ge 2} \frac{(-i\delta t)^k}{k!} H_{|1\rangle\langle 1|}^k \right) H_X \\
&= H_X H_{|1\rangle\langle 1|}^{-2} \left( e^{-i\delta t H_{|1\rangle\langle 1|}} - \mathbb{I} + i\delta t H_{|1\rangle\langle 1|} \right) H_X \\
&= i\delta t \omega^{-2} H_X H_{|1\rangle\langle 1|} H_X,
\end{aligned}
$$

using (35). Hence we have shown that

$$ (\mathbb{I} \otimes \langle 0|)e^{-i\delta t H'} (\mathbb{I} \otimes |0\rangle) = \mathbb{I} - i\delta t(H_{\mathbb{I}} - \omega^{-2}H_X H_{|1\rangle\langle 1|} H_X) + O((\delta t)^2). \quad (37) $$

$$ \bullet \quad (\mathbb{I} \otimes \langle 1|)e^{-i\delta t H'} (\mathbb{I} \otimes |0\rangle): $$

By a similar argument to above, the only contributing terms from Fig. 12 are those such that b is odd, so we can reduce to the cases 3, 7, and 8. In case 3, also notice that the $H_X \otimes X$ term must appear on the right of all the $H_{|1\rangle\langle 1|} \otimes |1\rangle\langle 1|$ terms. Hence

$$ (\mathbb{I} \otimes \langle 1|)e^{-i\delta t H'} (\mathbb{I} \otimes |0\rangle) = \sum_{k \ge 1} \frac{(-i\delta t)^k}{k!} H_{|1\rangle\langle 1|}^{k-1} H_X + O((\delta t)^{3/2}). $$

The sum here can be similarly simplified by Eq. (35):

$$ 
\begin{aligned}
\sum_{k \ge 1} \frac{(-i\delta t)^k}{k!} H_{|1\rangle\langle 1|}^{k-1} H_X &= H_{|1\rangle\langle 1|}^{-1} \left( \sum_{k \ge 0} \frac{(-i\delta t)^k}{k!} H_{|1\rangle\langle 1|}^k - \mathbb{I} \right) H_X \\
&= H_{|1\rangle\langle 1|}^{-1} (e^{-i\delta t H_{|1\rangle\langle 1|}} - \mathbb{I}) H_X \\
&= 0,
\end{aligned}
$$

so

$$ (\mathbb{I} \otimes \langle 1|)e^{-i\delta t H'} (\mathbb{I} \otimes |0\rangle) = O((\delta t)^{3/2}), \quad (38) $$

which, along with (37), completes the proof.

<figure><img src="image_14.png" /></figure>

## B.5.2 Trotter errors

The idea for the proof of Proposition 16 is to factorise the overall evolution operator

$$ e^{-i\delta t(H' + H_{\text{else}}\otimes\mathbb{I})} \approx e^{-i\delta tH_{\text{else}}\otimes\mathbb{I}}e^{-i\delta tH'}. $$

From here, we simply apply Proposition 15 to the initial state $|\psi\rangle \otimes |0\rangle$, and then evolve the $\mathcal{H}$ system of the resultant state under $H_{\text{else}}$. The technical difficulty is in bounding the errors of this Trotter expansion in a way which does not depend on the size of the system. Qualitatively, one might expect this behaviour due to the bounded spread of correlations in the system over a short time $\delta t$, under which only a limited set of interactions in $H_{\text{else}}$ can “interfere” with the evolution under $H'$. The difficulty of obtaining such bounds is compounded by the presence of terms in $H'$ which scale as $O((\delta t)^{-1})$ and $O((\delta t)^{-1/2})$. Our approach uses an explicit form of the Trotter error given by [CST+21]. We briefly outline this process here.

Let $A, B \in \text{Lin}(\mathcal{H})$. We aim to find an expression for the Trotter error incurred by the expansion $e^{t(A+B)} \approx e^{tA}e^{tB}$.
Observe that the function $f(t) = e^{tA}e^{tB}$ satisfies the differential equation

$$ 
\begin{aligned}
f'(t) &= A e^{tA} e^{tB} + e^{tA} B e^{tB} \\
&= (A + B)f(t) + e^{tA}(B - e^{-tA}Be^{tA})e^{tB}.
\end{aligned} 
\quad (39) $$

This differential equation, with initial condition $f(0) = \mathbb{I}$, can be solved using following lemma.

**Lemma 36** (Variation of parameters formula $[CST^{+21}]$). Let $K \in \text{Lin}(\mathcal{H})$, and let $L(t) \in \text{Lin}(\mathcal{H})$ be a continuous operator-valued function of t. Suppose that $f(t)$ satisfies the differential equation

$$ f'(t) = Kf(t) + L(t), \quad f(0) = \mathbb{I}. $$

Then there is a unique solution for $f$ which is given by

$$ f(t) = e^{tK} + \int_{0}^{t} d\tau e^{(t-\tau)K} L(\tau). $$

Hence, using Lemma 36 with $K = A + B$ and $L(t) = e^{tA}(B - e^{-tA}Be^{tA})e^{tB}$, we find that the Trotter error is given by

$$ e^{tA}e^{tB} - e^{t(A+B)} = \int_{0}^{t} d\tau e^{(t-\tau)(A+B)} e^{\tau A} (B - e^{-\tau A}Be^{\tau A}) e^{\tau B} \quad (40) $$

The expression (40) is particularly convenient because, when $A$ is a local Hamiltonian and $B$ acts only on $O(1)$ sites, the bracketed term $(B - e^{-\tau A}Be^{\tau A})$ can be bounded independently of $n$.

**Lemma 37.** Let $H = \sum_i h_i$ be a k-local Hamiltonian on a system $\mathcal{H} = \bigotimes_{i=1}^n \mathcal{H}_i$, with the degree of the interaction hypergraph bounded by an $O(1)$ constant and $\|h_i\| = O(1)$. Let $A$ be an observable supported on a set of $O(1)$ sites. Then

$$ \|e^{itH}Ae^{-itH} - A\| \le O(\|A\|t). $$

**Proof of Lemma 37.** For $X \in \text{Lin}(\mathcal{H})$, define $f_X(t) = \text{tr}[X(e^{itH}Ae^{-itH} - A)]$, so that

$$ \|e^{itH}Ae^{-itH} - A\| = \max_{X \in D(\mathcal{H})} |f_X(t)|. \quad (41) $$

We can see that $f_X(0) = 0$ and $f'_X(t) = \text{tr}[Xe^{itH}[H, A]e^{-itH}]$. Moreover, since $H$ is local on an $O(1)$-degree hypergraph, and $A$ is supported on an $O(1)$ set, only $O(1)$ terms in $H$ contribute to the commutator and hence $|f'_X(t)| \le \|X\|_1\|[H, A]\| = O(\|X\|_1\|A\|)$. By the mean value theorem, we therefore deduce that

$$ f_X(t) = O(\|X\|_1\|A\|t), $$

so by (41) we are done.

### B.5.3 Measurement gadgets with other terms

**Proof of Proposition 16.** Using (40) with $t = \delta t$, $A = -iH_{\text{else}} \otimes \mathbb{I}$, and $B = -iH'$, we obtain a Trotter error given by

$$ 
\begin{aligned}
& e^{-i\delta t H_{\text{else}} \otimes \mathbb{I}} e^{-i\delta t H'} - e^{-i\delta t (H_{\text{else}} \otimes \mathbb{I} + H')} := E \\
& = -i \int_{0}^{\delta t} d\tau e^{-i(\delta t - \tau)(H_{\text{else}} \otimes \mathbb{I} + H')} e^{-i\tau H_{\text{else}} \otimes \mathbb{I}} (H' - e^{i\tau H_{\text{else}} \otimes \mathbb{I}} H' e^{-i\tau H_{\text{else}} \otimes \mathbb{I}}) e^{-i\tau H'}.
\end{aligned} 
\quad (42) $$
We can write E in block form in the basis of the ancillary space,

$$E = \begin{pmatrix} (\mathbb{I} \otimes \langle 0|)E(\mathbb{I} \otimes |0\rangle) & (\mathbb{I} \otimes \langle 0|)E(\mathbb{I} \otimes |1\rangle) \\ (\mathbb{I} \otimes \langle 1|)E(\mathbb{I} \otimes |0\rangle) & (\mathbb{I} \otimes \langle 1|)E(\mathbb{I} \otimes |1\rangle) \end{pmatrix},$$

and we will focus on individually bounding these blocks. Notice that, commuting projectors on the ancillary space past $H_{\text{else}} \otimes \mathbb{I}$ and applying Lemma 37, we have

$$\begin{aligned} & \|(\mathbb{I} \otimes \langle 0|)(H' - e^{i\tau H_{\text{else}} \otimes \mathbb{I}} H' e^{-i\tau H_{\text{else}} \otimes \mathbb{I}})(\mathbb{I} \otimes |0\rangle)\| \\ &= \|(\mathbb{I} \otimes \langle 0|)H'(\mathbb{I} \otimes |0\rangle) - e^{i\tau H_{\text{else}}}(\mathbb{I} \otimes \langle 0|)H'(\mathbb{I} \otimes |0\rangle)e^{-i\tau H_{\text{else}}}\| \\ &= \|H_{\mathbb{I}} - e^{i\tau H_{\text{else}}}H_{\mathbb{I}}e^{-i\tau H_{\text{else}}}\| = O(\delta t). \end{aligned}$$

With a similar process for the other blocks, we obtain the following bounds:

$$\|(\mathbb{I} \otimes \langle 0|)(H' - e^{i\tau H_{\text{else}} \otimes \mathbb{I}} H' e^{-i\tau H_{\text{else}} \otimes \mathbb{I}})(\mathbb{I} \otimes |0\rangle)\| = O(\delta t), \quad (43a)$$

$$\|(\mathbb{I} \otimes \langle 1|)(H' - e^{i\tau H_{\text{else}} \otimes \mathbb{I}} H' e^{-i\tau H_{\text{else}} \otimes \mathbb{I}})(\mathbb{I} \otimes |0\rangle)\| = O(\delta t^{1/2}), \quad (43b)$$

$$\|(\mathbb{I} \otimes \langle 0|)(H' - e^{i\tau H_{\text{else}} \otimes \mathbb{I}} H' e^{-i\tau H_{\text{else}} \otimes \mathbb{I}})(\mathbb{I} \otimes |1\rangle)\| = O(\delta t^{1/2}), \quad (43c)$$

$$\|(\mathbb{I} \otimes \langle 1|)(H' - e^{i\tau H_{\text{else}} \otimes \mathbb{I}} H' e^{-i\tau H_{\text{else}} \otimes \mathbb{I}})(\mathbb{I} \otimes |1\rangle)\| = O(1). \quad (43d)$$

Since our initial state is of the form $|\psi\rangle \otimes |0\rangle$, we need only bound the magnitudes of the blocks $(\mathbb{I} \otimes \langle 0|)E(\mathbb{I} \otimes |0\rangle)$ and $(\mathbb{I} \otimes \langle 1|)E(\mathbb{I} \otimes |0\rangle)$. To this end, we need to describe the action of the operator $e^{-i\tau H'}$ on the operators $(\mathbb{I} \otimes |0\rangle)$ and $(\mathbb{I} \otimes |1\rangle)$, for $0 \le \tau \le \delta t$. By considering the series expansion as in (36), and noting that the ancillary qubit can only be flipped by a $H_X \otimes X$ term of order $O((\delta t)^{1/2})$, we see that

$$e^{-i\tau H'}(\mathbb{I} \otimes |0\rangle) = O(1) \otimes |0\rangle + O((\delta t)^{1/2}) \otimes |1\rangle, \quad (44a)$$

$$e^{-i\tau H'}(\mathbb{I} \otimes |1\rangle) = O((\delta t)^{1/2}) \otimes |0\rangle + O(1) \otimes |1\rangle. \quad (44b)$$

Notice that here we abuse big-O notation for matrices; for example, in the above expression $O((\delta t)^{1/2})$ should be interpreted as a matrix with operator norm bounded by $O(\delta t^{1/2})$. We can also crudely upper bound E as follows:

$$\begin{aligned} \|E\| &\le \int_0^{\delta t} \mathrm{d}\tau \|H' - e^{i\tau H_{\text{else}} \otimes \mathbb{I}} H' e^{-i\tau H_{\text{else}} \otimes \mathbb{I}}\| \\ &\le \int_0^{\delta t} \mathrm{d}\tau O(1) = O(\delta t), \end{aligned}$$

using (43d) to give the most pessimistic bound. Therefore in particular

$$e^{i\tau H_{\text{else}} \otimes \mathbb{I}} e^{i(\delta t - \tau)(H_{\text{else}} \otimes \mathbb{I} + H')} = e^{i\delta t H_{\text{else}} \otimes \mathbb{I}} e^{i(\delta t - \tau)H'} + O(\delta t),$$

so, using (44a),

$$\begin{aligned} e^{i\tau H_{\text{else}} \otimes \mathbb{I}} e^{i(\delta t - \tau)(H_{\text{else}} \otimes \mathbb{I} + H')} (\mathbb{I} \otimes |0\rangle) &= e^{-i\delta t H_{\text{else}} \otimes \mathbb{I}} e^{i(\delta t - \tau)H'} (\mathbb{I} \otimes |0\rangle) + O(\delta t) \\ &= O(1) \otimes |0\rangle + O((\delta t)^{1/2}) \otimes |1\rangle, \end{aligned} \quad (45)$$

and similarly

$$e^{i\tau H_{\text{else}} \otimes \mathbb{I}} e^{i(\delta t - \tau)(H_{\text{else}} \otimes \mathbb{I} + H')} (\mathbb{I} \otimes |1\rangle) = O((\delta t)^{1/2}) \otimes |0\rangle + O(1) \otimes |1\rangle. \quad (46)$$
We can now obtain the necessary bounds on the blocks of E. Firstly, we have

$$
\begin{align}
& \|(\mathbb{I} \otimes \langle 0 |) E(\mathbb{I} \otimes |0 \rangle)\| \nonumber \\
& \le \int_0^{\delta t} d\tau \|(\mathbb{I} \otimes \langle 0 |) e^{-i(\delta t - \tau)(H_{\text{else}} \otimes \mathbb{I} + H')} e^{-i\tau H_{\text{else}} \otimes \mathbb{I}} (H' - e^{i\tau H_{\text{else}} \otimes \mathbb{I}} H' e^{-i\tau H_{\text{else}} \otimes \mathbb{I}}) e^{-i\tau H'} (\mathbb{I} \otimes |0 \rangle)\| \nonumber \\
& \le \int_0^{\delta t} d\tau \left[ \begin{aligned}
& O(1) \|(\mathbb{I} \otimes \langle 0 |) (H' - e^{i\tau H_{\text{else}} \otimes \mathbb{I}} H' e^{-i\tau H_{\text{else}} \otimes \mathbb{I}}) (\mathbb{I} \otimes |0 \rangle)\| \\
& + O((\delta t)^{1/2}) \|(\mathbb{I} \otimes \langle 1 |) (H' - e^{i\tau H_{\text{else}} \otimes \mathbb{I}} H' e^{-i\tau H_{\text{else}} \otimes \mathbb{I}}) (\mathbb{I} \otimes |0 \rangle)\| \\
& + O((\delta t)^{1/2}) \|(\mathbb{I} \otimes \langle 0 |) (H' - e^{i\tau H_{\text{else}} \otimes \mathbb{I}} H' e^{-i\tau H_{\text{else}} \otimes \mathbb{I}}) (\mathbb{I} \otimes |1 \rangle)\| \\
& + O(\delta t) \|(\mathbb{I} \otimes \langle 1 |) (H' - e^{i\tau H_{\text{else}} \otimes \mathbb{I}} H' e^{-i\tau H_{\text{else}} \otimes \mathbb{I}}) (\mathbb{I} \otimes |1 \rangle)\|
\end{aligned} \right] \nonumber \\
& = O((\delta t)^2), \tag{47}
\end{align}
$$

using (43a-43d). Similarly, we can bound

$$
\begin{align}
& \|(\mathbb{I} \otimes \langle 1 |) E(\mathbb{I} \otimes |0 \rangle)\| \nonumber \\
& \le \int_0^{\delta t} d\tau \|(\mathbb{I} \otimes \langle 1 |) e^{-i(\delta t - \tau)(H_{\text{else}} \otimes \mathbb{I} + H')} e^{-i\tau H_{\text{else}} \otimes \mathbb{I}} (H' - e^{i\tau H_{\text{else}} \otimes \mathbb{I}} H' e^{-i\tau H_{\text{else}} \otimes \mathbb{I}}) e^{-i\tau H'} (\mathbb{I} \otimes |0 \rangle)\| \nonumber \\
& \le \int_0^{\delta t} d\tau \left[ \begin{aligned}
& O((\delta t)^{1/2}) \|(\mathbb{I} \otimes \langle 0 |) (H' - e^{i\tau H_{\text{else}} \otimes \mathbb{I}} H' e^{-i\tau H_{\text{else}} \otimes \mathbb{I}}) (\mathbb{I} \otimes |0 \rangle)\| \\
& + O(1) \|(\mathbb{I} \otimes \langle 1 |) (H' - e^{i\tau H_{\text{else}} \otimes \mathbb{I}} H' e^{-i\tau H_{\text{else}} \otimes \mathbb{I}}) (\mathbb{I} \otimes |0 \rangle)\| \\
& + O(\delta t) \|(\mathbb{I} \otimes \langle 0 |) (H' - e^{i\tau H_{\text{else}} \otimes \mathbb{I}} H' e^{-i\tau H_{\text{else}} \otimes \mathbb{I}}) (\mathbb{I} \otimes |1 \rangle)\| \\
& + O((\delta t)^{1/2}) \|(\mathbb{I} \otimes \langle 1 |) (H' - e^{i\tau H_{\text{else}} \otimes \mathbb{I}} H' e^{-i\tau H_{\text{else}} \otimes \mathbb{I}}) (\mathbb{I} \otimes |1 \rangle)\|
\end{aligned} \right] \nonumber \\
& = O((\delta t)^{3/2}). \tag{48}
\end{align}
$$

With the bounds (47) and (48) on the blocks of the Trotter error we can now conclude that

$$
\begin{align}
e^{-i\delta t(H' + H_{\text{else}} \otimes \mathbb{I})} (|\psi\rangle \otimes |0\rangle) &= e^{-i\delta t H_{\text{else}} \otimes \mathbb{I}} e^{-i\delta t H'} (|\psi\rangle \otimes |0\rangle) + E(|\psi\rangle \otimes |0\rangle) \nonumber \\
&= e^{-i\delta t H_{\text{else}} \otimes \mathbb{I}} (e^{-i\delta t H} |\psi\rangle + O((\delta t)^2)) \otimes |0\rangle + O((\delta t)^{3/2}) \otimes |1\rangle \nonumber \\
&\quad + O((\delta t)^2) \otimes |0\rangle + O((\delta t)^{3/2}) \otimes |1\rangle \nonumber \\
&= (e^{-i\delta t H_{\text{else}}} e^{-i\delta t H} |\psi\rangle + O((\delta t)^2)) \otimes |0\rangle + O((\delta t)^{3/2}) \otimes |1\rangle, \tag{49}
\end{align}
$$

where in the second inequality we invoke Proposition 15. It remains only to bound the Trotter error in the product $e^{-i\delta t H_{\text{else}}} e^{-i\delta t H}$, which we can accomplish similarly. Using (40) with $t = \delta t$, $A = -iH_{\text{else}}$, $B = -iH$, we obtain

$$
\begin{align}
& e^{-i\delta t H_{\text{else}}} e^{-i\delta t H} - e^{-i\delta t(H+H_{\text{else}})} \nonumber \\
& = -i \int_0^{\delta t} d\tau e^{-i(\delta t - \tau)(H+H_{\text{else}})} e^{-i\tau H_{\text{else}}} (H - e^{i\tau H_{\text{else}}} H e^{-i\tau H_{\text{else}}}) e^{-i\tau H}. \tag{50}
\end{align}
$$

So by Lemma 37 we have

$$
e^{-i\delta t H_{\text{else}}} e^{-i\delta t H} - e^{-i\delta t(H+H_{\text{else}})} \le O((\delta t)^2) \quad (51)
$$

Combining (51) with (49) completes the proof.

<figure><img src="image_15.png" /></figure>