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...

ver descrição completa

Detalhes bibliográficos
Principais autores: Aaronson, Scott, Ambainis, Andris
Outros Autores: Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
Formato: Artigo
Idioma:en_US
Publicado em: Electronic Colloquium on Computational Complexity 2012
Acesso em linha:http://hdl.handle.net/1721.1/72055
https://orcid.org/0000-0003-1333-4045