Revolutionizing Complexity Theory: Quantum Versions of the Karp-Lipton Theorem 🚀

Scott Aaronson (University of Texas at Austin)
https://simons.berkeley.edu/talks/scott-aaronson-university-texas-austin-2025-05-29
Quantum Algorithms, Complexity, and Fault Tolerance Reunion

The celebrated Karp-Lipton Theorem says that NP is in P/poly, then the polynomial hierarchy collapses to NP^NP. I've been curious for decades about which quantum analogues of this statement hold. In 2010, Andy Drucker and I showed that if NP is in BQP/qpoly -- that is, if quantum advice makes NP-complete problems easy -- then coNP^NP is contained in QMA^PromiseQMA. In 2006, I claimed to show that if PP is in BQP/qpoly, then the counting hierarchy CH collapses to PP, but unfortunately my proof had a gap. Last year my (then-)PhD student Justin Yirka filled the gap, in part by using the main result of me and Drucker from 2010: namely, the "BQP/qpoly = YQP/poly" theorem. I'll tell this whole story and then speculate about where to go next in understanding quantum advice.