Universal quantum simulation for open-system dynamics

We construct an efficient classical algorithm for designing efficient quantum circuits to simulate open-system dynamics under a completely-positive trace-preserving (CPTP) map. Specifically our approach to simulating~$N$ two-level particles in an open system is to decompose the CPTP map into a sequence of global unitary gates, which can be decomposed efficiently into a set of universal one- and two-qubit unitary gates, and simultaneous single-qubit non-unitary gates. Our single-qubit simulator requires just two qubits and one random bit. Our circuit design algorithm employs the Trotter-Suzuki product formula and a modification of the Solovay-Kitaev-Dawson-Nielsen algorithm for decomposing unitary gates. The resultant quantum circuit for~$N$ particles has space and time resources that scale polynomially with~$N$.