A Note on the Quantum Collision and Set Equality Problems

Mark Zhandry

The results showing a quantum query complexity of $\Theta (N^{1/3})$ for the collision problem do not apply to random functions. The issues are two-fold. First, the $\Omega (N^{1/3})$ lower bo…