We present two quantum walk algorithms for 3-Distinctness. Both algorithms have time complexity O(n~(5/7)), improving the previous O(n~(3/4)) and matching the best known upper bound for query complexity (obtained via learning graphs) up to log factors. The first algorithm is based on a connection between quantum walks and electric networks. The second algorithm uses an extension of the quantum walk search framework that facilitates quantum walks with nested updates.
展开▼
