Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR11-001 | 2nd January 2011 14:15

Impossibility of Succinct Quantum Proofs for Collision-Freeness

RSS-Feed




TR11-001
Authors: Scott Aaronson
Publication: 2nd January 2011 14:15
Downloads: 3199
Keywords: 


Abstract:

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 $\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.



ISSN 1433-8092 | Imprint