Quantum Simulation for Open-System Dynamics*

Simulations are essential for predicting and explaining properties of physical and mathematical systems yet so far have been restricted to classical and closed quantum systems [1,2]. Although forays have been made into open-system quantum simulation [3], the strict algorithmic aspect has not been explored yet is necessary to account fully for resource consumption to deliver bounded-error answers to computational questions. An open-system quantum simulator would encompass classical and closed-system simulation and also solve outstanding problems concerning, e.g. dynamical phase transitions in non-equilibrium systems, establishing long-range order via dissipation, verifying the simulatability of open-system dynamics on a quantum Turing machine. We construct an efficient autonomous algorithm for designing an efficient quantum circuit to simulate many-body open-system dynamics described by a local Hamiltonian plus decoherence due to separate baths for each particle. The execution time and number of gates for the quantum simulator both scale polynomially with the system size.\\[4pt] [1] S. Lloyd, Science 273, 1073 (1996).\\[0pt] [2] D. W. Berry et al, Comm. Math. Phys. 270, 359 (2007).\\[0pt] [3] M. Kliesch et al, Phys. Rev. Lett. 107, 120501 (2011).