Perturbative gadgets without strong interactions

Abstract

Perturbative gadgets are used to construct a quantum Hamiltonian whose low-energy subspace approximates a given quantum $k$-body Hamiltonian up to an absolute error $\epsilon$. Typically, gadget constructions involve terms with large interaction strengths of order $\text{poly}({\epsilon }^{-1})$. Here we present a 2-body gadget construction and prove that it approximates a target many-body Hamiltonian of interaction strength $\gamma =O(1)$ up to absolute error $\epsilon \ll \gamma$ using interactions of strength $O(\epsilon )$ instead of the usual inverse polynomial in $\epsilon$. 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 $k$-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 $O(\text{poly}({\epsilon }^{-1}))$. 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.

26 pages, 8 figures

References in corpus (4)

• 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
• A new construction for a QMA complete 3-local Hamiltonian

Cited by in corpus (4)

• Local tests of global entanglement and a counterexample to the generalized area law
• Complexity classification of local Hamiltonian problems
• On complexity of the quantum Ising model
• Efficient estimation of perturbative error with cellular automata