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:2407.11782 · Physical Review A

Quantum dissipative search via Lindbladians

Peter J. Eder, Jernej Rudi Finžgar, Sarah Braun, Christian B. Mendl

Published Apr 25, 2025• 5 citations
arXivHTMLPDF

Abstract

Closed quantum systems follow a unitary time evolution that can be simulated on quantum computers. By incorporating nonunitary effects via, e.g., measurements on ancilla qubits, these algorithms can be extended to open-system dynamics, such as Markovian processes described by the Lindblad master equation. In this paper, we analyze the convergence criteria and speed of a Markovian, purely dissipative quantum random walk on an unstructured classical search space. Notably, we show that certain jump operators make the quantum process replicate a classical one, while others yield differences between open quantum (OQRW) and classical random walks. We also clarify a previously observed quadratic speedup, demonstrating that OQRWs are no more efficient than classical search. Finally, we analyze a dissipative discrete-time ground-state preparation algorithm with a lower implementation cost. This allows us to interpolate between the dissipative and the unitary domain and thereby illustrate the important role of coherence for the quadratic speedup.

DOI
10.1103/physreva.111.042430

Related papers

Computational Problems Related to Open Quantum Systems

Chunhao Wang

A quantum system that has interaction with external resources, such as probability distribution, dissipation, and noise, is referred to as an open quantum system. Not only do open quantum systems play a vital role in the field of quantum physics, but they are also fundamental objects in quantum information and quantum computing. In this thesis, we focus on computational problems related to open quantum systems. In particular, we study efficient constructions of open quantum systems and their algorithmic applications. \n \nA unitary 2-design is a quantum analogue of universal 2-hash functions. It is an example of open quantum systems in the sense that it is a probability distribution of unitaries. As unitary 2-designs inherit many properties of the Haar randomness on the unitary group, they have many applications in quantum information, such as benchmarking and decoupling. We study the structures of unitary 2-designs and present efficient methods for their constructions. \n \nThe continuous-time evolution of a closed quantum system can be described by the Schrödinger equation. A natural generalization of the Schrödinger equation to Markovian open quantum systems, in the sense of generating dynamical semigroups, is called the Lindblad equation. We show that it is impossible for a simple reductionist approach to simulate Lindblad evolution with gate complexity that has linear dependence in evolution time. Moreover, we use a novel variation of the "linear combination of unitaries" construction that pertains to quantum channels to achieve the desired linear dependence in evolution time and poly-logarithmic dependence in precision. \n \nOpen quantum systems can also be used as building blocks of quantum algorithms. We present a dissipative query model, which is based on the amplitude damping process. With this dissipative query model, we provide a quantum algorithm that performs a fixed-point quantum search while preserving the quadratic speedup against classical algorithms.

•Aug 22, 2018•1 citation

Hamiltonian dynamics from pure dissipation

Zhong-Xia Shang, Daniel Stilck França

The fundamental difference between closed and open quantum dynamics lies in their environmental interaction: closed systems are perfectly isolated and evolve reversibly under unitary Hamiltonian dynamics, whereas open systems continuously couple to an external bath, resulting in irreversible dissipation and information loss. In this work, we show internal Hamiltonian dynamics can be "faked`` via external pure dissipation, i.e., Lindbladians without a coherent Hamiltonian part. More concretely, we show that, in a GKSL representation with zero explicit Hamiltonian term but nontraceless jump operators, bounded-norm dissipative generators can approximate Hamiltonian dynamics within $ε$ error in diamond norm using $\mathcal{O}(t^2/ε)$ evolution time. We further prove that for time-independent dynamics this $\mathcal{O}(t^2/ε)$ scaling is in the worst case, necessary and optimal from a geometric perspective, which captures the fundamental decoherence cost for catching up with the speed of Hamiltonian dynamics. Our construction leads to various implications, including the BQP-completeness of purely dissipative dynamics even before reaching approximate equilibrium, a Zeno-adjacent state-independent freezing effect, the no super-quadratic fast-forwarding theorem of a class of purely dissipative dynamics, and reducing Lindbladian simulation cost via gauge changing.

quant-pharXiv:2604.18533•Apr 21, 2026•0 citations

Quantum algorithm to simulate Lindblad master equations

Evan Borras, Milad Marvian

We present a quantum algorithm for simulating a family of Markovian master equations that can be realized through a probabilistic application of unitary channels and state preparation. Our approach employs a second-order product formula for the Lindblad master equation, achieved by decomposing the dynamics into dissipative and Hamiltonian components and replacing the dissipative segments with randomly compiled, easily implementable elements. The sampling approach eliminates the need for ancillary qubits to simulate the dissipation process and reduces the gate complexity in terms of the number of jump operators. We provide a rigorous performance analysis of the algorithm. We also extend the algorithm to time-dependent Lindblad equations, generalize the family of Markovian master equations it can be applied to, and explore applications beyond the Markovian noise model. A new error bound, in terms of the diamond norm, for second-order product formulas for time-dependent Liouvillians is provided that might be of independent interest.

arXiv:2406.12748•Physical Review Research•Apr 22, 2025•10 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

Efficient Quantum Algorithms for Simulating Lindblad Evolution

Richard Cleve, Chunhao Wang

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.

arXiv:1612.09512•Leibniz international proceedings in informatics•Dec 30, 2016•41 citations

Quadratic Speedup for Spatial Search by Continuous-Time Quantum Walk

Simon Apers, Shantanav Chakraborty, Leonardo Novo +1 more

Continuous-time quantum walks provide a natural framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search. Whether spatial search by continuous-time quantum walk provides a quadratic advantage over classical random walks has been an outstanding problem. Thus far, this advantage is obtained only for specific graphs or when a single node of the underlying graph is marked. In this Letter, we provide a new continuous-time quantum walk search algorithm that completely resolves this: our algorithm can find a marked node in any graph with any number of marked nodes, in a time that is quadratically faster than classical random walks. The overall algorithm is quite simple, requiring time evolution of the quantum walk Hamiltonian followed by a projective measurement. A key component of our algorithm is a purely analogue procedure to perform operations on a state of the form e^{-tH^{2}}|ψ⟩, which, for a given Hamiltonian H, only requires evolving H for time scaling as sqrt[t]. This allows us to quadratically fast-forward the dynamics of a continuous-time classical random walk. The applications of our Letter thus go beyond the realm of quantum walks and can lead to new analog quantum algorithms for preparing ground states of Hamiltonians or solving optimization problems.

arXiv:2112.12746•Physical Review Letters•Oct 14, 2022•65 citations
Closed quantum systems follow a unitary time evolution that can be simulated on quantum computers. By incorporating nonunitary effects via, e.g., measurements on ancilla qubits, these algorithms can be extended to open-system dynamics, such as Markovian processes described by the Lindblad master equation. In this paper, we analyze the convergence criteria and speed of a Markovian, purely dissipative quantum random walk on an unstructured classical search space. Notably, we show that certain jump operators make the quantum process replicate a classical one, while others yield differences between open quantum (OQRW) and classical random walks. We also clarify a previously observed quadratic speedup, demonstrating that OQRWs are no more efficient than classical search. Finally, we analyze a dissipative discrete-time ground-state preparation algorithm with a lower implementation cost. This allows us to interpolate between the dissipative and the unitary domain and thereby illustrate the important role of coherence for the quadratic speedup.
A quantum system that has interaction with external resources, such as probability distribution, dissipation, and noise, is referred to as an open quantum system. Not only do open quantum systems play a vital role in the field of quantum physics, but they are also fundamental objects in quantum information and quantum computing. In this thesis, we focus on computational problems related to open quantum systems. In particular, we study efficient constructions of open quantum systems and their algorithmic applications. \n \nA unitary 2-design is a quantum analogue of universal 2-hash functions. It is an example of open quantum systems in the sense that it is a probability distribution of unitaries. As unitary 2-designs inherit many properties of the Haar randomness on the unitary group, they have many applications in quantum information, such as benchmarking and decoupling. We study the structures of unitary 2-designs and present efficient methods for their constructions. \n \nThe continuous-time evolution of a closed quantum system can be described by the Schrödinger equation. A natural generalization of the Schrödinger equation to Markovian open quantum systems, in the sense of generating dynamical semigroups, is called the Lindblad equation. We show that it is impossible for a simple reductionist approach to simulate Lindblad evolution with gate complexity that has linear dependence in evolution time. Moreover, we use a novel variation of the "linear combination of unitaries" construction that pertains to quantum channels to achieve the desired linear dependence in evolution time and poly-logarithmic dependence in precision. \n \nOpen quantum systems can also be used as building blocks of quantum algorithms. We present a dissipative query model, which is based on the amplitude damping process. With this dissipative query model, we provide a quantum algorithm that performs a fixed-point quantum search while preserving the quadratic speedup against classical algorithms.
The fundamental difference between closed and open quantum dynamics lies in their environmental interaction: closed systems are perfectly isolated and evolve reversibly under unitary Hamiltonian dynamics, whereas open systems continuously couple to an external bath, resulting in irreversible dissipation and information loss. In this work, we show internal Hamiltonian dynamics can be "faked`` via external pure dissipation, i.e., Lindbladians without a coherent Hamiltonian part. More concretely, we show that, in a GKSL representation with zero explicit Hamiltonian term but nontraceless jump operators, bounded-norm dissipative generators can approximate Hamiltonian dynamics within εεε error in diamond norm using O(t2/ε)\mathcal{O}(t^2/ε)O(t2/ε) evolution time. We further prove that for time-independent dynamics this O(t2/ε)\mathcal{O}(t^2/ε)O(t2/ε) scaling is in the worst case, necessary and optimal from a geometric perspective, which captures the fundamental decoherence cost for catching up with the speed of Hamiltonian dynamics. Our construction leads to various implications, including the BQP-completeness of purely dissipative dynamics even before reaching approximate equilibrium, a Zeno-adjacent state-independent freezing effect, the no super-quadratic fast-forwarding theorem of a class of purely dissipative dynamics, and reducing Lindbladian simulation cost via gauge changing.
We present a quantum algorithm for simulating a family of Markovian master equations that can be realized through a probabilistic application of unitary channels and state preparation. Our approach employs a second-order product formula for the Lindblad master equation, achieved by decomposing the dynamics into dissipative and Hamiltonian components and replacing the dissipative segments with randomly compiled, easily implementable elements. The sampling approach eliminates the need for ancillary qubits to simulate the dissipation process and reduces the gate complexity in terms of the number of jump operators. We provide a rigorous performance analysis of the algorithm. We also extend the algorithm to time-dependent Lindblad equations, generalize the family of Markovian master equations it can be applied to, and explore applications beyond the Markovian noise model. A new error bound, in terms of the diamond norm, for second-order product formulas for time-dependent Liouvillians is provided that might be of independent interest.
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 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.
Continuous-time quantum walks provide a natural framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search. Whether spatial search by continuous-time quantum walk provides a quadratic advantage over classical random walks has been an outstanding problem. Thus far, this advantage is obtained only for specific graphs or when a single node of the underlying graph is marked. In this Letter, we provide a new continuous-time quantum walk search algorithm that completely resolves this: our algorithm can find a marked node in any graph with any number of marked nodes, in a time that is quadratically faster than classical random walks. The overall algorithm is quite simple, requiring time evolution of the quantum walk Hamiltonian followed by a projective measurement. A key component of our algorithm is a purely analogue procedure to perform operations on a state of the form e^{-tH^{2}}|ψ⟩, which, for a given Hamiltonian H, only requires evolving H for time scaling as sqrt[t]. This allows us to quadratically fast-forward the dynamics of a continuous-time classical random walk. The applications of our Letter thus go beyond the realm of quantum walks and can lead to new analog quantum algorithms for preparing ground states of Hamiltonians or solving optimization problems.