Faster Quantum Walk Search on a Weighted Graph

A randomly walking quantum particle evolving by Schrödinger's equation searches for a unique marked vertex on the "simplex of complete graphs" in time $Θ(N^{3/4})$. In this paper, we give a weighted version of this graph that preserves vertex-transitivity, and we show that the time to search on it can be reduced to nearly $Θ(\sqrt{N})$. To prove this, we introduce two novel extensions to degenerate perturbation theory: an adjustment that distinguishes the weights of the edges, and a method to determine how precisely the jumping rate of the quantum walk must be chosen.

No reviews yet.

No comments yet.