Perturbation Gadgets: Arbitrary Energy Scales from a Single Strong Interaction
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Springer Science and Business Media LLC
https://doi.org/10.1007/s00023-019-00871-7
https://doi.org/10.1007/s00023-019-00871-7
Abstract
Description
<jats:title>Abstract</jats:title><jats:p>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<jats:italic>k</jats:italic>-body and approximates a target Hamiltonian to within precision<jats:inline-formula><jats:alternatives><jats:tex-math>$$\epsilon $$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>ϵ</mml:mi></mml:math></jats:alternatives></jats:inline-formula>. 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<jats:inline-formula><jats:alternatives><jats:tex-math>$$\Theta (1/N^{2+\delta })$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>Θ</mml:mi><mml:mo>(</mml:mo><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:msup><mml:mi>N</mml:mi><mml:mrow><mml:mn>2</mml:mn><mml:mo>+</mml:mo><mml:mi>δ</mml:mi></mml:mrow></mml:msup><mml:mo>)</mml:mo></mml:mrow></mml:math></jats:alternatives></jats:inline-formula>, for a small parameter<jats:inline-formula><jats:alternatives><jats:tex-math>$$\delta >0$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>δ</mml:mi><mml:mo>></mml:mo><mml:mn>0</mml:mn></mml:mrow></mml:math></jats:alternatives></jats:inline-formula>, and for<jats:italic>N</jats:italic>terms in the target Hamiltonian<jats:inline-formula><jats:alternatives><jats:tex-math>$$\mathbf H_\mathrm {t}=\sum _{i=1}^N \mathbf h_i$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>H</mml:mi><mml:mi>t</mml:mi></mml:msub><mml:mo>=</mml:mo><mml:msubsup><mml:mo>∑</mml:mo><mml:mrow><mml:mi>i</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mi>N</mml:mi></mml:msubsup><mml:msub><mml:mi>h</mml:mi><mml:mi>i</mml:mi></mml:msub></mml:mrow></mml:math></jats:alternatives></jats:inline-formula>to be simulated: in its low-energy subspace, our constructed system can approximate any such target Hamiltonian<jats:inline-formula><jats:alternatives><jats:tex-math>$$\mathbf H_t$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>H</mml:mi><mml:mi>t</mml:mi></mml:msub></mml:math></jats:alternatives></jats:inline-formula>with norm ratios<jats:inline-formula><jats:alternatives><jats:tex-math>$$r=\max _{i,j\in \{1,\ldots ,N\}}\Vert \mathbf h_i\Vert / \Vert \mathbf h_j \Vert ={{\,\mathrm{O}\,}}(\exp (\exp ({{\,\mathrm{poly}\,}}N)))$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>r</mml:mi><mml:mo>=</mml:mo><mml:msub><mml:mo>max</mml:mo><mml:mrow><mml:mi>i</mml:mi><mml:mo>,</mml:mo><mml:mi>j</mml:mi><mml:mo>∈</mml:mo><mml:mo>{</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:mi>N</mml:mi><mml:mo>}</mml:mo></mml:mrow></mml:msub><mml:mrow><mml:mo>‖</mml:mo></mml:mrow><mml:msub><mml:mi>h</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mrow><mml:mo>‖</mml:mo><mml:mo>/</mml:mo><mml:mo>‖</mml:mo></mml:mrow><mml:msub><mml:mi>h</mml:mi><mml:mi>j</mml:mi></mml:msub><mml:mrow><mml:mo>‖</mml:mo><mml:mo>=</mml:mo><mml:mrow><mml:mspace/><mml:mi>O</mml:mi><mml:mspace/></mml:mrow><mml:mrow><mml:mo>(</mml:mo><mml:mo>exp</mml:mo><mml:mrow><mml:mo>(</mml:mo><mml:mo>exp</mml:mo><mml:mrow><mml:mo>(</mml:mo><mml:mrow><mml:mspace/><mml:mi>poly</mml:mi><mml:mspace/></mml:mrow><mml:mi>N</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>)</mml:mo></mml:mrow><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:mrow></mml:math></jats:alternatives></jats:inline-formula>to within<jats:italic>relative</jats:italic>precision<jats:inline-formula><jats:alternatives><jats:tex-math>$${{\,\mathrm{O}\,}}(N^{-\delta })$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mrow><mml:mspace/><mml:mi>O</mml:mi><mml:mspace/></mml:mrow><mml:mo>(</mml:mo><mml:msup><mml:mi>N</mml:mi><mml:mrow><mml:mo>-</mml:mo><mml:mi>δ</mml:mi></mml:mrow></mml:msup><mml:mo>)</mml:mo></mml:mrow></mml:math></jats:alternatives></jats:inline-formula>. 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<jats:sc>Local Hamiltonian</jats:sc>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 QMA<jats:sub>EXP</jats:sub>-, or even BQEXPSPACE-complete.</jats:p>
Pembroke College (JRF)
Pembroke College (JRF)