Adiabatic quantum algorithms are often most easily formulated using many-body interactions. However, experimentally available interactions are generally two-body. In 2004, Kempe, Kitaev, and Regev introduced perturbative gadgets, by which arbitrary three-body effective interactions can be obtained using Hamiltonians consisting only of two-body interactions. These three-body effective interactions arise from the third order in perturbation theory. Since their introduction, perturbative gadgets have become a standard tool in the theory of quantum computation. Here we construct generalized gadgets so that one can directly obtain arbitrary
k-body effective interactions from two-body Hamiltonians. These effective interactions arise from the
kth order in perturbation theory.
Application of the adiabatic model of quantum computation requires efficient encoding of the solution to computational problems into the lowest eigenstate of a Hamiltonian that supports universal adiabatic quantum computation. Experimental systems are typically limited to restricted forms of two-body interactions. Therefore, universal adiabatic quantum computation requires a method for approximating quantum many-body Hamiltonians up to arbitrary spectral error using at most two-body interactions. Hamiltonian gadgets, introduced around a decade ago, offer the only current means to address this requirement. Although the applications of Hamiltonian gadgets have steadily grown since their introduction, little progress has been made in overcoming the limitations of the gadgets themselves. In this experimentally motivated theoretical study, we introduce several gadgets which require significantly more realistic control parameters than similar gadgets in the literature. We employ analytical techniques which result in a reduction of the resource scaling as a function of spectral error for the commonly used subdivision, three- to two-body and
k-body gadgets. Accordingly, our improvements reduce the resource requirements of all proofs and experimental proposals making use of these common gadgets. Next, we numerically optimize these gadgets to illustrate the tightness of our analytical bounds. Finally, we introduce a gadget that simulates a
YY interaction term using Hamiltonians containing only
X,Z,XX,ZZ terms. Apart from possible implications in a theoretical context, this work could also be useful for a first experimental implementation of these key building blocks by requiring less control precision without introducing extra ancillary qubits.
Perturbative gadgets are used to construct a quantum Hamiltonian whose low-energy subspace approximates a given quantum
k-local Hamiltonian up to an absolute error
ϵ. Typically, gadget constructions involve terms with large interaction strengths of order
poly(ϵ−1). Here we present a 2-body gadget construction and prove that it approximates a Hamiltonian of interaction strength
γ=O(1) up to absolute error
ϵ≪γ using interactions of strength
O(ϵ) instead of the usual inverse polynomial in
ϵ. A key component in our proof is a new condition for the convergence of the perturbation series, allowing our gadget construction to be applied in parallel on multiple many-body terms. We also discuss how to apply this gadget construction for approximating 3- and
k-local Hamiltonians. The price we pay for using much weaker interactions is a large overhead in the number of ancillary qubits, and the number of interaction terms per particle, both of which scale as
O(poly(ϵ−1)). Our strong-from-weak gadgets have their primary application in complexity theory (QMA hardness of restricted Hamiltonians, a generalized area law counterexample, gap amplification), but could also motivate practical implementations with several weak interactions simulating a much stronger quantum many-body interaction.
Abstract: Fundamentally, it is believed that interactions between physical objects are two-body. Perturbative gadgets are one way to break up an effective many-body coupling into pairwise interactions: a Hamiltonian with high interaction strength introduces a low-energy space in which the effective theory appears k-body and approximates a target Hamiltonian to within precision ϵ. One caveat of existing constructions is that the interaction strength generally scales exponentially in the locality of the terms to be approximated. In this work we propose a many-body Hamiltonian construction which introduces only a single separate energy scale of order Θ(1/N2+δ), for a small parameter δ>0, and for N terms in the target Hamiltonian Ht=∑i=1Nhi to be simulated: in its low-energy subspace, our constructed system can approximate any such target Hamiltonian Ht with norm ratios r=maxi, j∈{1, …, N}‖hi‖/‖hj‖=O(exp(exp(polyN))) to within relative precision O(N-δ). This comes at the expense of increasing the locality by at most one, and adding an at most poly-sized ancillary system for each coupling; interactions on the ancillary system are geometrically local, and can be translationally invariant. In order to prove this claim, we borrow a technique from high energy physics—where matter fields obtain effective properties (such as mass) from interactions with an exchange particle—and employ a tiling Hamiltonian to discard all cross-terms at higher expansion orders of a Feynman–Dyson series expansion. As an application, we discuss implications for QMA-hardness of the Local Hamiltonian problem, and argue that “almost” translational invariance—defined as arbitrarily small relative variations of the strength of the local terms—is as good as non-translational invariance in many of the constructions used throughout Hamiltonian complexity theory. We furthermore show that the choice of geared limit of many-body systems, where e.g. width and height of a lattice are taken to infinity in a specific relation, can have different complexity-theoretic implications: even for translationally invariant models, changing the geared limit can vary the hardness of finding the ground state energy with respect to a given promise gap from computationally trivial, to QMAEXP-, or even BQEXPSPACE-complete.
Abstract Fundamentally, it is believed that interactions between physical objects are two-body. Perturbative gadgets are one way to break up an effective many-body coupling into pairwise interactions: a Hamiltonian with high interaction strength introduces a low-energy space in which the effective theory appearsk-body and approximates a target Hamiltonian to within precision
ϵ ϵ . One caveat of existing constructions is that the interaction strength generally scales exponentially in the locality of the terms to be approximated. In this work we propose a many-body Hamiltonian construction which introduces only a single separate energy scale of order
Θ(1/N2+δ) Θ(1/N2+δ) , for a small parameter
δ>0 δ>0 , and forNterms in the target Hamiltonian
Ht=∑i=1Nhi Ht=∑i=1Nhi to be simulated: in its low-energy subspace, our constructed system can approximate any such target Hamiltonian
Ht Ht with norm ratios
r=maxi,j∈{1,…,N}∥hi∥/∥hj∥=O(exp(exp(polyN))) r=maxi,j∈{1,…,N}‖hi‖/‖hj‖=O(exp(exp(polyN))) to withinrelativeprecision
O(N−δ) O(N-δ) . This comes at the expense of increasing the locality by at most one, and adding an at most poly-sized ancillary system for each coupling; interactions on the ancillary system are geometrically local, and can be translationally invariant. In order to prove this claim, we borrow a technique from high energy physics—where matter fields obtain effective properties (such as mass) from interactions with an exchange particle—and employ a tiling Hamiltonian to discard all cross-terms at higher expansion orders of a Feynman–Dyson series expansion. As an application, we discuss implications for QMA-hardness of theLocal Hamiltonianproblem, and argue that “almost” translational invariance—defined as arbitrarily small relative variations of the strength of the local terms—is as good as non-translational invariance in many of the constructions used throughout Hamiltonian complexity theory. We furthermore show that the choice of geared limit of many-body systems, where e.g. width and height of a lattice are taken to infinity in a specific relation, can have different complexity-theoretic implications: even for translationally invariant models, changing the geared limit can vary the hardness of finding the ground state energy with respect to a given promise gap from computationally trivial, to QMAEXP-, or even BQEXPSPACE-complete.