Multidimensional Quantum Walks, with Application to $k$-Distinctness

Stacey Jeffery, Sebastian Zur

While the quantum query complexity of $k$-distinctness is known to be $O\left(n^{3/4-1/4(2^k-1)}\right)$ for any constant $k\ge 4$, the best previous upper bound on the time comp…