Exponential Quantum Advantage for Simulating Open Classical Systems

A recent promising arena for quantum advantage is simulating exponentially large classical systems. Here, we broaden this arena to include open classical systems experiencing dissipation. This is a particularly interesting class of systems since dissipation plays a key role in contexts ranging from fluid dynamics to thermalization. We adopt the Caldeira-Leggett Hamiltonian, a generic model for dissipation in which the system is coupled to a bath of harmonic oscillators with a large number $N$ of degrees of freedom. To date, the most efficient classical algorithms for simulating such systems have a polynomial dependence on $N$. In this work, we give a quantum algorithm with an exponential advantage, capable of simulating $m$ system degrees of freedom coupled to $N = 2^n \gg m$ independent bath degrees of freedom, to within error $\eps$, using $O(\| \hat\matH t\|/\sqrt{\eps}) = O(\poly(m,n))$ quantum gates.