Constant-time equilibration of observables under rapid Lindbladian dynamics

AI summary

Overview

Research area: Quantum information science — open quantum systems, Lindbladian (Markovian) dynamics, dissipative state preparation, and quantum Gibbs sampling.

Technical level: Intermediate to Advanced. The paper is written for readers comfortable with density matrices, trace distance, the Heisenberg picture, spectral gaps, and Lieb–Robinson bounds. The core conceptual message, however, is accessible: you often do not need the whole quantum state to settle before you can measure what you care about.

One-sentence scope: The paper introduces "observable-specific" mixing times and proves that, under quasi-local rapidly mixing Lindbladians, sums of geometrically local observables equilibrate in a time independent of system size — unlike the polylogarithmic time required for full-state convergence — with consequences for the end-to-end runtime of quantum and classical algorithms.

What This Paper Is About

Dissipative quantum algorithms, such as quantum Gibbs samplers and ground-state preparation protocols, work by engineering a Lindbladian whose steady state is the state you want. Their cost is normally judged by the global mixing time — the worst-case trace distance between the evolving state and the steady state, taken over all possible initial states. The authors ask whether this criterion is unnecessarily strict when the actual goal is only to measure a few physically relevant quantities, such as the energy or a local order parameter.

They answer no: for many Lindbladians, specific observables equilibrate qualitatively faster than the full state, so the strict global criterion overestimates the runtime of realistic tasks.

Key Contributions

1. A new definition of mixing. The authors define the mixing time of an observable $O$ as $t_{\text{mix}}^{(O)}(\epsilon) = \inf{t \geq 0 \mid \lVert e^{t\mathcal{L}}[O] - \operatorname{Tr}(O\sigma)\cdot I\rVert \leq \epsilon\lVert O\rVert}$ (Definition II.2), and show it is compatible with the standard global mixing time through $t_{\text{mix}}(\epsilon) = \sup_O t_{\text{mix}}^{(O)}(\epsilon)$.

2. A constant-time theorem for local observables. Theorem III.1 proves that for uniform families of quasi-local, rapidly mixing qudit Lindbladians with a uniform lower bound on the spectral gap, any observable written as a sum of geometrically local terms mixes in $t_{\text{mix}}^{(O)}(\epsilon) = \mathcal{O}(\log(1/\epsilon))$ — independent of system size.

3. Runtime reductions for quantum and classical simulation. The theorem lowers the quantum cost of estimating such expectation values to $\mathcal{O}(n \cdot \operatorname{poly}(1/\epsilon))$, and the authors provide a quantum-inspired classical Algorithm 1 running in $\mathcal{O}(n \cdot e^{\mathcal{O}(\log(1/\epsilon)^D)})$ time, where $D$ is the lattice dimension.

4. Analysis beyond the local, interacting setting. For separable qudit Lindbladians the authors give large classes of observables mixing in constant time plus an example (Example III.9) mixing in $\Theta(\log(n/\epsilon))$; for quadratic fermionic and bosonic Lindbladians they show quadratic quantum Gibbs samplers thermalise quadratic observables in constant time. These classes include non-local observables, so locality is not strictly necessary.

Main Findings

• Separation between state mixing and observable mixing. The global state needs (poly-)logarithmic time under a rapidly mixing Lindbladian, whereas sums of geometrically local observables need only $\mathcal{O}(\log(1/\epsilon))$, with no system-size dependence.

• Practical corollaries for Gibbs samplers and ground-state preparation. Corollary III.1.1 covers weakly interacting systems $H = H_0 + \lambda V$ with a separable $H_0$ below a system-size-independent $\lambda_{\text{max}}$; Corollary III.1.2 covers high temperatures below $\beta_\star = 1/(615^D \cdot 2J)$ with $J = hkl$ for a $(k,l)$-local Hamiltonian with $\lVert h_X\rVert \leq h$; Corollary III.1.3 covers 1D chains at any fixed temperature using the sampler of [36]; Corollary III.1.4 covers ground states of $H = -\sum_i Z_i + \lambda V$ below a $\lambda_{\text{max}}$.

• Rapid mixing, not merely a gap, is required. Remark III.2 notes that with only fast mixing from a constant spectral gap, the inner-region contribution would scale as $e^{\mathcal{O}(t^D) - \Delta t}$, an increasing function of $t$ for any $D \geq 2$ that does not decay.

• Quantum versus classical scaling. For $D \geq 2$ the quantum algorithm retains a superpolynomial speed-up in the error $\epsilon$ over Algorithm 1; in one dimension the classical algorithm is fully efficient for any short-range Hamiltonian.

• Non-local observables can also mix fast. In the separable-qudit, fermionic, and bosonic settings, observables without geometric locality still exhibit system-size-independent mixing, indicating that locality alone is not the determining structure. For bosonic systems the authors introduce a regularised mixing-time definition for unbounded operators (Definition V.1).

• Numerics show no large hidden constants. Small-scale simulations of quantum Gibbs samplers using exact diagonalisation and tensor networks, applied to the Fermi–Hubbard model and the transverse-field Ising model, indicate that the asymptotic analysis captures finite-size dynamics well. Specific lattice sizes and error values are not reported in the provided content.

• Complexity landscape relative to classical methods. Classical cluster/cumulant expansions are provably efficient — polynomial in both $n$ and $1/\epsilon$ — only within their radius of convergence. The authors expect quantum advantage where that expansion breaks down but rapid mixing persists, drawing an analogy to two-dimensional Ising models where the cluster expansion fails before the critical temperature while Glauber dynamics stays rapidly mixing up to it.

• Relation to prior work. A similar idea appears in [61] as an energy-based mixing time for ground-state preparation, and in [33], which analyses a noisy analogue simulator for observables on $\mathcal{O}(1)$ sites and rules out, assuming $\text{BQP} \neq \text{BPP}$, a classical algorithm polynomial in $1/\epsilon$ for systems in at least two dimensions.

Methodology in Plain English

The proof is a scaling argument that combines two ingredients: rapid mixing of the Lindbladian, and Lieb–Robinson bounds, which say that information propagates through a lattice at finite speed.

Take a local observable $O_A$ supported on a small region $A$. Split the evolution into two pieces. Inside a ball $B_A(r)$ of radius $r$ around $A$, the truncated dynamics equilibrates $O_A$ rapidly, contributing an error of order $\operatorname{poly}(\lvert B_A(r)\rvert)\cdot e^{-\Delta t}$. Outside the ball, the difference between the true and truncated evolution is suppressed by the Lieb–Robinson bound, with constants $J$, $v$, and $\gamma$, giving a term of order $\lvert A\rvert J \frac{e^{vt}-1-vt}{v} e^{-\gamma r}$.

Choose the radius so the outside term is small, $r = \mathcal{O}(t + \log(1/\epsilon))$. Because the ball volume grows only polynomially in $r$, the inner error becomes $\operatorname{poly}(t, \log(1/\epsilon))\cdot e^{-\Delta t}$, and exponential decay eventually beats polynomial growth. The result is a mixing time independent of system size — remarkably, $O_A$ equilibrates after interacting with only a finite portion of the Lindbladian.

To extend from a single local term to a sum $O = \sum_A O_A$, the authors use Lemma II.3, which bounds the mixing time of a sum by the worst mixing time among its parts, provided $\sum_A \lVert O_A\rVert / \lVert O\rVert$ is bounded by a constant. For geometrically local observables this follows from a Pauli-norm bound $\sum_i \lVert O_i\rVert/\lVert O\rVert \leq 2^D \cdot V \cdot 4^V$, where $V = \prod_{k=1}^D R_k$ is the maximal interaction volume, with qudit observables mapped to qubit observables at the cost of a factor $\lceil \log_2(d)\rceil$ in range.

For the non-interacting cases, the authors solve the Heisenberg-picture evolution of observables exactly, which lets them read off mixing behaviour directly.

Why This Matters

The standard practice of quoting a global mixing time can overstate the runtime of a dissipative algorithm by as much as a polynomial factor. This paper shows that when the target is a physically meaningful observable rather than the entire state, the required evolution time can drop to a constant, and the overall scaling becomes linear in system size. That changes how the cost of quantum Gibbs sampling and ground-state preparation should be booked, and it sharpens where a quantum advantage over classical methods can plausibly be claimed.

Potential applications implied by the paper:

• Estimating Gibbs state energies for local Hamiltonians, which is the inner loop of many thermal-state and materials calculations.
• Measuring local order parameters, relevant to detecting phases and phase transitions in spin and fermionic lattice models.
• Estimating partition functions, noted by the authors as a task where the worst-case criterion is a qualitative overestimate.
• Ground-state preparation via dissipative Lindbladians for weakly interacting systems, using Corollary III.1.4.

Industry relevance: the results directly affect the resource estimates used by quantum algorithm and hardware teams building thermal-state samplers and dissipative state-preparation routines. The accompanying classical Algorithm 1 also matters for simulation software: it gives a baseline whose runtime is linear in $n$ but grows as $e^{\mathcal{O}(\log(1/\epsilon)^D)}$, defining the regime where quantum simulation should win and where classical cluster-expansion methods are expected to fail.

Future Directions

• Stability of constant mixing times under perturbation of the Lindbladian, mirroring the known stability of expectation values themselves [20].
• Extension to weakly interacting Lindbladians, since the non-interacting results do not require local observables and suggest a broader phenomenon.
• Bounding observable-specific mixing times for Lindbladians whose full mixing times are unknown, or even exhibiting efficiently mixing observables for Lindbladians whose full states are known to mix slowly.
• Locating the practical advantage regime more precisely — the authors place it in the temperature and coupling window where cluster expansions break down but rapid mixing persists, which the present numerics only probe at small scale.

Target Audience

Quantum information theorists and algorithm designers working on open-system dynamics, dissipative state preparation, and Gibbs sampling will find the central theorem and corollaries most directly useful. Complexity theorists interested in the boundary between quantum and classical simulation of thermal and steady-state properties will value the comparison between the $\mathcal{O}(n \cdot \operatorname{poly}(1/\epsilon))$ quantum cost and the $e^{\mathcal{O}(\log(1/\epsilon)^D)}$ classical cost. Physicists and chemists using Lindblad master equations for lattice models will benefit from the concrete corollaries and the numerical checks on the Fermi–Hubbard and transverse-field Ising models. Readers needing only the headline result can read Theorem III.1, its corollaries, and the discussion; the proof requires familiarity with Lieb–Robinson bounds and spectral-gap-based contractivity.

Authors’ abstract

Markovian open-system dynamics have widespread applications throughout quantum information science, including algorithmic state preparation. Their convergence is commonly quantified using the worst case global trace distance between the evolving and stationary states. However, this criterion can be unnecessarily stringent when only physically relevant observables are of interest. Here we introduce and study observable-specific mixing times. We prove that, for quasi-local, rapidly mixing Lindbladians, sums of geometrically local observables equilibrate in a time independent of system size, in contrast to the logarithmic dependence of global state mixing. This separation reduces the runtime of dissipative quantum algorithms, including quantum Gibbs samplers, for estimating quantities such as the Gibbs state energy and local order parameters, yielding an overall scaling that is linear in system size. Complementing this quantum result, we develop a quantum-inspired classical algorithm for estimating the same quantities. Its runtime is likewise linear in system size, but scaling exponentially in $\mathcal{O}\big(\log(1/ε)^D\big)$, where $D$ denotes the spatial dimension of the lattice. We further analyse non-interacting Lindbladians over qudits, fermions, and bosons, demonstrating that locality of observables is not always necessary for a qualitatively faster mixing. Small-scale simulations of quantum Gibbs samplers reveal no large hidden constants in our asymptotic analysis and show that the theoretical predictions closely capture the finite-size dynamics.