Multidimensional Quantum Walks

While the quantum query complexity of k -distinctness is known to be O ( n 3/4 − 1/4(2 k −1) ) for any constant k ≥ 4 [Belovs, FOCS 2012], the best previous upper bound on the time complexity was O ( n 1−1/ k ). We give a new upper bound of O ( n 3/4 − 1/4(2 k −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 O ( n ) queries and O ( n 2 ) time using this new technique, showing that the new quantum walk framework can achieve exponential speedups.

Authors

• Stacey Jeffery
• Sebastian Zur

Keywords

• element distinctness
• phase estimation
• quantum algorithms
• quantum random walk
• superpolynomial speedup
• welded trees