6533b81ffe1ef96bd1277c62
RESEARCH PRODUCT
Faster Quantum Walk Search on a Weighted Graph
Thomas G. Wongsubject
PhysicsVertex (graph theory)Quantum particleQuantum PhysicsDegenerate energy levelsFOS: Physical sciencesGraph theory01 natural sciencesAtomic and Molecular Physics and OpticsGraph010305 fluids & plasmasCombinatoricsQuantum mechanics0103 physical sciencesQuantum walk010306 general physicsQuantum Physics (quant-ph)description
A randomly walking quantum particle evolving by Schr\"odinger's equation searches for a unique marked vertex on the "simplex of complete graphs" in time $\Theta(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 $\Theta(\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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2015-07-27 |