Criteria for quantum computation and simulation
In a review of the prospective possibilities of quantum computing38 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. 5.
Fig. 5: A summary of the DiVincenzo38 and Cirac-Zoller10 criteria.
The DiVincenzo criteria provide necessary and sufficient requirements for universal digital quantum computers. Similarly, the Cirac-Zoller criteria offer a set of requirements for analogue quantum simulation, for which universality may not be available.
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 by Cirac et al.10, also summarised in Fig. 5. These are all natural requirements to ask of a quantum simulator, but it is noteworthy that criterion 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 \({{{\rm{U}}}}({({{\mathbb{C}}}^{2})}^{\otimes k})\) of unitary transformations relatively cheaply due to the Solovay-Kitaev theorem39, the task of an analogue quantum simulator is to implement k-qudit interactions from the unbounded set of possible Hamiltonians Herm \((({\mathbb{C}})^{{{\rm{d}}}})^{\otimes k}\left)\right.\). 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). In addition, in order to ensure the local and size-independent encoding of each site into the simulator, we argue that the simulator should grow no faster than linearly with the size of the target system. If each site is encoded into more than O(1) simulator sites, it will be impossible to encode the full system into a simulator of the same dimension while preserving geometric locality (without introducing scaling interactions). We summarise these requirements 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 Θ(1).
It is worth noting that further formalisation is required to make this definition robust. For example, suppose we are given a Hamiltonian H = h1 + h2 where ∥h1∥, ∥h2∥ = O(n−1), which violates the size-independence requirement. One could simply define \({h}_{1}^{{\prime} }={h}_{1}+K\), \({h}_{2}^{{\prime} }={h}_{2}-K\), for some K = Θ(1), and then \(H={h}_{1}^{{\prime} }+{h}_{2}^{{\prime} }\) 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 Wilming et al.40.
As well as being experimentally and qualitatively desirable, encoding interactions independently has quantitative benefits; as noted by Cubitt et al.11, 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, Aharonov et al.19 show that restriction to such Hamiltonians will necessarily sacrifice some sense of the universality of the simulator. Earlier results in Hamiltonian complexity theory31, however, show that in many cases, it is still possible to simulate ground state energies up to an extensive error.
Hamiltonian complexity theory
We say that a Hamiltonian H on the space 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 hj acts on at most k of the qubit sites. We consider the hj 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. 6.
Fig. 6: Example Hamiltonian interaction hypergraph.
A Hamiltonian H on 4 qubits, and its associated interaction hypergraph. The Hamiltonian consists of a 3-local (orange) and a 2-local (red) term, so we say that H is 3-local.
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 = poly(n), and for each j we have ∥hj∥ ≤ poly(n) and hj is specified by O(poly(n)) bits.
Given a < b with b−a > 1/poly(n), let λ0(H) denote the lowest eigenvalue of H. Then the output should distinguish between the cases
Through the Feynman-Kitaev circuit-to-Hamiltonian construction41, it was established that the 5-local Hamiltonian problem is QMA-complete, and subsequent works optimising the construction30 and using gadget techniques42 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, refs. 43,44); indeed hardness results have been shown to hold even under the significant restriction to 1-dimensional translationally invariant systems45. QMA-completeness is closely related to a notion of universality for simulators; an equivalence was proved by Kohler et al.15.
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. A notable exception to this is the work of Bravyi et al.31, 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 that of Cubitt et al.11, in which the authors study methods of encoding Hamiltonians via a map \({{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}:{{{\rm{Herm}}}}({{{\mathcal{H}}}})\to {{{\rm{Herm}}}}({{{{\mathcal{H}}}}}^{{\prime} })\), which satisfy the natural requirement of preserving the spectrum of observables. Additionally, in the case that \({{{\mathcal{H}}}}={\otimes }_{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}}}}}^{{\prime} }={\otimes }_{i=1}^{{n}^{{\prime} }}{{{{\mathcal{H}}}}}_{i}^{{\prime} }\). By deriving the most general possible form of a spectrum-preserving Hamiltonian encoding, and then imposing natural locality conditions, the authors arrive at the following definition.
Definition 3
(Local Hamiltonian encoding11) A local Hamiltonian encoding is a map \({{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}:{{{\rm{Lin}}}}({\otimes }_{i=1}^{n}{{{{\mathcal{H}}}}}_{i})\to {{{\rm{Lin}}}}({\otimes }_{i=1}^{n}{{{{\mathcal{H}}}}}_{i}^{{\prime} })\) of the form
$${{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}(M)=V(M\otimes P+\bar{M}\otimes Q){V}^{{{\dagger}} }\,,$$
(1)
where P and Q are locally distinguishable orthogonal projectors on an ancillary space \({{{\mathcal{A}}}}={\otimes _{i=1}^{n}}{{{{\mathcal{A}}}}_{i}}\), and \(V={ \otimes _{i=1}^{n}}{{V}_{i}}\) where \({V}_{i}\in {{{\rm{Isom}}}}({{{{\mathcal{H}}}}}_{i}\otimes {{{{\mathcal{A}}}}}_{i},{{{{\mathcal{H}}}}}_{i}^{{\prime} })\) for all i. Here \(\bar{M}\) denotes the complex conjugate of the matrix M.
Projectors \(P,Q\in {{{\rm{Proj}}}}({\otimes }_{i}{{{{\mathcal{A}}}}}_{i})\) are locally distinguishable if, for all i, there exist orthogonal projectors \({P}_{i},{Q}_{i}\in {{{\rm{Proj}}}}({{{{\mathcal{A}}}}}_{i})\) such that (Pi ⊗ I)P = P and (Qi ⊗ I)Q = Q. Generally, we consider the case of rank(P) > 0 (referred to as standard11), for which one can define a corresponding state encoding
$${{{{\mathcal{E}}}}}_{{{{\rm{state}}}}}(\rho )=V(\rho \otimes \tau ){V}^{{{\dagger}} }\,,$$
(2)
where τ is a state on \({{{\mathcal{A}}}}\) satisfying Pτ = τ.
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
((Δ, η, ϵ)-simulation11) A Hamiltonian \({H}^{{\prime} }\in {{{\rm{Herm}}}}({{{{\mathcal{H}}}}}^{{\prime} })={{{\rm{Herm}}}}({\otimes }_{i=1}^{n}{{{{\mathcal{H}}}}}_{i}^{{\prime} })\) is said to (Δ, η, ϵ)-simulate a Hamiltonian \(H\in {{{\rm{Herm}}}}({{{\mathcal{H}}}})={{{\rm{Herm}}}}({\otimes }_{i=1}^{n}{{{{\mathcal{H}}}}}_{i})\) if there exists a local encoding (Definition 3) \({{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}(M)=V(M\otimes P+\bar{M}\otimes Q){V}^{{{\dagger}} }\) such that
(i)
There exists an encoding \({\tilde{{{{\mathcal{E}}}}}}_{{{{\rm{obs}}}}}(M)=\tilde{V}(M\otimes P+\bar{M}\otimes Q){\tilde{V}}^{{{\dagger}} }\) (where \(\tilde{V}\in {{{\rm{Isom}}}}({{{\mathcal{H}}}}\otimes {{{\mathcal{A}}}},{{{{\mathcal{H}}}}}^{{\prime} })\) need not have a tensor product structure as in Definition 3) such that \(\parallel V-\tilde{V}\parallel \le \eta\) and \({\tilde{{{{\mathcal{E}}}}}}_{{{{\rm{obs}}}}}({{{\rm{I}}}})={P}_{\le \Delta ({H}^{{\prime} })}\) is the projection onto the low-energy (≤ Δ) subspace of \({H}^{{\prime} }\), and
(ii)
\(\parallel {P}_{\le \Delta ({H}^{{\prime} })}{H}^{{\prime} }{P}_{\le \Delta ({H}^{{\prime} })}-{\tilde{{{{\mathcal{E}}}}}}_{{{{\rm{obs}}}}}(H)\parallel \le \epsilon\).
This approach (later generalised by Apel et al.46 and refined with resource constraints by Zhou et al.16) 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.
Framework
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}_{\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 Ω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 Ωobs. We denote by \({{{{\mathcal{H}}}}}^{{\prime} }\) the Hilbert space corresponding to the simulator system, and for \(t\in (0,\, {t}_{\max })\) we write \({T}_{t}:D({{{{\mathcal{H}}}}}^{{\prime} })\to D({{{{\mathcal{H}}}}}^{{\prime} })\) for the family of time evolution quantum channels implemented by the simulator, where \(D({{{{\mathcal{H}}}}}^{{\prime} })\) is the set of density matrices on \({{{{\mathcal{H}}}}}^{{\prime} }\). This approach, in which we view simulations in terms of individual observables rather than the entire Hamiltonian, has been considered in earlier work25,26,27.
The minimal requirement for a simulator is that it should approximate the expectation values of the elements of Ωobs. That is, \({{{\rm{tr}}}}(O{e}^{-iHt}\rho {e}^{iHt})\) should be close to \({{{\rm{tr}}}}({O}^{{\prime} }{T}_{t}({\rho }^{{\prime} }))\) for all ρ ∈ Ωstate and O ∈ Ωobs, where \({\rho }^{{\prime} }\) and \({O}^{{\prime} }\) 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 ρ and O, with \({{{{\mathcal{H}}}}}^{{\prime} }\) a space large enough to contain all of them and by encoding ρ into several copies. However, this would violate the size-independence requirement of Definition 1. if Ωobs and Ω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}}}}}_{{{{\rm{state}}}}}:D({{{\mathcal{H}}}})\to D({{{{\mathcal{H}}}}}^{{\prime} })\). Correspondingly, to accommodate for quantum outputs, we require the observable encoding \(O\mapsto {O}^{{\prime} }\) to be a unital and completely positive map \({{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}:{{{\rm{Herm}}}}({{{\mathcal{H}}}})\to {{{\rm{Herm}}}}({{{{\mathcal{H}}}}}^{{\prime} })\). This ensures that the Hilbert-Schmidt dual operator \({{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}^{*}\) is a quantum channel, so measurement of \({{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}(O)\) on \({\rho }^{{\prime} }\) can equivalently be thought of as a measurement of O on a decoded state \({{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}^{*}(\rho )\). 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 = ∑kOk (a task, for example, useful for variational quantum algorithms47), in the following way. Often the Ok 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 Ok each time (this process can be sped up by combining simultaneously measurable terms48), and summing the average results.
The above discussion leads us to the following definition, which is illustrated in Fig. 2.
Definition 5
(Analogue quantum simulation) Given a set of states Ωstate on a Hilbert space \({{{\mathcal{H}}}}\), a normalised set of observables Ωobs (i.e. ∥O∥ = 1 for all O ∈ Ωobs, where ∥ ⋅ ∥ denotes the operator norm), a time \({t}_{\max } > 0\), a Hamiltonian \(H\in {{{\rm{Herm}}}}({{{\mathcal{H}}}})\), and ϵ > 0, we say that a family of quantum channels \({T}_{t}:D({{{{\mathcal{H}}}}}^{{\prime} })\to D({{{{\mathcal{H}}}}}^{{\prime} })\), for \(t\in (0,{t}_{\max })\) simulates H with respect to Ωstate and Ωobs with accuracy ϵ if there exists
1.
A state encoding quantum channel \({{{{\mathcal{E}}}}}_{{{{\rm{state}}}}}:D({{{\mathcal{H}}}})\to D({{{\mathcal{H}}}}^{\prime} )\) which maps states to the simulator Hilbert space \({{{{\mathcal{H}}}}}^{{\prime} }\),
2.
An observable encoding, given by a unital and completely positive map \({{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}:\,{\mbox{Herm}}\,({{{\mathcal{H}}}})\to \,{\mbox{Herm}}\,({{{{\mathcal{H}}}}}^{{\prime} })\),
such that
$$\left\vert \right.{{{\rm{tr}}}}({{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}(O)({T}_{{t}^{\circ}} \, {{{{\mathcal{E}}}}}_{{{{\rm{state}}}}}) \, (\rho ))-{{{\rm{tr}}}}\left.(O({e}^{-itH}\rho {e}^{itH}))\right)\left\vert \right.\le \epsilon \,,$$
(3)
for all ρ ∈ Ωstate, O ∈ Ωobs, and \(t\in (0,{t}_{\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 semigroup28,29. It should be noted also that Definition 5 could equivalently have been phrased in terms of a set of POVMs rather than observables Ωobs. We use the latter for convenience in relating our work to other results. It is plausible that one could engineer a time-dependent observable observable encoding \({{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}\), but here we restrict our focus to the time-independent case to avoid the complexity of the simulation task being hidden in this step.
By the triangle inequality, (3) holds for any convex combination of the states and observables in Ωstate and Ωobs respectively, so we could without loss of generality assume that the two sets are convex to begin with.
Often the simulation channels Tt in Definition 5 are taken simply as time evolution under some simulator Hamiltonian \({H}^{{\prime} }\in {{{\rm{Herm}}}}({{{{\mathcal{H}}}}}^{{\prime} })\), 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 setup49. 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 criterion III of Fig. 5. 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 Tt should not require engineering a system of size, which grows more than linearly in n, or boundlessly scaling interaction energies. Another important constraint is that Tt should not include the use of adaptive channels based on feed-forward measurements—hence distinguishing the process from digital quantum computation.
We note that Hamiltonian models of quantum computation such as quantum walks50 and previous notions of dynamical Hamiltonian simulation51 are not consistent with our definition of analogue simulation: such constructions also incur scalings in both the system size and in necessary evolution time (corresponding to scalings in interaction strength, if time is normalised) which violate the size-independence conditions of Definition 1.
Local encodings
Although Definition 5 is phrased in terms of general encoding maps, it is practically useful to ensure that states and observables are encoded in a way that is both practical to implement and behaves favourably with respect to noise. In this section, we present such a notion of local encodings and state some basic properties; proofs are contained in Supplementary Note 1. A similar discussion is presented for the stronger case of local Hamiltonian encodings by Cubitt et al.11, and a discussion of the stability of local observable measurements to local noise is given by Trivedi et al.27.
Definition 6
(Local state encoding) Let \({{{\mathcal{H}}}}={\otimes }_{i=1}^{n}{{{{\mathcal{H}}}}}_{i}\) and \({{{{\mathcal{H}}}}}^{{\prime} }={\otimes }_{j=1}^{{n}^{{\prime} }}{{{{\mathcal{H}}}}}_{j}^{{\prime} }\). We say that a state encoding \({{{{\mathcal{E}}}}}_{{{{\rm{state}}}}}:D({{{\mathcal{H}}}})\to D({{{{\mathcal{H}}}}}^{{\prime} })\) is local if it has a Stinespring representation of the form
$${{{{\mathcal{E}}}}}_{{{{\rm{state}}}}}(\rho )={{{{\rm{tr}}}}}_{E}(U(\rho \otimes \left\vert 0\right\rangle {\left\langle 0\right\vert }_{F}){U}^{{{\dagger}} })\,,$$
(4)
where F = ⊗ kFk and E = ⊗ lEl are ancillary systems and \(U\in {{{\rm{U}}}}({{{\mathcal{H}}}}\otimes F,{{{{\mathcal{H}}}}}^{{\prime} }\otimes E)\) is a constant-depth quantum circuit.
It is immediate that constant-depth quantum circuits (built from one-qubit and two-qubit gates) preserve locality. That is, given a local operator A on \({{{\mathcal{H}}}}\otimes F\), the operator UAU† is local (acting on the forward light cone of the support of A) on \({{{{\mathcal{H}}}}}^{{\prime} }\otimes E\), and similarly for the inverse U†. In fact, it is known in the theory of quantum cellular automata that this constraint is equivalent to representability as a constant-depth quantum circuit52.
For simulating physical systems, one particularly desirable feature of a simulator is local error back-propagation. That is, local noise on the simulator system should correspond in some way to local (perhaps realistic) noise on the target system. Ideally, we would like to prove that for any state \(\rho \in D({{{\mathcal{H}}}})\) and local error channel \({{{{\mathcal{N}}}}}^{{\prime} }:D({{{{\mathcal{H}}}}}^{{\prime} })\to D({{{{\mathcal{H}}}}}^{{\prime} })\) on the simulator, there exists a corresponding local error channel \({{{\mathcal{N}}}}:D({{{\mathcal{H}}}})\to D({{{\mathcal{H}}}})\) on the target system satisfying
$${{{{\mathcal{N}}}}}^{{\prime} }\circ \, \, {{{{\mathcal{E}}}}}_{{{{\rm{state}}}}}(\rho )\mathop{=}^{?}{{{{\mathcal{E}}}}}_{{{{\rm{state}}}}}\circ \, \, {{{\mathcal{N}}}}(\rho ) \, .$$
(5)
However, we cannot hope to prove this in general, since the noise operator \({{{{\mathcal{N}}}}}^{{\prime} }\) may take the simulator system outside the image of \({{{{\mathcal{E}}}}}_{{{{\rm{state}}}}}\). Instead we have a slightly weaker version of this statement, which is a direct consequence of the causal structure of local state encodings.
Proposition 7
(Local error back-propogation) Let \({{{{\mathcal{E}}}}}_{{{{\rm{state}}}}}:D({{{\mathcal{H}}}})\to D({{{{\mathcal{H}}}}}^{{\prime} })\) be a local state encoding as in Definition 6, and let \({{{{\mathcal{N}}}}}^{{\prime} }:D({{{{\mathcal{H}}}}}^{{\prime} })\to D({{{{\mathcal{H}}}}}^{{\prime} })\) be a channel whose Kraus operators \(\{{X}_{k}^{{\prime} }\}\) each act on O(1) sites in \({{{{\mathcal{H}}}}}^{{\prime} }\). Then there exists a channel \({{{\mathcal{N}}}}:D({{{\mathcal{H}}}}\otimes F)\to D({{{\mathcal{H}}}}\otimes F)\) whose Kraus operators {Xk} each act on O(1) sites in \({{{\mathcal{H}}}}\otimes F\), and such that for all \(\rho \in {{{\mathcal{H}}}}\),
$${{{{\mathcal{N}}}}}^{{\prime} }\circ \, \, {{{{\mathcal{E}}}}}_{{{{\rm{state}}}}}(\rho )={{{{\rm{tr}}}}}_{E}(U{{{\mathcal{N}}}}(\rho \otimes \left\vert 0\right\rangle {\left\langle 0\right\vert }_{F}){U}^{{{\dagger}} })\,.$$
(6)
In other words, local noise on the simulator corresponds to local noise on the target system and ancillary encoding system. The corresponding result with locality replaced by geometric locality holds in the case when the light cones of U are local with respect to the underlying geometry of the simulator and target systems.
Similarly, we have local forward-propogation under such an encoding, in the sense that local operations on a site \({{{{\mathcal{H}}}}}_{i}\) to \(\rho \in D({{{\mathcal{H}}}})\) will not affect the reduced density matrix \({{{{\rm{tr}}}}}_{A}({{{{\mathcal{E}}}}}_{{{{\rm{state}}}}}(\rho ))\), where A is the forward light cone of \({{{{\mathcal{H}}}}}_{i}\) under U in \({{{{\mathcal{H}}}}}^{{\prime} }\).
We define local observable encodings analogously to the state encoding case.
Definition 8
(Local observable encoding) Let \({{{\mathcal{H}}}}={\otimes }_{i=1}^{n}{{{{\mathcal{H}}}}}_{i}\) and \({{{{\mathcal{H}}}}}^{{\prime} }={\otimes }_{j=1}^{{n}^{{\prime} }}{{{{\mathcal{H}}}}}_{j}^{{\prime} }\). We say that an observable encoding \({{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}:{{{\rm{Herm}}}}({{{\mathcal{H}}}})\to {{{\rm{Herm}}}}({{{{\mathcal{H}}}}}^{{\prime} })\) is local if it is the adjoint (with respect to the Hilbert-Schmidt inner product) of a local state encoding.
It is immediate from this definition that one can measure the encoded observable \({{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}(O)\) by first applying the constant-depth quantum circuit \({{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}^{*}:D({{{{\mathcal{H}}}}}^{{\prime} })\to D({{{\mathcal{H}}}})\) to \({\rho }^{{\prime} }\in D({{{{\mathcal{H}}}}}^{{\prime} })\), and then measuring O. When O is local, we can alternatively implement the measurement via a local POVM directly on the simulator system.
Proposition 9
(Encoded measurements) Let \({{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}\) be a local observable encoding as in Definition 8, and let O be a local operator on \({{{\mathcal{H}}}}\). Then \({{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}(O)\) can be measured using a local POVM on \({{{{\mathcal{H}}}}}^{{\prime} }\).
Applications of the framework
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 of Cubitt et al.11 (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 10 provides a formal statement of this fact (proved in Supplementary Note 2) 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 \(\{\left\vert \downarrow \right\rangle,\left\vert 0\right\rangle,\left\vert \uparrow \right\rangle \}\). We write \({P}_{0}^{(j)}=\left\vert 0\right\rangle \left\langle 0\right\vert\) and \({P}_{\uparrow }^{(j)}=\left\vert \uparrow \right\rangle \left\langle \uparrow \right\vert\), where the superscript indicates that the projectors act on the jth qutrit.
Proposition 10
Let \({{{\mathcal{H}}}}={({{\mathbb{C}}}^{3})}^{\otimes n}\) be the space of n qutrits acted on by the Hamiltonian
$${H}_{n}=\mathop{\sum}_{j=1}^{n}({P}_{0}^{(j)}+{P}_{\uparrow }^{(j)})\,.$$
(7)
Suppose \({H}_{n}^{{\prime} }={\sum }_{j=1}^{K}{h}_{j}^{{\prime} }\) is a k-local Hamiltonian on \({{{{\mathcal{H}}}}}^{{\prime} }={({{\mathbb{C}}}^{2})}^{\otimes m}\), where m = O(n1+α), for α ≥ 0 and k = O(1). Assume the interaction hypergraph of \({H}_{n}^{{\prime} }\) has degree bounded by d = O(1).
If \({H}_{n}^{{\prime} }\) is a (Δ, η, ϵ)-simulation for Hn in the sense of Definition 4, for η ∈ (0, 1) and ϵ ≥ 0, then
$${\max }_{j}\parallel {h}_{j}^{{\prime} }\parallel=\Omega ({n}^{1-\alpha }(1-{\eta }^{2}))\,.$$
(8)
From (8) 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. This constitutes a violation of the requirements of Definition 1. and imposes an unnecessary experimental requirement for the task of simulating non-interacting qutrits. 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. 1. 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 10, we can simulate all observables under Hn on \({{{{\mathcal{H}}}}}^{{\prime} }={\otimes }_{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}\,,$$
(9)
encoding each qutrit into two qubits. To realise a simulator in the sense of Definition 5, we let
$${{{{\mathcal{E}}}}}_{{{{\rm{state}}}}}:\rho \, \mapsto {V}^{\otimes n}\rho {({V}^{\otimes n})}^{{{\dagger}} }\,,\quad {{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}:O \, \mapsto {V}^{\otimes n}O{({V}^{\otimes n})}^{{{\dagger}} }\,,$$
(10)
and
$${T}_{t}={e}^{-it{{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}({H}_{n})}(\cdot ){e}^{it{{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}({H}_{n})}\,,$$
(11)
which is just time evolution under a 2-local Hamiltonian with bounded-strength interactions.
Although Proposition 10 does not necessarily rule out simulations in which the n qutrits are encoded into Ω(n2) qubits, such approaches suffer from a different problem. Generally, if each qudit in a D-dimensional system is encoded into Ω(nα) qudits for α > 0, whilst keeping the dimension fixed, then the inflated system size will necessarily cause the distances between encoded sites to grow with n. In a system of interacting qutrits (for which the proof of Proposition 10 still holds), this means that scaling interactions can be necessary to overcome Lieb-Robinson bounds and ensure that correlations can spread sufficiently fast through the enlarged system. The following simple geometric lemma provides some intuition for a quantitative lower bound on the growing length scales in such situations.
Lemma 11
Let \({\{{x}_{i}\}}_{i=1}^{n}\) be the points in a hypercube of side length L ~ n1/D in the square lattice \({x}_{i}\in {{\mathbb{Z}}}^{D}\). Let \({{{\mathcal{E}}}}:{x}_{i}\mapsto {X}_{i}\subseteq {{\mathbb{Z}}}^{D}\) be a map which encodes each point xi into a connected set of points in \({{\mathbb{Z}}}^{D}\) such that ∣Xi∣ = Ω(nα) and \({X}_{i}\cap {X}_{j}={{\emptyset}}\). Let \(d(x,y):{{\mathbb{Z}}}^{D}\times {{\mathbb{Z}}}^{D}\to {\mathbb{Z}}\) be the taxicab metric on \({{\mathbb{Z}}}^{D}\).
For a radius R = O(L), and any \(y\in {{\mathbb{Z}}}^{D}\), the number of encoded points intersecting with the ball of radius R centred at y is bounded by
$$| {B}_{R}(y)| :=| \{{X}_{i}:{\mbox{}}\exists x\in {X}_{i}\,{\mbox{with}}\,d(x,y)\le R{\mbox{}}\}|=O\left({n}^{1-\min \{\alpha,1/D\}}\right)\,.$$
(12)
Letting \(\lambda=\min \{\alpha,\, 1/D\}\), we see that there are at most O(n1−λ) sites Xj within radius R = O(L) = O(n1/D) of any Xi. On the other hand, there are at least Ω(n1−λ) of the xj within radius O(n(1−λ)/D) of xi in the original lattice. In particular, this implies that there exist a pair of sites xi, xj with d(xi, xj) = O(n(1−λ)/D) whose encodings have d(Xi, Xj) = Ω(n1/D)—in the encoded system, the distance is increased by a factor of nλ/D.
The scalings here apply as a result of the requirement that analogue quantum simulators reproduce the dynamics of a target system. In other situations, such as adiabatic quantum simulation in which an approximately simulated ground state is the only requirement, encodings with superlinear qubit overhead are possible53,54.
Noisy analogue simulators
Suppose we have quantum channels Tt, for \(t\in (0,\, {t}_{\max })\) which simulate some \(H\in {{{\rm{Herm}}}}({{{\mathcal{H}}}})\) with respect to Ωstate and Ωobs up to accuracy ϵ as in Definition 5, corresponding to encoding maps \({{{{\mathcal{E}}}}}_{{{{\rm{state}}}}}\) and \({{{{\mathcal{E}}}}}_{{{{\rm{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}}}}}}_{{{{\rm{state}}}}}\), and \({\tilde{{{{\mathcal{E}}}}}}_{{{{\rm{obs}}}}}\). For any O ∈ Ωobs, ρ ∈ Ωstate, we may bound the additional error in observable expectation values incurred by the noisy maps by
$$ | {{{\rm{tr}}}}({{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}(O)({T}_{t}\circ \;\; {{{{\mathcal{E}}}}}_{{{{\rm{state}}}}})(\rho ))-{{{\rm{tr}}}}({\tilde{{{{\mathcal{E}}}}}}_{{{{\rm{obs}}}}}(O)\left.\right({\tilde{T}}_{t}\circ \;\; {\tilde{{{{\mathcal{E}}}}}}_{{{{\rm{state}}}}}(\rho ))| \\ \quad=| {{{\rm{tr}}}}(O\left({{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}^{*}\circ \;\; {T}_{t}\circ \;\; {{{{\mathcal{E}}}}}_{{{{\rm{state}}}}}-{\tilde{{{{\mathcal{E}}}}}}_{{{{\rm{obs}}}}}^{*}\circ \;\; {\tilde{T}}_{t}\circ \;\; {\tilde{{{{\mathcal{E}}}}}}_{{{{\rm{state}}}}}\right)(\rho ))\\ \quad \le \parallel {{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}^{*}\circ \;\; {T}_{t}\circ \;\; {{{{\mathcal{E}}}}}_{{{{\rm{state}}}}}-{\tilde{{{{\mathcal{E}}}}}}_{{{{\rm{obs}}}}}^{*}\circ \;\; {\tilde{T}}_{t}\circ \;\; {\tilde{{{{\mathcal{E}}}}}}_{{{{\rm{state}}}}}{\parallel }_{1\to 1}\\ \quad \le \parallel {{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}^{*}-{\tilde{{{{\mathcal{E}}}}}}_{{{{\rm{obs}}}}}^{*}{\parallel }_{1\to 1}+\parallel {T}_{t}-{\tilde{T}}_{t}{\parallel }_{1\to 1}+\parallel {{{{\mathcal{E}}}}}_{{{{\rm{state}}}}}-{\tilde{{{{\mathcal{E}}}}}}_{{{{\rm{state}}}}}{\parallel }_{1\to 1}\,,$$
(13)
where ∥⋅∥1→1 denotes the one-to-one norm \(\parallel \Lambda {\parallel }_{1\to 1}=\mathop{\sup }_{\rho }\parallel \Lambda (\rho ){\parallel }_{1}\) (defined as the induced trace norm55—note that this is in particular upper bounded by the diamond norm), and \({{{{\mathcal{E}}}}}^{*}\) denotes the Hilbert-Schmidt dual of a superoperator \({{{\mathcal{E}}}}\). Hence the noisy simulator \({\tilde{T}}_{t}\) also simulates H with respect to Ωstate and Ωobs, up to error
$${\epsilon }^{{\prime} }\le \epsilon+{\sup }_{t}\parallel \!{T}_{t}-{\tilde{T}}_{t}{\parallel }_{1\to 1}+\parallel {{{{\mathcal{E}}}}}_{{{{\rm{state}}}}}-{\tilde{{{{\mathcal{E}}}}}}_{{{{\rm{state}}}}}{\parallel }_{1\to 1}+\!\parallel {{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}^{*}-{\tilde{{{{\mathcal{E}}}}}}_{{{{\rm{obs}}}}}^{*}{\parallel }_{1\to 1}\,.$$
(14)
Local Hamiltonian simulation in a subspace
Suppose that \({H}^{{\prime} }\) is a (Δ, η, ϵ)-simulation of H as defined by Cubitt et al.11 (Definition 4), corresponding to encodings \({{{{\mathcal{E}}}}}_{{{{\rm{state}}}}}\) and \({{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}\), with the projector Q = 0. Here we show that the time evolution channel under \({H}^{{\prime} }\), \((\cdot )\mapsto {e}^{-it{H}^{{\prime} }}(\cdot ){e}^{it{H}^{{\prime} }}\) gives a simulation in our sense, Definition 5.
We make use of the following lemmas. Lemma 12 ensures that measurement and time evolution are consistent with the encodings of Definition 4, and Lemma 13 bounds the error of (Δ, η, ϵ)-simulations under time evolution.
Lemma 12
(Cubitt et al., Proposition 411) If \({{{{\mathcal{E}}}}}_{{{{\rm{state}}}}}\) and \({{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}\) are encodings as in Definition 4 and (2), then for all observables O and states ρ on the target system \({{{\mathcal{H}}}}\),
$${{{\rm{tr}}}}({{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}(O){{{{\mathcal{E}}}}}_{{{{\rm{state}}}}}(\rho ))={{{\rm{tr}}}}(O\rho )\,.$$
(15)
Moreover if the encoding is standard (rank(P) > 0 in Definition 4) then
$${e}^{-i{{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}(H)t}{{{{\mathcal{E}}}}}_{{{{\rm{state}}}}}(\rho ){e}^{i{{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}(H)t}={{{{\mathcal{E}}}}}_{{{{\rm{state}}}}}\left({e}^{-iHt}\rho {e}^{iHt}\right)\,.$$
(16)
Lemma 13
(Cubitt et al., Proposition 2811) Let \({H}^{{\prime} }\) be a (Δ, η, ϵ)-simulation of H in the sense of Definition 4 corresponding to encodings \({{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}\), \({{{{\mathcal{E}}}}}_{{{{\rm{state}}}}}\). If \({\rho }^{{\prime} }\) is a state in the simulator system \({{{{\mathcal{H}}}}}^{{\prime} }\) satisfying \({{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}({{{\rm{I}}}}){\rho }^{{\prime} }={\rho }^{{\prime} }\), then for all t
$$\parallel {e}^{-i{H}^{{\prime} }t}{\rho }^{{\prime} }{e}^{i{H}^{{\prime} }t}-{e}^{-i{{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}(H)t}{\rho }^{{\prime} }{e}^{i{{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}(H)t}{\parallel }_{1}\le 2\epsilon t+4\eta \,.$$
(17)
Combining these lemmas, we see that for any observable O and state ρ on \({{{\mathcal{H}}}}\),
$$ | {{{\rm{tr}}}}({{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}(O){e}^{-i{H}^{{\prime} }t}{{{{\mathcal{E}}}}}_{{{{\rm{state}}}}}(\rho ){e}^{i{H}^{{\prime} }t})-{{{\rm{tr}}}}(O{e}^{-iHt}\rho {e}^{iHt})| \\ \quad=\left| {{{\rm{tr}}}}\left({{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}(O)\left({e}^{-i{H}^{{\prime} }t}{{{{\mathcal{E}}}}}_{{{{\rm{state}}}}}(\rho ){e}^{i{H}^{{\prime} }t}-{e}^{-i{{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}(H)t}{{{{\mathcal{E}}}}}_{{{{\rm{state}}}}}(\rho ){e}^{i{{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}(H)t}\right)\right)\right| \\ \quad \le \parallel \! O \!\parallel (2\epsilon t+4\eta )\,.$$
(18)
Hence the channels \({T}_{t}:{\rho }^{{\prime} }\mapsto {e}^{-i{H}^{{\prime} }t}{\rho }^{{\prime} }{e}^{i{H}^{{\prime} }t}\), for \(t\in (0,{t}_{\max })\) simulate H in the sense of Definition 5 with respect to any Ωstate and Ωobs, up to error
$${\epsilon }^{{\prime} }\le 2\epsilon {t}_{\max }+4\eta .$$
(19)
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 Cubitt et al.11 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 Ω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 dynamics24. 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 computers25,26, and more recently in the setting of analogue simulators27. We explain here how the latter fits into our framework.
Consider the case of a Hamiltonian Hn on a d-dimensional lattice of n qubits \({{{\mathcal{H}}}}\cong {({{\mathbb{C}}}^{2})}^{\otimes n}\), such that
$${H}_{n}=\mathop{\sum}_{x=1}^{n}{h}_{x}\,,$$
(20)
where the hx is a nearest-neighbour local interaction with ∥hx∥ ≤ 1, translated to position x in the lattice, so that Hn is translationally invariant.
If one is only interested in simulating the finite-time dynamics of a few local observables Ωobs which are contained within a small neighbourhood of the origin, starting from a state \(\rho=\left\vert 0\right\rangle {\left\langle 0\right\vert }^{\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. 7. This situation is studied by Trivedi et al.27, in particular for the thermodynamic limit n → ∞.
Fig. 7: Simulation with Lieb-Robinson bounds.
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.
Let \({H}_{m}={\sum }_{y=1}^{m}{h}_{y}\) be the simulator Hamiltonian, defined identically to Hn but on a lattice of size m < n, \({{{{\mathcal{H}}}}}^{{\prime} }\cong {({{\mathbb{C}}}^{2})}^{\otimes m}\). We encode ρ and O simply by restricting them to the smaller subsystem. Then a simulation of an observable O ∈ Ωobs up to accuracy ϵ, satisfying
$$| {{{\rm{tr}}}}(O{e}^{-i{H}_{n}t}\rho {e}^{i{H}_{n}t})-{{{\rm{tr}}}}({{{{\mathcal{E}}}}}_{{{{\rm{obs}}}}}(O){e}^{-i{H}_{m}t}{{{{\mathcal{E}}}}}_{{{{\rm{state}}}}}(\rho ){e}^{i{H}_{m}t})| \le \epsilon \,,$$
(21)
can be accomplished in the large-n regime for all \(t\in (0,{t}_{\max })\) if one takes \(m=O\left({\log }^{d}(1/\epsilon )+{t}_{\max }^{d}\right)\) (see Trivedi et al.27, Lemma 1).
Modular encodings and gadgets
In this section, we focus on the case of a simulator channel Tt given by time evolution under a local simulator Hamiltonian \({H}^{{\prime} }\), which should reproduce the dynamics of the local target Hamiltonian H = ∑iHi. In light of the size-independence requirement of Definition 1., it is natural to encode each Hi term separately into some term \({H}_{i}^{{\prime} }\), but systematically doing so is a non-trivial task: we need the encoded terms to interact with each other in a way that mimics the original system.
This problem can be tackled using perturbative gadgets. Perturbative gadgets were initially introduced by Kempe et al.42 as a means of proving QMA-completeness of the 2-local Hamiltonian problem by reduction from the three-local case30, 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 hypergraph17 and, in general, to reduce Hamiltonians to more restrictive families of interactions44,56,57. Moreover, beyond Hamiltonian complexity-theoretic results, gadgets can be tailored to improve the performance of variational quantum algorithms34.
In this work, we introduce a formalism which we argue encompasses any attempt at gadgetisation, in a sense which we make precise Definition (14), in order to prove general properties of such constructions. Note that our approach, and the (η, ϵ) accuracy parameters, are closely related to those used in other definitions of simulation11,18. 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}^{{\prime} }\) cannot reduce the locality of interactions (for example, reducing a 3-local Hamiltonian to a 2-local Hamiltonian).
The setup is as follows: we consider a large system \({{{\mathcal{H}}}}={\otimes }_{i=1}^{n}{{{{\mathcal{H}}}}}_{i}\), within which a local interaction \(H\in {{{\rm{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}^{{\prime} }\in {{{\rm{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}^{{\prime} }\) should (when restricted to some subspace defined by a projector \({P}^{{\prime} }\)) approximately reproduce the full spectrum of H. Moreover, for \({H}^{{\prime} }\) 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}^{{\prime} }\in {{{\rm{Proj}}}}({{{\mathcal{H}}}}\otimes {{{\mathcal{A}}}})\) such that \({P}^{{\prime} }({H}^{{\prime} }+{H}_{{{{\rm{else}}}}}\otimes {{{\rm{I}}}}){P}^{{\prime} }\) approximates the spectrum of H + Helse, for any \({H}_{{{{\rm{else}}}}}\in {{{\rm{Herm}}}}({{{\mathcal{H}}}})\) (see Fig. 3a). We formalise this with the following definition.
Definition 14
((ζ, ϵ)-gadget property) Given a Hamiltonian \(H\in {{{\rm{Herm}}}}({{{\mathcal{H}}}})\) acting on a system \({{{\mathcal{H}}}}={\otimes }_{i=1}^{n}{{{{\mathcal{H}}}}}_{i}\), and \({H}^{{\prime} }\in {{{\rm{Herm}}}}({{{\mathcal{H}}}}\otimes {{{\mathcal{A}}}})\) for \({{{\mathcal{A}}}}\) an ancillary system, we say that \(({H}^{{\prime} },\, {{{\mathcal{A}}}})\) satisfies the (ζ, ϵ)-gadget property for H if there exists \({P}^{{\prime} }\in {{{\rm{Proj}}}}({{{\mathcal{H}}}}\otimes {{{\mathcal{A}}}})\), \(\tilde{P}\in {{{\rm{Proj}}}}({{{\mathcal{A}}}})\setminus \{0\}\) such that, for any \({H}_{{{{\rm{else}}}}}\in {{{\rm{Herm}}}}({{{\mathcal{H}}}})\), there exists a unitary \({\tilde{U}}_{{H}_{{{{\rm{else}}}}}}\in {{{\rm{U}}}}({{{\mathcal{H}}}}\otimes {{{\mathcal{A}}}})\) with
$$\parallel {P}^{{\prime} }({H}^{{\prime} }+{H}_{{{{\rm{else}}}}}\otimes {{{\rm{I}}}}){P}^{{\prime} }-{\tilde{U}}_{{H}_{{{{\rm{else}}}}}}\left((H+{H}_{{{{\rm{else}}}}})\otimes \tilde{P}\right){\tilde{U}}_{{H}_{{{{\rm{else}}}}}}^{{{\dagger}} }\parallel \le \epsilon+\zeta \parallel {H}_{{{{\rm{else}}}}}\parallel \,.$$
(22)
In other words, \(({H}^{{\prime} },{{{\mathcal{A}}}})\) satisfies the (ζ, ϵ)-gadget property for H if, when restricted a subspace defined by \({P}^{{\prime} }\), \({H}^{{\prime} }+{H}_{{{{\rm{else}}}}}\otimes {{{\rm{I}}}}\) approximates the spectrum of H + Helse up to error ϵ + ζ∥Helse∥. Notice that \(\tilde{P}\) is almost arbitrary; its rank determines the multiplicity of each eigenvalue of H + Helse in the simulator system, but otherwise it can be rotated by \({\tilde{U}}_{{H}_{{{{\rm{else}}}}}}\), which rotates the eigenvectors of \((H+{H}_{{{{\rm{else}}}}})\otimes \tilde{P}\) approximately onto those of \({P}^{{\prime} }({H}^{{\prime} }+{H}_{{{{\rm{else}}}}}\otimes {{{\rm{I}}}}){P}^{{\prime} }\).
As noted by Cubitt et al.11, 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 14 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 Helse in Definition 14 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 14 is a natural requirement, it is not convenient to work with due to the appearance of the general Helse acting on the entire of \({{{\mathcal{H}}}}\), upon which \(\tilde{U}\) depends. The following alternative definition does not suffer from this problem.
Definition 15
((η, ϵ)-gadget) Let \(H\in {{{\rm{Herm}}}}({{{\mathcal{H}}}})\) be a Hamiltonian on a Hilbert space \({{{\mathcal{H}}}}\), and let \({{{\mathcal{A}}}}\) be an ancillary Hilbert space. For \({H}^{{\prime} }\in {{{\rm{Herm}}}}({{{\mathcal{H}}}}\otimes {{{\mathcal{A}}}})\), we say that \(({H}^{{\prime} },{{{\mathcal{A}}}})\) is a (η, ϵ)-gadget for H if there exists \(P\in {{{\rm{Proj}}}}({{{\mathcal{A}}}})\setminus \{0\}\) and \(U\in {{{\rm{U}}}}({{{\mathcal{H}}}}\otimes {{{\mathcal{A}}}})\) such that
$$\parallel U-{{{\rm{I}}}}\parallel \le \eta \,,\quad \parallel {P}^{{\prime} }{H}^{{\prime} }{P}^{{\prime} }-U(H\otimes P){U}^{{{\dagger}} }\parallel \le \epsilon \,,$$
(23)
where \({P}^{{\prime} }=U({{{\rm{I}}}}\otimes P){U}^{{{\dagger}} }\in {{{\rm{Proj}}}}({{{\mathcal{H}}}}\otimes {{{\mathcal{A}}}})\).
The advantage of Definition 15 is that it is stated in terms of a local rather than global property. Assuming that \(H,{H}^{{\prime} },{P}^{{\prime} }\) 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}^{{\prime} }\) is a gadget. This is in contrast with Definition 14, 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 15, 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, proved in Supplementary Note 3.
Theorem 16
((η, ϵ)-gadgets have the (ζ, ϵ)-gadget property) Suppose that \(({H}^{{\prime} },\, {{{\mathcal{A}}}})\) is a (η, ϵ)-gadget for H. Then \(({H}^{{\prime} },\, {{{\mathcal{A}}}})\) satisfies the (ζ, ϵ)-gadget property for H, where ζ = O(η).
Theorem 17
(The (ζ, ϵ)-gadget property requires a (η, ϵ)-gadget) Suppose that \(({H}^{{\prime} },{{{\mathcal{A}}}})\) satisfies the (ζ, ϵ)-gadget property for H, where H, \({H}^{{\prime} }\), and \({P}^{{\prime} }\) act on O(1) sites in \({{{\mathcal{H}}}}={\otimes }_{i=1}^{n}{{{{\mathcal{H}}}}}_{i}\). Then \(({H}^{{\prime} },\, {{{\mathcal{A}}}})\) is a \((\eta,{\epsilon }^{{\prime} })\)-gadget for H, where \(\eta=O(\epsilon )+O({\zeta }^{\frac{1}{2}})\) and \({\epsilon }^{{\prime} }=O(\epsilon )+O(\zeta )\).
The roles of the η and ϵ parameters are to bound the error in the eigenvectors and eigenvalues respectively. Roughly speaking, η quantifies how well the gadget combines with other terms, and ϵ quantifies the spectral error of the gadget in isolation. A good gadget requires both of these parameters to be small. In the next section we present a 3-to-2 local gadget which is an extreme case of this, with ϵ = 0 at the cost of a large η error.
Prior work in Hamiltonian complexity theory has focused on gadgetisation in the context of ground state estimation18,30,44 or simulation in a low-energy subspace11; as a result, a case of particular relevance is when \({P}^{{\prime} }\) projects onto the low-energy subspace of \({H}^{{\prime} }\). For \(\Delta \in {\mathbb{R}}\), we write \({P}_{\le \Delta ({H}^{{\prime} })}\) for the projector onto the span of the eigenvectors of \({H}^{{\prime} }\) with eigenvalues in the range ( − ∞, Δ).
Definition 18
((Δ, η, ϵ)-gadget) Let \(H\in {{{\rm{Herm}}}}({{{\mathcal{H}}}})\) be a Hamiltonian on a Hilbert space \({{{\mathcal{H}}}}\), and let \({{{\mathcal{A}}}}\) be an ancillary Hilbert space. For \({H}^{{\prime} }\in {{{\rm{Herm}}}}({{{\mathcal{H}}}}\otimes {{{\mathcal{A}}}})\), we say that \(({H}^{{\prime} },{{{\mathcal{A}}}})\) is a (Δ, η, ϵ)-gadget for H if there exists \(P\in {{{\rm{Proj}}}}({{{\mathcal{A}}}})\setminus \{0\}\), and \(U\in {{{\rm{U}}}}({{{\mathcal{H}}}}\otimes {{{\mathcal{A}}}})\) such that \({P}_{\le \Delta ({H}^{{\prime} })}=U({{{\rm{I}}}}\otimes P){U}^{{{\dagger}} }\), and
$$\parallel U-{{{\rm{I}}}}\parallel \le \eta \,,\quad \parallel {P}_{\le \Delta ({H}^{{\prime} })}{H}^{{\prime} }{P}_{\le \Delta ({H}^{{\prime} })}-U(H\otimes P){U}^{{{\dagger}} }\parallel \le \epsilon \,.$$
(24)
In other words, the pair \(({H}^{{\prime} },{{{\mathcal{A}}}})\) satisfy Definition 15, in the special case where we can use \({P}^{{\prime} }={P}_{\le \Delta ({H}^{{\prime} })}\).
Notice that Definition 18 imposes a significantly stronger requirement on \({H}^{{\prime} }\) than Definition 15; a priori there is no reason to expect that there will exist any choice of P and U such that \({P}_{\le \Delta ({H}^{{\prime} })}=U({{{\rm{I}}}}\otimes P){U}^{{{\dagger}} }\). Definitions Definition 15 and Definition 18 are sufficient to guarantee desirable combination properties, and are satisfied by widely-used constructions.
Examples of gadgets
Lemmas 4–7 of Bravyi et al.18 can be naturally adapted to give several constructions for (Δ, η, ϵ) gadgets, which we use to demonstrate that Definition 15 encompasses commonly-used techniques. In the following we take \({{{{\mathcal{H}}}}}^{{\prime} }={{{\mathcal{H}}}}\otimes {{{\mathcal{A}}}}\), and \({{{\mathcal{A}}}}\cong {{\mathbb{C}}}^{2}\). For V an operator on \({{{{\mathcal{H}}}}}^{{\prime} }\) we write it in block-diagonal form with respect to the basis of \({{{\mathcal{A}}}}\) as
$$V=\left(\begin{array}{cc}{V}_{00}&{V}_{01}\\ {V}_{10}&{V}_{11}\end{array}\right)\,,$$
(25)
where, for instance, \({V}_{00}=({{{\rm{I}}}}\otimes \left\langle 0\right\vert )V({{{\rm{I}}}}\otimes \left\vert 0\right\rangle )\).
Lemma 19
(First-order gadgets, adapted from Bravyi et al.18) Suppose \(H\in {{{\rm{Herm}}}}({{{\mathcal{H}}}})\) and \(V\in {{{\rm{Herm}}}}({{{{\mathcal{H}}}}}^{{\prime} })\) are such that
$$\parallel H-{V}_{00}\parallel \le \frac{\epsilon }{2}\,.$$
(26)
Then \({H}^{{\prime} }=\Delta {H}_{0}+V\) defines a (O(Δ), η, ϵ)-gadget for H, where \({H}_{0}={{{\rm{I}}}}\otimes \left\vert 1\right\rangle \left\langle 1\right\vert\), provided that Δ ≥ O(ϵ−1∥V∥2 + η−1∥V∥).
Lemma 20
(Second-order gadgets, adapted from Bravyi et al.18) Let \(H\in {{{\rm{Herm}}}}({{{\mathcal{H}}}})\), and suppose \({V}^{(1)},{V}^{(0)}\in {{{\rm{Herm}}}}({{{{\mathcal{H}}}}}^{{\prime} })\) are such that ∥V(1)∥, ∥V(0)∥ ≤ Λ, \({V}_{10}^{(0)}={V}_{01}^{(0)}={V}_{00}^{(1)}=0\), and
$$\parallel H-{V}_{00}^{(0)}+{V}_{01}^{(1)}{V}_{10}^{(1)}\parallel \le \frac{\epsilon }{2}\,.$$
(27)
Then \({H}^{{\prime} }=\Delta {H}_{0}+{\Delta }^{\frac{1}{2}}{V}^{(1)}+{V}^{(0)}\) is a (O(Δ), η, ϵ)-gadget for H, where \({H}_{0}={{{\rm{I}}}}\otimes \left\vert 1\right\rangle \left\langle 1\right\vert\), if
$$\Delta \ge O({\epsilon }^{-2}{\Lambda }^{6}+{\eta }^{-2}{\Lambda }^{2})\,.$$
(28)
Lemma 21
(Third-order gadgets, adapted from Bravyi et al.18) Let \(H\in {{{\rm{Herm}}}}({{{\mathcal{H}}}})\), and suppose \({V}^{(2)},{V}^{(1)},{V}^{(0)}\in {{{\rm{Herm}}}}({{{{\mathcal{H}}}}}^{{\prime} })\) are such that ∥V(2)∥, ∥V(1)∥, ∥V(0)∥ ≤ Λ, \({V}_{10}^{(1)}={V}_{01}^{(1)}={V}_{10}^{(0)}={V}_{01}^{(0)}=0\), \({V}_{00}^{(2)}=0\),
$$\parallel H-{V}_{00}^{(0)}-{V}_{01}^{(2)}{V}_{11}^{(2)}{V}_{10}^{(2)}\parallel \le \frac{\epsilon }{2}\,,\quad \,{\mbox{and}}\,\quad {V}_{00}^{(1)}={V}_{01}^{(2)}{V}_{10}^{(2)}\,.$$
(29)
Then \({H}^{{\prime} }=\Delta {H}_{0}+{\Delta }^{\frac{2}{3}}{V}^{(2)}+{\Delta }^{\frac{1}{3}}{V}^{(1)}+{V}^{(0)}\) is a (O(Δ), η, ϵ)-gadget for H, where \({H}_{0}={{{\rm{I}}}}\otimes \left\vert 1\right\rangle \left\langle 1\right\vert\), if
$$\Delta \ge O({\epsilon }^{-3}{\Lambda }^{12}+{\eta }^{-3}{\Lambda }^{3})\,.$$
(30)
We illustrate the application of these lemmas to our definition with the following ubiquitous gadgets from Oliviera et al.17:
Given a target Hamiltonian \(H=A\otimes B\in {{{\rm{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}^{{\prime} }=\Delta {H}_{0}+{\Delta }^{\frac{1}{2}}{V}^{(1)}+{V}^{(0)}\,,$$
(31)
where
$${H}_{0}={{{\rm{I}}}}\otimes {{{\rm{I}}}}\otimes \left\vert 1\right\rangle \left\langle 1\right\vert \,,$$
(32)
$${V}^{(1)}=\frac{1}{\sqrt{2}}(-A\otimes {{{\rm{I}}}}+{{{\rm{I}}}}\otimes B)\otimes X\,,$$
(33)
$${V}^{(0)}=\frac{1}{2}({A}^{2}\otimes {{{\rm{I}}}}+{{{\rm{I}}}}\otimes {B}^{2})\otimes {{{\rm{I}}}}\,.$$
(34)
Then by Lemma 20 we see that, for sufficiently large Δ, \(({H}^{{\prime} },{{{{\mathcal{H}}}}}_{C})\) defines a (O(Δ), η, ϵ)-gadget for H (see Fig. 8a).
Fig. 8: Existing gadgets.
a Interaction hypergraphs of a 2-system interaction before (above) and after (below) the use of the subdivision gadget. b Interaction hypergraphs of a 3-system interaction before (above) and after (below) the use of the 3-to-2 gadget.
Given a target Hamiltonian \(H=A\otimes B\otimes C\in {{{\rm{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}^{{\prime} }=\Delta {H}_{0}+{\Delta }^{\frac{2}{3}}{V}^{(2)}+{\Delta }^{\frac{1}{3}}{V}^{(1)}+{V}^{(0)}\,,$$
(35)
where
$${H}_{0}={{{\rm{I}}}}\otimes {{{\rm{I}}}}\otimes {{{\rm{I}}}}\otimes \left\vert 1\right\rangle \left\langle 1\right\vert \,,$$
(36)
$${V}^{(2)}=\frac{1}{\sqrt{2}}(-A\otimes {{{\rm{I}}}}+{{{\rm{I}}}}\otimes B)\otimes {{{\rm{I}}}}\otimes X-{{{\rm{I}}}}\otimes {{{\rm{I}}}}\otimes C\otimes \left\vert 1\right\rangle \left\langle 1\right\vert \,,$$
(37)
$${V}^{(1)}=\frac{1}{2}{(-A\otimes {{{\rm{I}}}}+{{{\rm{I}}}}\otimes B)}^{2}\otimes {{{\rm{I}}}}\otimes {{{\rm{I}}}}\,,$$
(38)
$${V}^{(0)}=\frac{1}{2}({A}^{2}\otimes {{{\rm{I}}}}+{{{\rm{I}}}}\otimes {B}^{2})\otimes C\otimes {{{\rm{I}}}}\,.$$
(39)
By Lemma 20 we see that, for sufficiently large Δ, \(({H}^{{\prime} },{{{{\mathcal{H}}}}}_{D})\) defines a (O(Δ), η, ϵ)-gadget for H (see Fig. 8b).
We provide the following example to illustrate the importance of the η parameter as a quantifier of how well a gadget combines with other terms.
Let \(H=A\otimes B\otimes C\in {{{\rm{Herm}}}}({({{\mathbb{C}}}^{2})}^{\otimes 3})\) be a 3-qubit interaction, and diagonalise A, B, and C as
$$A={\lambda }_{0}^{A}\left\vert 0\right\rangle \left\langle 0\right\vert+{\lambda }_{1}^{A}\left\vert 1\right\rangle \left\langle 1\right\vert \,,\quad B={\lambda }_{0}^{B}\left\vert 0\right\rangle \left\langle 0\right\vert+{\lambda }_{1}^{B}\left\vert 1\right\rangle \left\langle 1\right\vert \,,\quad C={\lambda }_{0}^{C}\left\vert 0\right\rangle \left\langle 0\right\vert+{\lambda }_{1}^{C}\left\vert 1\right\rangle \left\langle 1\right\vert \,.$$
(40)
Let \({H}^{{\prime} }\in {{{\rm{Herm}}}}({({{\mathbb{C}}}^{2})}^{\otimes 4})\) be defined as
$${H}^{{\prime} } ={\lambda }_{0}^{B}(A-{\lambda }_{0}^{A}{{{\rm{I}}}})\otimes {{{\rm{I}}}}\otimes {{{\rm{I}}}}\otimes C\\ +{\lambda }_{1}^{B}{{{\rm{I}}}}\otimes (A-{\lambda }_{0}^{A}{{{\rm{I}}}})\otimes {{{\rm{I}}}}\otimes C\\ +{\lambda }_{0}^{A}{{{\rm{I}}}}\otimes {{{\rm{I}}}}\otimes B\otimes C\,,$$
(41)
and let \({P}^{{\prime} }\in {{{\rm{Proj}}}}({({{\mathbb{C}}}^{2})}^{\otimes 4})\) be
$${P}^{{\prime} }=({{{\rm{I}}}}\otimes \left\vert 0\right\rangle \left\langle 0\right\vert \otimes \left\vert 0\right\rangle \left\langle 0\right\vert+\left\vert 0\right\rangle \left\langle 0\right\vert \otimes {{{\rm{I}}}}\otimes \left\vert 1\right\rangle \left\langle 1\right\vert )\otimes {{{\rm{I}}}}\,.$$
(42)
Then in fact the restriction of \({H}^{{\prime} }\) to the image of \({P}^{{\prime} }\) exactly reproduces the spectrum of H. This hence defines a 3-to-2 (η, 0)-gadget—or a (Δ, η, 0)-gadget, if one adds a term of the form \(O(\Delta )({{{\rm{I}}}}-{P}^{{\prime} })\) to \({H}^{{\prime} }\). The caveat is that this gadget has a large η parameter, and hence it does not combine well with other interactions. For instance, in Definition 15 we might take \(P=\left\vert 0\right\rangle \left\langle 0\right\vert \otimes {{{\rm{I}}}}\otimes {{{\rm{I}}}}\otimes {{{\rm{I}}}}\), and \(U=({\mathbb{F}}\otimes \left\vert 0\right\rangle \left\langle 0\right\vert+{{{\rm{I}}}}\otimes {{{\rm{I}}}}\otimes \left\vert 1\right\rangle \left\langle 1\right\vert )\otimes {{{\rm{I}}}}\), where \({\mathbb{F}}\) is the two-qubit swapping operator. This gives η = 2.
The construction of \({H}^{{\prime} }\) can be thought of as splitting the A qubit into two qubits (see Fig. 9), 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 that 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.
Fig. 9: The exact 3-to-2 gadget.
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 A1 and A2. However, after this process, the 2-local interaction (red) between A and another qubit E is replaced by two 3-local interactions between E, A1, B and E, A2, B. Compare this with Fig. 8b, for which additional interactions on qubit A will remain on qubit A of the gadgetised Hamiltonian without any need for adjustment.
Gadget combination results
The following results show that gadgets satisfying Definition 15 or Definition 18 can be systematically combined as desired. Our techniques and proofs extend prior work17,31,58, using the convenient formalism of the direct rotation59. The scalings of the parameters \({\eta }^{{\prime} },{\epsilon }^{{\prime} }\) are not necessarily optimal, though they sufficient for application to the subdivision and 3-to-2 gadget constructions exhibited above. The proofs of our gadget combination results can be found in Supplementary Note 4.
We summarise the setup below, which will be used throughout the following results.
Setup 22
Let \(H\in {{{\rm{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 Hi 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, ∥Hi∥ ≤ J for all i.
In the below propositions we consider a family (depending on n) of gadgets \(({H}_{i}^{{\prime} },{{{{\mathcal{A}}}}}_{i})\) for Hi, with Ui, Pi, and \({P}_{i}^{{\prime} }\) defined as in Definition 15, for each i. Assume that \({{{{\mathcal{A}}}}}_{i}\) consists of O(1) ancillary sites and that \({H}_{i}^{{\prime} }\) is a local Hamiltonian consisting of O(1) interactions, such that
$$\parallel {H}_{i}^{{\prime} }\parallel \le \; {J}^{{\prime} }\,,\quad \parallel ({{{\rm{I}}}}\otimes {P}_{i}){H}_{i}^{{\prime} }({{{\rm{I}}}}\otimes {P}_{i}^{\perp })\parallel \le \;{J}_{O}^{{\prime} }\,.$$
(43)
Firstly, we state the main result: that gadgets as in Definition 15 may be systematically combined to produce new gadgets.
Proposition 23
(Parallel (η, ϵ)-gadget combination) Let H = ∑i Hi be as in Setup 22, and suppose that each \(({H}_{i}^{{\prime} },{{{{\mathcal{A}}}}}_{i})\) defines a (η, ϵ)-gadget for Hi.
Define
$${H}^{{\prime} }=\mathop{\sum}_{i}{H}_{i}^{{\prime} }\in {{{\rm{Herm}}}}\left({{{\mathcal{H}}}}\otimes ({\otimes }_{i}{{{{\mathcal{A}}}}}_{i})\right)\,.$$
(44)
Then \(({H}^{{\prime} },{\otimes }_{i}{{{{\mathcal{A}}}}}_{i})\) is a \(({\eta }^{{\prime} },{\epsilon }^{{\prime} })\)-gadget for H, where
$${\epsilon }^{{\prime} }=O(n\epsilon+n\eta J+n{\eta }^{3}{J}_{O}^{{\prime} }+n{\eta }^{4}{J}^{{\prime} })\,,\quad {\eta }^{{\prime} }=O(n\eta )\,.$$
(45)
For completeness, we also prove a similar result that (Δ, η, ϵ)-gadgets can be combined to create a new \(({\Delta }^{{\prime} },{\eta }^{{\prime} },{\epsilon }^{{\prime} })\)-gadget. It follows from Proposition 23 that the combination of many (Δ, η, ϵ)-gadgets defines a \(({\eta }^{{\prime} },{\epsilon }^{{\prime} })\)-gadget, however it still remains to show that the projector \({P}^{{\prime} }\) in the sense of Definition 15 may be taken as a low-energy projector \({P}_{\le {\Delta }^{{\prime} }({H}^{{\prime} })}\).
Proposition 24
(Parallel (Δ, η, ϵ)-gadget combination) Let H = ∑i Hi be as in Setup 22„ and suppose that each \(({H}_{i}^{{\prime} },{{{{\mathcal{A}}}}}_{i})\) defines a (Δ, η, ϵ)-gadget for Hi, where
$$\Delta \ge \frac{\parallel H\parallel+J+N(\epsilon+2J\eta )}{\frac{1}{4}-2\eta }=O(nJ)\,,$$
(46)
and assume that the scaling of η with n is bounded as
$$\eta=o({n}^{-\frac{1}{2}})\,,$$
(47)
and moreover that, for large \({J}^{{\prime} }\),
$$n\epsilon+n\eta J+n{\eta }^{3}{J}_{O}^{{\prime} }+n{\eta }^{4}{J}^{{\prime} }=o({J}^{{\prime} })\,,\quad {J}^{{\prime} }=O(\Delta )\,.$$
(48)
Define
$${H}^{{\prime} }=\mathop{\sum}_{i}{H}_{i}^{{\prime} }\in {{{\rm{Herm}}}}({{{\mathcal{H}}}}\otimes ({\otimes }_{i}{{{{\mathcal{A}}}}}_{i}))\,.$$
(49)
Then \(({H}^{{\prime} },{\otimes }_{i}{{{{\mathcal{A}}}}}_{i})\) is a \(({\Delta }^{{\prime} },{\eta }^{{\prime} },{\epsilon }^{{\prime} })\)-gadget for H, where
$${\Delta }^{{\prime} }=\frac{1}{2}\Delta \,,\quad {\epsilon }^{{\prime} }=O(n\epsilon+n\eta J+n{\eta }^{3}{J}_{O}^{{\prime} }+{n}^{3}{\eta }^{4}{J}^{{\prime} })\,,\quad {\eta }^{{\prime} }=O(n\eta )\,.$$
(50)
For an example of how these conditions can be satisfied, consider the case of combining many of the 3-to-2 gadgets described above. Setting J = 1 for convenience, we have \({J}^{{\prime} }=\Theta (\Delta )\), \({J}_{O}^{{\prime} }=\Theta ({\Delta }^{2/3})\), and ϵ, η = O(Δ−1/3). The errors \({\epsilon }^{{\prime} }\) and \({\eta }^{{\prime} }\) both grow as O(nΔ−1/3), so a good gadget will require Δ = Ω(n3). A direct computation verifies that this condition also ensures that ((46)–(48)) are satisfied. Hence reduction from a 3-local to 2-local Hamiltonian in this way requires interaction strengths to scale as n3.
To combine (Δ, η, ϵ) gadgets using Proposition 24 requires the unappealing conditions of (46)–(47), which explicitly require the gadget energies to scale with n. In fact, as noted by Bravyi et al.31, 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 25
(Ground state energy estimation with (Δ, η, ϵ)-gadgets, generalising Bravyi et al., Theorem 131) Let H = ∑iHi be as in Setup 22, and suppose that each \(({H}_{i}^{{\prime} },{{{{\mathcal{A}}}}}_{i})\) defines a (Δ, η, ϵ)-gadget for Hi.
Define
$${H}^{{\prime} }={\sum}_{i}{H}_{i}^{{\prime} }\in {{{\rm{Herm}}}}({{{\mathcal{H}}}}\otimes ({\otimes }_{i}{{{{\mathcal{A}}}}}_{i}))\,.$$
(51)
Then the ground state energies of H and \({H}^{{\prime} }\) satisfy
$$| {\lambda }_{0}(H)-{\lambda }_{0}({H}^{{\prime} })|=O(n\epsilon+n\eta J+n{\eta }^{3}{J}_{O}^{{\prime} }+n{\eta }^{4}{J}^{{\prime} })\,.$$
(52)
Gadget energy scaling
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 (η, ϵ)-gadgets (Definition 15), and hence follows even from the relaxed (ζ, ϵ)-gadget property of Definition 14.
Theorem 26
(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}\,.$$
(53)
Suppose \(({H}^{{\prime} },\, {{{\mathcal{A}}}})\) is a (η, ϵ)-gadget for H for \({H}^{{\prime} }\) a \({k}^{{\prime} }\)-local Hamiltonian, where \({k}^{{\prime} } < \, k\).
Then, provided ϵ < J, the gadget must have energy scale \(\parallel {H}^{{\prime} }\parallel \ge \frac{J-\epsilon }{\eta }=\Omega ({\eta }^{-1})\).
The method of proof (found in Supplementary Note 5) is simple, and very likely does not provide an optimal lower bound for \(\parallel {H}^{{\prime} }\parallel\), 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 Oliviera et al.17 and higher-order gadgets34,60, 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 by Bravyi et al.31, and is still unresolved. Using the formalism introduced here, this problem can be precisely stated, and optimisation of Theorem 26 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 26 is that it essentially rules out a size-independent (Definition 1.) simulation of a k-local Hamiltonian H by another \({k}^{{\prime} }\)-local Hamiltonian \({H}^{{\prime} }\) for \({k}^{{\prime} } < \, k\), for the following reason. Any modular encodings require the use of term-by-term gadgets, which must each satisfy the (ζ, ϵ)-gadget property (Definition 14) with ζ, η = O(n−1) to guarantee that they can be combined (since the rest of the Hamiltonian will have ∥Helse∥ = O(n)). By Theorem 17, this requires the use of (η, ϵ)-gadgets (Definition 15) with η = O(n−1/2), and by Theorem 26 this will require interactions which scale at least as Ω(n1/2).
A couple of notes on gadget energy scalings in existing work: Bausch61 gives a method to reduce the exponential or doubly-exponential scaling in perturbative Hamiltonians to polynomial scaling, and Cao et al.33 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.
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 26 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 Tt in Definition 5 to take advantage of an additional resource: dissipation.
We will see that, despite some impractical features for experimental implementation, this approach offers a theoretical 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.
Let \(H\in {{{\rm{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}^{{\prime} }\in {{{\rm{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 δt. By the quantum Zeno effect62, this forces the \({{{\mathcal{A}}}}\) system to stay in the \(\left\vert 0\right\rangle\) state with high probability, meanwhile simulating the desired interaction on the \({{{\mathcal{H}}}}\) system.
The following result, Proposition 27, provides a formal construction for the measurement-based gadgets described above—see Supplementary Note 6 for the proof. Qualitatively, this result tells us that if we evolve \(\left\vert \psi \right\rangle \otimes \left\vert 0\right\rangle\) for time δt under the simulator Hamiltonian \({H}^{{\prime} }\), and then measure the ancillary qubit, we will obtain a ‘1’ result with probability O((δt)3) (corresponding to an amplitude of O((δ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}\left\vert \psi \right\rangle\), for some new Hamiltonian H, up to error O((δt)2). By repeating this process t/δt times, we will hence obtain a state \({e}^{-itH}\left\vert \psi \right\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(δt)2, hence can be controlled provided that δt = O(t−1/2), which will always be satisfied if we choose δt = O(t−1) in order to control the error on the post-measurement state.
Proposition 27
For a Hilbert space \({{{\mathcal{H}}}}\) and an ancillary qubit \({{{\mathcal{A}}}}={{\mathbb{C}}}^{2}\), let \({H}^{{\prime} }\in {{{\rm{Herm}}}}({{{\mathcal{H}}}}\otimes {{{\mathcal{A}}}})\) be a Hamiltonian given by
$${H}^{{\prime} }={H}_{{{{\rm{I}}}}}\otimes {{{\rm{I}}}}+{H}_{X}\otimes X+{H}_{\left\vert 1\right\rangle \left\langle 1\right\vert }\otimes \left\vert 1\right\rangle \left\langle 1\right\vert \,,$$
(54)
for some \({H}_{{{{\rm{I}}}}},\, {H}_{X},\, {H}_{\left\vert 1\right\rangle \left\langle 1\right\vert }\in {{{\rm{Herm}}}}({{{\mathcal{H}}}})\) depending on a small parameter δt such that ∥HI∥ = O(1), ∥HX∥ = O((δt)−1/2), and \(\parallel {H}_{\left\vert 1\right\rangle \left\langle 1\right\vert }\parallel=O({(\delta t)}^{-1})\) with \({H}_{\left\vert 1\right\rangle \left\langle 1\right\vert }^{2}={\omega }^{2}{{{\rm{I}}}}\), \(\omega=\frac{2\pi }{\delta t}\).
Then, for any \(\left\vert \psi \right\rangle \in {{{\mathcal{H}}}}\),
$${e}^{-i\delta t{H}^{{\prime} }}(\left\vert \psi \right\rangle \otimes \left\vert 0\right\rangle )=\left({e}^{-i\delta tH}\left\vert \psi \right\rangle+O({(\delta t)}^{2})\right)\otimes \left\vert 0\right\rangle+O({(\delta t)}^{3/2})\otimes \left\vert 1\right\rangle \,,$$
(55)
where
$$H={H}_{{{{\rm{I}}}}}-{\omega }^{-2}{H}_{X}{H}_{\left\vert 1\right\rangle \left\langle 1\right\vert }{H}_{X}\,.$$
(56)
This provides a new 3-to-2-local gadget for Pauli strings. For example, we can set HI = −Z1, \({H}_{X}=\sqrt{\frac{\omega }{2}}({Z}_{2}+{Z}_{3})\), \({H}_{\left\vert 1\right\rangle \left\langle 1\right\vert }=-\omega {Z}_{1}\); this yields a 2-local Hamiltonian \({H}^{{\prime} }\) simulating the 3-local interaction H = Z1 ⊗ Z2 ⊗ Z3. More generally, given three commuting Pauli strings Aa, Bb, Cc, we can set HI = −Aa, \({H}_{X}=\sqrt{\frac{\omega }{2}}({B}_{b}+{C}_{c})\), \({H}_{\left\vert 1\right\rangle \left\langle 1\right\vert }=-\omega {A}_{a}\) to simulate the interaction H = Aa ⊗ Bb ⊗ Cc. This procedure may be used to simulate a k-local Pauli string using a (⌈k/3⌉ + 1)-local Hamiltonian.
Although Proposition 27 shows that evolution and repeated measurements under \({H}^{{\prime} }\) reproduce the dynamics of H, it is also important to guarantee that it can be combined with other interactions. Proposition 28 provides the necessary result for this, by verifying that the conclusions of Proposition 27 also hold when an additional term \({H}_{{{{\rm{else}}}}}\in {{{\rm{Herm}}}}({{{\mathcal{H}}}})\) is added to both the target and simulator Hamiltonian.
Proposition 28
Let Helse = ∑ihi be a k-local Hamiltonian on \({{{\mathcal{H}}}}={\otimes }_{i}{{{{\mathcal{H}}}}}_{i}\) such that ∥hi∥ = 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}^{{\prime} }\in {{{\rm{Herm}}}}({{{\mathcal{H}}}}\otimes {{{\mathcal{A}}}})\) be a Hamiltonian given by
$${H}^{{\prime} }={H}_{{{{\rm{I}}}}}\otimes {{{\rm{I}}}}+{H}_{X}\otimes X+{H}_{\left\vert 1\right\rangle \left\langle 1\right\vert }\otimes \left\vert 1\right\rangle \left\langle 1\right\vert \,,$$
(57)
for some \({H}_{{{{\rm{I}}}}},{H}_{X},{H}_{\left\vert 1\right\rangle \left\langle 1\right\vert }\in {{{\rm{Herm}}}}({{{\mathcal{H}}}})\) depending on a small parameter δt such that ∥HI∥ = O(1), ∥HX∥ = O((δt)−1/2), and \(\parallel {H}_{\left\vert 1\right\rangle \left\langle 1\right\vert }\parallel=O({(\delta t)}^{-1})\) with \({H}_{\left\vert 1\right\rangle \left\langle 1\right\vert }^{2}={\omega }^{2}{{{\rm{I}}}}\), \(\omega=\frac{2\pi }{\delta t}\). Assume that HI, HX, and \({H}_{\left\vert 1\right\rangle \left\langle 1\right\vert }\) act on O(1) sites in \({{{\mathcal{H}}}}\).
Then, for any \(\left\vert \psi \right\rangle \in {{{\mathcal{H}}}}\),
$${e}^{-i\delta t({H}^{{\prime} }+{H}_{{{{\rm{else}}}}}\otimes {{{\rm{I}}}})}(\left\vert \psi \right\rangle \otimes \left\vert 0\right\rangle ) =\left({e}^{-i\delta t(H+{H}_{{{{\rm{else}}}}})}\left\vert \psi \right\rangle+O({(\delta t)}^{2})\right) \\ \otimes \left\vert 0\right\rangle+O({(\delta t)}^{3/2})\otimes \left\vert 1\right\rangle \,,$$
(58)
where
$$H={H}_{{{{\rm{I}}}}}-{\omega }^{-2}{H}_{X}{H}_{\left\vert 1\right\rangle \left\langle 1\right\vert }{H}_{X}\,.$$
(59)
The significance of Proposition 28 is that the errors do not depend on the size of the system through ∥Helse∥, due to bounds we place on the Trotter error in the expansion \({e}^{-i\delta t(H+{H}_{{{{\rm{else}}}}})} \, \approx \, {e}^{-i\delta tH}{e}^{-i\delta t{H}_{{{{\rm{else}}}}}}\).
