PaperlayerView exact revision on arXiv

Source-linked AI summary

Rapid adiabatic preparation of injective PEPS and Gibbs states

Yimin Ge, András Molnár, J. Ignacio Cirac

arXiv:1508.00570v2quant-ph

TL;DR

The paper seeks faster preparation of injective PEPS and Gibbs-state purifications, including the challenge posed by non-commuting Hamiltonians. It uses smooth adiabatic paths, localizes their evolutions with Lieb–Robinson bounds, and proves efficient preparation under gap assumptions. For non-commuting systems at sufficiently high constant temperature, it constructs a logarithmically local approximation with polynomially many terms and obtains polynomial-time preparation.

Abstract

from arXiv · show

We propose a quantum algorithm for many-body state preparation. It is especially suited for injective PEPS and thermal states of local commuting Hamiltonians on a lattice. We show that for a uniform gap and sufficiently smooth paths, an adiabatic runtime and circuit depth of $O(\operatorname{polylog}N)$ can be achieved for $O(N)$ spins. This is an almost exponential improvement over previous bounds. The total number of elementary gates scales as $O(N\operatorname{polylog}N)$. This is also faster than the best known upper bound of $O(N^2)$ on the mixing times of Monte Carlo Markov chain algorithms for sampling classical systems in thermal equilibrium.

Proof of the adiabatic theorem with almost exponential error decay

The paper proves an adiabatic theorem with almost-exponential error suppression for sufficiently smooth, Gevrey-class Hamiltonian paths. The proof combines an asymptotic adiabatic expansion with endpoint derivative conditions and bounds involving the spectral gap.

Proof strategy

  • The theorem establishes almost-exponential dependence of adiabatic error on runtime for Gevrey-class Hamiltonian paths with vanishing endpoint derivatives.The construction uses an asymptotic expansion whose truncation order is chosen using the Gevrey bounds.Source: Proof of the adiabatic theorem with… · p. 6

Assumptions

  • The proof assumes a finite-dimensional smooth Hamiltonian path with ground-state gap at least ∆ throughout the evolution.Runtime is written as τ = 1/ϵ, and the ground-state energy is fixed to zero.Source: Proof of the adiabatic theorem with… · p. 6

Endpoint conditions

  • Endpoint vanishing of Hamiltonian derivatives ensures the higher-order expansion terms satisfy the required initial and final-state conditions.At the initial endpoint, derivatives vanish so the expansion starts in the ground state; analogous conditions at the final endpoint make the truncated state parallel to the target ground state.Source: Proof of the adiabatic theorem with… · pp. 7–8

Expansion construction

  • The expansion is built recursively from the instantaneous ground state and the pseudo-inverse of the Hamiltonian.The proof controls derivatives of the pseudo-inverse and ground state using Cauchy-integral representations and Gevrey product bounds.Source: Proof of the adiabatic theorem with… · pp. 7–10

Error bound

  • Gevrey derivative estimates bound the asymptotic coefficients and yield the final adiabatic error estimate after selecting a suitable truncation order.The argument first bounds derivatives of the ground state and expansion vectors, then concludes the theorem.Source: Proof of the adiabatic theorem with… · pp. 7, 8, 11, 12

Locality of local adiabatic change

The paper localizes each adiabatic change to a polylogarithmic neighborhood while preserving the evolved state up to a small error. Lieb–Robinson bounds provide the locality estimate, and disjoint local evolutions can be parallelized.

Locality scale

  • For τ = O(log^(1+α)(N/ε)), the required locality radius is polylogarithmic in N/ε.The proof relies on the fact that the achieved locality scales linearly with the runtime.Source: Locality of local adiabatic change · p. 12

Mechanism

  • Lieb–Robinson bounds suppress contributions from terms separated from the changing support by a distance proportional to the runtime.The commutator bound decays exponentially with separation after accounting for propagation time.Source: Locality of local adiabatic change · pp. 12–13

Local replacement

  • Replacing the globally supported Hamiltonian by a localized version does not significantly alter the evolution or final state.The localized generator retains only terms within a distance proportional to the adiabatic runtime from the changing support.Source: Locality of local adiabatic change · p. 12

Relaxations on the assumption of a uniform gap along the path

The uniform-gap requirement along every adiabatic path can be relaxed: a gap at the initial point, together with positivity and bounded operators Qλ, implies a constant lower bound throughout the path.

Gap relaxation

Algorithmic implication

  • Thus, the main-text assumption of a uniformly lower-bounded gap is sufficient to guarantee a constant gap throughout each Hamiltonian path used by the algorithm.The conclusion applies the relaxed theorem to the algorithm’s specific paths.Source: Relaxations on the assumption of a… · p. 14

Proof mechanism

  • The relaxed result follows because the interpolating Hamiltonians remain positive semidefinite and preserve the relevant kernel.The proof compares the path Hamiltonian with an auxiliary operator whose gap inherits the initial inequality.Source: Relaxations on the assumption of a… · p. 14

Gibbs state preparation in the non-commuting case for high temperatures

For non-commuting Hamiltonians, the commuting-state preparation method does not apply directly because the parent Hamiltonian can become nonlocal and have exponentially large terms. At sufficiently high constant temperature, the paper replaces it with a logarithmically local approximation and obtains polynomial-time preparation.

Limitation of commuting construction

  • The commuting construction cannot generally be applied directly to Gibbs states of non-commuting Hamiltonians.The corresponding parent Hamiltonian is nonlocal, and individual term norms may be exponentially large in N.Source: Gibbs state preparation in the… · p. 14

High-temperature approximation

  • At sufficiently high but constant temperature, the nonlocal parent Hamiltonian can be approximated by an O(log N)-local Hamiltonian with O(poly(N)) terms.The approximation is denoted Gr.Source: Gibbs state preparation in the… · p. 14

Spectral properties

  • The approximating and nonlocal parent Hamiltonians have an Ω(1) spectral gap in this regime, so the ground state of Gr approximates the desired Gibbs-state purification.The gap and approximation together support adiabatic preparation of the approximate state.Source: Gibbs state preparation in the… · p. 14

Result

  • The resulting adiabatic algorithm runs in O(poly(N)) time and gives a good approximation to the purification of the non-commuting Gibbs state.The temperature must be sufficiently high but remain constant.Source: Gibbs state preparation in the… · p. 14

3. Prepare adiabatically the ground state of Gr(β)

The section constructs an O(log N)-local approximation Gr to the parent Hamiltonian at sufficiently high constant temperature and establishes that it retains a constant spectral gap. The approximating Hamiltonian has polynomially many efficiently computable terms.

Cluster expansion

  • For sufficiently small constant β, an r = O(log N)-local Hamiltonian Gr with O(poly(N)) terms approximates the parent Hamiltonian.The approximation is obtained by truncating the cluster expansion, with error O(1/poly(N)).Source: §3 · pp. 15–16
  • The approximating Hamiltonian Gr can be calculated in O(poly(N)) time because it contains polynomially many terms and each term is efficiently evaluable.Source: §3 · pp. 15–16
  • The construction uses a cluster expansion expressed through Möbius transformations and local terms whose norms decay exponentially with support size.This decay, together with lattice growth bounds, controls the truncation error at high temperature.Source: §3 · pp. 15–16
  • The cluster expansion is truncated by omitting connected sets of size at least r, yielding an O(log N)-local Hamiltonian above a constant temperature.The truncation produces polynomially small error and preserves a polynomial-size description.Source: §3 · p. 16

Gap of Gnl

  • For sufficiently small constant β, the parent Hamiltonian Gnl has spectral gap Ω(1).The proof uses that Gnl is positive and frustration-free and compares it with separated local terms whose gap is 1.Source: §3 · pp. 16–17
Loading 1508.00570v2…