Computer Science/Discrete Mathematics Seminar I

Since the work of Karp and Lipton in the 1980s, complexity theorists know and love the /poly operator, which adds a polynomial-sized advice string to any complexity class. But it's interesting to consider much more general kinds of "advice objects" than strings. In this talk, I'll present a new framework for understanding the limitations of advice objects. Results include: Given any "S-black-box"---a box that computes a Boolean function drawn from a known set S of singly exponential size---we can simulate it using *untrusted* S-black-boxes together with a polynomial-sized advice string. BQP/qpoly, or quantum polynomial-time with polynomial-size quantum advice, is contained in QMA/poly. This improves my previous result that BQP/qpoly is contained in PP/poly. Indeed, given any language L in BQP/qpoly, there exists a local Hamiltonian H such that any ground state of H is a valid quantum advice state for L. A polynomial-space quantum computer that can flip an "advice coin" an unlimited number of times, can be simulated in PSPACE/poly. This is so despite the surprising fact that a bounded-space quantum computer can detect arbitrarily small changes in the bias of a coin. Joint work with Andrew Drucker.