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...
| Hoofdauteur: | |
|---|---|
| Andere auteurs: | |
| Formaat: | Artikel |
| Taal: | en_US |
| Gepubliceerd in: |
Hasso-Plattner-Institut für Softwaresystemtechnik GmbH
2012
|
| Online toegang: | http://hdl.handle.net/1721.1/72073 https://orcid.org/0000-0003-1333-4045 |