Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with PP/poly:
TR04-026 | 17th February 2004
Scott Aaronson

Limitations of Quantum Advice and One-Way Communication

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 is contained in ... more >>>

ISSN 1433-8092 | Imprint