Foundations of Quantum Hardness: On the Power of Quantum Proofs and the Approximability of Local Hamiltonians

This project investigates the computational limits of computing key properties of quantum many-body systems, such as those found in chemistry and materials science. While calculating exact properties efficiently is often impossible, this research seeks to determine how difficult it is to obtain the approximations necessary for practical applications. In particular, this research will investigate designing new quantum and classical algorithms, identify the computational limitation based on complexity theoretical approaches, and explore potential applications to chemistry and materials science. This project will serve the national interest by promoting the progress of science and advancing national prosperity through guiding the development of efficient quantum algorithms for fundamental quantum many-body problems with significant applications in quantum physics, chemistry, and materials science. Additionally, the project supports the national welfare by funding graduate and postdoctoral training, introducing new quantum computing curricula, and mentoring undergraduates in this critical technology field. In the technical part, this project investigates the computational complexity of approximating key properties of quantum many-body systems, such as ground-state energy, partition functions, and thermal states—quantities that play a central role in quantum physics, chemistry, and materials science. While solving these problems exactly in polynomial time is widely believed to be intractable, achieving good approximations or (super-)polynomial speedup are often useful for practical applications. This motivates the core question: How hard is it to obtain a good approximation of quantum Hamiltonian properties? To address this, the project focuses on two foundational open directions: (1) characterizing the complexity of approximating ground-state energy and related quantities through a fine-grained complexity paradigm and new algorithm design, and (2) Determining the conditions under which quantum proofs and queries are strictly more powerful than classical ones by developing new techniques for analyzing query and space complexity. TThese directions lie at the heart of quantum complexity theory and connect to major open problems, including the Quantum PCP Conjecture and the Simulation Conjecture. 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. NSF Award ID: 2535028 | Program: 01002627DB NSF RESEARCH & RELATED ACTIVIT | Principal Investigator: Nai-Hui Chia | Institution: William Marsh Rice University, HOUSTON, TX | Award Amount: $599,360 View on NSF Award Search: https://www.nsf.gov/awardsearch/show-award/?AWD_ID=2535028 View on Research.gov: https://www.research.gov/awardapi-service/v1/awards/2535028.html