Search by Lackadaisical Quantum Walk with Symmetry Breaking
arXiv:2108.13856 · doi:10.1103/PhysRevA.104.062211
Abstract
The lackadaisical quantum walk is a lazy version of a discrete-time, coined quantum walk, where each vertex has a weighted self-loop that permits the walker to stay put. They have been used to speed up spatial search on a variety of graphs, including periodic lattices, strongly regular graphs, Johnson graphs, and the hypercube. In these prior works, the weights of the self-loops preserved the symmetries of the graphs. In this paper, we show that the self-loops can break all the symmetries of vertex-transitive graphs while providing the same computational speedups. Only the weight of the self-loop at the marked vertex matters, and the remaining self-loop weights can be chosen randomly, as long as they are small compared to the degree of the graph.
arXiv comment15 pages, 8 figures
References in corpus (16)
- A Quantum Random Walk Search Algorithm
- From quantum cellular automata to quantum lattice gases
- Universal quantum computation using the discrete time quantum walk
- On the absence of homogeneous scalar unitary cellular automata
- Grover Search with Lackadaisical Quantum Walks
- Faster Search by Lackadaisical Quantum Walk
- Coined Quantum Walks on Weighted Graphs
- Discrete-query quantum algorithm for NAND trees
- Quantum Walk Search on the Complete Bipartite Graph
- Lackadaisical quantum walk for spatial search
- Search by Lackadaisical Quantum Walk with Nonhomogeneous Weights
- Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk
- Analysis of Lackadaisical Quantum Walks
- Lackadaisical quantum walks on 2D grids with multiple marked vertices
- Search of clustered marked states with lackadaisical quantum walks
- Quantum search on Hanoi network