Abstract Continuous-time quantum hardware implementations generally lack the native capability to implement high-order terms that would facilitate efficient compilation of quantum algorithms. This limitation has, in part, motivated the development of perturbative gadgets—multi-qubit constructions used to effect a desired Hamiltonian using engineered low-energy subspaces of a larger system constructed using simpler, usually two-body, primitives. In this work, we demonstrate how a class of non-perturbative gadgets can produce high-order multi-body interactions by taking advantage of the odd–even properties of topological defect subspaces. The simplest example uses domain-wall defects in an effective Ising spin chain with linear connectivity and three-body couplings, alongside three- or five-body driving terms depending on the intended use. We demonstrate a version of a gadget which can perform an encoded bit-flip operation on a minor embedding chain, an important task to mitigate the limitations of quasi-two-dimensional (also sometimes called quasi-planar) topology. Although this will be the main focus of the paper due to conceptual simplicity, there exist systems constructed with only two-body couplings where the boundaries determine whether there are an odd or even number of defects, namely ice-like systems which may yield more complex gadget-like constructions.
Abstract Continuous-time quantum hardware implementations generally lack the native capability to implement high-order terms that would facilitate efficient compilation of quantum algorithms. This limitation has, in part, motivated the development of perturbative gadgets—multi-qubit constructions used to effect a desired Hamiltonian using engineered low-energy subspaces of a larger system constructed using simpler, usually two-body, primitives. In this work, we demonstrate how a class of non-perturbative gadgets can produce high-order multi-body interactions by taking advantage of the odd–even properties of topological defect subspaces. The simplest example uses domain-wall defects in an effective Ising spin chain with linear connectivity and three-body couplings, alongside three- or five-body driving terms depending on the intended use. We demonstrate a version of a gadget which can perform an encoded bit-flip operation on a minor embedding chain, an important task to mitigate the limitations of quasi-two-dimensional (also sometimes called quasi-planar) topology. Although this will be the main focus of the paper due to conceptual simplicity, there exist systems constructed with only two-body couplings where the boundaries determine whether there are an odd or even number of defects, namely ice-like systems which may yield more complex gadget-like constructions.
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.
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.
We develop and investigate several quantum many-body spin models of use for topological quantum information processing and storage. These models fall into two categories: those that are designed to be more realistic than alternative models with similar phenomenology, and those that are designed to have richer phenomenology than related models. In the first category, we present a procedure to obtain the Hamiltonians of the toric code and Kitaev quantum double models as the perturbative low-energy limits of entirely two-body Hamiltonians. This construction reproduces the target models' behavior using only couplings which are natural in terms of the original Hamiltonians. As an extension of this work, we construct parent Hamiltonians involving only local 2-body interactions for a broad class of Projected Entangled Pair States (PEPS). We define a perturbative Hamiltonian with a finite order low energy effective Hamiltonian that is a gapped, frustration-free parent Hamiltonian for an encoded version of a desired PEPS. For topologically ordered PEPS, the ground space of the low energy effective Hamiltonian is shown to be in the same phase as the desired state to all orders of perturbation theory. We then move on to define models that generalize the phenomenology of several well-known systems. We first define generalized cluster states based on finite group algebras, and investigate properties of these states including their PEPS representations, global symmetries, relationship to the Kitaev quantum double models, and possible applications. Finally, we propose a generalization of the color codes based on finite groups. For non-Abelian groups, the resulting model supports non-Abelian anyonic quasiparticles and topological order. We examine the properties of these models such as their relationship to Kitaev quantum double models, quasiparticle spectrum, and boundary structure.
The need for Hamiltonians with many-body interactions arises in various applications of quantum computing. However, interactions beyond two-body are difficult to realize experimentally. Perturbative gadgets were introduced to obtain arbitrary many-body effective interactions using Hamiltonians with at most two-body interactions. Although valid for arbitrary k-body interactions, their use is limited to small k because the strength of interaction is kth order in perturbation theory. In this paper we develop a nonperturbative technique for obtaining effective k-body interactions using Hamiltonians consisting of at most l-body interactions with l<k. The idea is to first apply a unitary transformation on the system plus ancilla qubits (possibly using a gate-based device), then evolve with a new Hamiltonian which is more local than the original one (using an analog device), and finally reverse the unitary transformation. The net effect of this procedure is shown to be equivalent to evolving the system with the original nonlocal Hamiltonian. This technique does not suffer from the aforementioned shortcoming of perturbative methods and requires only one ancilla qubit for each k-body interaction irrespective of the value of k. It works best for Hamiltonians with a few many-body interactions involving a large number of qubits and can be used together with perturbative gadgets to embed Hamiltonians of considerable complexity in proper subspaces of two-local Hamiltonians. We describe how our technique can be implemented in a hybrid (gate-based and adiabatic) as well as solely adiabatic quantum computing scheme.
Abstract: Fundamentally, it is believed that interactions between physical objects are two-body. Perturbative gadgets are one way to break up an effective many-body coupling into pairwise interactions: a Hamiltonian with high interaction strength introduces a low-energy space in which the effective theory appears k-body and approximates a target Hamiltonian to within precision ϵ. One caveat of existing constructions is that the interaction strength generally scales exponentially in the locality of the terms to be approximated. In this work we propose a many-body Hamiltonian construction which introduces only a single separate energy scale of order Θ(1/N2+δ), for a small parameter δ>0, and for N terms in the target Hamiltonian Ht=∑i=1Nhi to be simulated: in its low-energy subspace, our constructed system can approximate any such target Hamiltonian Ht with norm ratios r=maxi, j∈{1, …, N}‖hi‖/‖hj‖=O(exp(exp(polyN))) to within relative precision O(N-δ). This comes at the expense of increasing the locality by at most one, and adding an at most poly-sized ancillary system for each coupling; interactions on the ancillary system are geometrically local, and can be translationally invariant. In order to prove this claim, we borrow a technique from high energy physics—where matter fields obtain effective properties (such as mass) from interactions with an exchange particle—and employ a tiling Hamiltonian to discard all cross-terms at higher expansion orders of a Feynman–Dyson series expansion. 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.
Many-body entangled systems, in particular topologically ordered spin systems proposed as resources for quantum information processing tasks, often involve highly nonlocal interaction terms. While one may approximate such systems through two-body interactions perturbatively, these approaches have a number of drawbacks in practice. In this Letter, we propose a scheme to simulate many-body spin Hamiltonians with two-body Hamiltonians nonperturbatively. Unlike previous approaches, our Hamiltonians are not only exactly solvable with exact ground state degeneracy, but also support completely localized quasiparticle excitations, which are ideal for quantum information processing tasks. Our construction is limited to simulating the toric code and quantum double models, but generalizations to other nonlocal spin Hamiltonians may be possible.