Engineering the Success of Quantum Walk Search Using Weighted Graphs

Abstract

Continuous-time quantum walks are natural tools for spatial search, where one searches for a marked vertex in a graph. Sometimes, the structure of the graph causes the walker to get trapped, such that the probability of finding the marked vertex is limited. We give an example with two linked cliques, proving that the captive probability can be liberated by increasing the weights of the links. This allows the search to succeed with probability 1 without increasing the energy scaling of the algorithm. Further increasing the weights, however, slows the runtime, so the optimal search requires weights that are neither too weak nor too strong.

11 pages, 8 figures

References in corpus (6)

• Environment-Assisted Quantum Walks in Photosynthetic Energy Transfer
• Exponential algorithmic speedup by quantum walk
• Spatial search by quantum walk
• Connectivity is a Poor Indicator of Fast Quantum Search
• Hamiltonian Oracles
• Diagrammatic Approach to Quantum Search

Cited by in corpus (6)

• On the optimality of spatial search by continuous-time quantum walk
• Coined Quantum Walks on Weighted Graphs
• Engineering topological states and quantum-inspired information processing using classical circuits
• Controlled quantum search on structured databases
• Searching Weighted Barbell Graphs with Laplacian and Adjacency Quantum Walks
• Equivalent Laplacian and Adjacency Quantum Walks on Irregular Graphs