Efficient Quantum Algorithms for Simulating Lindblad Evolution

DOI10.4230/LIPICS.ICALP.2017.17MaRDI QIDQ5111346zbMATHOpenAlexFDO

Authors Richard Cleve, Chun-Hao Wang

Publication date 27 May 2020

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

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)

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.

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

Cited in

(18)

• Wave Matrix Lindbladization II: General Lindbladians, Linear Combinations, and Polynomials
• Algorithms for perturbative analysis and simulation of quantum dynamics
• The Kitaev-Feynman clock for open quantum systems
• Quantum circuit simulation of superchannels
• Quantum simulation dynamics and circuit synthesis of FMO complex on an NMR quantum computer
• Commutation simulator for open quantum dynamics
• On the efficiency of quantum algorithms for Hamiltonian simulation
• Lattice Lindblad simulation
• Efficient Algorithms for Universal Quantum Simulation
• Szegedy walk unitaries for quantum maps
• Wave Matrix Lindbladization I: Quantum Programs for Simulating Markovian Dynamics
• Digital Simulation of Single Qubit Markovian Open Quantum Systems: A Tutorial
• Efficient Quantum Algorithms for Testing Symmetries of Open Quantum Systems
• Succinct description and efficient simulation of non-Markovian open quantum systems
• Structure-preserving numerical schemes for Lindblad equations
• Hybrid quantum variational algorithm for simulating open quantum systems with near-term devices
• A Brief Journey through Collision Models for Multipartite Open Quantum Dynamics
• Efficient quantum algorithms to construct arbitrary Dicke states

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)