The Limits of Advice

COMPUTER SCIENCE/DISCRETE MATH I
Topic:	The Limits of Advice
Speaker:	Scott Aaronson
Affiliation:	Massachusetts Institute of Technology
Date:	Monday, January 26
Time/Room:	11:15am - 12:15pm/S-101

---

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.