Quantum algorithms on noisy devices and the edge of classical simulations*

Physical noise in quantum devices detrimentally affects quantum algorithms, resulting in less accurate outcomes. In the absence of a fully fault tolerant implementation, when does noise facilitate an efficient classical simulation of a quantum computation? 

In this talk I discuss recent progress on classical simulations of noisy quantum circuits at a fixed level of physical error per gate, with a focus on operator truncation methods. These techniques truncate the evolution of observables in the Heisenberg picture and enable rigorous trade-offs between complexity, approximation error and physical noise. First, I describe a classical simulation algorithm for noisy parameterised quantum circuits, with implications to dynamical simulations and variational algorithms. In the presence of certain types of noise, expectation values of parametrised circuits can be efficiently estimated classically, in an average case sense. Secondly, this work can be positioned into a larger framework of polynomial-time classical algorithms for other quantum tasks under physical noise, such as noisy random circuit sampling. Finally, I discuss practical limitations and consequences of these results for error mitigation and for benchmarking quantum applications on hardware.