## Perturbation Gadgets: Arbitrary Energy Scales from a Single Strong Interaction

##### View / Open Files

##### Authors

##### Publication Date

2020-01##### Journal Title

Annales Henri Poincaré

##### ISSN

1424-0637

##### Publisher

Springer Nature

##### Volume

21

##### Issue

1

##### Pages

81-114

##### Language

en

##### Type

Article

##### This Version

AM

##### Metadata

Show full item record##### Citation

Bausch, J. (2020). Perturbation Gadgets: Arbitrary Energy Scales from a Single Strong Interaction. Annales Henri Poincaré, 21 (1), 81-114. https://doi.org/10.1007/s00023-019-00871-7

##### 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 $\epsilon$.
One caveat of existing constructions is that the interaction strength generally scales exponentially in the locality of the terms to be approximated, i.e.\ as $\Omega(1/\epsilon^k)$; if $\epsilon=1/\poly n$ in the system size $n$, as is necessary for e.g.\ QMA-hardness constructions, the energy differences become highly unphysical.
In this work we propose a many-body Hamiltonian construction which introduces only a single separate energy scale of order $\Theta(1/N^{2+\delta})$, for a small parameter $\delta>0$, and for $N$ terms in the target Hamiltonian---i.e.\ all local terms of the simulator have either this norm, or one of $\BigO(1)$.
In its low-energy subspace, we can approximate any normalized target Hamiltonian $\op H_\mathrm{t}=\sum_{i=1}^N \op h_i$
with norm ratios $r=\|\op h_i\|_2 / \| \op h_j \|_2=\BigO(\exp(\exp(\poly n)))$ to within \emph{relative} precision $\BigO(N^{-\delta})$.
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; the ancillas being qutrits for exponential scaling, and qudits for doubly exponential $r$; the interactions on the ancilliary 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 a tiling Hamiltonian to drop all cross terms at higher expansion orders, which simplifies the analysis of a traditional Feynman-Dyson series expansion.
As an application, we discuss implications for \QMA-hardness of the \lham 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.

##### Sponsorship

Pembroke College (JRF)

##### Embargo Lift Date

2020-11-01

##### Identifiers

External DOI: https://doi.org/10.1007/s00023-019-00871-7

This record's URL: https://www.repository.cam.ac.uk/handle/1810/299199

##### Rights

All rights reserved