Impossibility of Succinct Quantum Proofs for Collision-Freeness
We show that any quantum algorithm to decide whether a function f:\left[n\right] \rightarrow\left[ n\right] is a permutation or far from a permutation\ must make \Omega\left( n^{1/3}/w\right) queries to f, even if the algorithm is given a w-qubit quantum witness in support of f being a permutation...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Hasso-Plattner-Institut für Softwaresystemtechnik GmbH
2012
|
| Online Access: | http://hdl.handle.net/1721.1/72073 https://orcid.org/0000-0003-1333-4045 |
| _version_ | 1811079454101864448 |
|---|---|
| author | Aaronson, Scott |
| 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 |
| author_sort | Aaronson, Scott |
| collection | MIT |
| description | We show that any quantum algorithm to decide whether a function f:\left[n\right] \rightarrow\left[ n\right] is a permutation or far from a permutation\ must make \Omega\left( n^{1/3}/w\right) queries to f, even if the algorithm is given a w-qubit quantum witness in support of f being a permutation. This implies that there exists an oracle A such that \mathsfSZKA\mathsfQMAA , answering an eight-year-old open question of the author. Indeed, we show that relative to some oracle, \mathsfSZK is not in the counting class \mathsfA\mathsf0\mathsfPP defined by Vyalyi. The proof is a fairly simple extension of the quantum lower bound for the collision problem.. |
| first_indexed | 2024-09-23T11:15:17Z |
| format | Article |
| id | mit-1721.1/72073 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:15:17Z |
| publishDate | 2012 |
| publisher | Hasso-Plattner-Institut für Softwaresystemtechnik GmbH |
| record_format | dspace |
| spelling | mit-1721.1/720732022-09-27T18:10:23Z Impossibility of Succinct Quantum Proofs for Collision-Freeness Aaronson, Scott Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Aaronson, Scott Aaronson, Scott We show that any quantum algorithm to decide whether a function f:\left[n\right] \rightarrow\left[ n\right] is a permutation or far from a permutation\ must make \Omega\left( n^{1/3}/w\right) queries to f, even if the algorithm is given a w-qubit quantum witness in support of f being a permutation. This implies that there exists an oracle A such that \mathsfSZKA\mathsfQMAA , answering an eight-year-old open question of the author. Indeed, we show that relative to some oracle, \mathsfSZK is not in the counting class \mathsfA\mathsf0\mathsfPP defined by Vyalyi. The proof is a fairly simple extension of the quantum lower bound for the collision problem.. National Science Foundation (U.S.) (grant 0844626) United States. Defense Advanced Research Projects Agency (YFA grant) 2012-08-09T15:27:20Z 2012-08-09T15:27:20Z 2011-01 Article http://purl.org/eprint/type/JournalArticle 1433-8092 http://hdl.handle.net/1721.1/72073 Aaronson, Scott. "Impossibility of Succinct Quantum Proofs for Collision-Freeness." Electronic Colloquium on Computational Complexity (2011): TR11-001. https://orcid.org/0000-0003-1333-4045 en_US http://eccc.hpi-web.de/report/2011/001/ Electronic Colloquium on Computational Complexity Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Hasso-Plattner-Institut für Softwaresystemtechnik GmbH MIT web domain |
| spellingShingle | Aaronson, Scott Impossibility of Succinct Quantum Proofs for Collision-Freeness |
| title | Impossibility of Succinct Quantum Proofs for Collision-Freeness |
| title_full | Impossibility of Succinct Quantum Proofs for Collision-Freeness |
| title_fullStr | Impossibility of Succinct Quantum Proofs for Collision-Freeness |
| title_full_unstemmed | Impossibility of Succinct Quantum Proofs for Collision-Freeness |
| title_short | Impossibility of Succinct Quantum Proofs for Collision-Freeness |
| title_sort | impossibility of succinct quantum proofs for collision freeness |
| url | http://hdl.handle.net/1721.1/72073 https://orcid.org/0000-0003-1333-4045 |
| work_keys_str_mv | AT aaronsonscott impossibilityofsuccinctquantumproofsforcollisionfreeness |