Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with root-finding:
TR11-008 | 27th January 2011
Scott Aaronson, Andrew Drucker

Advice Coins for Classical and Quantum Computation

We study the power of classical and quantum algorithms equipped with nonuniform advice, in the form of a coin whose bias encodes useful information. This question takes on particular importance in the quantum case, due to a surprising result that we prove: a quantum finite automaton with just two states ... more >>>

ISSN 1433-8092 | Imprint