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 |
| Summary: | 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.. |
|---|