Seminar: January 9, 2009, 2:30pm
Scott Aaronson, MIT
The Limits of Advice
Since the work of Karp and Lipton in the 1980s, complexity theorists have grown to love the /poly operator, which adds a polynomial-size "advice string" to any complexity class. But it's interesting to consider much more general kinds of "advice objects" than just strings. In this talk, I'll present a new framework for understanding the limitations of advice objects. Results include the following:
- Given as "advice" a black box that computes an arbitrary Boolean function f drawn from a set of singly exponential size, we can simulate that black box using an *untrusted* black box combined with a polynomial-size advice string.
- The complexity class BQP/qpoly, or quantum polynomial-time with polynomial-size quantum advice, is contained in QMA/poly. Indeed, given any language L in BQP/qpoly, one can give a local Hamiltonian H on poly(n) qubits such that any ground state of H is a valid quantumadvice 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 my student Andy Drucker.