A dissipative quantum Church-Turing theorem

Abstract

We show that the time evolution of an open quantum system, described by a possibly time dependent Liouvillian, can be simulated by a unitary quantum circuit of a size scaling polynomially in the simulation time and the size of the system. An immediate consequence is that dissipative quantum computing is no more powerful than the unitary circuit model. Our result can be seen as a dissipative Church-Turing theorem, since it implies that under natural assumptions, such as weak coupling to an environment, the dynamics of an open quantum system can be simulated efficiently on a quantum computer. Formally, we introduce a Trotter decomposition for Liouvillian dynamics and give explicit error bounds. This constitutes a practical tool for numerical simulations, e.g., using matrix-product operators. We also demonstrate that most quantum states cannot be prepared efficiently.

4 pages + 5 pages appendix, Implication 3 corrected

References in corpus (6)

• Quantum States and Phases in Driven Open Quantum Systems with Cold Atoms
• An Open-System Quantum Simulator with Trapped Ions
• Dividing Quantum Channels
• Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
• Genuine quantum trajectories for non-Markovian processes
• Charge and spin transport in strongly correlated one-dimensional quantum systems driven far from equilibrium

Cited by in corpus (96)

• Non-Hermitian Physics
• Quantum Chemistry in the Age of Quantum Computing
• Quantum trajectories and open many-body quantum systems
• Reconstructing quantum states with generative models
• Input-output theory for waveguide QED with an ensemble of inhomogeneous atoms
• Algebraic versus exponential decoherence in dissipative many-particle systems
• Quantum simulation of open-system dynamical maps with trapped ions
• A positive tensor network approach for simulating open quantum many-body systems
• Quantum Simulation of Generic Many-Body Open System Dynamics Using Classical Noise
• Digital quantum simulation of open quantum systems using quantum imaginary time evolution
• Collision models can efficiently simulate any multipartite Markovian quantum dynamics
• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• Quantum Synchronization on the IBM Q System
• Quasi-locality and efficient simulation of Markovian quantum dynamics
• The Dirac equation as a quantum walk: higher dimensions, observational convergence
• A general quantum algorithm for open quantum dynamics demonstrated with the Fenna-Matthews-Olson complex
• Universal simulation of Markovian open quantum systems
• Direct certification of a class of quantum simulations
• Rapid mixing implies exponential decay of correlations
• Simulating Open Quantum Systems Using Hamiltonian Simulations
• Solovay-Kitaev Decomposition Strategy for Single-Qubit Channels
• Quantum simulation of dissipative collective effects on noisy quantum computers
• Digital quantum simulation of many-body non-Markovian dynamics
• Lieb-Robinson bounds and the simulation of time evolution of local observables in lattice systems
• Experimental simulation of open quantum system dynamics via Trotterization
• Introduction to Quantum Algorithms for Physics and Chemistry
• Simulating Open Quantum System Dynamics on NISQ Computers with Generalized Quantum Master Equations
• Variational Quantum Algorithm for Non-equilibrium Steady States
• Dissipative Universal Lindbladian Simulation
• Randomizing multi-product formulas for Hamiltonian simulation
• Optimized Lie-Trotter-Suzuki decompositions for two and three non-commuting terms
• Quantum Simulation of Dissipative Processes without Reservoir Engineering
• Two-Unitary Decomposition Algorithm and Open Quantum System Simulation
• Engineered thermalization and cooling of quantum many-body systems
• Quantum many-body systems in thermal equilibrium
• Simulation of single-qubit open quantum systems
• Accelerated quantum Monte Carlo with mitigated error on noisy quantum computer
• Hardware-efficient quantum algorithm for the simulation of open-system dynamics and thermalisation
• Quantum circuit design for accurate simulation of qudit channels
• Efficient Quantum Algorithms for Simulating Lindblad Evolution
• Superdiffusive quantum stochastic walk definable of arbitrary directed graph
• Efficient simulation of sparse Markovian quantum dynamics
• Toward quantum simulations of biological information flow
• Robust entanglement generation by reservoir engineering
• Lieb-Robinson bounds for open quantum systems with long-ranged interactions
• The modified logarithmic Sobolev inequality for quantum spin systems: classical and commuting nearest neighbour interactions
• Quantum Simulation of the Radical Pair Dynamics of the Avian Compass
• Engineered Open Systems and Quantum Simulations with Atoms and Ions
• Experimental repetitive quantum channel simulation
• Quantum Algorithms for Open Lattice Field Theory
• Dissipative Preparation of Many-Body Quantum States: Towards Practical Quantum Advantage
• Quantum simulations of dissipative dynamics: time-dependence instead of size
• Long-Time Error-Mitigating Simulation of Open Quantum Systems on Near Term Quantum Computers
• A quantum algorithm for the direct estimation of the steady state of open quantum systems
• Variational Quantum Algorithms for Steady States of Open Quantum Systems
• Efficient quantum algorithm to simulate open systems through a single environmental qubit
• Single Qubit Error Mitigation by Simulating Non-Markovian Dynamics
• Fundamental limitations for measurements in quantum many-body systems
• Solvable BCS-Hubbard Liouvillians in arbitrary dimensions
• Dissipative Bose-Einstein condensation in contact with a thermal reservoir
• Coupling function from bath density of states
• Choi states, symmetry-based quantum gate teleportation, and stored-program quantum computing
• Simulating open quantum systems with giant atoms
• Quantum computational advantage with constant-temperature Gibbs sampling
• Feynman's Clock for open quantum systems
• Asymptotically Decreasing Lieb-Robinson Velocity for a Class of Dissipative Quantum Dynamics
• Succinct Description and Efficient Simulation of Non-Markovian Open Quantum Systems
• A game of quantum advantage: linking verification and simulation
• Algorithmic quantum simulation of memory effects
• Design nearly optimal quantum algorithm for linear differential equations via Lindbladians
• Error-mitigated deep-circuit quantum simulation of open systems: steady state and relaxation rate problems
• Protected State Transfer via an Approximate Quantum Adder
• Quantum algorithms for powering stable Hermitian matrices
• Exponentially reduced circuit depths in Lindbladian simulation
• Lower bound for simulation cost of open quantum systems: Lipschitz continuity approach
• Classifying quantum data by dissipation
• Area laws and efficient descriptions of quantum many-body states
• Quantum Neural Network and Soft Quantum Computing
• Commutation simulator for open quantum dynamics
• Preparing Renormalization Group Fixed Points on NISQ Hardware
• Lindblad engineering for quantum Gibbs state preparation under the eigenstate thermalization hypothesis
• Perfect Sampling for Quantum Gibbs States
• On Quasi-Locality and Decay of Correlations for Long-Range Models of Open Quantum Spin Systems
• Initial states of qubit-boson models leading to conserved quantities
• Simulation-assisted learning of open quantum systems
• Trotterless Simulation of Open Quantum Systems for NISQ Quantum Devices
• Classical simulation of dissipative fermionic linear optics
• Scalable quantum simulator with an extended gate set in giant atoms
• A Riemannian Approach to the Lindbladian Dynamics of a Locally Purified Tensor Network
• Weighted Quantum Channel Compiling through Proximal Policy Optimization
• Quantum algorithms based on quantum trajectories
• Instability of steady-state mixed-state symmetry-protected topological order to strong-to-weak spontaneous symmetry breaking
• A Randomized Method for Simulating Lindblad Equations and Thermal State Preparation
• Efficient and simple Gibbs state preparation of the 2D toric code via duality to classical Ising chains
• Non-normality and dissipation in Markovian quantum dynamics: Implications for quantum simulation
• Quantum Imaginary-Time Evolution with Polynomial Resources in Evolution Time