Simulating the evolution of Markovian open quantum systems on quantum computers

Simulating the evolution of quantum systems becomes one of the most appealing tasks researchers hope to perform when small quantum computers are emerging. The simulation of Hamiltonian evolution has been well studied in previous results: the best known gate complexity is $O(t\,\polylog(t/\epsilon))$, where $t$ is the evolution time and $\epsilon$ is the precision. In this talk, we consider simulating the evolution of a class of more generalized systems: the Markovian open quantum systems (a.k.a Lindblad evolution). We first present an efficient quantum algorithm for simulating such evolution with gate complexity $O(t\,\polylog(t/\epsilon))$. Then we argue that it is impossible to achieve this linear dependency in $t$ by simply reducing Lindblad evolution to Hamiltonian evolution in "the Church of larger Hilbert space''.