arXiv:2609.17490
Query-optimal quantum simulation of Lindblad evolution
Chunhao Wang, Christopher Ye
Abstract
For the problem of simulating Lindblad evolution for time $t$ to precision $ε$, Hamiltonian simulation provides an additive query lower bound, informally, $Ω(t + \mathrm{polylog}(1/ε))$. However, the best previously known algorithms for general Lindblad simulation achieve a multiplicative upper bound, informally, $\mathcal{O}(t\,\mathrm{polylog}(1/ε))$, 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.
AI Summary
The paper asks whether general Lindblad simulation requires multiplicative dependence on evolution time and precision, or can match the additive query bounds of Hamiltonian simulation. It treats arbitrary Hamiltonians and jump operators given through controlled block-encoding oracles and their adjoints, without assuming unitary jumps or a state-independent total jump rate. Writing $\tau=t(\alpha_H+\sum_j\alpha_j^2)$, it constructs a channel approximating $e^{t\mathcal L}$ within diamond-norm error $\epsilon$ using $O(c(\tau,\epsilon))$ queries to **each** input oracle, where $c(\tau,\epsilon)=1+\tau+\log(1/\epsilon)/\log(e+\log(1/\epsilon)/\tau)$. This matches the worst-case time–precision lower bound inherited from Hamiltonian simulation. Additional arbitrary one- and two-qubit gates scale as $O(c(\tau,\epsilon)[C_{\rm anc}+m+\log(e+(\tau+1)/\epsilon)\log(e+(m+1)(\tau+1)/\epsilon)])$. The construction composes first-order dissipative Stinespring transducers with Hamiltonian Cayley transducers. Composition collects oracle calls into one layer while keeping squared catalyst norm $O(\tau)$, independently of discretization length. Linear combinations of catalyst-reuse circuits cancel removal errors. Restricting the private-space analysis to chronologically valid histories yields factorial decay, with error bounded by $\sqrt{2\tau}(C\sqrt{\tau/q})^q$ using $O(q)$ queries. History compression, rotation reordering, LCU compilation, and segmentation reduce gate costs. The optimality claim concerns query dependence on time and precision, not total queries independent of $m$. Gate bounds use arbitrary rotations. A time-dependent extension requires coherent time-controlled access, fixed normalization bounds, and uniform continuity; finer discretization can increase gate costs through $\log r$. Independent concurrent work achieves the same query scaling and similar gate scaling.
GPT 5.6-Sol and later GPT 6-Astra were used to check the manuscript for errors and provided revisions for correctness, clarity, and readability.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 43 pages, no figures. Improved gate complexity