Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1612.09512 · Leibniz international proceedings in informatics

Efficient Quantum Algorithms for Simulating Lindblad Evolution

Richard Cleve, Chunhao Wang

Published Dec 30, 2016• 137 citations
arXivHTMLPDF

Abstract

We consider the natural generalization of the Schrödinger equation to Markovian open system dynamics: the so-called the Lindblad equation. We give a quantum algorithm for simulating the evolution of an $n$-qubit system for time $t$ within precision $ε$. If the Lindbladian consists of $\mathrm{poly}(n)$ operators that can each be expressed as a linear combination of $\mathrm{poly}(n)$ tensor products of Pauli operators then the gate cost of our algorithm is $O(t\, \mathrm{polylog}(t/ε)\mathrm{poly}(n))$. We also obtain similar bounds for the cases where the Lindbladian consists of local operators, and where the Lindbladian consists of sparse operators. This is remarkable in light of evidence that we provide indicating that the above efficiency is impossible to attain by first expressing Lindblad evolution as Schrödinger evolution on a larger system and tracing out the ancillary system: the cost of such a \textit{reduction} incurs an efficiency overhead of $O(t^2/ε)$ even before the Hamiltonian evolution simulation begins. Instead, the approach of our algorithm is to use a novel variation of the "linear combinations of unitaries" construction that pertains to channels.

DOI
10.4230/lipics.icalp.2017.17

Related papers

Efficient simulation of sparse Markovian quantum dynamics

Andrew M. Childs, Tongyang Li

Quantum algorithms for simulating Hamiltonian dynamics have been extensively developed, but there has been much less work on quantum algorithms for simulating the dynamics of open quantum systems. We give the first efficient quantum algorithms for simulating Markovian quantum dynamics generated by Lindbladians that are not necessarily local. We introduce two approaches to simulating sparse Lindbladians. First, we show how to simulate Lindbladians that act within small invariant subspaces using a quantum algorithm to implement sparse Stinespring isometries. Second, we develop a method for simulating sparse Lindblad operators by concatenating a sequence of short-time evolutions. We also show limitations on Lindbladian simulation by proving a no–fast-forwarding theorem for simulating sparse Lindbladians in black-box models.

arXiv:1611.05543•Quantum Information and Computation•Sep 1, 2017•70 citations

Learning Arbitrary Lindbladians from Time Evolution

Zhili Chen, Zhan Yu

We study the problem of learning arbitrary $n$-qubit Lindbladians, the generators of Markovian open-system dynamics, from their time evolution. We give the first known efficient algorithm that learns arbitrary Lindbladians without any structural assumptions. For an $n$-qubit Lindbladian of dynamical strength at most $Λ$, the algorithm estimates every coefficient to error $\varepsilon$ using $\widetilde O(Λ^2/\varepsilon^2)$ experiments and $\widetilde O(Λ/\varepsilon^2)$ total evolution time, with classical running time polynomial in $n$ and $Λ/\varepsilon$. Both experimental costs match known lower bounds up to polylogarithmic factors. The algorithm identifies candidate labels through product Pauli experiments and estimates their coefficients using random stabilizer preparations and Clifford measurements. It requires no ancillas or control during the unknown evolution. For constant $k$, our algorithm learns generic $k$-local Lindbladians of local dynamical strength at most $Λ_{\mathrm{loc}}$ using $\widetilde O(n^2Λ_{\mathrm{loc}}^2/\varepsilon^2)$ experiments and $\widetilde O(nΛ_{\mathrm{loc}}/\varepsilon^2)$ total evolution time, improving the upper bounds of prior works in terms of the dependence on $n$. We further improve the lower bounds of Arad, Chen, Guo, Rebentrost, and Yu (SODA 2027) using a family of $3$-local Lindbladians. They already hold when the support is known, and only one Hamiltonian coefficient is requested, even for adaptive protocols with arbitrary ancillas and quantum memory. These lower bounds establish that our algorithm is optimal up to polylogarithmic factors in both experiment count and total evolution time for every fixed $k \geq 3$.

quant-pharXiv:2607.28610•Jul 31, 2026•5 citations

Quantum-Trajectory-Inspired Lindbladian Simulation

Sirui Peng, Xiaoming Sun, Qi Zhao +1 more

Simulating the dynamics of open quantum systems is a crucial task in quantum computing, offering wide-ranging applications but remaining computationally challenging. In this paper, we propose two quantum algorithms for simulating the dynamics of open quantum systems governed by Lindbladians. We introduce a new approximation channel for short-time evolution, inspired by the quantum trajectory method, which underpins the efficiency of our algorithms. The first algorithm achieves a gate complexity independent of the number of jump operators, m , marking a significant improvement in efficiency. The second algorithm achieves near-optimal dependence on the evolution time t and precision ϵ and introduces only an additional O ~ ( m ) factor, which strictly improves upon state-of-the-art gate-based quantum algorithm that has an O ~ ( m 2 ) factor. The improvement stems from the integration of the new approximation channel with a novel structured linear combination of unitaries method. In both our algorithms, the reduction of dependence on m significantly enhances the efficiency of simulating practical dissipative processes characterized by a large number of jump operators.

arXiv:2408.10505•PRX Quantum•Aug 15, 2025•14 citations

Query-optimal quantum simulation of Lindblad evolution

Chunhao Wang, Christopher Ye

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.

quant-pharXiv:2609.17490•Sep 16, 2026•10 citations

Wave Matrix Lindbladization II: General Lindbladians, Linear Combinations, and Polynomials

Dhrumil Patel, Mark M. Wilde

In this paper, we investigate the problem of simulating open system dynamics governed by the well-known Lindblad master equation. In our prequel paper [Patel and Wilde, Open Sys. & Info. Dyn., 30:2350010 (2023)], we introduced an input model in which Lindblad operators are encoded into pure quantum states, called program states, and we also introduced a method, called wave matrix Lindbladization, for simulating Lindbladian evolution by means of interacting the system of interest with these program states. Therein, we focused on a simple case in which the Lindbladian consists of only one Lindblad operator and a Hamiltonian. Here, we extend the method to simulating general Lindbladians and other cases in which a Lindblad operator is expressed as a linear combination or a polynomial of the operators encoded into the program states. We propose quantum algorithms for all these cases and also investigate their sample complexity, i.e., the number of program states needed to simulate a given Lindbladian evolution approximately. Finally, we demonstrate that our quantum algorithms provide an efficient route for simulating Lindbladian evolution relative to full tomography of encoded operators, by proving that the sample complexity for tomography is dependent on the dimension of the system, whereas the sample complexity of wave matrix Lindbladization is dimension independent.

arXiv:2309.14453•Open Systems & Information Dynamics•Sep 1, 2023•18 citations

Query-Optimal and Gate-Efficient Lindbladian Simulation

Boyang Chen, Minbo Gao, Xinzhao Wang +1 more

We give a quantum algorithm for Lindbladian simulation given a block encoding of the Hamiltonian $H$ and a projected unitary encoding of the stacked jump operator $B=\sum_{k=1}^m \lvert k\rangle\otimes L_k$, with normalization factors $α_H$ and $α_B$, respectively. For evolution time $t$, set $τ=(α_H+α_B^2)t$. The algorithm approximates the evolution channel to diamond-norm error $\varepsilon$ using $O\!\left(τ+\frac{\log(1/\varepsilon)}{\log\!\left(e+\log(1/\varepsilon)/τ\right)}\right)$ oracle queries, matching the query lower bound for Hamiltonian simulation. The number of additional one- and two-qubit gates is linear in the query complexity up to polylogarithmic factors. The query- and gate-complexity bounds extend to Lipschitz-continuous time-dependent Lindbladians under coherent time-indexed oracle access. Our construction uses a one-query transducer that implements a product of rational approximations to short-time evolution when supplied with a catalyst. We bound the error from omitting the catalyst by exploiting orthogonality between different sequences of Kraus labels. The gate implementation combines a compressed Kraus-label representation, which stores only the positions and values of the nonzero labels, with the rotation factorization of Chen et al.

quant-pharXiv:2609.18757•Sep 17, 2026•9 citations
We consider the natural generalization of the Schrödinger equation to Markovian open system dynamics: the so-called the Lindblad equation. We give a quantum algorithm for simulating the evolution of an nnn-qubit system for time ttt within precision εεε. If the Lindbladian consists of poly(n)\mathrm{poly}(n)poly(n) operators that can each be expressed as a linear combination of poly(n)\mathrm{poly}(n)poly(n) tensor products of Pauli operators then the gate cost of our algorithm is O(t polylog(t/ε)poly(n))O(t\, \mathrm{polylog}(t/ε)\mathrm{poly}(n))O(tpolylog(t/ε)poly(n)). We also obtain similar bounds for the cases where the Lindbladian consists of local operators, and where the Lindbladian consists of sparse operators. This is remarkable in light of evidence that we provide indicating that the above efficiency is impossible to attain by first expressing Lindblad evolution as Schrödinger evolution on a larger system and tracing out the ancillary system: the cost of such a \textit{reduction} incurs an efficiency overhead of O(t2/ε)O(t^2/ε)O(t2/ε) even before the Hamiltonian evolution simulation begins. Instead, the approach of our algorithm is to use a novel variation of the "linear combinations of unitaries" construction that pertains to channels.
Quantum algorithms for simulating Hamiltonian dynamics have been extensively developed, but there has been much less work on quantum algorithms for simulating the dynamics of open quantum systems. We give the first efficient quantum algorithms for simulating Markovian quantum dynamics generated by Lindbladians that are not necessarily local. We introduce two approaches to simulating sparse Lindbladians. First, we show how to simulate Lindbladians that act within small invariant subspaces using a quantum algorithm to implement sparse Stinespring isometries. Second, we develop a method for simulating sparse Lindblad operators by concatenating a sequence of short-time evolutions. We also show limitations on Lindbladian simulation by proving a no–fast-forwarding theorem for simulating sparse Lindbladians in black-box models.
We study the problem of learning arbitrary nnn-qubit Lindbladians, the generators of Markovian open-system dynamics, from their time evolution. We give the first known efficient algorithm that learns arbitrary Lindbladians without any structural assumptions. For an nnn-qubit Lindbladian of dynamical strength at most ΛΛΛ, the algorithm estimates every coefficient to error ε\varepsilonε using O~(Λ2/ε2)\widetilde O(Λ^2/\varepsilon^2)O(Λ2/ε2) experiments and O~(Λ/ε2)\widetilde O(Λ/\varepsilon^2)O(Λ/ε2) total evolution time, with classical running time polynomial in nnn and Λ/εΛ/\varepsilonΛ/ε. Both experimental costs match known lower bounds up to polylogarithmic factors. The algorithm identifies candidate labels through product Pauli experiments and estimates their coefficients using random stabilizer preparations and Clifford measurements. It requires no ancillas or control during the unknown evolution. For constant kkk, our algorithm learns generic kkk-local Lindbladians of local dynamical strength at most ΛlocΛ_{\mathrm{loc}}Λloc​ using O~(n2Λloc2/ε2)\widetilde O(n^2Λ_{\mathrm{loc}}^2/\varepsilon^2)O(n2Λloc2​/ε2) experiments and O~(nΛloc/ε2)\widetilde O(nΛ_{\mathrm{loc}}/\varepsilon^2)O(nΛloc​/ε2) total evolution time, improving the upper bounds of prior works in terms of the dependence on nnn. We further improve the lower bounds of Arad, Chen, Guo, Rebentrost, and Yu (SODA 2027) using a family of 333-local Lindbladians. They already hold when the support is known, and only one Hamiltonian coefficient is requested, even for adaptive protocols with arbitrary ancillas and quantum memory. These lower bounds establish that our algorithm is optimal up to polylogarithmic factors in both experiment count and total evolution time for every fixed k≥3k \geq 3k≥3.
Simulating the dynamics of open quantum systems is a crucial task in quantum computing, offering wide-ranging applications but remaining computationally challenging. In this paper, we propose two quantum algorithms for simulating the dynamics of open quantum systems governed by Lindbladians. We introduce a new approximation channel for short-time evolution, inspired by the quantum trajectory method, which underpins the efficiency of our algorithms. The first algorithm achieves a gate complexity independent of the number of jump operators, m , marking a significant improvement in efficiency. The second algorithm achieves near-optimal dependence on the evolution time t and precision ϵ and introduces only an additional O ~ ( m ) factor, which strictly improves upon state-of-the-art gate-based quantum algorithm that has an O ~ ( m 2 ) factor. The improvement stems from the integration of the new approximation channel with a novel structured linear combination of unitaries method. In both our algorithms, the reduction of dependence on m significantly enhances the efficiency of simulating practical dissipative processes characterized by a large number of jump operators.
For the problem of simulating Lindblad evolution for time ttt to precision εεε, Hamiltonian simulation provides an additive query lower bound, informally, Ω(t+polylog(1/ε))Ω(t + \mathrm{polylog}(1/ε))Ω(t+polylog(1/ε)). However, the best previously known algorithms for general Lindblad simulation achieve a multiplicative upper bound, informally, O(t polylog(1/ε))\mathcal{O}(t\,\mathrm{polylog}(1/ε))O(tpolylog(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.
In this paper, we investigate the problem of simulating open system dynamics governed by the well-known Lindblad master equation. In our prequel paper [Patel and Wilde, Open Sys. & Info. Dyn., 30:2350010 (2023)], we introduced an input model in which Lindblad operators are encoded into pure quantum states, called program states, and we also introduced a method, called wave matrix Lindbladization, for simulating Lindbladian evolution by means of interacting the system of interest with these program states. Therein, we focused on a simple case in which the Lindbladian consists of only one Lindblad operator and a Hamiltonian. Here, we extend the method to simulating general Lindbladians and other cases in which a Lindblad operator is expressed as a linear combination or a polynomial of the operators encoded into the program states. We propose quantum algorithms for all these cases and also investigate their sample complexity, i.e., the number of program states needed to simulate a given Lindbladian evolution approximately. Finally, we demonstrate that our quantum algorithms provide an efficient route for simulating Lindbladian evolution relative to full tomography of encoded operators, by proving that the sample complexity for tomography is dependent on the dimension of the system, whereas the sample complexity of wave matrix Lindbladization is dimension independent.
We give a quantum algorithm for Lindbladian simulation given a block encoding of the Hamiltonian HHH and a projected unitary encoding of the stacked jump operator B=∑k=1m∣k⟩⊗LkB=\sum_{k=1}^m \lvert k\rangle\otimes L_kB=∑k=1m​∣k⟩⊗Lk​, with normalization factors αHα_HαH​ and αBα_BαB​, respectively. For evolution time ttt, set τ=(αH+αB2)tτ=(α_H+α_B^2)tτ=(αH​+αB2​)t. The algorithm approximates the evolution channel to diamond-norm error ε\varepsilonε using O ⁣(τ+log⁡(1/ε)log⁡ ⁣(e+log⁡(1/ε)/τ))O\!\left(τ+\frac{\log(1/\varepsilon)}{\log\!\left(e+\log(1/\varepsilon)/τ\right)}\right)O(τ+log(e+log(1/ε)/τ)log(1/ε)​) oracle queries, matching the query lower bound for Hamiltonian simulation. The number of additional one- and two-qubit gates is linear in the query complexity up to polylogarithmic factors. The query- and gate-complexity bounds extend to Lipschitz-continuous time-dependent Lindbladians under coherent time-indexed oracle access. Our construction uses a one-query transducer that implements a product of rational approximations to short-time evolution when supplied with a catalyst. We bound the error from omitting the catalyst by exploiting orthogonality between different sequences of Kraus labels. The gate implementation combines a compressed Kraus-label representation, which stores only the positions and values of the nonzero labels, with the rotation factorization of Chen et al.