Dissipative Quantum Church-Turing Theorem
- 12 September 2011
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 107 (12), 120501
- https://doi.org/10.1103/physrevlett.107.120501
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.Other Versions
This publication has 24 references indexed in Scilit:
- An open-system quantum simulator with trapped ionsNature, 2011
- Quantum computation and quantum-state engineering driven by dissipationNature Physics, 2009
- Charge and spin transport in strongly correlated one-dimensional quantum systems driven far from equilibriumPhysical Review B, 2009
- Quantum states and phases in driven open quantum systems with cold atomsNature Physics, 2008
- Trotter-Based Simulation of Quantum-Classical DynamicsThe Journal of Physical Chemistry B, 2007
- PROGRESS IN THE THEORY OF MIXED QUANTUM-CLASSICAL DYNAMICSAnnual Review of Physical Chemistry, 2006
- Genuine quantum trajectories for non-Markovian processesPhysical Review A, 2004
- Universal Quantum SimulatorsScience, 1996
- Product formula methods for time-dependent Schrodinger problemsJournal of Physics A: General Physics, 1990
- A Set of Postulates for the Foundation of LogicAnnals of Mathematics, 1932