FET: Small: A complexity theoretic lens on near- and medium-term quantum devices

The project aims to address critical gaps in our understanding of what noisy quantum devices can achieve, especially in the near and medium term. The investigators plans to explore three key areas: 1) developing new methods to demonstrate quantum advantage in noisy environments, particularly by making Shor's famous factoring algorithm feasible on current quantum devices; 2) proving the limitations of quantum devices that rely on geometrically local interactions, highlighting the need for long-range connectivity in experiments; and 3) creating benchmarks using machine learning theory to verify whether these devices are correctly implementing their intended tasks. By focusing on these areas, the research will develop new protocols and provide theoretical insights that are crucial for advancing quantum computing, even at current noise levels. The project will leverage ideas from quantum computing and machine learning, and closely collaborate with experimentalists to ensure their findings are both rigorous and practically applicable. The project will also develop new courses to bring together graduate and undergraduate students from different departments to grapple with present-day challenges in quantum computing. The proposal will focus on three critical areas to deepen our theoretical understanding of noisy quantum devices, i.e., Noisy Intermediate-Scale Quantum (NISQ). First, the researchers will develop a novel fault-tolerance theorem that maintains constant-depth overhead, enabling Shor's algorithm on NISQ devices. Second, they will aim to establish no-go theorems for geometrically local noisy quantum systems, providing rigorous proof that long-range interactions are essential for achieving quantum advantage in these systems. Finally, they will leverage learning theory to construct algorithms that can rigorously determine whether a noisy quantum device accurately executes the programmed quantum circuit or adiabatic process. This research will fill theoretical gaps in the understanding of NISQ devices, introducing new protocols that offer low-overhead fault tolerance, and provide formal proofs of the necessity of non-local interactions in quantum computation. Interdisciplinary techniques are expected to play a crucial role in the proposal. Collaboration with experimental groups will ensure the relevance and applicability of the theoretical models of noisy devices. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.