Faster Search by Lackadaisical Quantum Walk

Abstract

In the typical model, a discrete-time coined quantum walk searching the 2D grid for a marked vertex achieves a success probability of $O(1/\log N)$ in $O(\sqrt{N\log N})$ steps, which with amplitude amplification yields an overall runtime of $O(\sqrt{N}\log N)$. We show that making the quantum walk lackadaisical or lazy by adding a self-loop of weight $4/N$ to each vertex speeds up the search, causing the success probability to reach a constant near $1$ in $O(\sqrt{N\log N})$ steps, thus yielding an $O(\sqrt{\log N})$ improvement over the typical, loopless algorithm. This improved runtime matches the best known quantum algorithms for this search problem. Our results are based on numerical simulations since the algorithm is not an instance of the abstract search algorithm.

9 pages, 4 figures

References in corpus (7)

• Spatial search by quantum walk
• Faster quantum walk algorithm for the two dimensional spatial search
• Spatial search and the Dirac equation
• Connectivity is a Poor Indicator of Fast Quantum Search
• Coined Quantum Walks on Weighted Graphs
• Equivalence of Szegedy's and Coined Quantum Walks
• Quantum search on the two-dimensional lattice using the staggered model with Hamiltonians

Cited by in corpus (26)

• Lackadaisical quantum walk for spatial search
• Search by Lackadaisical Quantum Walk with Nonhomogeneous Weights
• Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk
• Classical Artificial Neural Network Training Using Quantum Walks as a Search Procedure
• One-Dimensional Lazy Quantum walk in Ternary System
• Quantum walk based state transfer algorithms on the complete M-partite graph
• Lazy Open Quantum Walks
• Quantum walk search by Grover search on coin space
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids
• Lackadaisical quantum walks on 2D grids with multiple marked vertices
• Search of clustered marked states with lackadaisical quantum walks
• Quantum walk search on a two-dimensional grid with extra edges
• Quantum walk state transfer on a hypercube
• Coined quantum walks on the line: Disorder, entanglement, and localization
• Lackadaisical quantum walk in the hypercube to search for multiple marked vertices
• Quantum search on Hanoi network
• Search by Lackadaisical Quantum Walk with Symmetry Breaking
• Nonlinear three-state quantum walks
• Universal dynamical scaling laws in three-state quantum walks
• Quantum walk-based protocol for secure communication between any two directly connected nodes on a network
• Quantum walk search for exceptional configurations
• Search and state transfer between hubs by quantum walks
• Lackadaisical quantum walks on triangular and honeycomb 2D grids
• Spectral analysis of three-state quantum walks with general coin matrices
• Faster Search of Clustered Marked States with Lackadaisical Quantum Walks
• Lackadaisical quantum walks with multiple marked vertices