Engineering the Success of Quantum Walk Search Using Weighted Graphs
arXiv:1605.04862 · doi:10.1103/PhysRevA.94.022304
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.
arXiv comment11 pages, 8 figures
References in corpus (23)
- Strengths and Weaknesses of Quantum Computing
- Quantum Computation and Decision Trees
- Environment-Assisted Quantum Walks in Photosynthetic Energy Transfer
- Perfect state transfer in quantum spin networks
- Exponential algorithmic speedup by quantum walk
- Spatial search by quantum walk
- On the relationship between continuous- and discrete-time quantum walk
- Spatial search by quantum walk is optimal for almost all graphs
- Grover Search with Lackadaisical Quantum Walks
- Global Symmetry is Unnecessary for Fast Quantum Search
- Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs
- Connectivity is a Poor Indicator of Fast Quantum Search
- Quantum Transport Enhancement by Time-Reversal Symmetry Breaking
- Laplacian versus Adjacency Matrix in Quantum Walk Search
- Chiral Quantum Walks
- Hamiltonian Oracles
- Continuous-Time Quantum Search on Balanced Trees
- Spatial Search by Continuous-Time Quantum Walk with Multiple Marked Vertices
- Quantum Search with Multiple Walk Steps per Oracle Query
- Quantum Walk Search on Johnson Graphs
- Faster Quantum Walk Search on a Weighted Graph
- Diagrammatic Approach to Quantum Search
- Quantum Walk Search with Time-Reversal Symmetry Breaking
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