The need for structure in quantum speedups
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 is inva...
Main Authors: | Aaronson, Scott, Ambainis, Andris |
---|---|
Other Authors: | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
Format: | Article |
Language: | en_US |
Published: |
Electronic Colloquium on Computational Complexity
2012
|
Online Access: | http://hdl.handle.net/1721.1/72055 https://orcid.org/0000-0003-1333-4045 |
Similar Items
-
Forrelation: A Problem That Optimally Separates Quantum from Classical Computing
by: Aaronson, Scott, et al.
Published: (2015) -
The structure of promises in quantum speedups
by: Ben David, Shalev
Published: (2014) -
Quantum speedups in query complexity
by: Ben David, Shalev
Published: (2018) -
Weak Parity
by: Aaronson, Scott, et al.
Published: (2015) -
Simplifications and speedups of the pseudoflow algorithm
by: Hochbaum, Dorit S., et al.
Published: (2013)