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 |