Source-linked AI summary
An efficient and exact noncommutative quantum Gibbs sampler
Chi-Fang Chen, Michael J. Kastoryano, András Gilyén
TL;DR
Quantum Gibbs samplers have lacked a consensus approach with provable guarantees, in part because enforcing detailed balance has relied on energy estimation. This paper constructs an efficiently simulable Lindbladian with exact detailed balance, and shows that lattice locality and purification yield localized dynamics and an adiabatic path for the purified Gibbs state.
Problem
Existing quantum Gibbs samplers generally enforce detailed balance only approximately unless individual energy eigenstates can be distinguished exactly.
Source: §I · pp. 1–2Method
The paper constructs an exactly detailed-balanced Lindbladian with Gaussian or Metropolis transition weights and a corresponding coherent term.
Source: §I · p. 2, A. Main results · p. 4Results
The Lindbladian has the Gibbs state as an exact stationary state and, for lattice Hamiltonians, uses quasi-local terms of radius ˜O(vLRβ).
Source: A. Main results · pp. 4–5Takeaways & Limitations
Purification yields temperature-dependent parent Hamiltonians whose zero-eigenstate is the canonical purified Gibbs state, with an adiabatic path for its preparation.
Source: §I · p. 2
Abstract
from arXiv · showhide
Preparing thermal and ground states is an essential quantum algorithmic task for quantum simulation. In this work, we construct the first efficiently implementable and exactly detailed-balanced Lindbladian for Gibbs states of arbitrary noncommutative Hamiltonians. Our construction can also be regarded as a continuous-time quantum analog of the Metropolis-Hastings algorithm. To prepare the quantum Gibbs state, our algorithm invokes Hamiltonian simulation for a time proportional to the mixing time and the inverse temperature $\beta$, up to polylogarithmic factors. Moreover, the gate complexity reduces significantly for lattice Hamiltonians as the corresponding Lindblad operators are (quasi-) local (with radius $\sim\beta$) and only depend on local Hamiltonian patches. Meanwhile, purifying our Lindbladians yields a temperature-dependent family of frustration-free "parent Hamiltonians", prescribing an adiabatic path for the canonical purified Gibbs state (i.e., the Thermal Field Double state). These favorable features suggest that our construction serves as a quantum algorithmic counterpart to classical Markov chain Monte Carlo sampling.
I. INTRODUCTION
Quantum detailed balance has been difficult to enforce exactly and efficiently because existing approaches rely on energy estimation. The paper constructs an exactly detailed-balanced Gibbs-sampling Lindbladian, with efficient simulation, lattice locality, and a purified-state adiabatic path.
I. INTRODUCTION
- The work frames its construction as a quantum counterpart to classical MCMC, whose detailed balance supports a simple stationary-state condition and whose complexity often depends on mixing time.The target quantum Gibbs state is stationary under the designed Lindbladian.Source: §I · p. 1
- Existing quantum Gibbs samplers generally enforce detailed balance only approximately unless they distinguish individual energy eigenstates, creating an accuracy-efficiency tradeoff.The cited challenge is tied to energy estimation and energy-time uncertainty.Source: §I · pp. 1–2
A. Main results
- The design enforces detailed balance smoothly without energy estimates, using a carefully chosen coherent term to cancel unwanted errors from the dissipative part.The construction uses smooth polynomial functions of the Hamiltonian without a phase-estimation subroutine.Source: §I · p. 2
I. INTRODUCTION
- Purifying the Lindbladian gives temperature-dependent parent Hamiltonians whose zero-eigenstate is the canonical Gibbs purification, and whose locality persists for lattice Hamiltonians.The resulting adiabatic path prepares the Thermal Field Double state.Source: §I · pp. 2–3
A. Main results
- A Gaussian transition weight can restrict transitions to a narrow energy window and potentially freeze dynamics, while a suitable linear combination of widths recovers Metropolis-like weights.Quantum detailed balance is preserved under linear combinations of Lindbladians.Source: A. Main results · p. 4
- The constructed Lindbladian satisfies quantum detailed balance exactly, making the Gibbs state stationary for both Gaussian and Metropolis transition weights.The Metropolis weight uses its corresponding coherent term.Source: A. Main results · p. 4
- For unit Lindbladian evolution time, the Hamiltonian simulation time is proportional to β up to polylogarithmic factors.The unit-time update is described as requiring characteristic simulation time ∼β.Source: §I · p. 2, A. Main results · p. 5
- For lattice Hamiltonians, each jump-centered Lindbladian term is quasi-local with radius ˜O(vLRβ), making cost per unit evolution time essentially independent of system size up to logarithmic dependencies.Lieb-Robinson bounds confine the terms to nearby Hamiltonian patches, with exponentially decaying tails.Source: A. Main results · p. 5
1. Purifying the Lindbladians
Purifying the exactly detailed-balanced Lindbladian yields a Hermitian, frustration-free discriminant that annihilates the purified Gibbs state. For lattice Hamiltonians, the resulting parent Hamiltonian is quasi-local, with terms whose radius scales with β.
1. Purifying the Lindbladians
- The discriminant is Hermitian, frustration-free, and annihilates the purified Gibbs state.The purified Gibbs state is a zero-eigenvector of the discriminant.Source: §1 · p. 6
- The parent Hamiltonian turns preparation of the purified Gibbs state into a ground-state problem and inherits quasi-locality for lattice Hamiltonians.Its terms have radius ∼v_LRβ, and its implementation cost is analogous to a constant-time Lindbladian evolution.Source: §1 · pp. 5–6
B. Roadmap
- The parent Hamiltonian is negative semidefinite, so the purified Gibbs state is its top eigenstate unless the operator is multiplied by −1.The paper leaves direct block-encoding of I + Hβ as an open problem for this construction.Source: B. Roadmap · p. 6, §1 · p. 6
A. Operator Fourier Transform
- The operator Fourier Transform groups jump-operator components by Bohr energy differences, allowing the construction to use smooth frequency weights instead of resolving exact energies.The relevant frequencies are energy differences arising from the commutator with H.Source: A. Operator Fourier Transform · p. 7
B. Exact detailed balance from that of the transition part
- A detailed-balanced Lindbladian can be constructed by choosing transition operators, fixing the decay part, then explicitly prescribing a coherent term.For a given Hermitian decay operator, the coherent term is unique up to an identity term.Source: B. Exact detailed balance from that of… · pp. 8–9
C. Exact detailed balance for Gaussian weights and their linear combinations
The section establishes exact detailed balance for Gaussian transition weights and their linear combinations. Gaussian filters permit finite energy width and efficient implementation, while combinations can broaden the transition band.
1. Exact detailed balance of the transition part
- Gaussian weights yield exact detailed balance for the transition part when their coefficient matrix satisfies the energy-domain symmetry.The symmetry is α_ν1,ν2 = α_-ν2,-ν1 e^-β(ν1+ν2)/2.Source: §1 · p. 10
- A positive-semidefinite coefficient matrix ensures positivity, and the Gaussian coefficients satisfy the required skew-symmetry.These properties establish the coefficient conditions used for exact detailed balance.Source: §1 · p. 11
- The Gaussian construction retains exact detailed balance with finite energy width, avoiding a width that scales linearly with 1/ϵ.The Gaussian weighted operator Fourier Transform has cost scaling with β and polylogarithmically with precision.Source: §1 · p. 12
- Gaussian transition weights concentrate on a narrow band around ωγ, which may increase mixing time relative to broader weights.The section proposes linear combinations of Gaussians to address this restriction.Source: §1 · p. 12
2. Adding the unitary term
The coherent term completes the exactly detailed-balanced Lindbladian after the transition and decay parts are set. Linear combinations of Gaussians offer filters with broader transition bands that resemble Metropolis and Glauber weights.
2. Adding the unitary term
- Trace preservation fixes the decay part, after which Lemma II.1 prescribes the coherent term needed to complete the Lindbladian.The displayed coherent term is given in the frequency domain for implementation.Source: §2 · p. 12
3. Linear combination of Gaussians
- Linear combinations of Gaussians widen the transition band and can produce filters resembling Metropolis and Glauber weights.The Metropolis-like limit is shifted by βσ².Source: §3 · p. 13
- The Gaussian linear-combination construction permits nonnegative coefficients when g(x) ≥ 0, though that condition is not necessary.Source: §3 · p. 13
III. ALGORITHMS
The algorithm recasts Lindbladian and parent-Hamiltonian terms in the time domain, where weighted integrals support block-encoding constructions. The parent-Hamiltonian representation uses a vectorized superoperator on a doubled Hilbert space.
III. ALGORITHMS
- The main algorithmic contribution is to assemble block encodings for the synthetic Lindbladian and its parent Hamiltonian from time-domain representations.The section presents these representations before deriving the corresponding block encodings and complexities.Source: §III · p. 14
A. Time-domain representation of our Lindbladians
- Weighted time integrals of rapidly decaying functions enable linear-combination-of-unitaries constructions using controlled Hamiltonian simulation.For the coherent-term approximation, the stated simulation cost is O(β log(1/ϵ)).Source: §III · p. 14, A. Time-domain representation of our… · p. 15
- The coherent term has time-domain representations for Gaussian and Metropolis-like weights, with the Metropolis-like form requiring an approximation to handle a mild logarithmic singularity.The Gaussian and Metropolis-like cases are given separately; the latter’s explicit weights are described as more cumbersome.Source: A. Time-domain representation of our… · pp. 14–15
B. Time-domain representation of our parent Hamiltonians
- The parent Hamiltonian is formed from a transition part and a decay-and-coherent part, and its superoperator representation is vectorized on a doubled Hilbert space.The first term corresponds to the transition part under a similarity transformation; the second combines decay and coherent contributions.Source: B. Time-domain representation of our… · p. 15
1. The transition part
- The transition part has time-domain expressions for both Gaussian and Metropolis weights, with the Gaussian case specified using ωγ = σE = σγ = 1/β.The section gives separate transition-part corollaries for the two weights.Source: §1 · p. 16
2. The N-term
This section presents time-domain forms for the parent Hamiltonian’s N term and develops block encodings for the terms needed by the Gibbs sampler and discriminant. The constructions use controlled Hamiltonian simulation and specified jump-operator encodings.
2. The N-term
- The N term is presented in the time domain for both Gaussian and Metropolis weights, and the section verifies that N is Hermitian in these cases.The stated Hermiticity check uses relations between the time-domain functions and the Hermiticity of Aa†Aa.Source: §2 · p. 16
C. Block-encodings
- The Gibbs sampler and parent-Hamiltonian implementation use block encodings of the jump operators, with a partial-transpose encoding also assumed for the discriminant.The listed components additionally include a quantum Fourier transform and controlled filtering of Boltzmann factors.Source: C. Block-encodings · p. 17, P repf · p. 17
P repf :
- The discriminant block encoding combines its transition part with the N part, while the Lindbladian simulation requires block encodings for the dissipative part and coherent term.The section relates these components to the black-box Lindbladian simulation algorithm.Source: P repf · p. 17
- The coherent-term block encoding uses constant calls to controlled Hamiltonian simulation, the jump encoding, and state-preparation operations for its time-domain weights.The proposition’s bilinear construction similarly uses the jump encoding and its partial-transpose counterpart; it applies when the relevant weight functions have 1-norm at most 1.Source: P repf · p. 18
D. Proving Theorem I.2: complexity for Lindbladian simulation
The section derives simulation and discriminant complexities from block encodings, controlled Hamiltonian simulation, and discretized time integrals. It then outlines applications and research directions, including lattice locality and convergence questions.
D. Proving Theorem I.2: complexity for Lindbladian simulation
- The Lindbladian simulation proof uses block encodings for the coherent and dissipative parts, with a logarithmic overhead for the Metropolis weight’s mild singularity.The time discretization is handled with a Fourier-transform register using polylogarithmically many qubits.Source: D. Proving Theorem I.2: complexity for… · p. 18
E. Proving Theorem I.3: complexity for the discriminant
- The discriminant construction adds block encodings for the transition and N terms and bounds the error from discretized, truncated time integrals.The proof treats the two-dimensional case using Riemann-sum error bounds.Source: E. Proving Theorem I.3: complexity for… · p. 19
- The implementation does not use I + Hβ, so it does not obtain the quadratic speedup on the discriminant gap that implementing that operator would allow.The authors state that they implement Hβ itself.Source: E. Proving Theorem I.3: complexity for… · p. 19
IV. DISCUSSION
- For lattice Hamiltonians, the proposed implementation simulates a Hamiltonian patch of radius about ˜O(β) around each jump operator.The discussion identifies this locality as potentially favorable for practical gate complexity.Source: §IV · p. 19
- Localized jumps and exact detailed balance enable rigorous study of convergence for noncommuting lattice Hamiltonians; rapid mixing also implies circuit complexity bounds for the purification through the Lindbladian gap.The discussion connects the latter implication to a dynamic perspective on the entanglement area law.Source: §IV · p. 19
- The discussion proposes numerical studies of mixing and thermal or ground-state preparation, and comparisons with existing classical and quantum algorithms.It also identifies possible uses in optimization and quantum semidefinite-program solvers, and frames open-system thermal phase transitions as a research direction.Source: §IV · p. 20
Appendix A: Deriving time-domain represantations
The appendix derives time-domain representations by Fourier transformation and identifies forms suitable for linear-combination-of-unitaries implementation. It also gives explicit Lindbladian and parent-Hamiltonian expressions for the Gaussian and Metropolis settings.
Appendix A: Deriving time-domain represantations
- Two-dimensional Fourier transforms represent bilinear expressions over two Bohr frequencies, and factorization reduces the transform to two one-dimensional transforms.Discretizing the resulting integral permits a linear-combination-of-unitaries implementation.Source: Appendix A · p. 24
1. Our Lindbladians
- The appendix derives explicit time-domain functions for the Lindbladian coherent term and states that the relevant time functions decay rapidly and have bounded ℓ1-norm.The bounded norm is identified as a requirement for the LCU implementation.Source: §1 · pp. 25–26
- The appendix notes that obtaining exact detailed balance may be difficult when Hamiltonian evolution times are below Ω(β).This caveat is tied to the time-domain width of the function used for the coherent term.Source: §1 · p. 25
2. Our parent Hamiltonians
- The parent Hamiltonian’s discriminant is expressed using transition and coherent-and-decay parts, with a stated norm bound ∥H∥≤2 for Metropolis or Gaussian weights.The appendix also gives a time-domain form of the N term and an operator-Fourier-transform expression for the transition part.Source: §2 · pp. 26–27
a. The transition part
The transition and N terms are expressed in the time domain using Fourier factorization and convolution, with bounds and normalization conditions stated for their components.
a. The transition part
- The transition discriminant factors as h_ν1,ν2 = 2π ˆh+(ν+) · ˆh−(ν−), yielding corresponding time-domain functions.The proof cancels the cross term in the exponential for ˆh+ and evaluates the remaining Gaussian integral.Source: a. The transition part · p. 28
- For the transition part, the stated time-domain bound is ∥h+(t)∥1 ≤ 1.The calculation sets σE = 1/β to obtain the bound.Source: a. The transition part · pp. 28–29
b. The N-term
- The N term is formed in the time domain by convolution, with factors redistributed so that n1 and n2 are normalized.The passage notes an overall extra factor of 2 relative to Corollary A.2.Source: b. The N-term · p. 29
Appendix B: Calculating the coherent term for the Metropolis-like weights
The appendix derives time-domain forms for the Metropolis-like coherent term and develops both an approximation and an exact expression, including bounds relevant to implementation.
Appendix B: Calculating the coherent term for the Metropolis-like weights
- The exact Metropolis coherent-term formula is cumbersome, while its norm is bounded by O(log(β∥H∥)).The bound uses ∥f−∥1 = O(1); the exact formula supports a precise approximation in Corollary III.2.Source: Appendix B · p. 31
- QSVT can implement the exact formula, but its subnormalization improves only from O(log(β∥H∥/ϵ)) to O(log(β∥H∥)).The comparison is between the precision-dependent requirement in Corollary III.2 and the natural choice θ = 1/β∥H∥ in Proposition B.2.Source: Appendix B · p. 32
- The authors suggest the exact formula may extend detailed balance to infinite-dimensional systems, but leave verification of the construction and analysis for future work.In the s = ∞ case, the passage also notes a diverging ℓ1 norm for f(∞).Source: Appendix B · pp. 31–32
- The Metropolis-like Lindbladian is argued to be approximable by finite s, with s = Θ((β∥H∥ + log(1/ϵ) + 1)^2) proposed for ϵ-closeness.The passage describes this bound as something careful execution of the perturbation bounds should establish.Source: Appendix B · p. 32
- For Hermitian X, µa(X) is bounded by 6∥Aa∥²∥X∥ and is an odd analytic entire function with derivative zero at X = 0.These properties are used in deriving bounds for individual jumps and the norm of their sum.Source: Appendix B · p. 33
Appendix C: The parent Hamiltonian and quasi-adiabatic algorithms
The appendix relates the purified Gibbs state to a local frustration-free parent Hamiltonian and describes quasi-adiabatic preparation under a system-size-independent gap condition. It also outlines a time-dependent simulation approach whose cost depends quadratically on the gap parameter.
Appendix C: The parent Hamiltonian and quasi-adiabatic algorithms
- For geometrically local lattice Hamiltonians, the parent Hamiltonian is geometrically local up to an exponentially decaying tail, and a system-size-independent gap across temperatures permits efficient quasi-adiabatic preparation.The gap is expected to be system-size independent when Gibbs-state correlations decay, but may diverge with system size near phase transitions.Source: Appendix C · p. 34
- At β = 0, the purified Gibbs state is a Bell state across two copies; the parent Hamiltonian and Lindbladian spectrum are nonpositive, motivating a sign flip.The appendix presents quasi-adiabatic evolution as an alternative to amplitude-amplification-based adiabatic algorithms and notes its quasi-local circuit for geometrically local systems.Source: Appendix C · p. 34
1. Simulating the quasi-adiabatic operator using time-dependent Hamiltonian simulation
- The quasi-adiabatic simulation cost has quadratic dependence on 1/∆, from the filter width and its normalization.The high-precision time-dependent simulation is intended for suitable subsets of jumps and neighboring Hamiltonian terms on polylogarithmic patches, not the full system at once.Source: §1 · p. 35
N [CKBG23]. Then,
The appendix outlines block-encoding and state-preparation components for quasi-adiabatic evolution, then describes adding temperature control to the parent-Hamiltonian simulation.
N [CKBG23]. Then,
- The controlled quasi-adiabatic evolution is block-encoded and assembled using an additional LCU together with the time-domain state-preparation procedure.The appendix states that the HHKL implementation glues together simulated polylogarithmic patches.Source: N [CKBG23]. Then · pp. 36–37
2. Additional gates for β-control gates
- For a linear temperature schedule, β-control of the parent-Hamiltonian block encoding is obtained by extending uses of controlled Hamiltonian simulation with β-controls.The integral expressions place the β dependence in the β-rescaling of Heisenberg dynamics; independently tuning σ < 1/β would require controlled state-preparation unitaries for the double time integrals.Source: §2 · pp. 37–38
3. Properties of the derivatives in the Gaussian case
The section examines Gaussian-weight derivatives, the time-domain basis for Gaussian filters, and extensions and limitations of detailed balance. It also compares Lindbladian mixing with parent-Hamiltonian gaps and discusses discretization constraints.
3. Properties of the derivatives in the Gaussian case
- For Gaussian transition weights with σ = σγ = 1/β, the β-derivative expressions involve double integrals, with β-dependence isolated through rescaled Heisenberg dynamics.The passage introduces first- and second-derivative bounds, but does not provide their explicit formulas here.Source: §3 · pp. 38–39
4. Comparing with the Lindbladian case
- The parent-Hamiltonian gap is qualitatively related to mixing time, but conversion overhead can scale with system size and low-depth implementation still needs parallelizable Lindbladian evolution.A rapid-mixing proof would require a quantum log-Sobolev inequality; HHKL parallelization relies on time reversal, which does not obviously extend to dissipation.Source: §4 · p. 39
Appendix D: Why Gaussians?
- The time-domain detailed-balance condition constrains the filter and correlation function, while the authors present this derivation at physicists’ rigor rather than as a mathematical theorem.The derivation assumes a real-on-the-real-axis, complex-analytic filter independent of β and a Hermitian jump operator.Source: Appendix D · p. 40
1. Solving the functional equation
- For fixed β, solving the functional equation gives Gaussian filters as the general solution, while the associated correlation function is not unique because linear combinations are allowed.The passage describes this as a solution of the functional equation for a fixed temperature.Source: §1 · pp. 40–41
Appendix E: Other notions of detailed balance
- Among two discussed variants of quantum detailed balance, only the first appears to work; the authors report no algorithmic way to ensure the other condition, whose known Davies generator requires exponentially long simulation.The Davies generator resolves level spacing using exponentially long Hamiltonian simulation time.Source: Appendix E · p. 41
1. Detailed balance with unitary drift
- Allowing unitary drift enlarges the family of Lindbladians for a stationary state, but the anti-self-adjoint component can break the qualitative link between fast mixing and a large parent-Hamiltonian gap.A gap bound is available under an additional condition relating the mixing-time bound to the size of the anti-self-adjoint component.Source: §1 · pp. 41, 43
2. s-detailed balance
The s-detailed-balance condition varies with the parameter s, although every choice has the same fixed point. The appendix also lists symbolic Mathematica checks for calculations and Fourier transforms.
2. s-detailed balance
- Different s values impose different detailed-balance conditions, but each condition prescribes the same fixed point, with L[ρ] = 0.The text notes that s = 1/2 appears to be a special point and that the authors do not know how to algorithmically ensure another condition.Source: §2 · p. 44
Appendix F: Mathematica code for symbolically verifying our calculations
- The appendix lists Mathematica checks for inverse Fourier-transform calculations, Proposition B.1, and the integral used in Corollary III.4.It also records Fourier-transform parameter settings and assumptions.Source: Appendix F · pp. 44–45