This paper introduces a new technique for removing existential quantifiers
over quantum states. Using this technique, we show that there is no way
to pack an exponential number of bits into a polynomial-size quantum
state, in such a way that the value of any one of those bits can later be
proven with the help of a polynomial-size quantum witness. We also show
that any problem in QMA with polynomial-size quantum advice, is also in
PSPACE with polynomial-size classical advice. This builds on our earlier
result that BQP/qpoly is contained in PP/poly, and offers an intriguing
counterpoint to the recent discovery of Raz that QIP/qpoly = ALL.
Finally, we show that QCMA/qpoly is contained in PP/poly and that
QMA/rpoly = QMA/poly.