Theory of Noisy Quantum Simulation of many-body Physics

Analog quantum simulation protocols, which aim to use quantum hardware without performing error correction to solve large quantum many-body problems, have emerged as a near-term as well as experimentally accessible alternative to a building a fault tolerant quantum computer for these problems. However, from a theoretical standpoint, whether analog simulators can be trusted to provide accurate results for large quantum many-body problems and if they provide an advantage over classical computers remains a largely unsolved problem. In ToNQS, I aim to rigorously understand the accuracy of analog quantum simulation of many-body problems in both low-energy and high-energy physics. I will do so by developing mathematically rigorous upper bounds on the deviation of the output of a noisy quantum simulator from the target observables which will then serve as an accuracy certificate for the quantum simulator.With this accuracy certificate, I will identify problems that can be reliably solved on quantum simulators – these will problems where the error in the noisy simulator output not grow with the problem size, and thus can be solved for large system sizes in the presence of noise. However, it is possible that problems that are stable are also classically easy and analog quantum simulators are incapable of providing speedups over classical computers while being accurate. In ToNQS, I will then aim to investigate if there is complexity-theoretic evidence for stable problems to also be hard for classical computers. This project will bring together ideas from different sub-areas of my expertise – quantum optics, many-body physics, quantum information and quantum complexity theory. If successful, this project would provide an end-to-end theoretical framework to identify problems for which a noisy quantum simulator can be trusted and reason about its quantum advantage for these problems, thus resolving a major theoretical objection to analog simulators as computational devices.