Exploring the Limits of Classical Simulation: From Computational Many-Body Dynamics to Quantum Advantage

For many years after the dawn of computing machines, it seemed to be the case that the dynamics of any physical system (including all computers, which of course are physical systems themselves) could be efficiently simulated by a simple model of a computer called the Turing machine. A consequence was that computational problems that were found to be hard for Turing machines---those requiring a runtime superpolynomial in the size of the input---remained hard no matter what machine was built to solve them. But in the latter part of the 20th century, an intriguing counterexample emerged: quantum mechanics. The simulation of straightforward quantum systems seemed to have an exponential computational cost. This led to a provocative question: what if one were to build a computer from quantum mechanical components? Could that machine outperform the Turing machine, and efficiently simulate arbitrary quantum processes? And are there other hard problems that such a machine could efficiently solve?In this dissertation we explore several questions stemming from those ideas. First, classical simulation of quantum many-body physics may be hard, but modern supercomputers are extremely powerful---with cutting-edge innovations in both hardware and algorithms, what quantum simulations can be achieved, and what physics can we learn from them? Second, while there has been astounding progress in the development of quantum computers, they are still small and noisy---what can we do on these near-term devices, that cannot be done with the powerful classical supercomputers just described? Furthermore, if we do a quantum mechanical computation that seems to be infeasible for even the fastest classical machines, how do we check that the result is actually correct? Answering these questions requires deeply exploring the physical nature of computing; at heart, it comes down to the beautiful puzzle of organizing the physical world around us to process information