Quantum Lower Bounds for Collision Problems
We establish tight lower bounds on the adaptive and non-adaptive quantum query complexities of Promised $k$-to-one Finding on an exactly $k$-to-one input string $x\in\mathbb Z_q^n$, for every fixed $k\ge2$ and every feasible alphabet size $q\ge n/k$. The lower bounds are $\Omega_k(n^{1/2-1/(2(2^k-1))})$ for unrestricte...