Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with influences:
TR09-110 | 5th November 2009
Scott Aaronson, Andris Ambainis

The Need for Structure in Quantum Speedups

Revisions: 1

Is there a general theorem that tells us when we can hope for exponential speedups from quantum algorithms, and when we cannot? In this paper, we make two advances toward such a theorem, in the black-box model where most quantum algorithms operate.

First, we show that for any problem that ... more >>>

ISSN 1433-8092 | Imprint