2015/07/27 by Thomas G. Wong · 1 citation
Physics and Astronomy · #quant-ph
paper · pdf · doi:10.1103/physreva.92.032320
published as Phys. Rev. A 92, 032320 (2015) · 8 pages, 5 figures
arxiv created 2015/07/27 · arxiv updated 2015/09/22
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 Θ(N3/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 Θ(√(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.