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:2509.09517 · Reports on Progress in Physics

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

Zhong-Xia Shang, Dong An, Changpeng Shao

Published May 1, 2026• 1 citation
arXivHTMLPDF

Abstract

We investigate Lindbladian fast-forwarding and its applications to estimating Gibbs state properties. Fast-forwarding refers to the ability to simulate a system of timetusing significantly fewer thantqueries 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 complexityO(t+log⁡(ε-1))up to errorε, 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 depthO(log⁡(t+log⁡(ε-1))), 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⟨ψ1|e-β(H+I)|ψ2⟩, up to additive errorϵ, withHthe Hamiltonian andβthe inverse temperature. For input states exhibiting certain coherence conditions-e.g.⟨0|⊗ne-β(H+I)|+⟩⊗n-our method achieves exponential improvement in complexity (measured by circuit depth),O(2-n/2ϵ-1log⁡β),compared to the quantum singular value transformation-based approach, with complexityO~(ϵ-1β). We show how to apply this exponential improvement to applications such as the ground state overlap testing and amplitude estimation. For general|ψ1⟩and|ψ2⟩, we also show how the level of improvement is changed with the coherence resource in|ψ1⟩and|ψ2⟩.

DOI
10.1088/1361-6633/ae6df7

Related papers

Fast-forwarding quantum algorithms for linear dissipative differential equations

Dong Un An, Akwum Onwunta, Gengzhi Yang

We establish improved complexity estimates of quantum algorithms for linear dissipative ordinary differential equations (ODEs) and show that the time dependence can be fast-forwarded to be sub-linear. Specifically, we show that a quantum algorithm based on truncated Dyson series can prepare history states of dissipative ODEs up to time T with cost O ~ ( log ⁡ ( T ) ( log ⁡ ( 1 / ϵ ) ) 2 ) , which is an exponential speedup over the best previous result. For final state preparation at time T , we show that its complexity is O ~ ( T ( log ⁡ ( 1 / ϵ ) ) 2 ) , achieving a polynomial speedup in T . We also analyze the complexity of simpler lower-order quantum algorithms, such as the forward Euler method and the trapezoidal rule, and find that even lower-order methods can still achieve O ~ ( T ) cost with respect to time T for preparing final states of dissipative ODEs. As applications, we show that quantum algorithms can simulate dissipative non-Hermitian quantum dynamics and heat processes with fast-forwarded complexity sub-linear in time.

arXiv:2410.13189•Quantum•Jan 27, 2026•0 citations

Fast-forwardable Lindbladians imply quantum phase estimation

Zhong-Xia Shang, Naixu Guo, Patrick Rebentrost +3 more

Quantum phase estimation (QPE) and Lindbladian dynamics are both foundational in quantum information science and central to quantum algorithm design. In this work, we bridge these two concepts: certain simple Lindbladian processes can be adapted to perform QPE-type tasks. However, unlike QPE, which achieves Heisenberg-limit scaling, these Lindbladian evolutions are restricted to standard quantum limit complexity. This indicates that, different from Hamiltonian dynamics, the natural dissipative evolution speed of such Lindbladians does not saturate the fundamental quantum limit, thereby suggesting the potential for quadratic fast-forwarding. We confirm this by presenting a quantum algorithm that simulates these Lindbladians for time $t$ within an error $\varepsilon$ using $\mathcal{O}\left(\sqrt{t\log(\varepsilon^{-1})}\right)$ cost, whose mechanism is fundamentally different from the fast-forwarding examples of Hamiltonian dynamics. As a bonus, this fast-forwarded simulation naturally serves as a new Heisenberg-limit QPE algorithm. Therefore, our work explicitly bridges the standard quantum limit-Heisenberg limit transition to the fast-forwarding of dissipative dynamics. We also adopt our fast-forwarding algorithm for efficient Gibbs state preparation and demonstrate the counter-intuitive implication: the allowance of a quadratically accelerated decoherence effect under arbitrary Pauli noise.

arXiv:2510.06759•Oct 8, 2025•0 citations

Parallelizing Dissipative Quantum Algorithms

Sudatta Hor, Nathan Wiebe, Yongshan Ding

Inspired by classical Markov Chain Monte Carlo (MCMC) methods, dissipative quantum algorithms are an emerging class of methods for preparing quantum states on a quantum computer. They operate by simulating a dissipative process governed by a mathematical operator known as the Lindbladian. The performance of these algorithms can be limited by the sequential implementation of the Lindbladian's constituent jump operators, which leads to high circuit depth. To address this issue, this work analyzes a parallelization scheme to implement jump operators simultaneously. We leverage the structure of geometric locality to show that individual jump operators remain spatially localized. This exponentially reduces the circuit depth per time step, resulting in an overall polynomial improvement. Numerical experiments demonstrate a 53x reduction in query depth for a 1D benchmark system of 100 qubits. The reduced circuit depth makes dissipative algorithms more practical for near-term quantum computing.

quant-pharXiv:2610.04176•Oct 6, 2026•0 citations

Fast-forwarding quantum evolution

Shouzhen Gu, Rolando D. Somma, Burak Şahinoğlu

We investigate the problem of fast-forwarding quantum evolution, whereby the dynamics of certain quantum systems can be simulated with gate complexity that is sublinear in the evolution time. We provide a definition of fast-forwarding that considers the model of quantum computation, the Hamiltonians that induce the evolution, and the properties of the initial states. Our definition accounts for any asymptotic complexity improvement of the general case and we use it to demonstrate fast-forwarding in several quantum systems. In particular, we show that some local spin systems whose Hamiltonians can be taken into block diagonal form using an efficient quantum circuit, such as those that are permutation-invariant, can be exponentially fast-forwarded. We also show that certain classes of positive semidefinite local spin systems, also known as frustration-free, can be polynomially fast-forwarded, provided the initial state is supported on a subspace of sufficiently low energies. Last, we show that all quadratic fermionic systems and number-conserving quadratic bosonic systems can be exponentially fast-forwarded in a model where quantum gates are exponentials of specific fermionic or bosonic operators, respectively. Our results extend the classes of physical Hamiltonians that were previously known to be fast-forwarded, while not necessarily requiring methods that diagonalize the Hamiltonians efficiently. We further develop a connection between fast-forwarding and precise energy measurements that also accounts for polynomial improvements.

arXiv:2105.07304•Quantum•Nov 15, 2021•45 citations

Exponential improvement in precision for simulating sparse Hamiltonians

Dominic William Berry, Andrew M. Childs, Richard Cleve +2 more

We provide a quantum algorithm for simulating the dynamics of sparse Hamiltonians with complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Specifically, we show that a d-sparse Hamiltonian H on n qubits can be simulated for time t with precision ε using O(τlog(τ/ε)/log log(τ/ε)) queries and O(τnlog2(τ/ε)/log log(τ/ε)) additional 2-qubit gates, where τ=d2||H||maxt. Unlike previous approaches based on product formulas, the query complexity is independent of the number of qubits acted on, and for time-varying Hamiltonians, the gate complexity is logarithmic in the norm of the derivative of the Hamiltonian. Our algorithm is based on a significantly improved simulation of the continuous- and fractional-query models using discrete quantum queries, showing that the former models are not much more powerful than the discrete model even for very small error. We also significantly simplify the analysis of this conversion, avoiding the need for a complex fault correction procedure. Our simplification relies on a new form of "oblivious amplitude amplification" that can be applied even though the reflection about the input state is unavailable. Finally, we prove new lower bounds showing that our algorithms are optimal as a function of the error.

arXiv:1312.1414•ACM Symposium on Theory of Computing (STOC)•May 31, 2014•324 citations

Lattice Lindbladian simulation by patching and merging

Kaoru Mizuta

Simulating the dynamics of dissipative quantum many-body systems governed by local Lindbladians is a fundamental task in quantum computation. While the near-optimal gate count has been achieved for Hamiltonian simulation, comparable results for Lindbladian simulation remain elusive. In this work, we develop quantum algorithms for lattice Lindbladians by exploiting their locality. First, we consider sparsely dissipative systems, in which the dissipation is sparsely located, including boundary-driven systems. We establish a near-optimal quantum algorithm for their dynamics with gate count $O(Nt \, \mathrm{polylog}(Nt/\varepsilon))$, where $N$ is the system size, $t$ is the evolution time, and $\varepsilon$ is the allowable error. We then consider generic lattice Lindbladians with finite-range interactions and dissipation, and develop an algorithm for simulating time-evolved observables with gate count $O((Nt)^{4/3} \, \mathrm{polylog}(Nt/\varepsilon))$ per sample with the sampling complexity $Θ(\varepsilon^{-2})$. The gate count has the smallest known dependence on the system size among algorithms retaining polylogarithmic dependence on $1/\varepsilon$. Our algorithms are based on two techniques that exploit locality: patching and merging. Patching decomposes dissipative dynamics into dynamics on subsystems with exponentially small error, generalizing a key idea underlying the Haah-Hastings-Kothari-Low algorithm for near-optimal Hamiltonian simulation. Merging absorbs reversed dissipative dynamics into other parts of the evolution, substantially reducing the overhead associated with quasi-probabilistic sampling. These results demonstrate that locality can be fully exploited to achieve fast quantum simulation of dissipative many-body dynamics, opening the way to applications such as predicting nonequilibrium phenomena and preparing desirable quantum states.

quant-pharXiv:2609.26372•Sep 23, 2026•0 citations
We investigate Lindbladian fast-forwarding and its applications to estimating Gibbs state properties. Fast-forwarding refers to the ability to simulate a system of timetusing significantly fewer thantqueries 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 complexityO(t+log⁡(ε-1))up to errorε, 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 depthO(log⁡(t+log⁡(ε-1))), 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⟨ψ1|e-β(H+I)|ψ2⟩, up to additive errorϵ, withHthe Hamiltonian andβthe inverse temperature. For input states exhibiting certain coherence conditions-e.g.⟨0|⊗ne-β(H+I)|+⟩⊗n-our method achieves exponential improvement in complexity (measured by circuit depth),O(2-n/2ϵ-1log⁡β),compared to the quantum singular value transformation-based approach, with complexityO~(ϵ-1β). We show how to apply this exponential improvement to applications such as the ground state overlap testing and amplitude estimation. For general|ψ1⟩and|ψ2⟩, we also show how the level of improvement is changed with the coherence resource in|ψ1⟩and|ψ2⟩.
We establish improved complexity estimates of quantum algorithms for linear dissipative ordinary differential equations (ODEs) and show that the time dependence can be fast-forwarded to be sub-linear. Specifically, we show that a quantum algorithm based on truncated Dyson series can prepare history states of dissipative ODEs up to time T with cost O ~ ( log ⁡ ( T ) ( log ⁡ ( 1 / ϵ ) ) 2 ) , which is an exponential speedup over the best previous result. For final state preparation at time T , we show that its complexity is O ~ ( T ( log ⁡ ( 1 / ϵ ) ) 2 ) , achieving a polynomial speedup in T . We also analyze the complexity of simpler lower-order quantum algorithms, such as the forward Euler method and the trapezoidal rule, and find that even lower-order methods can still achieve O ~ ( T ) cost with respect to time T for preparing final states of dissipative ODEs. As applications, we show that quantum algorithms can simulate dissipative non-Hermitian quantum dynamics and heat processes with fast-forwarded complexity sub-linear in time.
Quantum phase estimation (QPE) and Lindbladian dynamics are both foundational in quantum information science and central to quantum algorithm design. In this work, we bridge these two concepts: certain simple Lindbladian processes can be adapted to perform QPE-type tasks. However, unlike QPE, which achieves Heisenberg-limit scaling, these Lindbladian evolutions are restricted to standard quantum limit complexity. This indicates that, different from Hamiltonian dynamics, the natural dissipative evolution speed of such Lindbladians does not saturate the fundamental quantum limit, thereby suggesting the potential for quadratic fast-forwarding. We confirm this by presenting a quantum algorithm that simulates these Lindbladians for time ttt within an error ε\varepsilonε using O(tlog⁡(ε−1))\mathcal{O}\left(\sqrt{t\log(\varepsilon^{-1})}\right)O(tlog(ε−1)​) cost, whose mechanism is fundamentally different from the fast-forwarding examples of Hamiltonian dynamics. As a bonus, this fast-forwarded simulation naturally serves as a new Heisenberg-limit QPE algorithm. Therefore, our work explicitly bridges the standard quantum limit-Heisenberg limit transition to the fast-forwarding of dissipative dynamics. We also adopt our fast-forwarding algorithm for efficient Gibbs state preparation and demonstrate the counter-intuitive implication: the allowance of a quadratically accelerated decoherence effect under arbitrary Pauli noise.
Inspired by classical Markov Chain Monte Carlo (MCMC) methods, dissipative quantum algorithms are an emerging class of methods for preparing quantum states on a quantum computer. They operate by simulating a dissipative process governed by a mathematical operator known as the Lindbladian. The performance of these algorithms can be limited by the sequential implementation of the Lindbladian's constituent jump operators, which leads to high circuit depth. To address this issue, this work analyzes a parallelization scheme to implement jump operators simultaneously. We leverage the structure of geometric locality to show that individual jump operators remain spatially localized. This exponentially reduces the circuit depth per time step, resulting in an overall polynomial improvement. Numerical experiments demonstrate a 53x reduction in query depth for a 1D benchmark system of 100 qubits. The reduced circuit depth makes dissipative algorithms more practical for near-term quantum computing.
We investigate the problem of fast-forwarding quantum evolution, whereby the dynamics of certain quantum systems can be simulated with gate complexity that is sublinear in the evolution time. We provide a definition of fast-forwarding that considers the model of quantum computation, the Hamiltonians that induce the evolution, and the properties of the initial states. Our definition accounts for any asymptotic complexity improvement of the general case and we use it to demonstrate fast-forwarding in several quantum systems. In particular, we show that some local spin systems whose Hamiltonians can be taken into block diagonal form using an efficient quantum circuit, such as those that are permutation-invariant, can be exponentially fast-forwarded. We also show that certain classes of positive semidefinite local spin systems, also known as frustration-free, can be polynomially fast-forwarded, provided the initial state is supported on a subspace of sufficiently low energies. Last, we show that all quadratic fermionic systems and number-conserving quadratic bosonic systems can be exponentially fast-forwarded in a model where quantum gates are exponentials of specific fermionic or bosonic operators, respectively. Our results extend the classes of physical Hamiltonians that were previously known to be fast-forwarded, while not necessarily requiring methods that diagonalize the Hamiltonians efficiently. We further develop a connection between fast-forwarding and precise energy measurements that also accounts for polynomial improvements.
We provide a quantum algorithm for simulating the dynamics of sparse Hamiltonians with complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Specifically, we show that a d-sparse Hamiltonian H on n qubits can be simulated for time t with precision ε using O(τlog(τ/ε)/log log(τ/ε)) queries and O(τnlog2(τ/ε)/log log(τ/ε)) additional 2-qubit gates, where τ=d2||H||maxt. Unlike previous approaches based on product formulas, the query complexity is independent of the number of qubits acted on, and for time-varying Hamiltonians, the gate complexity is logarithmic in the norm of the derivative of the Hamiltonian. Our algorithm is based on a significantly improved simulation of the continuous- and fractional-query models using discrete quantum queries, showing that the former models are not much more powerful than the discrete model even for very small error. We also significantly simplify the analysis of this conversion, avoiding the need for a complex fault correction procedure. Our simplification relies on a new form of "oblivious amplitude amplification" that can be applied even though the reflection about the input state is unavailable. Finally, we prove new lower bounds showing that our algorithms are optimal as a function of the error.
Simulating the dynamics of dissipative quantum many-body systems governed by local Lindbladians is a fundamental task in quantum computation. While the near-optimal gate count has been achieved for Hamiltonian simulation, comparable results for Lindbladian simulation remain elusive. In this work, we develop quantum algorithms for lattice Lindbladians by exploiting their locality. First, we consider sparsely dissipative systems, in which the dissipation is sparsely located, including boundary-driven systems. We establish a near-optimal quantum algorithm for their dynamics with gate count O(Nt polylog(Nt/ε))O(Nt \, \mathrm{polylog}(Nt/\varepsilon))O(Ntpolylog(Nt/ε)), where NNN is the system size, ttt is the evolution time, and ε\varepsilonε is the allowable error. We then consider generic lattice Lindbladians with finite-range interactions and dissipation, and develop an algorithm for simulating time-evolved observables with gate count O((Nt)4/3 polylog(Nt/ε))O((Nt)^{4/3} \, \mathrm{polylog}(Nt/\varepsilon))O((Nt)4/3polylog(Nt/ε)) per sample with the sampling complexity Θ(ε−2)Θ(\varepsilon^{-2})Θ(ε−2). The gate count has the smallest known dependence on the system size among algorithms retaining polylogarithmic dependence on 1/ε1/\varepsilon1/ε. Our algorithms are based on two techniques that exploit locality: patching and merging. Patching decomposes dissipative dynamics into dynamics on subsystems with exponentially small error, generalizing a key idea underlying the Haah-Hastings-Kothari-Low algorithm for near-optimal Hamiltonian simulation. Merging absorbs reversed dissipative dynamics into other parts of the evolution, substantially reducing the overhead associated with quasi-probabilistic sampling. These results demonstrate that locality can be fully exploited to achieve fast quantum simulation of dissipative many-body dynamics, opening the way to applications such as predicting nonequilibrium phenomena and preparing desirable quantum states.