PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Thermal State Preparation

Chi-Fang Chen, Michael J. Kastoryano, Fernando G. S. L. Brandão, András Gilyén

arXiv:2303.18224v2quant-phmath-phmath.FAmath.MP

TL;DR

Quantum simulation depends on initial-state preparation, yet quantum Gibbs sampling faces technical challenges rooted in energy uncertainty. This paper develops Nature-inspired continuous-time Lindbladian samplers and an analytic framework for their guarantees, including results for purified Gibbs-state preparation and physically derived Lindbladians.

  • Problem

    Quantum Gibbs samplers lack satisfactory constructions and guarantees for general noncommuting Hamiltonians, while initial-state preparation remains an obstacle in quantum simulation.

    Source: §I · pp. 2–3

  • Method

    The paper constructs smoothed, Nature-inspired Lindbladian Gibbs samplers and develops analytic tools for secular approximation and approximate detailed balance.

    Source: §I · p. 5, §IV · p. 30

  • Results

    The authors present efficiently implementable Gibbs-sampling algorithms with fixed-point accuracy guarantees, compatible with Szegedy-type speedup and purified Gibbs-state preparation, and prove Gibbs-state stationarity for physically derived Lindbladians.

    Source: §IV · p. 30

  • Takeaways & Limitations

    The results potentially support proposals for quantum Gibbs samplers on analog quantum simulators.

    Source: §IV · p. 30

    The analysis is restricted to open-system settings that assume a Markovian bath.

    Source: §IV · p. 30

Abstract

from arXiv · show

Preparing ground states and thermal states is essential for simulating quantum systems on quantum computers. Despite the hope for practical quantum advantage in quantum simulation, popular state preparation approaches have been challenged. Monte Carlo-style quantum Gibbs samplers have emerged as an alternative, but prior proposals have been unsatisfactory due to technical obstacles rooted in energy-time uncertainty. We introduce simple continuous-time quantum Gibbs samplers that overcome these obstacles by efficiently simulating Nature-inspired quantum master equations (Lindbladians). In addition, we construct the first provably accurate and efficient algorithm for preparing certain purified Gibbs states (called thermal field double states in high-energy physics) of rapidly thermalizing systems; this algorithm also benefits from a quantum walk speedup. Our algorithms' costs have a provable dependence on temperature, accuracy, and the mixing time (or spectral gap) of the relevant Lindbladian. We complete the first rigorous proof of finite-time thermalization for physically derived Lindbladians by developing a general analytic framework for nonasymptotic secular approximation and approximate detailed balance. Given the success of classical Markov chain Monte Carlo (MCMC) algorithms and the ubiquity of thermodynamics, we anticipate that quantum Gibbs sampling will become indispensable in quantum computing.

I. INTRODUCTION

The introduction presents efficient, thermalization-inspired Lindbladian samplers as a response to difficult quantum state preparation, alongside an analytic framework for energy uncertainty and approximately Gibbs stationary states. It also contrasts these continuous-time, physically based samplers with prior approaches, including their assumptions and differing gap requirements.

I. INTRODUCTION

  • Quantum Gibbs samplers address a state-preparation gap: ground states can be QMA-hard, while practical simulation estimates assume initial states and no go-to method has emerged.The introduction also identifies quantum Gibbs sampling as a potential subroutine for semidefinite programs and quantum machine learning, while excluding classical Gibbs-state algorithms from the work’s scope.Source: §I · p. 2
  • For noncommuting Hamiltonians, finite-time energy uncertainty can break detailed balance, and prior finite-time Davies-type generators lacked a proof of a Gibbs-close fixed point.The introduction identifies the energy-time uncertainty principle as a central obstacle to implementing a quantum Gibbs sampler with a provable Gibbs fixed point.Source: §I · pp. 3, 5
  • The work presents a smoothed Davies-generator sampler with an approximately Gibbs fixed point and a purified-Gibbs-state algorithm with quadratic Szegedy-type speedup.The construction uses a weighted operator Fourier transform and approximate detailed balance to handle energy uncertainty.Source: §I · p. 5
  • Although whether their sampler arises from a physical weak-coupling limit is unknown, the framework proves the Lindbladian of [MABL13, ML20] has a stationary state close to Gibbs.The authors describe this as the first general proof of many-body Gibbs states in an open-system setting, assuming reasonably short mixing time.Source: §I · p. 5
  • The algorithms’ costs depend on Lindbladian mixing time or spectral gap, which can vary by system; the authors expect local gaps to be constant only in certain high-temperature or same-phase regimes.Calculating gaps for specific Hamiltonians is beyond the paper’s scope.Source: §I · p. 6

A. Existing work

  • Quantum Metropolis sampling [TOV+11] requires a complicated rejection subroutine and finite-resolution phase estimation, and its boosted shift-invariant version is described as provably impossible.The authors say they do not know whether the algorithm as stated works in practice.Source: A. Existing work · p. 6
  • Earlier system-bath approaches were qualitative or had practical limitations: [ML20] lacked a Gibbs-stationarity proof, while [CB21] lacked complete positivity and had large error bounds.The account also notes that [SM21] required the Eigenstate Thermalization Hypothesis for its accuracy guarantees and likewise did not extract a completely positive Lindbladian.Source: A. Existing work · p. 6
  • Coherent quantum Metropolis sampling [YAG12] and its extension [WT21] relied on perfect phase estimation or unphysical spectral-rounding promises, limiting their applicability.The coherent approach also requires quantum simulated annealing to prepare the purified Gibbs state.Source: A. Existing work · p. 6
  • Mixing times or spectral gaps can be exponentially unfavorable depending on temperature and system, although the authors expect reasonably small mixing times for Gibbs states appearing in nature.The passage notes that some spin-glass thermal states are expected to have high complexity, so efficient quantum algorithms are not expected in general.Source: Table I · p. 7
  • Prior randomized-rounding approaches incur large resource overhead, depart from the physical origin of these ideas, and are not known to offer a quadratic speedup.The comparison table summarizes provably guaranteed methods for trace-distance ϵ-approximations of Gibbs states; other approaches include heuristic variational circuits and methods requiring good initial states.Source: A. Existing work · pp. 7–8
  • Our Lindbladian samplers build on open-system simulation [CW17] and the coherent Gibbs sampler [WT21], using discrete Fourier transform jump operators and refined secular-approximation bounds to avoid unphysical assumptions such as rounding promises.They retain a simple error bound and handle the rejection step automatically, unlike discrete-time Metropolis-Hastings-style channels.Source: A. Existing work · p. 8
  • Unlike coherent samplers, Lindbladian samplers do not require the Lindbladian gap to stay open along the full high-to-low-temperature path, so their costs are not directly comparable.Coherent samplers rely on an open gap throughout the adiabatic path from 0 to β; direct Lindbladian sampling does not.Source: A. Existing work · p. 8

B. Outline and main results

The section establishes approximate Gibbs fixed points for physically motivated Lindbladians and develops the analytic tools needed to justify them. It then gives a block-encoding route to efficient Lindbladian simulation, supporting the paper’s quantum Gibbs sampling algorithms.

B. Outline and main results

  • The Lindbladian design permits arbitrary jump operators provided their adjoints are included, while transition weights obey the KMS condition and are bounded between zero and one.The Fourier-transform filter is real and ℓ2-normalized; Metropolis and Glauber weights are given as natural choices.Source: B. Outline and main results · pp. 8–9

1. Lindbladians from Nature

  • Under the stated symmetry, normalization, and transition-weight conditions, the Lindbladian has an approximate Gibbs fixed point, with accuracy worsening at low temperature, poor energy resolution, or long mixing time.The physical setting includes a system weakly coupled to a Markovian bath; the proof uses a finite-time analysis.Source: §1 · p. 9
  • Approximate detailed balance and a rigorous secular approximation control convergence and fixed-point errors when energy uncertainty perturbs the Lindbladian.The secular approximation truncates transitions with large energy deviations, and the framework is presented as applicable to nonasymptotic open-system analysis.Source: §1 · p. 10

2. Simulating Nature

  • A unitary block-encoding of the Lindbladian enables simulation of e^tL to diamond-norm error ϵ using e^O(t) controlled uses of U and U†.The proposed block-encoding uses O(T) controlled Hamiltonian-simulation time and resettable ancillas; the construction extracts bath functionality with polylogarithmic resettable ancillas.Source: §2 · p. 11

P rep :

The paper constructs continuous-time Gibbs samplers using operator Fourier transforms and Gaussian weights, then represents purified Gibbs states as leading eigenvectors of a discriminant proxy for quantum-walk preparation.

P rep :

  • Operator Fourier transforms provide an alternative to phase estimation for block-encoding jump operators, yielding physically motivated circuits compatible with the analytic framework.The construction is presented as a route to simple explicit circuits.Source: P rep · p. 12

3. Improving Nature

  • Gaussian weights give the Lindbladian an approximate Gibbs fixed point, with width setting the simulation time scale and energy resolution.The width sets a Hamiltonian simulation time scale proportional to σ_t and energy resolution proportional to σ_t^-1.Source: §3 · p. 12

4. Quantum-walk speedup

  • The discriminant proxy's leading eigenvector well-approximates the Gibbs state and yields a canonical purification, the thermofield double state.Taking a partial trace recovers the Gibbs state.Source: §4 · p. 13
  • The quantum-walk approach replaces Lindbladian mixing-time dependence with β∥H∥, but requires quantum simulated annealing and doubles the qubit count.The annealing path runs from a higher to a lower temperature.Source: §4 · p. 13

II. APPROXIMATE STATIONARITY OF THE GIBBS STATE

The section develops detailed balance as a tool for analyzing Gibbs fixed points and convergence, then introduces approximate detailed balance and uses a secular approximation to establish fixed-point accuracy for the constructed Lindbladians.

II. APPROXIMATE STATIONARITY OF THE GIBBS STATE

  • Detailed balance supports Gibbs-state fixed points and mixing-time analysis, while Lindbladians can be chosen to favor efficient implementation.The paper identifies efficient implementation, a unique desired fixed point, and rapid convergence as the sampler criteria.Source: §II · pp. 14–15

A. Approximate detailed balance

  • Approximate detailed balance addresses the difficulty of exact efficient construction under energy-time uncertainty and still guarantees an approximate fixed point.When the anti-Hermitian part vanishes, the condition reduces to exact detailed balance.Source: A. Approximate detailed balance · pp. 15–16
  • Even without detailed balance, mixing time remains controlled by spectral properties of the Lindbladian's Hermitian part.The section presents a mixing-time result based on the Hermitian component's gap.Source: A. Approximate detailed balance · p. 16

B. Proof of fixed point correctness (Theorem I.3)

  • The fixed-point proof introduces an intermediate secular-approximated Lindbladian to combine perturbation and approximate-detailed-balance bounds.The secular approximation truncates transitions in frequency; the Gaussian weight gives a mild truncation error, unlike the heavy-tailed error from step-function weights.Source: B. Proof of fixed point correctness… · pp. 16–17
  • Under the stated symmetry and normalization conditions, the proof simplifies its normalized error bound to O(βμ̄).The conditions include a permutation pairing jump operators with their adjoints at opposite frequencies.Source: B. Proof of fixed point correctness… · p. 17

III. QUANTUM ALGORITHMS FOR GIBBS SAMPLING

The paper presents incoherent and coherent Gibbs-sampling algorithms based on Lindbladian dynamics. It also develops weak-measurement and compressed methods for simulating those dynamics, with different complexity and implementation trade-offs.

A. Our quantum Gibbs sampling algorithms

  • The coherent algorithm uses a Szegedy-type quantum walk to implement a projector onto the coherent Gibbs state, enabling purified Gibbs-state preparation by simulated annealing with a quadratic speedup in the real spectral gap.The total speedup is only sub-quadratic in the gap because of the cost of block-encoding the discriminant matrix.Source: §III · p. 18, A. Our quantum Gibbs sampling algorithms · p. 18

1. Incoherent Lindbladian simulation algorithms

  • The weak-measurement method simulates Lindbladian evolution with simple, low-depth circuits and Trotter-like complexity scaling as t^2/ϵ for ϵ-accurate evolution over time t.The scheme can be extended to include the Hamiltonian coherence term by applying Hamiltonian evolution for time δ before the circuit.Source: §1 · p. 18, Figure 3 · p. 19
  • The paper also describes a second, [CW17]-inspired simulation method with near-optimal time and accuracy scaling, but its circuits use LCU, oblivious amplitude amplification, and compression techniques.The authors leave a practical comparison of the two schemes for future work.Source: §1 · p. 18, A. Our quantum Gibbs sampling algorithms · p. 18
  • For a convex combination of irreversible Lindbladians, independently sampling one component’s weak-measurement gadget per iteration preserves the same asymptotic iteration count.For the Gibbs sampler, this means an iteration need not apply every jump operator.Source: §1 · p. 20
  • The compressed simulation result assumes block-encoding access to the Lindbladian, and the authors identify their input model—one unitary encoding the entire set of jumps—as a generalization of individually encoded jumps.They state that this input model yields strictly better complexity for Lindbladian simulation.Source: §1 · pp. 18, 21
  • The compressed simulation algorithm achieves almost-linear scaling in time and polylogarithmic scaling in precision, with few ancillas, improving asymptotically on the weak-measurement method’s t^2/ϵ scaling.Its stated two-qubit gate count is O((t + 1)(c + 1)polylog((t + 1)/ϵ)).Source: §1 · p. 21

2. Coherent Lindbladian simulation algorithms

The coherent approach uses a vectorized discriminant associated with a detailed-balance Lindbladian to target the purified Gibbs state. An approximate discriminant proxy supports an efficient projector construction, while preparation also relies on simulated annealing and gap conditions.

2. Coherent Lindbladian simulation algorithms

  • Efficient coherent preparation requires an efficiently block-encoded Hermitian operator with a unique top eigenvector equal to the purified state, plus an adiabatic path whose top-eigenvalue gap remains open.The algorithm uses quantum simulated annealing to change inverse temperature from β′ = 0 to β′ = β.Source: §2 · pp. 22–23
  • A coherent Gibbs sampler can use the vectorized discriminant of a detailed-balance Lindbladian as its candidate operator, whose top eigenvector yields the purified state.The framework also allows coherent samplers that do not refer to an existing Lindbladian.Source: §2 · p. 22
  • An approximate discriminant proxy controls approximate detailed balance and, for a gapped Hermitian operator, its top eigenvector approximates the purified state.The implemented proxy can differ from the discriminant because of Gaussian-weight implementation and tail-truncation errors.Source: §2 · p. 22
  • The coherent-state preparation cost scales directly with the gap through quantum simulated annealing, rather than directly with the original Lindbladian’s mixing time.The gap dependence arises from eigenvalue and eigenvector perturbation arguments.Source: §2 · p. 23

B. Explicit block-encodings

The section builds block-encodings for the discretized Lindbladian and its discriminant proxy from block-encoded jump operators. For the Lindbladian, the operator Fourier transform and a controlled Boltzmann filter provide the central ingredients.

B. Explicit block-encodings

  • The discriminant proxy’s block-encoding is constructed from the Lindbladian block-encoding, with self-adjoint jump operators and a real Fourier weight as additional assumptions.The section notes that the proxy construction requires more symmetry than Lindbladian implementation.Source: B. Explicit block-encodings · p. 23

1. Block-encoding Lβ

  • For weak-measurement simulation, one randomly chosen Lindblad operator can be used at a time; unitary jumps allow two registers to be omitted, leaving n + ⌈log(N)⌉ + 2 qubits.The unitary-jump simplification sets b = c = 0.Source: Figure 4 · p. 24
  • The controlled Boltzmann filter obeys the KMS symmetry, assigning lower weights to heating transitions and relating the filter to detailed balance.Metropolis and Glauber weights are given as examples.Source: §1 · p. 25
  • The operator Fourier transform offers an operator-picture alternative to phase estimation and permits flexible choices of the time-weight function.The circuit combines this transform with controlled Hamiltonian simulation and the quantum Fourier transform.Source: §1 · p. 25
  • The unitary U in Equation (3.9) block-encodes the paper’s Lindbladian.The construction starts from a block-encoding of the jump operators and their discretized Fourier-weighted forms.Source: B. Explicit block-encodings · p. 23, §1 · p. 25

2. Block-encoding Dβ

This section constructs a block-encoding of a discriminant proxy using a Szegedy-style quantum walk. Under specified symmetries, the proxy is Hermitian, and the coherent-sampler analysis uses its spectral gap.

2. Block-encoding Dβ

  • Combining the discriminant construction with simulated annealing yields the advertised quadratic speedup under the stated symmetry assumptions.The assumptions are self-adjoint jump operators and a real Fourier weight.Source: §2 · p. 26
  • With a real Fourier weight and a self-adjoint set of jump operators, the discriminant proxy is Hermitian.The section establishes this using a self-adjointness result for discriminant proxies.Source: §2 · p. 26
  • The discriminant proxy is block-encoded using a unitary block-encoding of the Lindbladian and a reflection-based Szegedy quantum-walk construction.The circuit uses an additional system-register copy and ancillae, along with frequency negation and a permutation of jump labels.Source: §2 · pp. 26–28

3. Proof of coherent Gibbs sampler (Theorem I.4)

  • The coherent Gibbs sampler’s guarantees are proved in terms of the spectral gap rather than the Lindbladian case’s mixing time.The proof bounds eigenvector distance using errors from secular approximation and the discriminant proxy.Source: §3 · p. 28
  • The proof first gives finite-N bounds and then takes the continuum limit, where the discretization parameters disappear from the bound.The user chooses T, Gaussian width σ_t, Fourier resolution ω_0, and the number of points N; the truncation parameter μ̄ enters only implicitly in the secular-approximation analysis.Source: §3 · p. 29

C. Metropolis sampling with arbitrary spectral target weights

The section adapts the sampler construction to arbitrary spectral target weights, then discusses the broader scope and limits of the approach. It also identifies the missing mixing-time or spectral-gap estimates as an open step toward assessing ground-state preparation.

C. Metropolis sampling with arbitrary spectral target weights

  • The construction can target arbitrary spectral weights, although the paper reserves the rest of its analysis for Gibbs sampling.The adaptation requires accessing energies before and after a jump and uses a two-sided operator Fourier transform with a two-argument Metropolis weight.Source: C. Metropolis sampling with arbitrary… · p. 29
  • The two-sided construction is reminiscent of prior approaches but does not require a rounding promise.For a valid Hermitian discriminant proxy, the section assumes self-adjoint jumps and a real Fourier weight.Source: C. Metropolis sampling with arbitrary… · p. 30

IV. DISCUSSION

  • The paper presents efficiently implementable Gibbs-sampling algorithms with fixed-point accuracy guarantees and an analytic framework addressing energy uncertainty.The framework combines operator Fourier transforms, secular approximation, and approximate detailed balance, and is compatible with purified Gibbs-state preparation and Szegedy-type speedup.Source: §IV · p. 30
  • The analysis assumes a Markovian bath in an open-system setting, and the proposed samplers’ mixing time or spectral gap remains to be established.The authors identify direct numerical benchmarking at viable system sizes as an informative next step.Source: §IV · p. 30

Appendix A: Operator Fourier Transform: properties and error bounds

The appendix establishes symmetry and Parseval properties of operator Fourier transforms, then uses frequency filtering to analyze secular approximation errors. It also gives a simple circuit for preparing uniform weights.

Appendix A: Operator Fourier Transform: properties and error bounds

  • The discrete and continuous transformed operators satisfy Fourier-type symmetry and operator Parseval identities; normalized channel operators also resolve the identity.For channel operators, the Parseval inequality becomes equality.Source: Appendix A · pp. 36–37

1. Secular approximation

  • Secular approximation filters out Bohr frequencies far from the frequency label, and its error is controlled by the discarded Fourier tail and spectrum discretization.The discretization contribution shrinks with finer frequency resolution; the resulting discriminant proxy is self-adjoint under the stated symmetry and normalization conditions.Source: §1 · pp. 38, 41
  • When the Bohr frequencies lie on the Fourier grid, secular truncation can be represented by a perturbed weight function.For a general Hamiltonian, rounding the spectrum introduces an additional small error.Source: §1 · p. 39

2. Uniform weights

  • Uniform weights can be prepared with k + 1 Hadamard gates and n − k − 1 CNOT gates when T/t0 = 2^k.The real, normalized weights give transformed operators with the stated Fourier properties.Source: §2 · p. 41

3. Gaussian ansatz

The Gaussian ansatz provides rapidly decaying Fourier tails and an approximate state-preparation method. The appendix also relates continuous and discrete transforms and bounds errors relevant to secular approximation and detailed balance.

3. Gaussian ansatz

  • A truncated Gaussian state can be prepared up to error ϵ using O(n log(1/ϵ)^5/4) gates.The Gaussian’s Fourier transform remains Gaussian, giving it a rapidly decaying tail.Source: §3 · p. 42

4. Discretizing continuous functions via periodic summation

  • Periodic summation relates the continuous Fourier transform to the discrete transform under stated integrability, continuity, and boundedness conditions.The paper gives a self-contained treatment of this discretization approach.Source: §4 · p. 42

5. Tail bounds

  • Gaussian weights have rapidly decaying frequency tails, whereas uniform weights have a heavy tail that affects approximation accuracy.The tail analysis uses the 2-norm; the 1-norm tail for uniform weights would diverge.Source: §5 · pp. 43–44

1. A simpler but weaker bound

  • The discriminant-proxy result also yields approximate detailed balance for Lindbladians.The passage attributes this implication to a triangle inequality.Source: §1 · p. 46
  • For βμ ≤ 1, the discriminant-proxy error bound scales as 132 βμ∥S′∥.The weaker bound is sufficient for Gaussian-damped discriminants because their tails decay rapidly.Source: §1 · pp. 45, 46, 49

2. Bootstrapping the secular approximation

The appendix improves secular-approximation bounds for uniform weights through a bootstrapping argument. It also proves that a uniform-weight Fourier transform yields a purified-Gibbs-state approximation, with a stated gap-dependent cost limitation.

2. Bootstrapping the secular approximation

  • Bootstrapping the secular approximation gives improved bounds for uniform weights when the cutoff satisfies μ ≥ π/T.The argument decomposes the filter into exponentially increasing frequency intervals.Source: §2 · p. 51

3. Fourier Transform with uniform weights

  • Under the theorem’s conditions, the normalized top eigenvector approximates the purified Gibbs state using the plain Fourier transform.The plain transform is simpler to implement and can be implemented exactly with Hamiltonian simulation time O(T), though its asymptotic bound is worse than the Gaussian-damped case.Source: §3 · p. 51
  • The uniform-weight bound requires Hamiltonian simulation time scaling with the inverse gap squared, and the authors do not know whether better bounds are possible.Source: §3 · p. 52

Appendix C: Discretization error for Lindbladians and discriminant proxies

Appendix C develops discretization bounds for Lindbladians and discriminant proxies and shows convergence to the continuum under regularity conditions. It also identifies limits in the generality and tightness of these bounds.

Appendix C: Discretization error for Lindbladians and discriminant proxies

  • The discretized Lindbladian converges to the continuum when the transition weight and time weight are almost everywhere continuous, with the time weight bounded on finite intervals.The appendix presents this as a limiting convergence result.Source: Appendix C · p. 54
  • The convergence argument does not establish quantitative bounds for arbitrary bounded transition weights and square-integrable time weights; the authors need nonasymptotic bounds for their algorithmic functions.Their generic bound can give loose estimates of N, potentially off by polynomial factors, though the stated algorithmic cost depends logarithmically on N.Source: Appendix C · pp. 55, 57
  • The nonasymptotic discretization bounds require regularity conditions, including Lipschitz continuity of the transition weights and Fourier- and time-domain weights.Rounding the Hamiltonian spectrum can reduce the number of distinct Bohr frequencies relevant to the bound.Source: Appendix C · pp. 52, 55

Appendix D: Implications for Lindbladians from system-bath interaction

Appendix D connects physically derived Lindbladians to the paper’s algorithmic construction and analyzes Gibbs fixed points of the coarse-grained master equation (CGME). It treats both the dissipative generator and the Lamb-shift term, including approximate detailed balance and mixing-time considerations.

Appendix D: Implications for Lindbladians from system-bath interaction

  • The CGME construction differs from the algorithmic construction by including a unitary part and using continuous Bohr-frequency labels; its simulation uses a block-encoding.The time scale T depends on open-system parameters and is kept as a tunable abstract parameter in the error bounds.Source: Appendix D · pp. 58–59
  • The dissipative part of the CGME Lindbladian has an approximate Gibbs fixed point under its stated normalization and symmetry conditions.The proof uses bounds for the secular approximation and approximate detailed balance.Source: Appendix D · p. 60

1. Bounds for approximate detailed balance

  • Truncating the secular approximation at energy µ yields an approximate detailed-balance bound that does not depend on the discretization scale.The continuous-energy result follows by taking a continuum limit of the discrete-energy analysis.Source: §1 · p. 60

2. Effects of the Lamb-shift term

  • The full CGME generator has an approximate Gibbs fixed point under the stated symmetry and normalization conditions.The analysis including the Lamb-shift term introduces bounds involving two mixing times, both of which can be upper-bounded using the Hermitian gap of the dissipative part.Source: §2 · p. 60
  • The Lamb-shift analysis secularly approximates the Hamiltonian term and controls its contribution to the fixed-point error.The time-average approximation weakens off-diagonal entries in the H eigenbasis at large Bohr frequencies, with error depending on truncation value µ.Source: §2 · p. 61, a. Secular approximation for the… · p. 61

3. Altogether: Proof of fixed point correctness (Theorem D.2)

This section combines secular-approximation and approximate-detailed-balance errors to establish the full CGME fixed-point analysis. It also develops tools for controlling truncation and matrix perturbations used in that analysis.

3. Altogether: Proof of fixed point correctness (Theorem D.2)

  • The full fixed-point proof combines secular-approximation errors for the dissipative and Lamb-shift terms with approximate-detailed-balance errors and mixing-time bounds.It compares fixed points of the secularly approximated generators using eigenvector perturbation and accommodates distinct truncation energies for the two approximations.Source: §3 · pp. 62–63

4. Proof for secular approximation for time average (Lemma D.2)

  • Smoothly truncating the Bohr-frequency tail avoids the delicate 1-norm error associated with sharp truncation.The resulting time-domain function is a smeared sharp window, with its main error arising near the window edges.Source: §4 · pp. 63–64

Appendix E: Spectral bounds and mixing times

  • The appendix’s spectral and perturbation results support bounds on mixing times and fixed-point correctness.The paper identifies eigenvalue and eigenvector perturbation theory as crucial to those analyses.Source: Appendix E · p. 64

1. Perturbation bounds for eigenvalues and eigenvectors

  • Bauer-Fike perturbation bounds keep spectra close under matrix perturbation and preserve eigenvalue counts within connected components, including algebraic multiplicity.The perturbation result is stated for a normal matrix perturbed by an arbitrary matrix.Source: §1 · p. 65

a. Eigenvector perturbation bounds

  • The eigenvector perturbation bound applies when a nearby eigenvalue of the perturbed matrix is available; for non-Hermitian matrices, that nearby-eigenvalue condition is assumed.For a Hermitian matrix, the paper uses the spectral gap to identify a nearby eigenvalue.Source: a. Eigenvector perturbation bounds · pp. 65–66

2. Approximate detailed balance implies approximately correct fixed point

This section relates approximate detailed balance to fixed-point accuracy and develops perturbation bounds connecting Lindbladian gaps and mixing times. The bounds specify conditions under which these tools control convergence.

2. Approximate detailed balance implies approximately correct fixed point

  • If λgap(H) > 2ϵ, an ϵ-approximately ρ-detailed-balanced Lindbladian has a unique full-rank fixed point whose trace-norm deviation from ρ is at most 14ϵ/λgap(H).The stated bound may deteriorate when the anti-Hermitian component is large or the gap closes.Source: §2 · p. 66

3. Perturbation bounds for Lindbladians regarding gaps and mixing times

  • The appendix gives perturbation bounds for differences in fixed points and mixing times between Lindbladians.These results are presented as bounds for arbitrary pairs of Lindbladians.Source: §3 · pp. 67–68

a. Relating the mixing time to the spectral gap using exact detailed balance

  • Under exact detailed balance, the mixing-time bound can be expressed using the Lindbladian eigenvalue gap.The proposition defines mixing time through convergence in trace norm between states.Source: a. Relating the mixing time to the… · p. 68

b. Relating the mixing time to the Hermitian gap (and approximate detailed balance)

  • For general Lindbladians, the real-part spectral gap is bounded in terms of the Hermitian gap and anti-Hermitian component, and the paper relates these quantities to mixing time.The discussion notes that conversion from spectral gap to mixing time can be poor in the worst case when detailed balance is violated.Source: b. Relating the mixing time to the… · pp. 68–69

Appendix F: Improved incoherent Lindbladian simulation

The improved incoherent Lindbladian simulator compresses repeated postselected weak-measurement steps, reducing the required repetitions while retaining an accurate simulation. The theorem gives resource bounds for purely irreversible Lindbladians and extends to dynamics with a block-encoded coherent Hamiltonian term.

Compression

  • Compression reduces the required circuit repetitions from r = Θ(t^2/ϵ) to h ∼ t log(t/ϵ), enabling substantially improved complexity.The compressed scheme uses h repetitions rather than naively running r repetitions of the Figure 10 circuit.Source: Appendix F · p. 71

Theorem III.2

  • Theorem III.2 simulates e^tL to precision ϵ in diamond norm for purely irreversible Lindbladians, with stated controlled block-encoding and two-qubit-gate resource bounds.The gate count is O((t + 1)(c + 1)polylog((t + 1)/ϵ)).Source: Appendix F · p. 72

General Lindbladians

  • For Lindbladians with coherent term −i[H, ρ], the simulation also uses a block-encoding of H and additional controlled uses of V and V†.Here H = (⟨0c|⊗I)V(|0c⟩⊗I).Source: Appendix F · p. 72

Postselection and amplification

  • The postselected δ-step circuit yields an ϵ-accurate simulation, but its success probability can decrease exponentially with evolution time without amplification.For t > 2, the simulation is divided into ⌈t/2⌉ segments and each is amplified with constant coherent repetitions.Source: Appendix F · pp. 71, 73

Appendix G: Quantum simulated annealing

The appendix analyzes a coherent Gibbs-preparation annealing path, proves a β-linear black-box simulation-time lower bound, and establishes an incompatibility result for boosted shift-invariant phase estimation.

Appendix G: Quantum simulated annealing

  • QSVT gap boosting supplies a quadratic speedup; along a linear temperature path from the maximally entangled β=0 state, k=Θ(β||H||) keeps consecutive overlaps large for amplitude-amplification jumps.Source: Appendix G · p. 76

1. A simple lower bound on β dependence

  • Black-box Hamiltonian simulation requires T=Ω(β) both to implement a reflection about the purified Gibbs state and to prepare ρβ ∝e−βH.Source: §1 · p. 77

Appendix H: Impossibility of boosted shift-invariant in-place phase estimation

  • For every constant k and sufficiently large N, no continuous family of boosted shift-invariant in-place phase-estimation unitaries exists under the stated conditions.The passage identifies the incompatibility between the boosting and shift-invariance assumptions.Source: Appendix H · p. 78
Loading 2303.18224v2…