Dissipative Quantum Church-Turing Theorem

M. Kliesch; T. Barthel; C. Gogoln; Michael James Kastoryano; J. Eisert

doi:10.1103/PhysRevLett.107.120501

Dissipative Quantum Church-Turing Theorem

M. Kliesch, T. Barthel, C. Gogoln, Michael James Kastoryano, J. Eisert

55 Citations (Scopus)

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.

Original language	English
Journal	Physical Review Letters
Volume	107
Issue number	12
Pages (from-to)	120501
ISSN	0031-9007
DOIs	https://doi.org/10.1103/PhysRevLett.107.120501
Publication status	Published - 12 Sept 2011

Access to Document

10.1103/PhysRevLett.107.120501

Cite this

@article{b1bf3d82c9a94690889ed2e9a98cdd39,

title = "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.",

author = "M. Kliesch and T. Barthel and C. Gogoln and Kastoryano, {Michael James} and J. Eisert",

year = "2011",

month = sep,

day = "12",

doi = "10.1103/PhysRevLett.107.120501",

language = "English",

volume = "107",

pages = "120501",

journal = "Physical Review Letters",

issn = "0031-9007",

publisher = "American Physical Society",

number = "12",

}

TY - JOUR

T1 - Dissipative Quantum Church-Turing Theorem

AU - Kliesch, M.

AU - Barthel, T.

AU - Gogoln, C.

AU - Kastoryano, Michael James

AU - Eisert, J.

PY - 2011/9/12

Y1 - 2011/9/12

N2 - 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.

AB - 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.

U2 - 10.1103/PhysRevLett.107.120501

DO - 10.1103/PhysRevLett.107.120501

M3 - Journal article

SN - 0031-9007

VL - 107

SP - 120501

JO - Physical Review Letters

JF - Physical Review Letters

IS - 12

ER -

Dissipative Quantum Church-Turing Theorem

Abstract

Access to Document

Fingerprint

Cite this