Efficient Quantum Algorithms for Simulating Lindblad Evolution

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 $\epsilon$. 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/\epsilon )\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/\epsilon )$ 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.

26 pages, 4 figures, minor corrections

References in corpus (4)

• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Dissipative preparation of entanglement in optical cavities
• Toward quantum simulations of biological information flow

Cited by in corpus (19)

• Quantum simulation of non-equilibrium dynamics and thermalization in the Schwinger model
• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• Quantum algorithm for Petz recovery channels and pretty good measurements
• Quantum simulation of open quantum systems in heavy-ion collisions
• Thermal State Preparation via Rounding Promises
• Efficient simulation of sparse Markovian quantum dynamics
• Superdiffusive quantum stochastic walk definable of arbitrary directed graph
• Wave Matrix Lindbladization I: Quantum Programs for Simulating Markovian Dynamics
• Non-Equilibrium Dynamics of a Dissipative Two-Site Hubbard Model Simulated on IBM Quantum Computers
• Quantum Algorithms for Open Lattice Field Theory
• Long-Time Error-Mitigating Simulation of Open Quantum Systems on Near Term Quantum Computers
• Simulating spin biology using a digital quantum computer: Prospects on a near-term quantum hardware emulator
• Digital quantum simulation of non-perturbative dynamics of open systems with orthogonal polynomials
• Quantum algorithms for powering stable Hermitian matrices
• Commutation simulator for open quantum dynamics
• A Partially Random Trotter Algorithm for Quantum Hamiltonian Simulations
• Digital Simulation of Single Qubit Markovian Open Quantum Systems: A Tutorial
• Strong symmetries in collision models and physical dilations of covariant quantum maps
• Quantum algorithms based on quantum trajectories