PaperlayerView exact revision on arXiv

Source-linked AI summary

Perturbative gadgets without strong interactions

Yudong Cao, Daniel Nagaj

arXiv:1408.5881v1quant-ph

TL;DR

Conventional perturbative gadgets require interaction terms or local fields much stronger than the effective interaction they generate, while physically realizable systems may have limited interaction strengths. A condition on the original Hamiltonian’s high-energy subspace avoids the need to bound the norm of the whole perturbation. For 2-local targets with O(1) interaction strength, the gadget approximates the full spectrum within ε using 2-local interactions of strength O(ε).

  • Problem

    Conventional perturbative gadgets require interaction terms or local fields much stronger than the effective interaction they generate, while physically realizable systems may have limited interaction strengths.

    Source: §1 · p. 2

  • Method

    A condition on the original Hamiltonian’s high-energy subspace avoids the need to bound the norm of the whole perturbation.

    Source: §3.1 · p. 10

  • Results

    For 2-local targets with O(1) interaction strength, the gadget approximates the full spectrum within ε using 2-local interactions of strength O(ε).

    Source: §1.1 · p. 3

  • Takeaways & Limitations

    The construction supports coupling and eigenvalue-gap amplification and is presented as applicable to restricted-Hamiltonian complexity, area-law counterexamples, and mediated interactions.

    Source: §1.2 · p. 4

    The construction has massive degree overhead, and without degree-reduction gadgets the authors cannot reproduce their results in simpler geometries.

    Source: §1.2 · p. 5

Abstract

from arXiv · show

Perturbative gadgets are used to construct a quantum Hamiltonian whose low-energy subspace approximates a given quantum $k$-body 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 target many-body 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 show how to apply this gadget construction for approximating 3- and $k$-body 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 many weak interactions simulating a much stronger quantum many-body interaction.

1 Introduction

The paper asks how to realize many-body quantum interactions from restricted local terms, where conventional perturbative gadgets rely on interactions much stronger than the effective interaction. It presents weak-coupling 2-body constructions, extends them to 3- and k-body Hamiltonians, and discusses their applications and resource costs.

1.1 Summary

  • For 2-local targets with O(1) interaction strength, the construction approximates the full spectrum within ε using 2-local interactions of strength O(ε).The gadget uses polynomially many extra qubits and has Pauli degree polynomial in the target degree, norm of Helse, ε^-1, and term count.Source: §1.1 · p. 3
  • The 3-body construction approximates a target Hamiltonian within ε using 2-local interactions of strength O(ε), with polynomial overhead in ancillas and Pauli degree.The stated result assumes O(1) target interaction strength and a non-negative Helse with polynomially bounded norm.Source: §1.1 · pp. 3–4
  • The construction can be repeated in parallel to amplify couplings and eigenvalue gaps, producing an effective θH from interactions of O(1) strength or weaker.The corollary states that the low-lying spectrum approximates θ times the target spectrum and that low-lying states approximate the target states with ancillas in |0⋯0⟩.Source: §1.1 · p. 4
  • The k-local extension combines existing k-to-2-local gadgets with the weak 2-body construction, with expected total qubit count exponential in k.The authors note this overhead is not a problem for k = 3.Source: §1.1 · p. 4

1.2 Conclusions and Open Questions

  • The core construction replaces strong interactions with repeated interactions mediated by ancillas that remain close to |0⟩ in low-energy states.Parallelization requires a new condition for perturbation-series convergence that avoids bounding the norm of the entire perturbation.Source: §1.2 · p. 4
  • The authors identify applications to QMA-completeness of restricted 2-local Hamiltonians, efficient universality, a generalized area-law counterexample, and practical mediated interactions.The practical application is presented as an envisioned use of many coupled mediator spins.Source: §1.2 · p. 4
  • The construction has massive degree overhead, and without a quantum degree-reduction gadget the authors cannot reproduce the results in simpler geometries.They point to creating O(1)-norm effective interactions from O(1)-strength terms in 3D or 2D lattices as an open possibility.Source: §1.2 · p. 5
  • Robustness to deviations from the specified Hamiltonians, efficient parameter selection, and poly(k)-overhead k-to-2-body reductions remain open questions.The authors attribute the exponential overhead in the cited k-body reduction to conventional gadgets requiring interaction strengths polynomial in ε^-1.Source: §1.2 · p. 5

2 Effective interactions based on perturbation theory

Perturbative gadgets split a Hamiltonian into an ancilla-only penalty term and a perturbation coupling ancillas to target spins. The self-energy of the perturbed low-energy subspace can approximate an effective target Hamiltonian when it remains close to that Hamiltonian across the relevant energy range.

2 Effective interactions based on perturbation theory

  • The gadget Hamiltonian ˜H = H + V uses H to energetically favor an ancilla state or subspace and V to couple target spins to ancillas.The construction seeks to reproduce the target Hamiltonian within the low-energy subspace.Source: §2 · p. 5
  • Expanding the perturbed resolvent in powers of V yields higher-order terms that can generate effective many-body interactions.The expansion begins ˜G = G + GV G + GV GV G + · · ·.Source: §2 · pp. 5–6
  • The self-energy Σ−(z) approximates the gadget’s low-energy spectrum when it is roughly constant over the relevant range of z.It is defined from the projected resolvent as Σ−(z) = zI − (Π−˜G(z)Π−)−1.Source: §2 · pp. 5–6
  • The modified gadget approximation theorem requires separated perturbed low- and unperturbed high-energy subspaces and an effective Hamiltonian approximating Σ−(z) across an expanded energy interval.The effective Hamiltonian’s spectrum must lie below ∆/2 − ϵ, and the self-energy error must be at most ϵ throughout the specified interval.Source: §2 · p. 6
  • Unlike the original theorem’s condition ∥V∥ ≤ ∆/2, the modified condition avoids a bound that would limit ancilla counts regardless of perturbation structure.The authors note that perturbation theory in a similar context was justified by Bravyi et al. [6].Source: §2 · p. 6
  • The construction engineers the self-energy to be ϵ-close to Htarg ⊗ Π−, then checks both conditions of the modified theorem.The authors first review usual two-body gadgets before presenting a construction with more ancillas and weaker interactions.Source: §2 · p. 6

3 A new gadget for 2-body interactions

This section develops a 2-body gadget using O(ε)-strength interactions to simulate arbitrary O(1)-strength 2-local terms. It establishes a condition separating the low-energy subspace from the unperturbed high-energy subspace, proves convergence of the perturbation series and approximation by the effective Hamiltonian, and identifies the costs in ancillary qubits and interaction-graph degree.

3 A new gadget for 2-body interactions

  • O(ε)-strength interactions simulate arbitrary O(1)-strength 2-local target interactions without large-norm terms.The construction’s effective Hamiltonian matches the target up to an overall spectral shift, with β and J made small through choices of R and C.Source: §3 · pp. 7–8
  • A ferromagnetic core of C ancillas creates a gap Δ = JC, which remains unchanged when R direct ancillas are connected to it.The core uses pairwise ferromagnetic ZZ interactions and local fields of strength J/2; the direct ancillas couple to the target spins with strength β.Source: §3 · pp. 7–8
  • Parallel application handles M target terms using a shared core because second-order transitions flip and return one ancilla independently for each term.Each target term receives R direct ancillas; the construction’s total ancilla count is MR + C.Source: §3 · p. 9, Figure 3 · p. 9

3.1 The 2-local construction satisfies the subspace condition.

  • The proof lower-bounds the high-subspace energy by simplifying target operators and analyzing invariant core-state sectors as one-local ancilla Hamiltonians.The argument first replaces the target operators by identities and bounds Helse, then reduces interactions with the core to shifts and fields on direct ancillas.Source: §3.1 · pp. 10–11
  • When Helse is positive semidefinite and Δ ≥ 160Mγmax, the stated subspace condition holds for the parallel 2-body gadget.Here γmax is the largest absolute target coefficient; the condition separates the perturbed low-energy subspace from the unperturbed high-energy subspace.Source: §3 · p. 10, §3.1 · p. 11
  • Every state in L2 has energy above λ*, establishing the subspace condition for the 2-local construction.The proof combines this bound with the preceding result to establish Claim 1.Source: §3.1 · p. 15

3.2 The perturbation series converges.

  • O(ϵ) interaction strengths suffice for the 2-body gadget, whose effective Hamiltonian approximates the target up to O(ϵ), at the cost of poly(ϵ^-1) ancillas.The construction sets ∆ = M^3R^d for a constant d in (0, 1); the authors describe the weak-interaction strength and ancilla count as a tradeoff.Source: §3.2 · p. 15, §3.2.2 · p. 19

3.2.1 A simplified calculation without Helse

  • Without Helse, odd-order terms vanish, and a Catalan-number bound shows that even-order error terms decay exponentially and sum to a small error when ∆≫M.The bound overcounts valid transition paths, which suffices to establish convergence in this simplified case.Source: §3.2.1 · pp. 16–17

3.2.2 A general calculation including Helse

  • With Helse included, transitions may leave the ancilla state unchanged; bounding these paths by Motzkin numbers yields a convergent geometric error series.The resulting effective Hamiltonian is the target Hamiltonian projected onto L−, plus an overall shift, with error O(ϵ).Source: §3.2.2 · pp. 17, 19
  • For a target on n qubits, the gadget uses n + MR + C qubits, and its interaction-graph degree is poly(D, ϵ^-1, ∥Helse∥, M).Here D is the target interaction-graph degree; the authors characterize both resource overheads as polynomial in the indicated parameters.Source: §3.2.2 · p. 19

4 Reducing k-body to 2-body interactions (k ≥3)

The paper describes routes to reduce 3- and k-body Hamiltonians to weak 2-body interactions, but a proposed direct parallelized construction lacks desirable properties. Existing standard reductions can be combined with the 2-body gadget, though efficiency remains a concern.

4 Reducing k-body to 2-body interactions (k ≥3)

  • The attempted direct parallelized 3-to-2-body gadget does not have all the desirable properties of the 2-body construction.The authors identify proving the relevant conditions as difficult for k-body gadgets as well.Source: §4 · p. 19
  • A 3-body interaction can be approximated by replacing the standard gadget’s strong local field with a core and reducing its strong 2-body terms using the weak 2-body gadget.The standard construction uses a direct ancilla with strong target couplings and an additional coupling to compensate for a second-order error.Source: §4 · p. 19, Figure 7 · p. 20
  • For general k-body reduction, the paper proposes applying the weak 2-body gadget to a standard 2-local gadget without extra 1-local terms, but notes that the resulting efficiency is poor.The authors plan to detail and improve these constructions in subsequent work.Source: §4 · p. 19

A Upper bounds on low-order perturbation series terms for 2-body gadgets

The appendix bounds low-order contributions to the self-energy expansion for the 2-body gadget. It relates the second-order target contribution to the higher-order bounds and suggests geometric convergence.

A Upper bounds on low-order perturbation series terms for 2-body gadgets

  • The appendix’s low-order calculations are presented as upper bounds intended to illustrate the perturbation series for the 2-body gadget.The authors speculate that the even-order bounds decrease geometrically for their parameter choice, implying exponential convergence.Source: A Upper bounds on low-order… · pp. 21, 23
  • The second-order contribution sums over target terms and has norm on the order of M for unit-norm target operators.Each target term’s R direct ancillas contribute in parallel to the expansion.Source: A Upper bounds on low-order… · pp. 21–22
  • At fourth order, the bound is ∥T4∥ ≤ N(N−1)(2βmax)^4, with an additional relative factor 2Mγmax/∆ compared with the second-order term.The bound counts processes involving pairs of direct ancillas.Source: A Upper bounds on low-order… · p. 22
  • At sixth order, ∥T6∥ is bounded by two terms from distinct transition patterns, and the authors note another relative factor 2Mγmax/∆.The displayed bound is given in equation (64); the comparison is with the fourth-order bound.Source: A Upper bounds on low-order… · pp. 22–23

B Justification for the sequence of simplifying Hamiltonians when bounding E+

The energy comparison argues that the minimum energy in the high-energy subspace cannot increase when target–ancilla couplings are removed and the direct ancillas instead receive −X terms.

B Justification for the sequence of simplifying Hamiltonians when bounding E+

  • The argument compares the interaction contribution using the fact that Aa is a Pauli operator, so its relevant matrix element has magnitude at most 1.This bounds the target-coupled contribution against the version using −I.Source: B Justification for the sequence of… · p. 23
  • Replacing target–ancilla interactions Aa ⊗ Xj with −I ⊗ Xj can only lower or preserve the minimum energy restricted to L+.The proof chooses positive ancilla-state coefficients and a target state minimizing Helse, while preserving the expectation of the diagonal part H.Source: B Justification for the sequence of… · p. 23
  • The proposed three-body construction uses q ancillas to mediate the target interaction and w and y ancillas to cancel unwanted terms.The figure describes cancellation of extra 2-local and 1-body terms.Source: Figure 8 · p. 24

C An alternative idea for 3-local gadget construction

The proposed 3-local gadget uses a core and direct ancillas to generate a target interaction at third order, with unwanted terms canceled by additional couplings. The authors identify unresolved conditions that prevent establishing this as a gadget using only weak interactions.

C An alternative idea for 3-local gadget construction

  • Each gadget uses a core of C qubits and three sets of R direct ancillas, coupled to one another and to the three target spins.The core qubits interact as a complete graph with ferromagnetic strength J/2 and a local field J/2.Source: C An alternative idea for 3-local… · p. 24
  • The perturbative construction can be applied in parallel to M target terms because third-order transitions through the direct ancilla do not involve more than one direct ancilla.The passage describes the gadget Hamiltonian for M different 3-local target terms.Source: C An alternative idea for 3-local… · p. 24
  • The construction generates the desired 3-local interaction at third order and cancels unwanted terms, leaving the target interaction and an overall energy shift.The last two terms in the gadget Hamiltonian compensate for unwanted two-local and one-local terms in the expansion.Source: C An alternative idea for 3-local… · p. 25
  • The authors leave open whether this 3-local construction can satisfy the subspace and convergence conditions with all coupling strengths O(ϵ).Their analysis identifies a required asymptotic scaling that is incompatible with keeping the couplings weak, so this construction cannot consist only of weak terms.Source: C An alternative idea for 3-local… · pp. 25–26

Reducing k-body to 2-body interactions

The authors describe routes from k-body interactions to 2-body interactions, but characterize the conventional route as inefficient and the direct parallelized alternative as difficult to verify.

Reducing k-body to 2-body interactions

  • Applying standard k-body-to-2-body gadgets and then the strong-from-weak construction yields k-local interactions from weak 2-body interactions, but with poor efficiency.The conventional k-body gadgets typically use strong interactions before the weak-interaction construction is applied.Source: Reducing k-body to 2-body interactions · p. 26
  • A direct parallelized construction modeled on the 3-body gadget is proposed as an alternative, with core interactions replacing strong couplings.The passage points to Figure 8 as the analogous construction.Source: Reducing k-body to 2-body interactions · p. 26
  • For that direct k-body approach, the authors say it will be difficult to establish the subspace conditions, perturbation-series convergence, and weak interaction strengths.Source: Reducing k-body to 2-body interactions · p. 26
Loading 1408.5881v1…