Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > BQP/QPOLY:
Reports tagged with BQP/qpoly:
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 >>>


TR18-099 | 19th May 2018
Scott Aaronson

PDQP/qpoly = ALL

We show that combining two different hypothetical enhancements to quantum computation---namely, quantum advice and non-collapsing measurements---would let a quantum computer solve any decision problem whatsoever in polynomial time, even though neither enhancement yields extravagant power by itself. This complements a related result due to Raz. The proof uses locally decodable ... more >>>




ISSN 1433-8092 | Imprint