Computational Complexity of Noisy and Perturbed Quantum Systems

The field of quantum computation has matured tremendously since the early remarkable discoveries of exponential quantum algorithms speed ups, quantum error correction and fault tolerance. However, some of the most basic, fundamental questions, remain a challenge. What are the conditions for quantum fault tolerance, and what are its fundamental limitations? What other problems admit quantum algorithmic speed ups, and how can we design new quantum algorithms? Can quantum Hamiltonian complexity be more relevant to phenomena that physicists encounter in the lab? Can we provide evidence for scalable quantum advantage on near term devices?To make progress on these major challenges, this proposal focuses on one overarching theme: the effect of noise and perturbation on computational complexity of quantum systems. For quantum algorithms, we propose to treat noise and perturbations as a tool, rather than an obstacle, and to introduce those deliberately in quantum algorithm design. We aim to develop a mathematical theory of quantum fault tolerance, and within it, study the conditions for this remarkable phenomenon to hold. In quantum complexity we will address questions such as the sensitivity of quantum complexity to perturbations; while the quantum complexity of naturally noisy systems without error correction will be studied in the attempt to make progress on demonstrating quantum advantage in near term devices.We postulate that the theme of noise and perturbations not only underlies these questions, but also connects them in deep and insightful ways. We hope to use this perspective to make significant progress and open new frontiers both on important challenges within fault tolerance, quantum algorithmic advantage and quantum complexity, from the computer science side, as well as on ourunderstanding of multi-partite entanglement, stability, relaxation times and the transition from quantum to classical, from the physics side.