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.
Perturbative gadgets are a tool to encode part of a Hamiltonian, usually the low-energy subspace, into a different Hamiltonian with favorable properties, for instance, reduced locality. Many constructions of perturbative gadgets have been proposed over the years. Still, all of them are restricted in some ways: Either they apply to some specific classes of Hamiltonians, they involve recursion to reduce locality, or they are limited to studying time evolution under the gadget Hamiltonian, e.g., in the context of adiabatic quantum computing, and thus involve subspace restrictions. In this work, we fill the gap by introducing a versatile universal, nonrecursive, nonadiabatic perturbative gadget construction without subspace restrictions, that encodes an arbitrary many-body Hamiltonian into the low-energy subspace of a three-body Hamiltonian and is therefore applicable to gate-based quantum computing. Our construction requires
rk additional qubits for a
k-body Hamiltonian comprising
r terms. Besides a specific gadget construction, we also provide a recipe for constructing similar gadgets, which can be tailored to different properties, which we discuss.
Perturbative gadgets were originally introduced to generate effective
k-local interactions in the low-energy sector of a
2-local Hamiltonian. Extending this idea, we present gadgets which are specifically suited for realizing Hamiltonians exhibiting non-abelian anyonic excitations. At the core of our construction is a perturbative analysis of a widely used hopping-term Hamiltonian. We show that in the low-energy limit, this Hamiltonian can be approximated by a certain ordered product of operators. In particular, this provides a simplified realization of Kitaev's quantum double Hamiltonians.
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.
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.