Perturbative gadgets were originally introduced to generate effective
k-local interactions in the low-energy sector of a
2-local Hamiltonian. Extending this idea, we present gadgets which are specifically suited for realizing Hamiltonians exhibiting non-abelian anyonic excitations. At the core of our construction is a perturbative analysis of a widely used hopping-term Hamiltonian. We show that in the low-energy limit, this Hamiltonian can be approximated by a certain ordered product of operators. In particular, this provides a simplified realization of Kitaev's quantum double Hamiltonians.
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.
Perturbative gadgets are a tool to encode part of a Hamiltonian, usually the low-energy subspace, into a different Hamiltonian with favorable properties, for instance, reduced locality. Many constructions of perturbative gadgets have been proposed over the years. Still, all of them are restricted in some ways: Either they apply to some specific classes of Hamiltonians, they involve recursion to reduce locality, or they are limited to studying time evolution under the gadget Hamiltonian, e.g., in the context of adiabatic quantum computing, and thus involve subspace restrictions. In this work, we fill the gap by introducing a versatile universal, nonrecursive, nonadiabatic perturbative gadget construction without subspace restrictions, that encodes an arbitrary many-body Hamiltonian into the low-energy subspace of a three-body Hamiltonian and is therefore applicable to gate-based quantum computing. Our construction requires
rk additional qubits for a
k-body Hamiltonian comprising
r terms. Besides a specific gadget construction, we also provide a recipe for constructing similar gadgets, which can be tailored to different properties, which we discuss.
Adiabatic quantum algorithms are often most easily formulated using many-body interactions. However, experimentally available interactions are generally two-body. In 2004, Kempe, Kitaev, and Regev introduced perturbative gadgets, by which arbitrary three-body effective interactions can be obtained using Hamiltonians consisting only of two-body interactions. These three-body effective interactions arise from the third order in perturbation theory. Since their introduction, perturbative gadgets have become a standard tool in the theory of quantum computation. Here we construct generalized gadgets so that one can directly obtain arbitrary
k-body effective interactions from two-body Hamiltonians. These effective interactions arise from the
kth order in perturbation theory.