Perturbative gadgets without strong interactions
arXiv:1408.5881
Abstract
Perturbative gadgets are used to construct a quantum Hamiltonian whose low-energy subspace approximates a given quantum -body Hamiltonian up to an absolute error . Typically, gadget constructions involve terms with large interaction strengths of order . Here we present a 2-body gadget construction and prove that it approximates a target many-body Hamiltonian of interaction strength up to absolute error using interactions of strength instead of the usual inverse polynomial in . A key component in our proof is a new condition for the convergence of the perturbation series, allowing our gadget construction to be applied in parallel on multiple many-body terms. We also show how to apply this gadget construction for approximating 3- and -body Hamiltonians. The price we pay for using much weaker interactions is a large overhead in the number of ancillary qubits, and the number of interaction terms per particle, both of which scale as . Our strong-from-weak gadgets have their primary application in complexity theory (QMA hardness of restricted Hamiltonians, a generalized area law counterexample, gap amplification), but could also motivate practical implementations with many weak interactions simulating a much stronger quantum many-body interaction.
arXiv comment26 pages, 8 figures
References in corpus (12)
- An Area Law for One Dimensional Quantum Systems
- Schrieffer-Wolff transformation for quantum many-body systems
- Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
- Realizable Hamiltonians for Universal Adiabatic Quantum Computers
- Non-perturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins
- Simulation of Many-Body Hamiltonians using Perturbation Theory with Bounded-Strength Interactions
- Perturbative Gadgets at Arbitrary Orders
- A new construction for a QMA complete 3-local Hamiltonian
- Adiabatic quantum optimization with the wrong Hamiltonian
- Hamiltonian gadgets with reduced resource requirements
- Non-perturbative gadget for topological quantum codes
- Simplifying quantum double Hamiltonians using perturbative gadgets