Multidimensional Quantum Walks

While the quantum query complexity of 𝑘-distinctness is known to be 𝑂 (𝑛 3 4 -1 4 1 2 𝑘 -1 ) for any constant 𝑘 ≥ 4 [Belovs, FOCS 2012], the best previous upper bound on the time complexity was 𝑂 (𝑛 1-1/𝑘 ).

We give a new upper bound of 𝑂 (𝑛 3 4 -1 4 1 2 𝑘 -1 ) on the time complexity, matching the query complexity up to polylogarithmic factors. In order to achieve this upper bound, we give a new technique for designing quantum walk search algorithms, which is an extension of the electric network framework. We also show how to solve the welded trees problem in 𝑂 (𝑛) queries and 𝑂 (𝑛 2 ) time using this new technique, showing that the new quantum walk framework can achieve exponential speedups.