Transitions in Computational Complexity of Continuous-Time Local Open Quantum Dynamics

Authors:
Open Access
Publisher website
Google Scholar
Abstract
We analyze the complexity of classically simulating continuous-time dynamics of locally interacting quantum spin systems with a constant rate of entanglement breaking noise. We prove that a polynomial time classical algorithm can be used to sample from the state of the spins when the rate of noise is higher than a threshold determined by the strength of the local interactions. Furthermore, by encoding a 1D fault tolerant quantum computation into the dynamics of spin systems arranged on two or higher dimensional grids, we show that for several noise channels, the problem of weakly simulating the output state of both purely Hamiltonian and purely dissipative dynamics is expected to be hard in the low-noise regime.
Funding Information
  • H2020 European Research Council (QUENOCOBA)
  • Horizon 2020 Framework Programme (742102)
  • Deutsche Forschungsgemeinschaft (414325145)
  • Austrian Science Fund (SFB F7104)

This publication has 51 references indexed in Scilit: