Summary: Impossibility of Succinct Quantum Proofs for Collision-Freeness
We show that any quantum algorithm to decide whether a function f : [n] [n] is a
permutation or far from a permutation must make n1/3
/w 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 SZKA
, answering an eight-year-old open question
of the author. Indeed, we show that relative to some oracle, SZK is not in the counting class
A0PP defined by Vyalyi. The proof is a fairly simple extension of the quantum lower bound for
the collision problem.
The collision problem is to decide whether a black-box function f : [n] [n] is one-to-one (i.e.,
a permutation) or two-to-one function, promised that one of these is the case. Together with its
close variants, the collision problem is one of the central problems studied in quantum computing
theory; it abstractly models numerous other problems such as graph isomorphism and the breaking
of cryptographic hash functions.
In this paper, we will mostly deal with a slight generalization of the collision problem that we