Perturbative gadgets without strong interactions (pp1197-1222)
          Yudong Cao and Daniel Nagaj
          doi: https://doi.org/10.26421/QIC15.13-14-7
Abstracts: Perturbative gadgets are used to construct a quantum Hamiltonian whose low-energy subspace approximates a given quantum k-local Hamiltonian up to an absolute error . Typically, gadget constructions involve terms with large interaction strengths of order poly(−1 ). Here we present a 2-body gadget construction and prove that it approximates a Hamiltonian of interaction strength γ = O(1) up to absolute error   γ using interactions of strength O() 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 discuss how to apply this gadget construction for approximating 3- and k-local 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(poly(−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 several weak interactions simulating a much stronger quantum many-body interaction.
Key words: local Hamiltonian, perturbation theory, quantum complexity