Forrelation: A Problem That Optimally Separates Quantum from Classical Computing
We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using a property-testing problem called Forrelation, where one needs to decide whether one Boolean function is highly correlated with the Fourier transform of a second function. This pro...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2015
|
| Online Access: | http://hdl.handle.net/1721.1/99662 https://orcid.org/0000-0003-1333-4045 |
| _version_ | 1826204583430455296 |
|---|---|
| author | Aaronson, Scott Ambainis, Andris |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Aaronson, Scott Ambainis, Andris |
| author_sort | Aaronson, Scott |
| collection | MIT |
| description | We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using a property-testing problem called Forrelation, where one needs to decide whether one Boolean function is highly correlated with the Fourier transform of a second function. This problem can be solved using 1 quantum query, yet we show that any randomized algorithm needs Ω(√(N)log(N)) queries (improving an Ω(N[superscript 1/4]) lower bound of Aaronson). Conversely, we show that this 1 versus Ω(√(N)) separation is optimal: indeed, any t-query quantum algorithm whatsoever can be simulated by an O(N[superscript 1-1/2t])-query randomized algorithm. Thus, resolving an open question of Buhrman et al. from 2002, there is no partial Boolean function whose quantum query complexity is constant and whose randomized query complexity is linear. We conjecture that a natural generalization of Forrelation achieves the optimal t versus Ω(N[superscript 1-1/2t]) separation for all t. As a bonus, we show that this generalization is BQP-complete. This yields what's arguably the simplest BQP-complete problem yet known, and gives a second sense in which Forrelation "captures the maximum power of quantum computation." |
| first_indexed | 2024-09-23T12:57:46Z |
| format | Article |
| id | mit-1721.1/99662 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:57:46Z |
| publishDate | 2015 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/996622022-10-01T12:09:08Z Forrelation: A Problem That Optimally Separates Quantum from Classical Computing Aaronson, Scott Ambainis, Andris Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Aaronson, Scott We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using a property-testing problem called Forrelation, where one needs to decide whether one Boolean function is highly correlated with the Fourier transform of a second function. This problem can be solved using 1 quantum query, yet we show that any randomized algorithm needs Ω(√(N)log(N)) queries (improving an Ω(N[superscript 1/4]) lower bound of Aaronson). Conversely, we show that this 1 versus Ω(√(N)) separation is optimal: indeed, any t-query quantum algorithm whatsoever can be simulated by an O(N[superscript 1-1/2t])-query randomized algorithm. Thus, resolving an open question of Buhrman et al. from 2002, there is no partial Boolean function whose quantum query complexity is constant and whose randomized query complexity is linear. We conjecture that a natural generalization of Forrelation achieves the optimal t versus Ω(N[superscript 1-1/2t]) separation for all t. As a bonus, we show that this generalization is BQP-complete. This yields what's arguably the simplest BQP-complete problem yet known, and gives a second sense in which Forrelation "captures the maximum power of quantum computation." National Science Foundation (U.S.) (Waterman Award) National Science Foundation (U.S.) (Grant 1249349) 2015-11-02T19:43:04Z 2015-11-02T19:43:04Z 2015-06 Article http://purl.org/eprint/type/ConferencePaper 9781450335362 http://hdl.handle.net/1721.1/99662 Scott Aaronson and Andris Ambainis. 2015. Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC '15). ACM, New York, NY, USA, 307-316. https://orcid.org/0000-0003-1333-4045 en_US http://dx.doi.org/10.1145/2746539.2746547 Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC '15) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) MIT web domain |
| spellingShingle | Aaronson, Scott Ambainis, Andris Forrelation: A Problem That Optimally Separates Quantum from Classical Computing |
| title | Forrelation: A Problem That Optimally Separates Quantum from Classical Computing |
| title_full | Forrelation: A Problem That Optimally Separates Quantum from Classical Computing |
| title_fullStr | Forrelation: A Problem That Optimally Separates Quantum from Classical Computing |
| title_full_unstemmed | Forrelation: A Problem That Optimally Separates Quantum from Classical Computing |
| title_short | Forrelation: A Problem That Optimally Separates Quantum from Classical Computing |
| title_sort | forrelation a problem that optimally separates quantum from classical computing |
| url | http://hdl.handle.net/1721.1/99662 https://orcid.org/0000-0003-1333-4045 |
| work_keys_str_mv | AT aaronsonscott forrelationaproblemthatoptimallyseparatesquantumfromclassicalcomputing AT ambainisandris forrelationaproblemthatoptimallyseparatesquantumfromclassicalcomputing |