Source-linked AI summary
Efficient quantum Gibbs samplers with Kubo--Martin--Schwinger detailed balance condition
Zhiyan Ding, Bowen Li, Lin Lin
TL;DR
Implementing quantum Gibbs samplers can require resolving closely spaced Bohr frequencies, while finite-jump alternatives have been lacking. This work constructs KMS-detailed-balanced Lindblad dynamics from weighted coupling operators and establishes quasi-locality for local settings, while mixing-time analysis remains challenging.
Problem
Implementing Davies-based Gibbs samplers can require resolving Bohr frequencies with exponentially small minimum separation, making Hamiltonian simulation impractically long.
Source: §2.1 · p. 11Method
The construction starts from self-adjoint coupling operators and weighting functions to define a Lindbladian satisfying σβ-KMS detailed balance.
Source: §3.1 · pp. 15–16Results
For local Hamiltonians and local couplings, Gaussian-type weighting produces quasi-local jump operators and a coherent operator that is a sum of quasi-local operators.
Source: §3.4 · p. 23Takeaways & Limitations
Quasi-locality does not affect simulation complexity, but it is crucial when analyzing mixing time.
Source: §3.4 · p. 24The secular frequency sum can demand impractically long simulation when Bohr-frequency gaps are exponentially small.
Source: §2.1 · p. 11
Abstract
from arXiv · showhide
Lindblad dynamics and other open-system dynamics provide a promising path towards efficient Gibbs sampling on quantum computers. In these proposals, the Lindbladian is obtained via an algorithmic construction akin to designing an artificial thermostat in classical Monte Carlo or molecular dynamics methods, rather than treated as an approximation to weakly coupled system-bath unitary dynamics. Recently, Chen, Kastoryano, and Gily\'en (arXiv:2311.09207) introduced the first efficiently implementable Lindbladian satisfying the Kubo--Martin--Schwinger (KMS) detailed balance condition, which ensures that the Gibbs state is a fixed point of the dynamics and is applicable to non-commuting Hamiltonians. This Gibbs sampler uses a continuously parameterized set of jump operators, and the energy resolution required for implementing each jump operator depends only logarithmically on the precision and the mixing time. In this work, we build upon the structural characterization of KMS detailed balanced Lindbladians by Fagnola and Umanit\`a, and develop a family of efficient quantum Gibbs samplers using a finite set of jump operators (the number can be as few as one), \re{akin to the classical Markov chain-based sampling algorithm. Compared to the existing works, our quantum Gibbs samplers have a comparable quantum simulation cost but with greater design flexibility and a much simpler implementation and error analysis.} Moreover, it encompasses the construction of Chen, Kastoryano, and Gily\'en as a special instance.
1. Introduction
Quantum Gibbs sampling with Lindblad dynamics seeks to prepare Gibbs states through algorithmically designed open-system dynamics. This work develops KMS-detailed-balanced samplers with finite jump sets, addressing implementation challenges while leaving mixing-time analysis as an important open question.
1.1. Related works.
- Earlier decaying-filter approximations to Davies generators satisfy only approximate GNS detailed balance, leaving their fixed points unknown and requiring accumulated trajectory error to be tracked.Their energy resolution can scale polynomially with β, inverse mixing time, and inverse precision.Source: §1.1 · p. 3
1.2. Contribution and outline.
- For KMS detailed balance, complex filtering functions with a mild symmetry condition remove the outer frequency integration required by earlier real-filter constructions.This flexibility applies when the goal is KMS detailed balance rather than approximating Davies generators.Source: §1.2 · p. 4
- The sampler uses a finite set of jump operators—one per jump proposal—and has computational cost comparable to [CKG23] with simpler simulation and error analysis.The construction uses LCU and supports high-order Lindblad simulation algorithms.Source: §1.2 · p. 5
1.3. Discussion and open questions.
- The paper distinguishes efficient simulation from rapid mixing; proving mixing bounds for non-commuting Hamiltonians at moderate or low temperatures remains challenging.Mixing times may vary substantially among samplers, and the effect of coherent terms on mixing remains open.Source: §1.3 · pp. 6–7
2. Structures of detailed balanced Lindbladians
This section develops structural forms for detailed-balanced Lindbladians, covering implementation feasibility in the Davies and KMS cases and a necessary-and-sufficient characterization of KMS-detailed balanced generators that also expresses GNS-detailed balanced generators in that form.
2. Structures of detailed balanced Lindbladians
- Detailed balance with respect to a full-rank state makes that state invariant; KMS detailed balance is weaker than GNS detailed balance but still fixes the Gibbs state.For inner products indexed by s other than 1/2, the detailed-balance conditions are equivalent and stronger than KMS detailed balance.Source: §2 · p. 9, §2.2 · p. 11
2.1. Davies generator and GNS-detailed balance.
- Davies generators characterize GNS-detailed-balanced semigroups up to a coherent term, but resolving all Bohr frequencies can require impractically long simulation.The minimum gap between Bohr frequencies may be exponentially small, and the sum over frequencies arises from a secular approximation.Source: §2.1 · pp. 9, 11
2.2. KMS-detailed balanced generators.
- Revisiting [FU07, Theorems 7.2 and 7.3], the authors give a canonical form for σ-KMS-detailed-balanced Lindbladians, with both Ψ and Φ(X)=K†X+XK KMS-self-adjoint.The form is an if-and-only-if characterization.Source: §2.2 · pp. 11–12
- A Lindbladian satisfies σβ-KMS detailed balance if and only if it has the structural form specified by operators Lj and a self-adjoint G.The passage states that G is given by an accompanying formula, but its expression is not included in the supplied text.Source: §2.2 · p. 13
- GNS-detailed balanced Lindbladians are a subclass of KMS-detailed balanced ones, and their canonical form can be reformulated in the KMS form.This reformulation fills a structural gap because eigenvectors of Δσβ are generally not solutions to (2.28).Source: §2.2 · pp. 13–14
- The reformulation applies to both self-adjoint jumps and non-self-adjoint jumps paired with their adjoint-index partners.For the non-self-adjoint case, the paired Lindbladian Lj + Lj′ also matches the KMS structural form.Source: §2.2 · p. 14
3. A family of efficient quantum Gibbs samplers
This section develops a framework for constructing σβ-KMS detailed-balanced Lindblad samplers from coupling operators and weighting functions, and for approximating and block-encoding their generators for efficient simulation. It also gives an oracle-based simulation guarantee and establishes quasi-locality of the jump and coherent operators for local systems.
3.1. Quantum Gibbs samplers via KMS-detailed balanced Lindbladian.
- Self-adjoint coupling proposals and symmetric weights define filtered jumps; together with the coherent term, they yield a σβ-KMS detailed-balanced Lindbladian.The filter modifies transitions according to their energy differences, analogously to a rejection step in classical sampling.Source: §3.1 · pp. 15–16
3.2. Choice of weighting function q(ν) and κ(ν).
- Compactly supported Gevrey choices for q and κ make the time-domain filters decay rapidly, enabling trapezoidal quadrature to approximate the jumps and coherent term with controlled error.Proposition 15 gives a quadrature error bound under its stated assumptions.Source: §3.2 · pp. 17–19
- The weighting-function approach bounds quadrature error in the time domain using Poisson summation, avoiding the “rounding Hamiltonian” technique introduced in [CKBG23].Source: §3.2 · p. 19
3.3. Efficient simulation of the Lindblad master equation (3.13).
- Once block encodings of the jumps and coherent term are constructed with LCU, existing Lindblad-simulation algorithms [LW23] can simulate the dynamics.The construction uses coupling-operator block encodings, controlled Hamiltonian simulations, and prepare oracles for the filtering functions.Source: §3.3 · pp. 20–22
- Under the stated oracle and weighting-function assumptions, Theorem 18 guarantees simulation of (3.13) through t_mix within ε-diamond distance for β > 0.The theorem’s total Hamiltonian simulation-time expression is not included in the supplied passage.Source: §3.3 · p. 23
- With finitely many jump operators, simulation needs a block encoding of their controlled sum; for |A| ≫ 1, an alternative oracle construction with weak measurement and compression achieves optimal scaling in oracle uses.The alternative uses block encodings for all coupling operators, following [CKBG23, Appendix B.1 Lemma III.1], the weak-measurement scheme of [CKG23, Section III.1], and compression techniques in.Source: §3.3 · p. 23
3.4. Quasi-locality.
- For local (k, l)-Hamiltonians and local coupling operators, Gaussian-type weighting yields quasi-local jump operators and a coherent operator that is a sum of quasi-local operators at any temperature.The quasi-locality result is established using Lieb–Robinson bounds.Source: §3.4 · p. 23
- For q(ν)=bh(ν)ω(ν/S), with S≥4∥H∥ and |h(t)|∼exp(−Θ(|t|^p)) as t→∞ for p≥1, quasi-locality does not affect simulation complexity but is crucial for mixing-time analysis [RFA24].The proposed La and G operators are also quasi-local at any temperature, paving the way for future spectral-gap analyses of the proposed Gibbs sampler.Source: §3.4 · pp. 24–25
4. Recovery of the Gibbs sampler in [CKG23]
The construction recovers the Gibbs sampler of [CKG23] as a special case by selecting a weighting function that reproduces its jumps. The section also contrasts the energy-transition structure of that sampler with the broader support of the proposed construction.
4. Recovery of the Gibbs sampler in [CKG23]
- The [CKG23] coherent term makes the dynamics KMS detailed balanced while allowing moderate σE, reducing computational cost.Without that correction, σE must be small enough for the Gibbs state to be an approximate fixed point.Source: §4 · p. 25
- For a single self-adjoint coupling, the coefficient matrix is real, positive semidefinite, and centrosymmetric, enabling an eigendecomposition with symmetric or skew-symmetric eigenvectors.The resulting coherent term and jumps satisfy the requirements of Theorem 10.Source: §4 · p. 26
- Choosing the weighting function makes the proposed construction reproduce the jumps of the [CKG23] Gibbs sampler.The resulting weighting function satisfies the required symmetry condition.Source: §4 · p. 27
- As σE approaches zero, the coefficient matrix becomes diagonal up to a constant and the associated dynamics becomes GNS detailed balanced.The resulting jumps are consistent with those in the Davies-generator form (2.35).Source: §4 · p. 27
- In the [CKG23] construction, transition weights concentrate near the diagonal or origin, whereas the proposed sampler has support on [−S, S]^2 independent of β and permits different energy transitions.For the Metropolis-type weight, the diagonal concentration narrows as β increases.Source: §4 · p. 27
Appendix A. Block encoding
Block encoding represents a rescaled matrix within a unitary’s upper-left block. The appendix assumes access to encodings of relevant input matrices and tracks errors in encodings derived from them.
Appendix A. Block encoding
- Block encoding provides a framework for encoding non-unitary matrices using unitaries implementable on quantum devices..Source: Appendix A · p. 31
- Block encoding represents the rescaled matrix A/α in the upper-left block of a unitary.The unitary is an (α, m, ϵ)-block-encoding, with α called the block encoding or subnormalization factor.Source: Appendix A · p. 31
- The work assumes query access to block encodings of relevant matrices, including H and the coupling operators.It assumes no error in input-matrix block encodings and tracks errors in derived encodings such as those of jump operators.Source: Appendix A · p. 31
Appendix B. Linear combination of unitaries
The appendix presents linear combination of unitaries (LCU) as a primitive for coherently implementing matrix combinations using block encoding. Its construction uses coefficient state-preparation oracles and a select oracle for the component unitaries.
Appendix B. Linear combination of unitaries
- LCU coherently implements a matrix expressed as a linear combination of unitaries using block encoding.The appendix presents a version applicable to possibly complex coefficients.Source: Appendix B · p. 31
- The coefficients are supplied through a pair of state-preparation oracles, with left and right coefficients chosen to multiply to each complex coefficient.The balanced choice minimizes the block encoding factor.Source: Appendix B · pp. 31–32
- A select oracle accesses the component unitaries, yielding a (∥c∥1, ℓ, 0)-block-encoding of their linear combination.The select oracle can be constructed using controlled versions of the component block encodings.Source: Appendix B · p. 32
Appendix C. Gevrey functions
The appendix supplies self-contained Gevrey-function results with explicit constants for the paper’s analysis. It uses high-order derivative bounds and a Paley–Wiener-type estimate for Fourier decay.
Appendix C. Gevrey functions
- The appendix gives self-contained proofs of Gevrey-function results with explicit constants.It identifies these results as useful for the work and notes related findings in and.Source: Appendix C · p. 32
- Faà di Bruno’s formula and partial Bell polynomials express high-order derivatives, supporting the verification that the function belongs to a Gevrey class.The appendix applies this approach to the function involving 1+x^2+x^4 and establishes derivative estimates.Source: Appendix C · pp. 32–33
- A Paley–Wiener-type estimate establishes rapid Fourier-transform decay for Gevrey functions with compact support.The appendix also gives a derivative estimate using Leibniz’s rule.Source: Appendix C · pp. 32, 34
Appendix D. Error analysis and complexity
Appendix D bounds the filtering and coherent-term functions and uses those bounds to analyze discretization and simulation costs. Under stated oracle and weighting-function assumptions, its main theorem gives an error-controlled simulation of the Lindbladian evolution up to the mixing time.
Function bounds
- Lemma 30 bounds the decay and integrability of the jump and coherent-term functions f and g under Assumption 13 and Eq. (3.17).These bounds support the later truncation analysis.Source: Appendix D · pp. 34–35
Discretization error
- Proposition 31 analyzes discretized jump and coherent terms using a finite time grid, truncation bounds, and Poisson summation.The proof treats the jump and coherent terms separately and invokes Poisson summation under stated step-size conditions.Source: Appendix D · pp. 37–40
Normalization bounds
- Lemma 33 bounds the discretization normalization constants using the L1 norms of f and g when the discretization step is sufficiently small.These normalization factors enter preparation-oracle complexity.Source: Appendix D · p. 40
Main simulation theorem
- Theorem 34 establishes an ε-diamond-distance simulation guarantee up to time t_mix under the stated weighting-function, block-encoding, Hamiltonian-simulation, and preparation-oracle assumptions.It expresses the cost in total Hamiltonian simulation time; the supplied theorem passage does not include the cost formula.Source: Appendix D · p. 41
Resource accounting
- Theorem 34 also accounts for additional ancilla qubits needed for preparation oracles and simulation, with logarithmic parameter terms stated in the appendix.The listed terms include log(t_mix|A|/ε) and log C_u,w.Source: Appendix D · p. 41