CAREER: The computational complexity of many-body entanglement

Many-body quantum systems exhibit entanglement patterns that make tasks such as predicting outcomes, certifying device behavior, or succinctly describing the ground state/space computationally prohibitive. This project will develop a theory of computational complexity that explains when physically motivated quantum states (especially ground and low-energy states of local Hamiltonians) admit efficient description and verification, and when they provably do not. These insights are particularly timely due to the growing capabilities of near-term quantum devices, whose behavior increasingly probes regimes of entanglement that are classically intractable. This project will also strengthen quantum-information training by developing graduate-level curriculum in quantum complexity theory and by creating mentored research pathways for undergraduate and graduate students, with the goal of broadening participation in theoretical quantum computing. Technically, this project formulates and proves lower bounds on the description complexity of many-body states arising from local Hamiltonians, focusing on the resources required to (i) represent these states succinctly, (ii) verify or test their properties from local measurements or interactive procedures, and (iii) perform state transformations such as cloning. The particular focus on the description complexity of ground states of local Hamiltonians yields a lens that connects the peculiar nature of entanglement with established tools from theoretical computer science, such as query complexity lower-bounds, classical and quantum error-correction, and boolean function analysis. Expected outcomes include improving our understanding of core quantum complexity classes (e.g., QMA vs QCMA), bettering our understanding of quantum query complexity and state transformations, and making progress towards the quantum PCP conjecture, the major open problem in quantum complexity theory. In addition, these contributions are expected to influence multiple subfields: in theoretical physics, by clarifying how entanglement behaves in realistic models; in quantum cryptography, by enabling constructions like public-key quantum money and unclonable schemes from first principles; and in engineering, by identifying principled computational obstructions to simulation and verification in near-term 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.