BQP and the Polynomial Hierarchy
The relationship between BQP and PH has been an open problem since the earliest days of quantum computing. We present evidence that quantum computers can solve problems outside the entire polynomial hierarchy, by relating this question to topics in circuit complexity, pseudorandomness, and Fourier a...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2010
|
| Online Access: | http://hdl.handle.net/1721.1/54236 https://orcid.org/0000-0003-1333-4045 |
| _version_ | 1826216745816293376 |
|---|---|
| author | Aaronson, Scott |
| 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 |
| author_sort | Aaronson, Scott |
| collection | MIT |
| description | The relationship between BQP and PH has been an open problem since the earliest days of quantum computing. We present evidence that quantum computers can solve problems outside the entire polynomial hierarchy, by relating this question to topics in circuit complexity, pseudorandomness, and Fourier analysis.
First, we show that there exists an oracle relation problem (i.e., a problem with many valid outputs) that is solvable in BQP, but not in PH. This also yields a non-oracle relation problem that is solvable in quantum logarithmic time, but not in AC[superscript 0].
Second, we show that an oracle decision problem separating BQP from PH would follow from the Generalized Linial-Nisan Conjecture, which we formulate here and which is likely of independent interest. The original Linial-Nisan Conjecture (about pseudorandomness against constant-depth circuits) was recently proved by Braverman, after being open for twenty years. |
| first_indexed | 2024-09-23T16:52:45Z |
| format | Article |
| id | mit-1721.1/54236 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:52:45Z |
| publishDate | 2010 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | mit-1721.1/542362022-10-03T08:51:37Z BQP and the Polynomial Hierarchy Aaronson, Scott Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Aaronson, Scott Aaronson, Scott The relationship between BQP and PH has been an open problem since the earliest days of quantum computing. We present evidence that quantum computers can solve problems outside the entire polynomial hierarchy, by relating this question to topics in circuit complexity, pseudorandomness, and Fourier analysis. First, we show that there exists an oracle relation problem (i.e., a problem with many valid outputs) that is solvable in BQP, but not in PH. This also yields a non-oracle relation problem that is solvable in quantum logarithmic time, but not in AC[superscript 0]. Second, we show that an oracle decision problem separating BQP from PH would follow from the Generalized Linial-Nisan Conjecture, which we formulate here and which is likely of independent interest. The original Linial-Nisan Conjecture (about pseudorandomness against constant-depth circuits) was recently proved by Braverman, after being open for twenty years. 2010-04-26T19:57:06Z 2010-04-26T19:57:06Z 2010 Article http://purl.org/eprint/type/ConferencePaper 978-1-4503-0050-6 http://hdl.handle.net/1721.1/54236 Aaronson, Scott. “BQP and the polynomial hierarchy.” in Proceedings of the 42nd ACM Symposium on Theory of Computing. Cambridge, Massachusetts, USA: ACM, 2010. 141-150. https://orcid.org/0000-0003-1333-4045 en_US Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC '10 Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Association for Computing Machinery arXiv |
| spellingShingle | Aaronson, Scott BQP and the Polynomial Hierarchy |
| title | BQP and the Polynomial Hierarchy |
| title_full | BQP and the Polynomial Hierarchy |
| title_fullStr | BQP and the Polynomial Hierarchy |
| title_full_unstemmed | BQP and the Polynomial Hierarchy |
| title_short | BQP and the Polynomial Hierarchy |
| title_sort | bqp and the polynomial hierarchy |
| url | http://hdl.handle.net/1721.1/54236 https://orcid.org/0000-0003-1333-4045 |
| work_keys_str_mv | AT aaronsonscott bqpandthepolynomialhierarchy |