Adversary Lower Bounds for the Collision and the Set Equality Problems

Aleksandrs Belovs, Ansis Rosmanis

We prove tight $\Omega (n^{1/3})$ lower bounds on the quantum query complexity of the Collision and the Set Equality problems, provided that the size of the alphabet is large enough. We…