Repository logo
 

Perturbation Gadgets: Arbitrary Energy Scales from a Single Strong Interaction

Published version
Peer-reviewed

Change log

Abstract

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. In its low-energy subspace, the construction can approximate any normalized target Hamiltonian Ht=∑i=1Nhi 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 ancilliary system for each coupling; interactions on the ancilliary system are geometrically local, and can be translationally-invariant. 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.

Description

Keywords

quant-ph, quant-ph, cond-mat.other, math-ph, math.MP

Journal Title

Annales Henri Poincare

Conference Name

Journal ISSN

1424-0637
1424-0661

Volume Title

21

Publisher

Springer Nature
Sponsorship
Pembroke College, University of Cambridge (JRF)