Repository logo

Perturbation Gadgets: Arbitrary Energy Scales from a Single Strong Interaction

Published version

Change log



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.




Journal Title

Annales Henri Poincaré

Conference Name

Journal ISSN


Volume Title



Springer International Publishing
Pembroke College, University of Cambridge (JRF)