Faster Quantum Walk Search on a Weighted Graph

Abstract

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 $\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.

8 pages, 5 figures

References in corpus (8)

• Spatial search by quantum walk
• Grover Search with Lackadaisical Quantum Walks
• Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs
• Connectivity is a Poor Indicator of Fast Quantum Search
• Hamiltonian Oracles
• Quantum Search with Multiple Walk Steps per Oracle Query
• Diagrammatic Approach to Quantum Search
• Quantum Walk Search with Time-Reversal Symmetry Breaking

Cited by in corpus (13)

• Laplacian versus Adjacency Matrix in Quantum Walk Search
• Coined Quantum Walks on Weighted Graphs
• Continuous-Time Quantum Search on Balanced Trees
• Spatial Search by Continuous-Time Quantum Walk with Multiple Marked Vertices
• Quantum Walk Search on Johnson Graphs
• Irreconcilable Difference Between Quantum Walks and Adiabatic Quantum Computing
• Engineering the Success of Quantum Walk Search Using Weighted Graphs
• Quantum Walk to Train a Classical Artificial Neural Network
• Controlled quantum search on structured databases
• Topological classification of time-asymmetry in unitary quantum processes
• Doubling the Success of Quantum Walk Search Using Internal-State Measurements
• Searching Weighted Barbell Graphs with Laplacian and Adjacency Quantum Walks
• Exact simulation of coined quantum walks with the continuous-time model