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:1810.00865 · Annales Henri Poincaré

Perturbation Gadgets: Arbitrary Energy Scales from a Single Strong Interaction

Johannes Bausch

Published Nov 29, 2019• 4 citations
arXivHTMLPDF

Abstract

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 appearsk-body and approximates a target Hamiltonian to within precision $$\epsilon $$ ϵ . 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 $$\Theta (1/N^{2+\delta })$$ Θ(1/N2+δ) , for a small parameter $$\delta >0$$ δ>0 , and forNterms in the target Hamiltonian $$\mathbf H_\mathrm {t}=\sum _{i=1}^N \mathbf h_i$$ Ht=∑i=1Nhi to be simulated: in its low-energy subspace, our constructed system can approximate any such target Hamiltonian $$\mathbf H_t$$ Ht with norm ratios $$r=\max _{i,j\in \{1,\ldots ,N\}}\Vert \mathbf h_i\Vert / \Vert \mathbf h_j \Vert ={{\,\mathrm{O}\,}}(\exp (\exp ({{\,\mathrm{poly}\,}}N)))$$ r=maxi,j∈{1,…,N}‖hi‖/‖hj‖=O(exp(exp(polyN))) to withinrelativeprecision $${{\,\mathrm{O}\,}}(N^{-\delta })$$ 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 theLocal Hamiltonianproblem, 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.

DOI
10.1007/s00023-019-00871-7

Related papers

Perturbation Gadgets: Arbitrary Energy Scales from a Single Strong Interaction

Johannes Bausch

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.

•Jun 8, 2019•4 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•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

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•4 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

Many-body perturbation theory for strongly correlated effective Hamiltonians using effective field theory methods

Raphaël Photopoulos, Antoine Boulet

Introducing low-energy effective Hamiltonians is usual to grasp most correlations in quantum many-body problems. For instance, such effective Hamiltonians can be treated at the mean-field level to reproduce some physical properties of interest. Employing effective Hamiltonians that contain many-body correlations renders the use of perturbative many-body techniques difficult because of the overcounting of correlations. In this work, we develop a strategy to apply an extension of the many-body perturbation theory starting from an effective interaction that contains correlations beyond the mean-field level. The goal is to re-organize the many-body calculation to avoid the overcounting of correlations originating from the introduction of correlated effective Hamiltonians in the description. For this purpose, we generalize the formulation of the Rayleigh-Schrödinger perturbation theory by including free parameters adjusted to reproduce the appropriate limits. In particular, the expansion in the bare weak-coupling regime and the strong-coupling limit serves as a valuable input to fix the value of the free parameters appearing in the resulting expression. This method avoids double counting of correlations using beyond-mean-field strategies for the description of many-body systems. The ground state energy of various systems relevant for ultracold atomic, nuclear, and condensed matter physics is reproduced qualitatively beyond the domain of validity of the standard many-body perturbation theory. Finally, our method suggests interpreting the formal results obtained as an effective field theory using the proposed reorganization of the many-body calculation. The results, like ground state energies, are improved systematically by considering higher orders in the extended many-body perturbation theory while maintaining a straightforward polynomial expansion.

arXiv:2402.17627•SciPost Physics•Jan 6, 2025•0 citations
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 appearsk-body and approximates a target Hamiltonian to within precision ϵ\epsilon ϵ ϵ . 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+δ)\Theta (1/N^{2+\delta })Θ(1/N2+δ) Θ(1/N2+δ) , for a small parameter δ>0\delta >0δ>0 δ>0 , and forNterms in the target Hamiltonian Ht=∑i=1Nhi\mathbf H_\mathrm {t}=\sum _{i=1}^N \mathbf h_iHt​=∑i=1N​hi​ Ht=∑i=1Nhi to be simulated: in its low-energy subspace, our constructed system can approximate any such target Hamiltonian Ht\mathbf H_tHt​ Ht with norm ratios r=max⁡i,j∈{1,…,N}∥hi∥/∥hj∥= O (exp⁡(exp⁡( poly N)))r=\max _{i,j\in \{1,\ldots ,N\}}\Vert \mathbf h_i\Vert / \Vert \mathbf h_j \Vert ={{\,\mathrm{O}\,}}(\exp (\exp ({{\,\mathrm{poly}\,}}N)))r=maxi,j∈{1,…,N}​∥hi​∥/∥hj​∥=O(exp(exp(polyN))) r=maxi,j∈{1,…,N}‖hi‖/‖hj‖=O(exp(exp(polyN))) to withinrelativeprecision  O (N−δ){{\,\mathrm{O}\,}}(N^{-\delta })O(N−δ) 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 theLocal Hamiltonianproblem, 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.
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.
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.
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.
Introducing low-energy effective Hamiltonians is usual to grasp most correlations in quantum many-body problems. For instance, such effective Hamiltonians can be treated at the mean-field level to reproduce some physical properties of interest. Employing effective Hamiltonians that contain many-body correlations renders the use of perturbative many-body techniques difficult because of the overcounting of correlations. In this work, we develop a strategy to apply an extension of the many-body perturbation theory starting from an effective interaction that contains correlations beyond the mean-field level. The goal is to re-organize the many-body calculation to avoid the overcounting of correlations originating from the introduction of correlated effective Hamiltonians in the description. For this purpose, we generalize the formulation of the Rayleigh-Schrödinger perturbation theory by including free parameters adjusted to reproduce the appropriate limits. In particular, the expansion in the bare weak-coupling regime and the strong-coupling limit serves as a valuable input to fix the value of the free parameters appearing in the resulting expression. This method avoids double counting of correlations using beyond-mean-field strategies for the description of many-body systems. The ground state energy of various systems relevant for ultracold atomic, nuclear, and condensed matter physics is reproduced qualitatively beyond the domain of validity of the standard many-body perturbation theory. Finally, our method suggests interpreting the formal results obtained as an effective field theory using the proposed reorganization of the many-body calculation. The results, like ground state energies, are improved systematically by considering higher orders in the extended many-body perturbation theory while maintaining a straightforward polynomial expansion.