Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2210.03099 · Physical Review A

Perturbative gadgets for gate-based quantum computing: Nonrecursive constructions without subspace restrictions

Simon Cichy, Paul K. Faehrmann, Sumeet Khatri, Jens Eisert

Published May 20, 2024• 3 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.109.052624

Related papers

Perturbative gadgets without strong interactions

Yudong Cao, Daniel Nagaj

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 $\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 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 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(\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 several weak interactions simulating a much stronger quantum many-body interaction.

arXiv:1408.5881•Quantum Information and Computation•Oct 1, 2015•17 citations

Nonperturbative embedding for highly nonlocal Hamiltonians

Yiğit Subaşı, Christopher Jarzynski

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 $k\mathrm{th}$ 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.

arXiv:1601.02922•Physical Review A•Jul 25, 2016•13 citations

Hamiltonian gadgets with reduced resource requirements

Yudong Cao, Ryan Babbush, Jacob Biamonte +1 more

Application of the adiabatic model of quantum computation requires efficient encoding of the solution to computational problems into the lowest eigenstate of a Hamiltonian that supports universal adiabatic quantum computation. Experimental systems are typically limited to restricted forms of two-body interactions. Therefore, universal adiabatic quantum computation requires a method for approximating quantum many-body Hamiltonians up to arbitrary spectral error using at most two-body interactions. Hamiltonian gadgets, introduced around a decade ago, offer the only current means to address this requirement. Although the applications of Hamiltonian gadgets have steadily grown since their introduction, little progress has been made in overcoming the limitations of the gadgets themselves. In this experimentally motivated theoretical study, we introduce several gadgets which require significantly more realistic control parameters than similar gadgets in the literature. We employ analytical techniques which result in a reduction of the resource scaling as a function of spectral error for the commonly used subdivision, three- to two-body and $k$-body gadgets. Accordingly, our improvements reduce the resource requirements of all proofs and experimental proposals making use of these common gadgets. Next, we numerically optimize these gadgets to illustrate the tightness of our analytical bounds. Finally, we introduce a gadget that simulates a $YY$ interaction term using Hamiltonians containing only ${X,Z,XX,ZZ}$ terms. Apart from possible implications in a theoretical context, this work could also be useful for a first experimental implementation of these key building blocks by requiring less control precision without introducing extra ancillary qubits.

arXiv:1311.2555•Physical Review A•Jan 12, 2015•35 citations

Perturbative gadgets without strong interactions

CaoYudong, NagajDaniel

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 e. Typically, gadget construction...

Quantum Information and Computation•Oct 1, 2015•0 citations

Perturbative gadgets at arbitrary orders

Stephen P. Jordan, Edward Farhi

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 $\mathit{k}$-body effective interactions from two-body Hamiltonians. These effective interactions arise from the $\mathit{k}$th order in perturbation theory.

arXiv:0802.1874•Physical Review A•Jun 19, 2008•91 citations

Simplifying quantum double Hamiltonians using perturbative gadgets

Robert König

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.

arXiv:0901.1333•Jan 9, 2009•0 citations
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 rkrkrk additional qubits for a kkk-body Hamiltonian comprising rrr 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 kkk-local Hamiltonian up to an absolute error ϵ\epsilonϵ. Typically, gadget constructions involve terms with large interaction strengths of order poly(ϵ−1)\text{poly}(\epsilon^{-1})poly(ϵ−1). Here we present a 2-body gadget construction and prove that it approximates a Hamiltonian of interaction strength γ=O(1)\gamma = O(1)γ=O(1) up to absolute error ϵ≪γ\epsilon\ll\gammaϵ≪γ using interactions of strength O(ϵ)O(\epsilon)O(ϵ) 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 discuss how to apply this gadget construction for approximating 3- and kkk-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))O(\text{poly}(\epsilon^{-1}))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.
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 kkk-body interactions, their use is limited to small kkk because the strength of interaction is kthk\mathrm{th}kth order in perturbation theory. In this paper we develop a nonperturbative technique for obtaining effective kkk-body interactions using Hamiltonians consisting of at most lll-body interactions with l<kl<kl<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 kkk-body interaction irrespective of the value of kkk. 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.
Application of the adiabatic model of quantum computation requires efficient encoding of the solution to computational problems into the lowest eigenstate of a Hamiltonian that supports universal adiabatic quantum computation. Experimental systems are typically limited to restricted forms of two-body interactions. Therefore, universal adiabatic quantum computation requires a method for approximating quantum many-body Hamiltonians up to arbitrary spectral error using at most two-body interactions. Hamiltonian gadgets, introduced around a decade ago, offer the only current means to address this requirement. Although the applications of Hamiltonian gadgets have steadily grown since their introduction, little progress has been made in overcoming the limitations of the gadgets themselves. In this experimentally motivated theoretical study, we introduce several gadgets which require significantly more realistic control parameters than similar gadgets in the literature. We employ analytical techniques which result in a reduction of the resource scaling as a function of spectral error for the commonly used subdivision, three- to two-body and kkk-body gadgets. Accordingly, our improvements reduce the resource requirements of all proofs and experimental proposals making use of these common gadgets. Next, we numerically optimize these gadgets to illustrate the tightness of our analytical bounds. Finally, we introduce a gadget that simulates a YYYYYY interaction term using Hamiltonians containing only X,Z,XX,ZZ{X,Z,XX,ZZ}X,Z,XX,ZZ terms. Apart from possible implications in a theoretical context, this work could also be useful for a first experimental implementation of these key building blocks by requiring less control precision without introducing extra ancillary qubits.
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\mathit{k}k-body effective interactions from two-body Hamiltonians. These effective interactions arise from the k\mathit{k}kth order in perturbation theory.
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.