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: | , |
|---|---|
| Other Authors: | |
| 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 |
| _version_ | 1811088086154608640 |
|---|---|
| author | Aaronson, Scott Ambainis, Andris |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Aaronson, Scott Ambainis, Andris |
| author_sort | Aaronson, Scott |
| collection | MIT |
| description | 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 invariant under permuting inputs and outputs (like the collision or the element distinctness problems), the quantum query complexity is at least the 9th root of the classical randomized query complexity. This resolves a conjecture of Watrous from 2002.
Second, inspired by recent work of O'Donnell et al. and Dinur et al., we conjecture that every bounded low-degree polynomial has a "highly influential" variable. Assuming this conjecture, we show that every T-query quantum algorithm can be simulated on most inputs by a poly(T)-query classical algorithm, and that one essentially cannot hope to prove P!=BQP relative to a random oracle. |
| first_indexed | 2024-09-23T13:56:02Z |
| format | Article |
| id | mit-1721.1/72055 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:56:02Z |
| publishDate | 2012 |
| publisher | Electronic Colloquium on Computational Complexity |
| record_format | dspace |
| spelling | mit-1721.1/720552022-09-28T17:10:34Z The need for structure in quantum speedups Aaronson, Scott Ambainis, Andris Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Aaronson, Scott Aaronson, Scott 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 invariant under permuting inputs and outputs (like the collision or the element distinctness problems), the quantum query complexity is at least the 9th root of the classical randomized query complexity. This resolves a conjecture of Watrous from 2002. Second, inspired by recent work of O'Donnell et al. and Dinur et al., we conjecture that every bounded low-degree polynomial has a "highly influential" variable. Assuming this conjecture, we show that every T-query quantum algorithm can be simulated on most inputs by a poly(T)-query classical algorithm, and that one essentially cannot hope to prove P!=BQP relative to a random oracle. 2012-08-08T21:01:16Z 2012-08-08T21:01:16Z 2009-01 Article http://purl.org/eprint/type/JournalArticle 1433-8092 http://hdl.handle.net/1721.1/72055 Aaronson, Scott and Andris Ambainis. "The need for structure in quantum speedups." Electronic Colloquium on Computational Complexity, Report No. 110 (2009). https://orcid.org/0000-0003-1333-4045 en_US http://eccc.hpi-web.de/report/2009/110/ Electronic Colloquium on Computational Complexity Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Electronic Colloquium on Computational Complexity MIT web domain |
| spellingShingle | Aaronson, Scott Ambainis, Andris The need for structure in quantum speedups |
| title | The need for structure in quantum speedups |
| title_full | The need for structure in quantum speedups |
| title_fullStr | The need for structure in quantum speedups |
| title_full_unstemmed | The need for structure in quantum speedups |
| title_short | The need for structure in quantum speedups |
| title_sort | need for structure in quantum speedups |
| url | http://hdl.handle.net/1721.1/72055 https://orcid.org/0000-0003-1333-4045 |
| work_keys_str_mv | AT aaronsonscott theneedforstructureinquantumspeedups AT ambainisandris theneedforstructureinquantumspeedups AT aaronsonscott needforstructureinquantumspeedups AT ambainisandris needforstructureinquantumspeedups |