LIMITATIONS OF QUANTUM ADVICE AND ONE-WAY COMMUNICATION
7 Acknowledgments
I thank Oded Regev for pointing out the connection between advice and one-way communication; An-
dris Ambainis for posing the coset and subset problems; Harry Buhrman for asking about an upper
bound on BQP/qpoly ; Lance Fortnow for pointing out that P/poly 6= PP/poly implies PP 6⊂ P/poly;
Hartmut Klauck and Ronald de Wolf for discussions that led to improvements of Lemma 4.5; Iordanis
Kerenidis and Andreas Winter for correcting me about the constant factors in R
1
2
(EQ) and Q
1
2
(EQ); and
the anonymous reviewers and ToC editors for helpful comments and corrections.
References
[1] * S. AARONSON: Quantum lower bound for the collision problem. In Proc. 34th ACM STOC, pp.
635–642, 2002. [STOC:509907.509999, arXiv:quant-ph/0111102]. 11, 6
[2] * S. AARONSON: Limitations of quantum advice and one-way communication. In 19th IEEE Conf.
Comput. Complexity (CCC), pp. 320–332, 2004. [CCC:10.1109/CCC.2004.1313854, arXiv:quant-
ph/0402095]. 1
[3] * S. AARONSON: Quantum computing, postselection, and probabilistic polynomial-time. Submit-
ted, 2004. [arXiv:quant-ph/0412187]. 3.1
[4] * L. ADLEMAN, J. DEMARRAIS, AND M.-D. HUANG: Quantum computability. SIAM J. Com-
puting, 26(5):1524–1540, 1997. [SICOMP:10.1137/S0097539795293639]. 3.1
[5] * A. AMBAINIS, A. NAYAK, A. TA-SHMA, AND U. V. VAZIRANI: Quantum dense coding and
quantum finite automata. J. ACM, 49:496–511, 2002. Earlier version in 31st ACM STOC, 1999,
pp. 376-383. [JACM:581771.581773, arXiv:quant-ph/9804043]. 1, 2.3
[6] * Z. BAR-YOSSEF, T. S. JAYRAM, AND I. KERENIDIS: Exponential separation of quantum
and classical one-way communication complexity. In 36th ACM STOC, pp. 128–137, 2004.
[STOC:1007352.1007379, ECCC:TR04-036]. 1, 2.1, 6
[7] * R. BEALS, H. BUHRMAN, R. CLEVE, M. MOSCA, AND R. DE WOLF: Quantum lower bounds
by polynomials. J. ACM, 48(4):778–797, 2001. Earlier version in 39th IEEE FOCS, 1998, pp.
352-361. [JACM:502090.502097, arXiv:quant-ph/9802049]. 1, 4, 4
[8] * C. BENNETT, E. BERNSTEIN, G. BRASSARD, AND U. VAZIRANI: Strengths and weaknesses of
quantum computing. SIAM J. Computing, 26(5):1510–1523, 1997. [SICOMP:30093, arXiv:quant-
ph/9701001]. 1, 4, 6
[9] * C. H. BENNETT, G. BRASSARD, C. CR
´
EPEAU, R. JOZSA, A. PERES, AND W. WOOTTERS:
Teleporting an unknown quantum state by dual classical and EPR channels. Phys. Rev. Lett.,
70:1895–1898, 1993. [PRL:10.1103/PhysRevLett.70.1895]. 1
[10] * C. H. BENNETT AND J. GILL: Relative to a random oracle A, P
A
6= NP
A
6= coNP
A
with proba-
bility 1. SIAM J. Computing, 10(1):96–113, 1981. [SICOMP:10/0210008]. 11
THEORY OF COMPUTING, Volume 1 (2005), pp. 1–28 25