Quantum walk search on a two-dimensional grid with extra edges

Abstract

Quantum walk has been successfully used to search for targets on graphs with vertices identified as the elements of a database. This spacial search on a two-dimensional periodic grid takes $\mathcal{O}\left(\sqrt{N\log N}\right)$ oracle consultations to find a target vertex from $N$ number of vertices with $\mathcal{O}(1)$ success probability, while reaching optimal speed of $\mathcal{O}(\sqrt{N})$ on $d\ge 3$ dimensional square lattice. Our numerical analysis based on lackadaisical quantum walks searches $M$ vertices on a 2-dimensional grid with optimal speed of $\mathcal{O}(\sqrt{N/M})$, provided the grid is attached with additional long range edges. Based on the numerical analysis performed with multiple sets of randomly generated targets for a wide range of $N$ and $M$ we suggest that the optimal time complexity of $\mathcal{O}(\sqrt{N/M})$ with constant success probability can be achieved for quantum search on a two-dimensional periodic grid with long-range edges.

8 pages, 7 figures, published in IJTP

References in corpus (13)

• Quantum Computing in the NISQ era and beyond
• Spatial search by quantum walk
• Faster quantum walk algorithm for the two dimensional spatial search
• Spatial search and the Dirac equation
• Grover Search with Lackadaisical Quantum Walks
• Connectivity is a Poor Indicator of Fast Quantum Search
• A Review on Quantum Search Algorithms
• Faster Search by Lackadaisical Quantum Walk
• Coined Quantum Walks on Weighted Graphs
• Anomalous Diffusion on the Hanoi Networks
• Lackadaisical quantum walk for spatial search
• Spatial Search Algorithms on Hanoi Networks
• Quantum search on Hanoi network

Cited by in corpus (4)

• Quantum walk search by Grover search on coin space
• Quantum walk search based edge detection of images
• Multi-target quantum walk search on Johnson graph
• Quantum walk search for exceptional configurations