Abstract

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.