Efficient Quantum Algorithms for Simulating Lindblad Evolution

DOI10.4230/LIPICS.ICALP.2017.17zbMATH Open1447.81074arXiv1612.09512OpenAlexW2964242287MaRDI QIDQ5111346FDOQ5111346

Authors: Richard Cleve, Chun-Hao Wang 

Publication date: 27 May 2020

Abstract: We consider the natural generalization of the Schr"{o}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 $mathrmpoly(n)$ operators that can each be expressed as a linear combination of $mathrmpoly(n)$ tensor products of Pauli operators then the gate cost of our algorithm is $O(t,mathrmpolylog(t/epsilon)mathrmpoly(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"{o}dinger evolution on a larger system and tracing out the ancillary system: the cost of such a extit{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.

Full work available at URL: https://arxiv.org/abs/1612.09512

Recommendations

• Quantum algorithm for simulating real time evolution of lattice Hamiltonians
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Hybrid quantum variational algorithm for simulating open quantum systems with near-term devices
• Algorithm for quantum simulation
• On the efficiency of quantum algorithms for Hamiltonian simulation

zbMATH Keywords

open quantum systemsquantum algorithmsLindblad simulation

Mathematics Subject Classification ID

Markov semigroups and applications to diffusion processes (47D07) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Open systems, reduced dynamics, master equations, decoherence (81S22)

Cited In (12)

• Commutation simulator for open quantum dynamics
• Digital Simulation of Single Qubit Markovian Open Quantum Systems: A Tutorial
• On the efficiency of quantum algorithms for Hamiltonian simulation
• Succinct description and efficient simulation of non-Markovian open quantum systems
• Efficient Quantum Algorithms for Testing Symmetries of Open Quantum Systems
• A Brief Journey through Collision Models for Multipartite Open Quantum Dynamics
• Wave Matrix Lindbladization I: Quantum Programs for Simulating Markovian Dynamics
• Efficient quantum algorithms to construct arbitrary Dicke states
• Hybrid quantum variational algorithm for simulating open quantum systems with near-term devices
• Efficient Algorithms for Universal Quantum Simulation
• Structure-preserving numerical schemes for Lindblad equations
• Wave Matrix Lindbladization II: General Lindbladians, Linear Combinations, and Polynomials

This page was built for publication: Efficient Quantum Algorithms for Simulating Lindblad Evolution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111346)