Perturbation Gadgets: Arbitrary Energy Scales from a Single Strong Interaction
arXiv:1810.00865 · doi:10.1007/s00023-019-00871-7
Abstract
In this work we propose a many-body Hamiltonian construction which introduces only a single separate energy scale of order , for a small parameter , and for terms in the target Hamiltonian. In its low-energy subspace, the construction can approximate any normalized target Hamiltonian with norm ratios to within relative precision . 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.
arXiv comment46 pages, significantly extended proofs
References in corpus (16)
- Schrieffer-Wolff transformation for quantum many-body systems
- The power of quantum systems on a line
- Renormalization group transformations on quantum states
- Power law violation of the area law in quantum spin chains
- Universal Quantum Hamiltonians
- Perturbative Gadgets at Arbitrary Orders
- Hamiltonian Quantum Cellular Automata in 1D
- The Feynman-Kitaev computer's clock: bias, gaps, idling and pulse tuning
- Space-Time Circuit-to-Hamiltonian Construction and Its Applications
- Universal 2-local Hamiltonian Quantum Computing
- The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension
- Polar Molecules with Three-Body Interactions on the Honeycomb Lattice
- Analysis and limitations of modified circuit-to-Hamiltonian constructions
- Non-Unitary Quantum Computation in the Ground Space of Local Hamiltonians
- The Complexity of Translationally-Invariant Low-Dimensional Spin Lattices in 3D
- Hamiltonian quantum computer in one dimension
Cited by in corpus (4)
- Translationally-Invariant Universal Quantum Hamiltonians in 1D
- Going Beyond Gadgets: The Importance of Scalability for Analogue Quantum Simulators
- Cost of Emulating a Small Quantum Annealing Problem in the Circuit-Model
- Perturbative gadgets for gate-based quantum computing: Non-recursive constructions without subspace restrictions