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

Quantum Information and Computation

Efficient optimization of perturbative gadgets

CaoYudong, KaisSabre

Published Aug 1, 2017• 1 citation
Publisher

Abstract

Perturbative gadgets are general techniques for reducing many-body spin interactions to two-body ones using perturbation theory. This allows for potential realization of effective many-body interac...
DOI
10.5555/3179561.3179564

Related papers

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•97 citations

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•23 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•14 citations

UEfficient optimization of perturbative gadgets

Yudong Cao, Sabre Kais

Perturbative gadgets are general techniques for reducing many-body spin interactions to two-body ones using perturbation theory. This allows for potential realization of effective many-body interactions using more physically viable two-body ones. In parallel with prior work (arXiv:1311.2555 [quant-ph]), here we consider minimizing the physical resource required for implementing the gadgets initially proposed by Kempe, Kitaev and Regev (arXiv:quant-ph/0406180) and later generalized by Jordan and Farhi (arXiv:0802.1874v4). The main innovation of our result is a set of methods that efficiently compute tight upper bounds to errors in the perturbation theory. We show that in cases where the terms in the target Hamiltonian commute, the bounds produced by our algorithm are sharp for arbitrary order perturbation theory. We provide numerics which show orders of magnitudes improvement over gadget constructions based on trivial upper bounds for the error term in the perturbation series. We also discuss further improvement of our result by adopting the Schrieffer-Wolff formalism of perturbation theory and supplement our observation with numerical results.

Quantum Information and Computation•Aug 1, 2017•3 citations

-2 An approximate method for solving the quantum many-body problem

L.D. Faddeev, L.A. Khalfin, I.V. Komarov

CRC Press eBooks•May 21, 2004•2 citations

Gadgets for simulating a non-native $XX$ interaction in quantum annealing

Banks, Robert J., Natasha Feinstein, Roopayan Ghosh +2 more

In certain scenarios, quantum annealing can be made more efficient by additional $XX$ interactions. It has been shown that the additional interactions can reduce the scaling of perturbative crossings. In traditional annealing devices these couplings do not exist natively. In this work, we develop two gadgets to achieve this: a three-body gadget that requires a strong $ZZZ$ interaction; and a one-hot gadget that uses only local $X$ drives and two-body $ZZ$ interactions. The gadgets partition the Hilbert space to effectively generate a limited number of $XX$ interactions in the low-energy subspace. We numerically verify that the one-hot gadget can mitigate a perturbative crossing on a toy problem. These gadgets establish new pathways for implementing and exploiting $XX$ interactions, enabling faster and more robust quantum annealing.

arXiv:2503.16663•Mar 20, 2025•6 citations
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 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.
Perturbative gadgets are general techniques for reducing many-body spin interactions to two-body ones using perturbation theory. This allows for potential realization of effective many-body interactions using more physically viable two-body ones. In parallel with prior work (arXiv:1311.2555 [quant-ph]), here we consider minimizing the physical resource required for implementing the gadgets initially proposed by Kempe, Kitaev and Regev (arXiv:quant-ph/0406180) and later generalized by Jordan and Farhi (arXiv:0802.1874v4). The main innovation of our result is a set of methods that efficiently compute tight upper bounds to errors in the perturbation theory. We show that in cases where the terms in the target Hamiltonian commute, the bounds produced by our algorithm are sharp for arbitrary order perturbation theory. We provide numerics which show orders of magnitudes improvement over gadget constructions based on trivial upper bounds for the error term in the perturbation series. We also discuss further improvement of our result by adopting the Schrieffer-Wolff formalism of perturbation theory and supplement our observation with numerical results.
Gadgets for simulating a non-native XXXXXX interaction in quantum annealing
In certain scenarios, quantum annealing can be made more efficient by additional XXXXXX interactions. It has been shown that the additional interactions can reduce the scaling of perturbative crossings. In traditional annealing devices these couplings do not exist natively. In this work, we develop two gadgets to achieve this: a three-body gadget that requires a strong ZZZZZZZZZ interaction; and a one-hot gadget that uses only local XXX drives and two-body ZZZZZZ interactions. The gadgets partition the Hilbert space to effectively generate a limited number of XXXXXX interactions in the low-energy subspace. We numerically verify that the one-hot gadget can mitigate a perturbative crossing on a toy problem. These gadgets establish new pathways for implementing and exploiting XXXXXX interactions, enabling faster and more robust quantum annealing.