Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk
arXiv:2002.11227 · doi:10.1007/s11128-020-02841-z
Abstract
The lackadaisical quantum walk is a discrete-time, coined quantum walk on a graph with a weighted self-loop at each vertex. It uses a generalized Grover coin and the flip-flop shift, which makes it equivalent to Szegedy's quantum Markov chain. It has been shown that a lackadaisical quantum walk can improve spatial search on the complete graph, discrete torus, cycle, and regular complete bipartite graph. In this paper, we observe that these are all vertex-transitive graphs, and when there is a unique marked vertex, the optimal weight of the self-loop equals the degree of the loopless graph divided by the total number of vertices. We propose that this holds for all vertex-transitive graphs with a unique marked vertex. We present a number of numerical simulations supporting this hypothesis, including search on periodic cubic lattices of arbitrary dimension, strongly regular graphs, Johnson graphs, and the hypercube.
arXiv comment17 pages, 5 figures
References in corpus (17)
- A Quantum Random Walk Search Algorithm
- From quantum cellular automata to quantum lattice gases
- One-Dimensional Three-State Quantum Walk
- On the absence of homogeneous scalar unitary cellular automata
- Grover Search with Lackadaisical Quantum Walks
- Global Symmetry is Unnecessary for Fast Quantum Search
- Quantum searches on highly symmetric graphs
- Faster Search by Lackadaisical Quantum Walk
- Coined Quantum Walks on Weighted Graphs
- Quantum Walk Search on the Complete Bipartite Graph
- Quantum Walk Search on Johnson Graphs
- Search by Lackadaisical Quantum Walk with Nonhomogeneous Weights
- Diagrammatic Approach to Quantum Search
- Lackadaisical quantum walk for spatial search
- Analysis of Lackadaisical Quantum Walks
- Exceptional Quantum Walk Search on the Cycle
- Doubling the Success of Quantum Walk Search Using Internal-State Measurements
Cited by in corpus (11)
- One-Dimensional Lazy Quantum walk in Ternary System
- Quantum walk based state transfer algorithms on the complete M-partite graph
- On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids
- Lackadaisical quantum walks on 2D grids with multiple marked vertices
- Quantum walk state transfer on a hypercube
- Lackadaisical quantum walk in the hypercube to search for multiple marked vertices
- Search by Lackadaisical Quantum Walk with Symmetry Breaking
- Multi-target quantum walk search on Johnson graph
- Search and state transfer between hubs by quantum walks
- Faster Search of Clustered Marked States with Lackadaisical Quantum Walks
- Quantum spatial best-arm identification via quantum walks