PaperlayerView exact revision on arXiv

Source-linked AI summary

Exponential Lindbladian fast forwarding and exponential amplification of certain Gibbs state properties

Zhong-Xia Shang, Dong An, Changpeng Shao

arXiv:2509.09517v2quant-ph

TL;DR

Existing Lindbladian simulation algorithms have multiplicative query complexity, while Gibbs states are important for studying thermal equilibrium and quantum-system properties. This work develops simulation and Gibbs-coherence estimation algorithms, reporting exponential improvements in β and n over QSVT when the spectral norm is unknown.

  • Problem

    Existing Lindbladian simulation algorithms have multiplicative query complexity, while Gibbs states characterize thermal equilibrium and matter properties.

    Source: §I · p. 2

  • Method

    The paper uses vectorization-space LCU for dissipative Lindbladian simulation and adapts it for block-diagonal Pauli jump operators and Gibbs coherence estimation.

    Source: §I · pp. 2–4

  • Results

    The Gibbs-coherence approach achieves exponential improvements in β and n over QSVT when the spectral norm is unknown.

    Source: §I · p. 3

  • Takeaways & Limitations

    For general input states, the level of improvement depends on the Hadamard-gate coherence resources required to prepare them.

    Source: §I · p. 3

    The exponential improvement is in circuit depth, not query complexity, and comes with large ancilla usage and parallel oracle access.

    Source: A. Lindbladian fast forwarding · p. 6

Abstract

from arXiv · show

Fast-forwarding refers to the ability to simulate a system of time $t$ using significantly fewer than $t$ queries or circuit depth. While various Hamiltonian systems are known to circumvent the no fast-forwarding theorem, analogous results for dissipative dynamics, governed by Lindbladians, remain largely unexplored. We first present a quantum algorithm for simulating purely dissipative Lindbladians with unitary jump operators, achieving additive query complexity $\mathcal{O}\left(t + \log(\varepsilon^{-1})\right)$ up to error~$\varepsilon$, improving previous algorithms. When the jump operators have certain structures (i.e., block-diagonal Paulis), the algorithm can be modified to achieve exponential fast-forwarding, attaining circuit depth $\mathcal{O}\left(\log\left(t + \log(\varepsilon^{-1})\right)\right)$, while preserving query complexity via parallel access. Using these fast-forwarding techniques, we develop a quantum algorithm for estimating Gibbs state properties of the form $\langle \psi_1 | e^{-\beta(H + I)} | \psi_2 \rangle$, up to additive error $\epsilon$, with $H$ the Hamiltonian and $\beta$ the inverse temperature. For input states exhibiting certain coherence conditions -- e.g.,~$\langle 0|^{\otimes n} e^{-\beta(H + I)} |+\rangle^{\otimes n}$ -- our method achieves exponential improvement in complexity (measured by circuit depth), $\mathcal{O} (2^{-n/2} \epsilon^{-1} \log \beta ),$ compared to the quantum singular value transformation-based approach, with complexity $\tilde{\mathcal{O}} (\epsilon^{-1} \sqrt{\beta} )$. We show how to apply this exponential improvement to applications such as the ground state overlap testing and amplitude estimation. For general $| \psi_1 \rangle$ and $| \psi_2 \rangle$, we also show how the level of improvement is changed with the coherence resource in $| \psi_1 \rangle$ and $| \psi_2 \rangle$.

I. INTRODUCTION

The introduction identifies fast-forwarding for dissipative Lindbladians as an open direction and presents algorithms for simulation and Gibbs coherence estimation. It highlights exponential circuit-depth improvements in structured cases, while noting that query complexity can remain unchanged.

I. INTRODUCTION

  • General Lindbladian simulation has a lower bound of Ω(t + log(ε^-1) log log(ε^-1)), ruling out general-case fast-forwarding, while special cases remain open to exploration.Existing algorithms achieve multiplicative query complexity Õ(t polylog(ε^-1)) [34, 35].Source: §I · p. 2
  • The introduction motivates Gibbs-state study through its role in characterizing thermal equilibrium and its relevance to condensed-matter physics, machine learning, and optimization.It notes that high-temperature Gibbs states are close to maximally mixed, whereas at moderately low temperatures they can have large ground-state overlap and be QMA-hard to prepare [41] [42].Source: §I · p. 2
  • The paper gives an additive-query algorithm for purely dissipative Lindbladians with unitary jump operators, improving on the prior multiplicative bound O(t polylog(ε^-1)).Its approach applies LCU in vectorization space, where dissipative evolution removes the need for oblivious amplitude amplification.Source: §I · pp. 2–3
  • For block-diagonal Pauli jump operators, the algorithm achieves exponential fast-forwarding in circuit depth while preserving query complexity through parallel access.Coherent parallel Pauli multiplication via tableau representation enables parallel Lindbladian queries; the stated improvement is in depth, not query count.Source: §I · p. 3
  • For certain states, including |ψ1⟩=|0⟩^⊗n and |ψ2⟩=|+⟩^⊗n, the algorithm achieves exponential improvements in β and n over QSVT when the spectral norm is unknown.The paper also relates GCA at limiting β values to amplitude estimation and ground state overlap testing.Source: §I · p. 3
  • For general input states, the complexity improvement depends on their quantum coherence resources, measured by the number of Hadamard gates needed to prepare them.The paper denotes the total Hadamard-gate count in the preparation circuits by n_h.Source: §I · pp. 3–4
  • The paper estimates Gibbs coherence amplitudes ⟨ψ1|e^−β(H+I)|ψ2⟩ using tailored Lindbladians whose dissipative evolution implements e^−β(H+I) on Pauli-encoded states.Pauli encoding can exponentially amplify certain amplitudes through the vector norm of vectorized Pauli matrices; GCA is related to complex-time Loschmidt echoes and boundary partition functions [51].Source: §I · pp. 3–4

A. Lindbladian fast forwarding

The paper improves query complexity for purely dissipative Lindbladians with unitary jumps, then obtains circuit-depth fast forwarding for block-diagonal Pauli jumps. That depth improvement keeps query complexity unchanged by using parallel access and more ancillas.

A. Lindbladian fast forwarding

  • For purely dissipative Lindbladians with unitary jump operators, query complexity improves to additive O(t + log(ε^-1)) from the previous multiplicative Õ(t polylog(ε^-1)).The result has strictly linear dependence on t.Source: A. Lindbladian fast forwarding · p. 6
  • For block-diagonal Pauli jump operators, the algorithm achieves exponential fast forwarding in circuit depth while retaining the query complexity of Theorem 1.The approach uses parallel Pauli multiplication via a tableau representation, enabling parallel Lindbladian queries.Source: A. Lindbladian fast forwarding · pp. 5–6
  • The special jump operators represent selected dephasing noise: each P_j,i acts on the subspace labeled by |j⟩ in the first register.For R = 1, the result directly applies to natural Pauli noise.Source: A. Lindbladian fast forwarding · p. 6
  • This fast forwarding is a depth improvement, not a query-complexity improvement, and requires parallel oracle access and large ancilla usage.The paper describes the trade-off as transferring circuit-depth cost to space without increasing overall space-time (query) complexity.Source: A. Lindbladian fast forwarding · p. 6

B. Estimating Gibbs coherence amplitude

The paper estimates Gibbs coherence amplitudes between circuit-prepared states using a Lindbladian-based algorithm. Its circuit-depth comparison with QSVT improves exponentially in coherence-related and temperature-related factors for specified cases, with applications to amplitude estimation and ground-state overlap testing.

B. Estimating Gibbs coherence amplitude

  • The Gibbs coherence amplitude is ⟨ψ1|e^-β(H+I)|ψ2⟩, with ψ1 and ψ2 prepared by circuits whose Hadamard-gate counts contribute to the complexity.The inputs are prepared from |+⟩^⊗n and |0⟩^⊗n, respectively, using circuits over {H, S, T, CNOT}.Source: B. Estimating Gibbs coherence amplitude · p. 7
  • For examples such as ⟨0|^⊗n e^-β(H+I)|+⟩^⊗n, the circuit-depth comparison with QSVT gives factors 2^-n/2 versus 1 and log(β) versus β.The comparison is stated for circuit depth.Source: B. Estimating Gibbs coherence amplitude · p. 7, Table I · p. 8
  • The method encodes the Gibbs operator in Lindbladian dynamics, but does not provide full Gibbs-state preparation or sampling.The GCA is related to the complex-time Loschmidt echo, also called the boundary partition function.Source: B. Estimating Gibbs coherence amplitude · pp. 7–8
  • At β = 0, GCA estimation becomes standard amplitude estimation, and the maximal improvement 2^-n/2 occurs for a +/- basis state paired with a computational-basis state.The cited corollary treats estimating ⟨+|^⊗n U|0⟩^⊗n.Source: B. Estimating Gibbs coherence amplitude · pp. 8–9
  • When n − nh = Θ(n), the stated complexity yields exponential improvement; examples include nh = √n or nh = 3n/4.The estimated GCA magnitude is also upper bounded by 2^-(n−nh)/2.Source: B. Estimating Gibbs coherence amplitude · pp. 7–8
  • At large β, GCA estimation can probe ground-state overlap when ψ2 has nonzero ground-state overlap; the paper gives an example starting from |+⟩^⊗n and testing |0⟩^⊗n.The stated comparison with ground-state preparation algorithms depends on frustration, gap, and the initial state's ground-state overlap.Source: B. Estimating Gibbs coherence amplitude · p. 9

III. METHODS OVERVIEW

The overview introduces vectorization as a representation of operators by vectors, then uses it to express linear transformations on operators as transformations on vectors.

III. METHODS OVERVIEW

  • Vectorization maps an operator O = ∑ij oij|i⟩⟨j| to the 2n-qubit vector |O⟩ = ∑ij oij|i⟩|j⟩.The paper also identifies |O⟩ as the Choi vector of O.Source: §III · p. 9
  • In the vectorized picture, a general transformation O → ∑i Ai O B_i† becomes |O⟩ → ∑i Ai ⊗ B_i* acting on |O⟩.The transformation moves from operators to vectors.Source: §III · p. 9
  • The notation distinguishes the Hermitian conjugate of B_i from its complex conjugate in the vectorized expression.The prose explicitly identifies B_i† and B_i*, respectively.Source: §III · p. 9

A. Lindbladian fast forwarding

For purely dissipative Lindbladians with unitary jump operators, the Taylor-series simulation avoids time discretization and has additive scaling in evolution time and error. With block-diagonal Pauli structure, the query count is preserved while circuit depth can be reduced exponentially.

A. Lindbladian fast forwarding

  • For unitary jump operators, the dynamics are represented by a Taylor truncation whose terms correspond to a quantum channel with unitary Kraus operators.A purification uses Ug and UF; both have O(K) query complexity, and UF queries are adaptive.Source: A. Lindbladian fast forwarding · pp. 9–10
  • The global Taylor-series approach has additive scaling in T and ε, avoiding time discretization and the repeated oblivious amplitude amplification used by earlier LCU approaches.Dissipation supplies an e^-T rescaling that keeps the expansion's coefficient 1-norm constant.Source: A. Lindbladian fast forwarding · p. 10
  • Block-diagonal Pauli jump operators permit products of K Pauli operators to be computed in logarithmic depth, reducing circuit depth while retaining K queries.Each jump operator has R Pauli blocks, which also contribute to the simulation complexity.Source: A. Lindbladian fast forwarding · pp. 10–11
  • The passage introduces the fast-forwarding algorithm’s total circuit depth without giving its value, and points to Appendix B 2 for further proof details about Theorem 2, including the number of ancillas.Source: A. Lindbladian fast forwarding · p. 11

B. Estimating Gibbs coherence amplitude

The Gibbs-coherence estimator encodes the desired matrix element in a channel's non-diagonal density-matrix blocks. Vectorization gives the identity an exponentially large norm, enabling amplification under coherence conditions, while dissipative channels can also make the relevant norm small.

B. Estimating Gibbs coherence amplitude

  • The algorithm estimates ⟨ψ1|e^-β(H+I)|ψ2⟩ by constructing a quantum channel that encodes the Gibbs-coherence amplitude.It reads the real and imaginary parts through expectations of X ⊗ I_n and Y ⊗ I_n, respectively.Source: B. Estimating Gibbs coherence amplitude · p. 11
  • Vectorization makes the identity operator a Bell state with norm 2^n/2, producing the 2^-n/2 amplification factor in estimation complexity.This is the stated origin of the exponential amplification.Source: B. Estimating Gibbs coherence amplitude · p. 11
  • The relevant encoded norm can be small because of the dissipative nature of quantum channels.The cited passage identifies this as a possible constraint on the amplification.Source: B. Estimating Gibbs coherence amplitude · p. 12
  • Pauli encoding relates the encoded operator norm to quantum coherence, yielding a 2^n_h/2 factor in Theorem 3.Under this encoding, I maps to |0⟩ and X maps to |1⟩; for example, an operator proportional to I + X vectorizes to |+⟩.Source: B. Estimating Gibbs coherence amplitude · p. 12

IV. SUMMARY AND OUTLOOK

The paper summarizes additive-complexity simulation for purely dissipative Lindbladians and exponential circuit-depth fast-forwarding for block-diagonal Pauli jumps, then connects these methods to Gibbs-coherence estimation. It also supplies amplitude-estimation and vectorization tools used in the analysis.

IV. SUMMARY AND OUTLOOK

  • For unitary-jump purely dissipative Lindbladians, simulation has additive complexity; block-diagonal Pauli jumps additionally permit exponential circuit-depth fast-forwarding while preserving query complexity.The paper presents this as its first Lindbladian fast-forwarding result; it also reports exponential advantages in two parameters for Gibbs-coherence estimation under coherence conditions.Source: §IV · p. 12

1. Amplitude estimation

  • Amplitude estimation gives additive-error estimates of state overlap magnitudes, and the Hadamard test extends it to real and imaginary overlap parts with O(ε^-1 log(δ^-1)) queries.Adaptive calls make the circuit depth O(ε^-1 log(δ^-1)).Source: §1 · pp. 18–19

2. Vectorization

  • Vectorization maps a matrix O to the two-register vector |O⟩⟩, while matrixization reverses that mapping; the Lindbladian is expressed in this vectorized representation.The density matrix ρ(t) is represented as |ρ(t)⟩⟩, and L is the Liouvillian generator.Source: §2 · pp. 19–20

1. Proof of Theorem 1

The proof approximates purely dissipative Lindbladian evolution by a truncated Taylor expansion and implements the resulting channel with an environment-assisted circuit. The construction allows a broader jump-operator condition than unitarity alone.

1. Proof of Theorem 1

  • A Taylor truncation of the vectorized evolution yields a channel with unitary Kraus operators, implemented by purifying it with Ug and UF.The circuit starts from a pure system state and adds environment registers; efficient preparation of the truncated discrete Poisson state is one stated option.Source: §1 · pp. 20–21
  • The simulation's query complexity is O(K), with K = O(T + log(ε^-1) log log(ε^-1)); T is the rescaled evolution time.The circuit depth is also O(K) in this construction because UF is applied sequentially, while controlled-Ug operations can run in parallel.Source: §1 · pp. 20, 22
  • Tracing out the environment produces an approximate density matrix, and the construction implements the corresponding approximate quantum channel.The proof establishes an error bound in diamond norm before deriving Theorem 1.Source: §1 · pp. 22–23
  • The core condition can be relaxed beyond exactly unitary jumps, allowing non-unitary examples such as F1 = |0⟩⟨1| and F2 = |1⟩⟨0|.The stated generalization rests on the condition in Eq. B1.Source: §1 · p. 23

2. Proof of Theorem 2

The proof builds fast-forwarding from block-diagonal Pauli structure, using coherent Pauli multiplication to avoid applying each factor sequentially. Its supporting encoding tools represent general states in density-matrix blocks, compose encoded operations, and recover amplitudes.

2. Proof of Theorem 2

  • Block-diagonal products of Pauli operators can be computed directly in the Pauli group, enabling coherent parallelization and an exponential reduction in circuit depth.For K operators, the binary-tree multiplication circuit has depth log(K); the full construction also applies a transformation of depth R.Source: §2 · pp. 23–24

1. Non-diagonal density matrix encoding

  • Non-diagonal density matrix encoding places an arbitrary matrix in a non-diagonal block, bypassing density matrices’ Hermitian and positive-semidefinite constraints on the encoded information.A γ-NDME denotes an encoding with factor γ.Source: §1 · p. 26

2. Pauli encoding: I as |0⟩and X as |1⟩

  • Pauli encoding represents computational basis states using I and X in non-diagonal density-matrix blocks, allowing an n-qubit pure state to be encoded through NDME.The upper bound on the encoding factor varies by state: it is smallest for computational-basis states and largest for states in the +/- basis.Source: §2 · pp. 26–28

3. Channel block encoding

  • Channel block encoding applies a quantum channel to an NDME so that its upper-right block implements a chosen operation on the encoded state.The channel’s Kraus operators must satisfy the stated completeness conditions.Source: §3 · pp. 28–29

4. Optimal channel block encoding for elementary quantum gates

  • Strong-CBEs compose associatively, and the paper constructs optimal strong-CBEs for elementary unitary gates that attain their respective upper bounds.The listed constructions satisfy the strong-CBE condition.Source: §3 · p. 29, §4 · pp. 30–31, Table II · p. 30

5. Exponential amplitude amplification

  • Pauli expectations of the encoded density matrix contain computational-basis amplitudes, which amplitude estimation can estimate to additive error ε.The stated algorithm estimates the real and imaginary parts with success probability at least 1 − δ.Source: §5 · pp. 31–32

6. Proof of Theorem 3

The proof encodes the Gibbs-conjugate amplitude using channel block encoding and Lindbladian evolution. It estimates the resulting amplitude through a purification circuit, with circuit depth determined by the state-preparation circuits and the fast-forwarded evolution.

6. Proof of Theorem 3

  • Setting t = β makes the Lindbladian evolution a 1-CBE of the target operator e^-β(H′+I).The construction focuses on the upper-right density-matrix block and uses Pauli CBE constructions for terms in H′.Source: §6 · pp. 33–34
  • The construction applies the channels for U2, Lindbladian evolution, and U1† in sequence to an initial state that is a 1/2-NDME of |+⟩^⊗n.The resulting output state is an NDME of the target state; its purification is used for estimation.Source: §6 · p. 34
  • The Lindbladian jump operators have the specified form with R = 2, allowing exponential fast-forwarding with simulation depth log(K).K is the Taylor-expansion truncation order.Source: §6 · p. 35
  • Adaptive amplitude-estimation queries make total circuit depth the output-state preparation depth multiplied by the query complexity.The preparation depth is D + log(K), and the proof simplifies log(K) to log(β) because its error dependence is dominated by the ϵ^-1 factor.Source: §6 · p. 35

Appendix D: Estimating GCA through QSVT

This appendix gives a QSVT-based approach to estimating the Gibbs-conjugate amplitude and contrasts it with spectral amplification when the Hamiltonian norm is known. The supplied passages state that the latter has exponentially better scaling in β in that setting.

Appendix D: Estimating GCA through QSVT

  • The QSVT approach encodes the Gibbs-conjugate amplitude in a block-encoding and estimates its real and imaginary parts using adaptive queries.The stated overall depth is given in the cited complexity expression, whose value is not included in the passage.Source: Appendix D · p. 36
  • When the Hamiltonian norm is known and strictly below 1, spectral amplification constructs an amplified block-encoding by adaptively querying U_H.The construction uses O(α^-1∥H∥^-1 log(ϵ^-1)) queries.Source: Appendix D · p. 36
  • The resulting method achieves exponentially better scaling in β than the case where the spectral norm of H is unknown.The passage states this comparison without giving the displayed depth expression’s value.Source: Appendix D · p. 37

Appendix E: Ground state overlap testing

The appendix uses the Gibbs-conjugate amplitude to test overlap with a ground state, comparing the proposed method with standard ground-state preparation. Its stated advantage depends on frustration, the gap, and the choice of initial state.

Appendix E: Ground state overlap testing

  • For sufficiently large β and nonzero ground-state overlap in |ψ2⟩, e^-β(H+I)|ψ2⟩ is essentially proportional to the ground state, so the amplitude probes its overlap with |ψ1⟩.This frames the estimate as a way to assess how close the ground state is to a reference state.Source: Appendix E · p. 37
  • The analysis specializes to |ψ2⟩ = |+⟩^⊗n and |ψ1⟩ = |0⟩^⊗n, while stating that the derivation extends analogously to arbitrary input states.It assumes a unique ground state for simplicity and says the results extend naturally to degeneracy.Source: Appendix E · p. 37
  • The appendix compares the proposed ground-overlap test’s circuit depth with a state-of-the-art ground-state preparation algorithm combined with amplitude estimation.The supplied passages do not include the displayed complexity values.Source: Appendix E · p. 38
  • For frustration-free H with E0 = −1, the comparison gives C1 = 2^-n/2 versus C2 = ∆^-1 ≥ 1, but this case is a classically easy stabilizer Hamiltonian.The authors note that generally 1 + E0 > 0, with C1 depending on its relationship to the spectral gap ∆.Source: Appendix E · p. 39
  • For a guided initial state, the method retains exponential advantage when frustration 1 + E0 is smaller than the gap ∆.The guided-state case requires additive estimation error ϵ = O(2^-n/2).Source: Appendix E · p. 39
  • For an initial state sampled from a 1-design, the stated advantage condition is that 2(1 + E0) is smaller than the gap ∆.This is the non-guided-state case analyzed in the passage.Source: Appendix E · p. 39

Related papers

Loading 2509.09517v2…