ECCC-Report TR11-001https://eccc.weizmann.ac.il/report/2011/001Comments and Revisions published for TR11-001en-usSun, 02 Jan 2011 14:15:35 +0200
Paper TR11-001
| Impossibility of Succinct Quantum Proofs for Collision-Freeness |
Scott Aaronson
https://eccc.weizmann.ac.il/report/2011/001We 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 $\mathsf{SZK}^{A}\not \subset \mathsf{QMA}^{A}$, answering an eight-year-old open question of the author. Indeed, we show that relative to some oracle, $\mathsf{SZK}$ is not in the counting class $\mathsf{A}_{\mathsf{0}}\mathsf{PP}$ defined by Vyalyi. The proof is a fairly simple extension of the quantum lower bound for the collision problem.Sun, 02 Jan 2011 14:15:35 +0200https://eccc.weizmann.ac.il/report/2011/001