Source-linked AI summary
A dissipative quantum Church-Turing theorem
M. Kliesch, T. Barthel, C. Gogolin, M. Kastoryano, J. Eisert
TL;DR
Simulating dissipative processes without including every environmental mode motivates a tractable theory for open quantum systems. The paper bounds a Trotter decomposition for time-dependent local Liouvillians and shows that their evolution has an efficient unitary-circuit simulation, while excluding non-Markovian dynamics.
Problem
Simulating dissipative processes requires a setting that does not demand modeling every environmental mode, motivating a theory for open systems in the Markovian regime.
Source: p. 1Method
The paper introduces a Trotter decomposition for time-dependent local Liouvillians and proves explicit error bounds for the approximation.
Source: p. 2Results
Time-dependent Liouvillian dynamics can be simulated efficiently in the standard unitary circuit model, and dissipative quantum computing is no more powerful than the unitary circuit model.
Source: pp. 1–2Takeaways & Limitations
The bounds provide a mathematically sound foundation for Trotter-based simulation techniques, including numerical approaches such as matrix-product operators.
Source: pp. 3–4The result covers k-local dynamics on fixed finite-dimensional subsystems but excludes non-Markovian dynamics, such as those arising from strong coupling.
Source: pp. 1, 3
Abstract
from arXiv · showhide
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.
APPENDIX
The appendix develops technical bounds and arguments supporting the paper’s simulation results, including a limit on efficiently generated states.
APPENDIX
- It derives the Trotter-approximation error for time-dependent k-local Liouvillian evolution and gives a general bound for arbitrary time-dependent Liouvillians.The general bound is not needed for the paper’s main statements and is noted as non-optimal in some situations.Source: APPENDIX · p. 5
- It derives the additional error from replacing evolution over a short interval with evolution under the average Liouvillian.Source: APPENDIX · p. 5
- It extends an earlier state-space argument to density matrices in trace distance, showing that only an exponentially small subset of states is efficiently preparable.The claim concerns polynomial-time evolution under time-dependent k-local Liouvillians from a fixed reference state.Source: APPENDIX · p. 5
Trotter approximation for time dependent Liouvillians
The section establishes error bounds for decomposing time-dependent Liouvillian evolution into sequential evolutions under simpler generators. It handles general decompositions and then specializes the bounds to local Liouvillians.
Trotter approximation for time dependent Liouvillians
- The decomposition is applied iteratively to split a k-local Liouvillian into its strictly k-local terms.The short-interval construction sequentially evolves under a strictly k-local part and the remainder.Source: Trotter approximation for time… · p. 5
- CPT propagators are contractive in the induced 1-to-1 norm, a property used in bounding the decomposition error.Source: Trotter approximation for time… · p. 5
- For arbitrary time-dependent Liouvillians, the Trotter error is bounded using forward and backward propagator norms and an integral involving the generators’ commutator.The proof applies the fundamental theorem of calculus and bounds the resulting terms in the induced 1-to-1 norm.Source: Trotter approximation for time… · p. 6
- For k-local evolution, the bound specializes by controlling generator norms and commutators through the local Lindblad representations.The resulting local error bound follows by combining the general bound with bounds for strictly k-local terms.Source: Trotter approximation for time… · pp. 6–7
- Higher-order Trotter schemes can improve the error’s scaling with the time-step size.Source: Trotter approximation for time… · p. 7
Approximation by the average Liouvillian
The section bounds the extra error incurred when time-ordered evolution under a strictly local, time-dependent Liouvillian is replaced by evolution under its time average.
Approximation by the average Liouvillian
- Using ordinary exponentials of time-averaged Liouvillians makes the Trotter product formula more useful for applications, beyond the main simulation argument.Source: Approximation by the average Liouvillian · p. 7
- Theorem 7 bounds the additional approximation error from replacing time-dependent evolution by evolution under the average Liouvillian.The theorem applies to a strictly k-local Liouvillian and states the bound in terms of its Lindblad-operator norm bound and local dimension.Source: Approximation by the average Liouvillian · p. 7
- The time-averaged strictly k-local generator is itself a Liouvillian, so its exponential defines a valid quantum evolution.The proof uses closure of the set of CPT maps under limits.Source: Approximation by the average Liouvillian · pp. 7–8
Efficiently preparable states constitute an exponentially small
The section bounds how many circuits can approximate local Liouvillian evolutions, then compares the resulting reachable states with the full state space. For polynomial simulation times, the reachable set is exponentially small relative to that space.
Efficiently preparable states constitute an exponentially small
- The circuit-count argument uses Trotter error bounds, Stinespring dilation, and the Solovay-Kitaev algorithm to approximate channel evolution with unitary circuits.The construction approximates the propagator to accuracy ǫ using circuits from a fixed universal gate set.Source: subset of state space · p. 8
- Any such evolution can be approximated by one of a finite set of channel circuits, with the circuit count determined by system parameters and target accuracy.The approximation is in the induced 1-to-1 norm.Source: subset of state space · p. 8
- The proof compares the number of approximate evolutions with covering nets for state vectors, rank-one projectors, and density matrices.It extends a state-vector net argument to the physically relevant trace-distance setting for density matrices.Source: subset of state space · pp. 8–9
- For polynomial time, states reachable from a fixed initial state under k-local Liouvillian evolution occupy an exponentially small subset of the full state space.The theorem places the reachable states inside a union of trace-distance balls whose count is exponentially smaller than the size of a covering net for the state space.Source: subset of state space · p. 9