  Although a quantum state requires exponentially many classical bits to
describe, the laws of quantum mechanics impose severe restrictions on how that
state can be accessed. This paper shows in three settings that quantum messages
have only limited advantages over classical ones.
  First, we show that $\mathsf{BQP/qpoly}\subseteq\mathsf{PP/poly}$, where
$\mathsf{BQP/qpoly}$ is the class of problems solvable in quantum polynomial
time, given a polynomial-size "quantum advice state" that depends only on the
input length. This resolves a question of Buhrman, and means that we should not
hope for an unrelativized separation between quantum and classical advice.
Underlying our complexity result is a general new relation between
deterministic and quantum one-way communication complexities, which applies to
partial as well as total functions.
  Second, we construct an oracle relative to which $\mathsf{NP}\not \subset
\mathsf{BQP/qpoly}$. To do so, we use the polynomial method to give the first
correct proof of a direct product theorem for quantum search. This theorem has
other applications; for example, it can be used to fix a result of Klauck about
quantum time-space tradeoffs for sorting.
  Third, we introduce a new trace distance method for proving lower bounds on
quantum one-way communication complexity. Using this method, we obtain optimal
quantum lower bounds for two problems of Ambainis, for which no nontrivial
lower bounds were previously known even for classical randomized protocols.
  A preliminary version of this paper appeared in the 2004 Conference on
Computational Complexity (CCC).
