Query-optimal quantum simulation of Lindblad evolution

Christopher Ye; Chunhao Wang

REVIEW

Query-optimal quantum simulation of Lindblad evolution

Chunhao Wang, Christopher Ye

Quantum Physics · Submitted 15 Sep 2026

Pith's verdict: Resolves the open problem of additive query complexity for general Lindblad simulation with a technically rigorous transducer-based construction.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on September 17, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 1 major objection · 6 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2609.17490 (version 2)

Pith ID73RTT2J3, Pith's permanent record of this paper and its review

CitationChristopher Ye, Chunhao Wang. "Query-optimal quantum simulation of Lindblad evolution." arXiv:2609.17490 (2026). https://pith.science/paper/73RTT2J3

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

Here's my read on arXiv:2609.17490 by Wang and Ye. The headline: they finally close the gap between upper and lower bounds for general Lindblad simulation in the block-encoding model, achieving O(τ + polylog(τ/ε)) query complexity. This is a clean resolution of an open problem that's been around since at least 2017.

What's actually new: they port the transducer framework to dissipative dynamics, construct a local Lindblad transducer, and use the LCU-over-reuse-lengths trick to suppress catalyst-removal error. The factorial-decay analysis for the private-block norm is the technical heart, and it looks sound. The extension to multiple jump operators and a nonzero Hamiltonian is handled with a direct-sum composition that does not break the scaling.

What they do well: the proofs are detailed and self-contained. Every error source is accounted for—discretization, catalyst removal, amplification. They state their assumptions clearly (block-encoding oracles with known norms) and do not oversell. The gate complexity is acknowledged as high, which is honest.

Soft spots: the gate count is eO(m (τ+polylog)^3/ε), which is worse than existing algorithms, but the paper is about query complexity, not gate complexity, and they say so. The time-dependent extension is sketched rather than worked out in full detail, though it's a natural follow-up. The reliance on block-encodings is standard but not universal; if someone needs a different access model this algorithm does not directly apply.

Verdict: this is a strong paper that resolves an open question. It belongs in a good venue. I'd bring it to reading group and cite it when the topic comes up. Recommend accept with no major revision needed, though the authors might want to expand the time-dependent section a bit.

Referee report

Significance

This result closes a major open problem in quantum simulation: whether general Lindblad evolution can be simulated with additive, rather than multiplicative, dependence on time and precision. The optimal query complexity is provably O(τ + polylog(τ/ε)), matching the lower bound inherited from Hamiltonian simulation. The techniques — a dissipative transducer with factorial private-block decay and an LCU-based error reduction for reuse circuits — are new and likely to find further applications. The paper is rigorous, with full proofs for all technical claims, including error bounds for discretization, catalyst removal, and amplification. The work will be of high interest to the quantum-algorithms community and strengthens the theoretical foundations for open-system simulation, thermal-state preparation, and related applications.

Minor objections (6)

[Lemma 18] The statement of Lemma 18 contains a typesetting error: 'B√τ (B√τ q)^q' should probably read 'B√τ (B√τ / q)^q' or the equivalent form used in the proof. Please correct the equation and ensure the typesetting is unambiguous.
[Notation] The soft-O notation eO is used throughout but never defined. Please define eO at the start of Section 2 (e.g., eO(g) = O(g polylog(g)) for the relevant parameters).
[Lemma 15, proof] The derivation of the block-norm bound via the operator-valued Schur test is concise. It would aid readability to state explicitly that the maximum row sum uses the factor (r+u-1 choose u) because ∆_R departures can repeat time steps, while the maximum column sum includes an extra factor (r choose v)^{1/2} due to the square root in the Schur test. A short remark after the lemma would clarify the counting.
[Section 3.5, construction of p_err and λ_i] The conversion from p_annih(q) g_{6q} to λ_i is cited from [5] but the steps are not repeated. Since the LCU construction is critical to the claimed query complexity, the paper should either reproduce the conversion formula (Eq. (48) of [5]) with key parameters, or provide a self-contained derivation in a few lines.
[Eq. (114)] The constant C_comp from the Lie–Trotter bound is claimed to exist. Please state its explicit value (or a bound) in terms of α_H, Λ_D, and ∥L∥_be, or provide a reference where the bound is derived. This is a minor check but improves reproducibility.
[Abstract and Introduction] The abstract mentions 'catalyst-removal error' but the term is not defined until Section 2.3. A brief parenthetical explanation in the abstract would help readers new to the transducer framework.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

A quantum algorithm achieves optimal query complexity for simulating open-system dynamics, matching the Hamiltonian simulation lower bound.

The reading

The paper resolves a decade-old open problem by proving that simulating Markovian open quantum systems (Lindblad evolution) requires only O(τ + polylog(τ/ε)) oracle queries, where τ is the normalized evolution time. This matches the additive lower bound inherited from Hamiltonian simulation, which earlier algorithms failed to reach because they had multiplicative dependence on time. The key is a transducer-based approach that separates the number of evolution steps from the number of oracle calls, combined with a careful cancellation of errors using linear combinations of reuse circuits. The result shows that the multiplicative overhead in prior work was not fundamental, and identifies the remaining challenge of achieving the same query bound with optimal gate complexity.

What carries the argument

The transducer framework: a unitary S that acts on a public (system) and private (catalyst) space, implementing a target isometry while returning the catalyst unchanged. The local transducer uses a Cayley construction to realize the Kraus operators of a first-order approximation to the Lindblad evolution with error O($δ^{2}$). Multiple transducers are composed by assigning each timestep a separate private sector (via a time register), allowing oracle calls to be collected into a single layer. The catalyst is removed via a reuse construction that distributes the public input over s branches and reuses a scaled catalyst; errors from catalyst removal are further suppressed by combining reuse circuits of different lengths via linear combination of unitaries (LCU), exploiting a polynomial that annihilates the dominant part of the private-to-private block. This yields factorial decay of the error, leading to the additive query bound.

Extended reading notes

Core claim

The paper establishes that for any Lindbladian L with Hamiltonian H and jump operators L_j, given block-encodings of these operators, there exists a quantum algorithm that approximates the evolution channel $e^{{Lt}}$ to diamond-norm error ε using O(t ||L||_be + polylog(t ||L||_be / ε)) queries to each oracle. This matches the lower bound Ω(t + polylog(1/ε)) from Hamiltonian simulation, closing the gap for general Lindblad evolution. The algorithm is based on a transducer that implements a local first-order approximation to the evolution with a catalyst state, compositions of such transducers, and a reuse-and-LCU construction that removes the catalyst while suppressing the cumulative error.

Load-bearing premise

The algorithm assumes access to block-encodings of all operators (Hamiltonian and jump operators) with known normalization factors; this standard oracle model may not be available in all practical settings, and the algorithm does not provide a method to construct these block-encodings from more basic descriptions of the system.

Editorial extensions

If this is right

Lindblad simulation can now be performed with oracle complexity that matches the known lower bound, confirming that the multiplicative dependence in earlier algorithms was not intrinsic.
The result extends to time-dependent Lindbladians with a piecewise-constant approximation, maintaining the same query complexity under smoothness conditions.
The algorithm applies to any number of jump operators without explicit dependence on their count in the query complexity, as they can be stacked into a single operator.
Simulating open quantum systems is now query-optimal, similar to Hamiltonian simulation, which may simplify resource estimation for fault-tolerant implementations.
The high gate complexity (O(m (τ+polylog)^3/ε)) indicates that further work is needed to match the gate complexity of existing algorithms while keeping the optimal query scaling.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The transducer technique, originally developed for Hamiltonian simulation, proves flexible enough to handle non-unitary, non-normal generators of open-system dynamics, suggesting it may apply to other quantum channel simulation problems.
The additive query complexity implies that for sufficiently long simulation times, the cost is dominated by polylogarithmic factors, making long-time Lindblad simulation essentially as cheap as the shortest timescale of interest.
If block-encodings of system operators are available, simulating dissipative processes like spontaneous emission or thermalization may require fewer oracle calls than previously thought, potentially lowering error correction overhead.
The remaining gap between query complexity and gate complexity (cubic in τ vs. nearly linear in τ) points to a concrete open problem: can one achieve the same query bound with polylogarithmic gate overhead, perhaps via a quantum singular value transformation adapted to channels?

Original abstract

For the problem of simulating Lindblad evolution for time $t$ to precision $\epsilon$, Hamiltonian simulation provides an additive query lower bound, informally, $\Omega(t + \mathrm{polylog}(1/\epsilon))$. However, the best previously known algorithms for general Lindblad simulation achieve a multiplicative upper bound, informally, $\mathcal{O}(t\,\mathrm{polylog}(1/\epsilon))$, in query complexity. It has remained open whether this multiplicative dependence is necessary. In this paper, we close the gap in query complexity by giving an algorithm with optimal additive dependence on evolution time and precision in the block-encoding model. Our approach uses the transducer framework to reduce the query cost of composing first-order approximations to the evolution channel, together with linear combinations of reuse circuits of different lengths to suppress catalyst-removal error. We further achieve nearly optimal gate complexity in evolution time and precision through history compression and an efficient implementation of the query-free part of the transducer using operation reordering and linear combinations of unitaries, while preserving the optimal query complexity.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 5,052 input tokens.

What the abstract itself states, as probabilities: claims first 0.22 · states limitation 0.96 · human participants 0.01 · controlled comparison 0.10 · randomized assignment 0.01 · states quantitative result 0.89 · compares with prior results 0.98 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

For the problem of simulating Lindblad evolution for time $t$ to precision $\epsilon$, Hamiltonian simulation provides an additive query lower bound, informally, $\Omega(t + \mathrm{polylog}(1/\epsilon))$. However, the best previously known algorithms for general Lindblad simulation achieve a multiplicative upper bound, informally, $\mathcal{O}(t\,\mathrm{polylog}(1/\epsilon))$, in gate complexity. It has remained open whether this multiplicative dependence is necessary. In this paper, we close the gap in query complexity by giving an algorithm with optimal additive dependence on evolution time and precision in the block-encoding model. Our approach uses the transducer framework to reduce the query cost of composing first-order approximations to the evolution channel, together with linear combinations of reuse circuits of different lengths to suppress catalyst-removal error. Although our additional gate complexity is higher than that of existing algorithms, our optimal query complexity resolves the question of how much oracle access is fundamentally necessary and identifies the remaining challenge to achieve the optimal gate complexity.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	For the problem of simulating Lindblad evolution for time $t$ to precision $\epsilon$, Hamiltonian simulation provides an additive query lower bound, informally, $\Omega(t + \mathrm{polylog}(1/\epsilon))$.	background 0.99	0.10	0.04	asserted 0.99
s1	However, the best previously known algorithms for general Lindblad simulation achieve a multiplicative upper bound, informally, $\mathcal{O}(t\,\mathrm{polylog}(1/\epsilon))$, in gate complexity.	background 0.94	0.03	0.03	asserted 1.00
s2	It has remained open whether this multiplicative dependence is necessary.	gap 1.00	0.03	0.03	asserted 0.70
s3	In this paper, we close the gap in query complexity by giving an algorithm with optimal additive dependence on evolution time and precision in the block-encoding model.	contribution 0.92	0.97	0.92	asserted 1.00
s4	Our approach uses the transducer framework to reduce the query cost of composing first-order approximations to the evolution channel, together with linear combinations of reuse circuits of different lengths to suppress catalyst-removal error.	method 1.00	0.92	0.07	asserted 1.00
s5	Although our additional gate complexity is higher than that of existing algorithms, our optimal query complexity resolves the question of how much oracle access is fundamentally necessary and identifies the remaining challenge to achieve the optimal gate complexity.	interpretation 0.77	0.90	0.22	asserted 1.00

What kind of paper the classifier reports this is: theoretical result 0.51 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

References

Forward citations

Cited by 6 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Query-Optimal and Gate-Efficient Lindbladian Simulation
quant-ph 2026-09 accept novelty 9.0 of 10

This paper presents a quantum algorithm for simulating open quantum systems described by Lindblad master equations, achieving the optimal query complexity that matches the known lower bound for Hamiltonian simulation.
Transducer-based linear combination of unitaries: theory and applications
quant-ph 2026-09 conditional novelty 8.0 of 10

A transducer-based LCU construction implements a linear combination of unitaries at query cost O(C_max + (lambda/a) C-bar) instead of O(C_max lambda/a), when the unitaries share primitive oracle access.
Optimal low-rank compression of quantum dynamics
quant-ph 2026-09 conditional novelty 8.0 of 10

For local quantum dynamics, the minimal logarithmic rank of a compressed representation grows as sqrt(log(1/epsilon)) for static Hamiltonians and as (log(1/epsilon))^(2/3) for arbitrary driving, with matching lower bounds.
Dissipation accelerates quantum and classical simulation of open-system dynamics
quant-ph 2026-09 accept novelty 7.0 of 10

Dissipation that damps every nonidentity Pauli mode compresses Heisenberg observables, enabling system-size-independent quantum Trotter steps and polynomial-time classical Pauli-propagation simulation.
Lattice Lindbladian simulation by patching and merging
quant-ph 2026-09 accept novelty 7.0 of 10

Patching and merging local Lindbladian dynamics yields near-optimal O(Nt polylog) simulation for sparsely dissipative systems and an improved (Nt) to the 4/3 per-sample gate count for generic 1D lattice Lindbladians.

Show 1 more citing papers

Optimal transducers using symmetries
quant-ph 2026-10 conditional novelty 6.0 of 10

Symmetry reduces optimal-transducer construction to small optimization problems, yielding exact-constant transducers for search, amplitude amplification, and amplitude estimation.

How the literature uses it

Papers whose main result relates to this one's

How each label was checked · JSON

Found among the papers closest to this one by title and main claim. Pith's classifier compared each pair's main results and a second model family confirmed the relation; checked against two further families, shown conflicts agreed 118 times in 120 and shown same results 218 times in 239. The quoted sentence is the other paper's main claim.

States the same result 1 paper

The algorithm approximates the evolution channel to diamond-norm error $\varepsilon$ using $O\!\left(\tau+\frac{\log(1/\varepsilon)}{\log\!\left(e+\log(1/\varepsilon)/\tau\right)}\right)$ oracle queries, matching the query lower bound for Hamiltonian simulation.

Query-Optimal and Gate-Efficient Lindbladian Simulation · 0.93

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.