pith. sign in

arxiv: 2509.10425 · v2 · submitted 2025-09-12 · 🪐 quant-ph

Quantum algorithms based on quantum trajectories

Evan Borras , Milad Marvian This is my paper

Pith reviewed 2026-05-18 17:15 UTC · model grok-4.3

classification 🪐 quant-ph
keywords quantum simulationopen quantum systemsLindblad master equationquantum trajectoriesquery complexitydissipative dynamics
0
0 comments X p. Extension

The pith

A quantum algorithm based on trajectories achieves additive query complexity O(T + log(1/ε)) for many dissipative Lindbladians.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs a novel quantum algorithm that uses quantum trajectories to simulate open quantum systems obeying the Lindblad master equation. It reaches a total query complexity that grows as O(T + log(1/ε)), additive in the evolution time and the inverse error, rather than carrying extra polylogarithmic factors. A sympathetic reader would care because this complexity matches the known optimum for closed Hamiltonian simulation and removes a scaling penalty that had separated open-system algorithms from their closed counterparts. The result therefore lowers the cost of simulating realistic noisy dynamics on quantum hardware for a broad family of dissipative generators.

Core claim

We show that the additive complexity of O(T + log(1/ε)) is reachable for the simulation of a large class of dissipative Lindbladians by constructing a novel quantum algorithm based on quantum trajectories.

What carries the argument

Quantum trajectories, which unravel the Lindblad evolution into an ensemble of stochastic pure-state trajectories whose statistics reproduce the master equation without multiplicative overhead in the query model.

If this is right

  • The same additive scaling known for Hamiltonian simulation now extends to a wide family of open-system generators.
  • Long-time or high-precision simulations of dissipative dynamics become feasible with resources linear in T plus a logarithmic correction.
  • The algorithm applies directly to any Lindbladian for which the trajectory unravelling can be realized with additive query cost.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The construction may serve as a template for reaching additive complexity in simulations of other open-system or non-Markovian equations.
  • It could reduce the overhead of embedding realistic noise models into larger quantum algorithms such as error-corrected computation or quantum thermodynamics.
  • Numerical tests on small dissipative systems could quickly verify whether the predicted additive scaling appears in practice.

Load-bearing premise

The Lindbladians belong to a class large enough that sampling trajectories and applying jump operators incur no hidden multiplicative cost in the input-model queries.

What would settle it

An explicit implementation or query-count analysis on a concrete Lindbladian in the stated class that either scales strictly as O(T + log(1/ε)) or exhibits an extra polylog(T/ε) factor.

Figures

Figures reproduced from arXiv: 2509.10425 by Evan Borras, Milad Marvian.

Figure 1
Figure 1. Figure 1: FIG. 1: Implementing CP-maps with block encodings [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2: Trajectory circuit associated with [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
read the original abstract

Quantum simulation has emerged as a key application of quantum computing, with significant progress made in algorithms for simulating both closed and open quantum systems. The simulation of open quantum systems, particularly those governed by the Lindblad master equation, has received attention recently with the current state-of-the-art algorithms having an input model query complexity of $O(T\mathrm{polylog}(T/\epsilon))$, where $T$ and $\epsilon$ are the desired time and precision of the simulation respectively. For the Hamiltonian simulation problem it has been show that the optimal Hamiltonian query complexity is $O(T + \log(1/\epsilon))$, which is additive in the two parameters, but for Lindbladian simulation this question remains open. In this work we show that the additive complexity of $O(T + \log(1/\epsilon))$ is reachable for the simulation of a large class of dissipative Lindbladians by constructing a novel quantum algorithm based on quantum trajectories.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript claims to construct a novel quantum algorithm based on quantum trajectories that achieves additive query complexity O(T + log(1/ε)) for simulating a large class of dissipative Lindbladians, improving on the prior O(T polylog(T/ε)) bound for open-system simulation.

Significance. If the construction succeeds in eliminating multiplicative sampling or jump-handling overheads while preserving correctness for the stated class, the result would close the complexity gap with optimal Hamiltonian simulation and constitute a meaningful advance for quantum algorithms targeting open quantum systems.

major comments (2)
  1. §4 (algorithm construction): the claim of strictly additive complexity requires an explicit argument that the waiting-time distribution and jump-operator applications are realized without Monte-Carlo averaging or precision-dependent sampling; the current sketch leaves open whether a coherent deterministic embedding or a restricted class (e.g., single jump operator with ε-independent norm) is used to avoid the usual 1/ε or polylog(1/ε) factors.
  2. Definition of the Lindbladian class (near Eq. (3) or equivalent): the precise restrictions that keep the class 'large' yet free of hidden multiplicative costs must be stated formally; without them the additivity result cannot be verified to hold beyond specially engineered cases.
minor comments (1)
  1. Notation section: the input oracle model for the Lindbladian (block-encoding or query access to H and L_k) should be aligned with the standard models used in prior open-system simulation literature to facilitate comparison.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback on our manuscript. We address each major comment below with clarifications on the algorithm construction and the Lindbladian class. We will revise the manuscript to incorporate more explicit arguments and formal definitions as suggested.

read point-by-point responses

  1. Referee: §4 (algorithm construction): the claim of strictly additive complexity requires an explicit argument that the waiting-time distribution and jump-operator applications are realized without Monte-Carlo averaging or precision-dependent sampling; the current sketch leaves open whether a coherent deterministic embedding or a restricted class (e.g., single jump operator with ε-independent norm) is used to avoid the usual 1/ε or polylog(1/ε) factors.

    Authors: In Section 4 we realize the quantum trajectory via a coherent deterministic embedding: the waiting-time distribution is implemented by a fixed-norm jump-rate Hamiltonian whose evolution is simulated additively using standard techniques (e.g., qubitization or Trotterization with log(1/ε) overhead only). Jump-operator applications are performed by a controlled unitary whose amplitude encodes the jump probability directly, without Monte-Carlo sampling or ε-dependent repetition. The construction assumes a bounded total jump rate independent of ε, which is part of the class definition. We will add a formal lemma with a complete complexity analysis in the revised Section 4 to remove any ambiguity. revision: yes

  2. Referee: Definition of the Lindbladian class (near Eq. (3) or equivalent): the precise restrictions that keep the class 'large' yet free of hidden multiplicative costs must be stated formally; without them the additivity result cannot be verified to hold beyond specially engineered cases.

    Authors: The class is defined as Lindbladians whose jump operators satisfy ||L_k|| ≤ C for a constant C independent of T and ε, with a fixed number of jump operators, and whose Hamiltonian part admits additive-complexity simulation. This includes standard physical models such as constant-rate amplitude damping or dephasing on multiple qubits. These restrictions ensure that waiting times and jump probabilities introduce no additional 1/ε or polylog(1/ε) factors. We will insert a formal definition (new subsection after Eq. (3)) together with a theorem stating the precise conditions under which the O(T + log(1/ε)) bound holds. revision: yes

Circularity Check

0 steps flagged

No circularity: novel algorithmic construction for additive Lindbladian simulation

full rationale

The paper presents a new quantum algorithm based on quantum trajectories to achieve O(T + log(1/ε)) query complexity for a large class of dissipative Lindbladians. This is framed as an independent construction that reaches the additive bound previously open for Lindbladian simulation, contrasting with the polylog multiplicative overhead in prior work. No load-bearing steps reduce by definition, fitted-parameter renaming, or self-citation chains to the target result itself. The derivation is self-contained against external benchmarks for Hamiltonian simulation optimality and does not invoke unverified uniqueness theorems or ansatzes from overlapping prior work.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result depends on standard quantum query model assumptions plus the restriction to a large but unspecified class of dissipative Lindbladians; no free parameters or invented entities are mentioned in the abstract.

axioms (1)
  • domain assumption The input model for the Lindbladian allows efficient access to the jump operators and Hamiltonian such that quantum trajectories can be sampled with additive overhead.
    The complexity claim is stated only for a large class of dissipative Lindbladians.

pith-pipeline@v0.9.0 · 5683 in / 1144 out tokens · 40411 ms · 2026-05-18T17:15:28.805647+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

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

  1. Nonnormality and Dissipation in Markovian Quantum Dynamics: Implications for Quantum Simulation

    quant-ph 2026-04 unverdicted novelty 7.0

    Nonnormality is an intrinsically dissipative property of Lindbladian generators that controls transient growth in open quantum dynamics and increases the cost of quantum simulations.

Reference graph

Works this paper leans on

45 extracted references · 45 canonical work pages · cited by 1 Pith paper · 3 internal anchors

  1. [1]

    R. P. Feynman, International Journal of Theoretical Physics21, 467 (1982)

    work page 1982

  2. [2]

    D. W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders, Communications in Mathematical Physics270, 359 (2007)

    work page 2007

  3. [3]

    D. W. Berry, R. Cleve, and S. Gharibian, Gate-efficient discrete simulations of continuous-time quantum query algorithms (2013), arXiv:1211.4637

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  4. [4]

    D. W. Berry, A. M. Childs, Childs, R. Cleve, R. Kothari, and R. D. Somma, inProceedings of the forty-sixth annual ACM symposium on Theory of computing(ACM, 2014)

    work page 2014

  5. [5]

    D. W. Berry, A. M. Childs, and R. Kothari, in2015 IEEE 56th Annual Symposium on Foundations of Computer Science (2015) pp. 792–809

    work page 2015

  6. [6]

    D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, Phys. Rev. Lett.114, 090502 (2015)

    work page 2015

  7. [7]

    Campbell, Phys

    E. Campbell, Phys. Rev. Lett.123, 070503 (2019)

    work page 2019

  8. [8]

    A. M. Childs, A. Ostrander, and Y. Su, Quantum3, 182 (2019)

    work page 2019

  9. [9]

    A. M. Childs, Y. Su, M. C. Tran, N. Wiebe, and S. Zhu, Phys. Rev. X11, 011020 (2021)

    work page 2021

  10. [10]

    Lloyd, Science273, 1073 (1996)

    S. Lloyd, Science273, 1073 (1996)

    work page 1996

  11. [11]

    G. H. Low and I. L. Chuang, Phys. Rev. Lett.118, 010501 (2017)

    work page 2017

  12. [12]

    G. H. Low and I. L. Chuang, Quantum3, 163 (2019)

    work page 2019

  13. [13]

    Nakaji, M

    K. Nakaji, M. Bagherimehrab, and A. Aspuru-Guzik, PRX Quantum5, 020330 (2024)

    work page 2024

  14. [14]

    Poulin, A

    D. Poulin, A. Qarry, R. Somma, and F. Verstraete, Phys. Rev. Lett.106, 170501 (2011)

    work page 2011

  15. [15]

    G. D. Bartolomeo, M. Vischi, T. Feri, A. Bassi, and S. Donadi, Efficient quantum algorithm to simulate open systems through the quantum noise formalism (2023), arXiv:2311.10009

    work page arXiv 2023

  16. [16]

    H. Chen, B. Li, J. Lu, and L. Ying, A randomized method for simulating lindblad equations and thermal state preparation (2024), arXiv:2407.06594 [quant-ph]

    work page arXiv 2024

  17. [17]

    A. M. Childs and T. Li, Quantum Info. Comput.17, 901–947 (2017)

    work page 2017

  18. [18]

    Efficient Quantum Algorithms for Simulating Lindblad Evolution

    R. Cleve and C. Wang, Efficient quantum algorithms for simulating lindblad evolution (2019), arXiv:1612.09512

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  19. [19]

    I. J. David, I. Sinayskiy, and F. Petruccione, Faster quantum simulation of markovian open quantum systems via randomi- sation (2024), arXiv:2408.11683 [quant-ph]

    work page arXiv 2024

  20. [20]

    J. D. Guimar˜ aes, J. Lim, M. I. Vasilevskiy, S. F. Huelga, and M. B. Plenio, PRX Quantum4, 040329 (2023)

    work page 2023

  21. [21]

    J. D. Guimar˜ aes, A. Ruiz-Molero, J. Lim, M. I. Vasilevskiy, S. F. Huelga, and M. B. Plenio, Phys. Rev. A109, 052224 (2024)

    work page 2024

  22. [22]

    Z. Hu, R. Xia, and S. Kais, Scientific Reports10, 3301 (2020)

    work page 2020

  23. [23]

    Joo and T

    J. Joo and T. P. Spiller, New Journal of Physics25, 083041 (2023)

    work page 2023

  24. [24]

    Kliesch, T

    M. Kliesch, T. Barthel, C. Gogolin, M. Kastoryano, and J. Eisert, Phys. Rev. Lett.107, 120501 (2011)

    work page 2011

  25. [25]

    Li and C

    X. Li and C. Wang, Simulating markovian open quantum systems using higher-order series expansion (2023), arXiv:2212.02051

    work page arXiv 2023

  26. [26]

    Li and C

    X. Li and C. Wang, Communications in Mathematical Physics401, 147–183 (2023)

    work page 2023

  27. [27]

    H.-Y. Liu, X. Lin, Z.-Y. Chen, C. Xue, T.-P. Sun, Q.-S. Li, X.-N. Zhuang, Y.-J. Wang, Y.-C. Wu, M. Gong, and G.-P. Guo, Simulation of open quantum systems on universal quantum computers (2024), arXiv:2405.20712

    work page arXiv 2024

  28. [28]

    S. Peng, X. Sun, Q. Zhao, and H. Zhou, Quantum-trajectory-inspired lindbladian simulation (2024), arXiv:2408.10505 [quant-ph]

    work page arXiv 2024

  29. [29]

    A. W. Schlimgen, K. Head-Marsden, L. M. Sager, P. Narang, and D. A. Mazziotti, Phys. Rev. Lett.127, 270503 (2021)

    work page 2021

  30. [30]

    A. W. Schlimgen, K. Head-Marsden, L. M. Sager, P. Narang, and D. A. Mazziotti, Phys. Rev. Res.4, 023216 (2022)

    work page 2022

  31. [31]

    A. W. Schlimgen, K. Head-Marsden, L. M. Sager-Smith, P. Narang, and D. A. Mazziotti, Phys. Rev. A106, 022414 (2022)

    work page 2022

  32. [32]

    N. Suri, J. Barreto, S. Hadfield, N. Wiebe, F. Wudarski, and J. Marshall, Quantum7, 1002 (2023)

    work page 2023

  33. [33]

    Pocrnic, D

    M. Pocrnic, D. Segal, and N. Wiebe, Quantum simulation of lindbladian dynamics via repeated interactions (2024), arXiv:2312.05371 [quant-ph]

    work page arXiv 2024

  34. [34]

    Verstraete, M

    F. Verstraete, M. M. Wolf, and J. Ignacio Cirac, Nature Physics5, 633 (2009)

    work page 2009

  35. [35]

    Z. Ding, M. Junge, P. Schleich, and P. Wu, Lower bound for simulation cost of open quantum systems: Lipschitz continuity approach (2024), arXiv:2407.15357 [quant-ph]

    work page arXiv 2024

  36. [36]

    Breuer and F

    H.-P. Breuer and F. Petruccione,The Theory of Open Quantum Systems(Oxford University Press, 2007)

    work page 2007

  37. [37]

    Watrous, Basic notions of quantum information, inThe Theory of Quantum Information(Cambridge University Press,

    J. Watrous, Basic notions of quantum information, inThe Theory of Quantum Information(Cambridge University Press,

    work page

  38. [38]

    M. A. Nielsen and I. L. Chuang,Quantum Computation and Quantum Information: 10th Anniversary Edition(Cambridge University Press, 2010)

    work page 2010

  39. [39]

    C.-F. Chen, M. J. Kastoryano, F. G. S. L. Brand˜ ao, and A. Gily´ en, Quantum thermal state preparation (2023), arXiv:2303.18224

    work page internal anchor Pith review arXiv 2023

  40. [40]

    C.-F. Chen, M. J. Kastoryano, and A. Gily´ en, An efficient and exact noncommutative quantum gibbs sampler (2023), arXiv:2311.09207 [quant-ph]

    work page arXiv 2023

  41. [41]

    S. Ohta, M. Nakano, R. Kishi, H. Takahashi, and S. Furukawa, Chemical Physics Letters419, 70 (2006). 18

    work page 2006

  42. [42]

    vom Ende, Open Systems & Information Dynamics30, 2350003 (2023), https://doi.org/10.1142/S1230161223500038

    F. vom Ende, Open Systems & Information Dynamics30, 2350003 (2023), https://doi.org/10.1142/S1230161223500038

    work page doi:10.1142/s1230161223500038 2023

  43. [43]

    Gily´ en, Y

    A. Gily´ en, Y. Su, G. H. Low, and N. Wiebe, inProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC ’19 (ACM, 2019)

    work page 2019

  44. [44]

    Mitzenmacher and E

    M. Mitzenmacher and E. Upfal, Balls, bins, and random graphs, inProbability and Computing: Randomized Algorithms and Probabilistic Analysis(Cambridge University Press, 2005) p. 90–125

    work page 2005

  45. [45]

    Shang, D

    Z.-X. Shang, D. An, and C. Shao, Exponential lindbladian fast forwarding and exponential amplification of certain gibbs state properties (2025), arXiv:2509.09517 [quant-ph]. 19 Appendix A In this section we provide an alternative way to characterize the set of Lindbladians for which our algorithm can be applied to. As discussed in the main text our algori...

    work page arXiv 2025