Theory of Computing
-------------------
Title     : Limitations of Quantum Advice and One-Way Communication
Authors   : Scott Aaronson
Volume    : 1
Number    : 1
Pages     : 1-28
URL       : https://theoryofcomputing.org/articles/v001a001

Abstract
--------
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 BQP/qpoly \subseteq PP/poly, where
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 NP\not
\subset 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).