Quantum search on Hanoi network

Abstract

Hanoi network has a one-dimensional periodic lattice as its main structure with additional long-range edges, which allow having efficient quantum walk algorithm that can find a target state on the network faster than the exhaustive classical search. In this article, we use regular quantum walks and lackadaisical quantum walks respectively to search for a target state. From the curve fitting of the numerical results for Hanoi network of degree three and four we find that their running time for the regular quantum walks followed by amplitude amplification scales as $\mathcal{O}\left(N^{0.79}\sqrt{\log N}\right)$ and $\mathcal{O}\left(N^{0.65}\sqrt{\log N}\right)$ respectively. And for the search by lackadaisical quantum walks the running time scales as $\mathcal{O}\left(N^{0.57}\log N\right)$ and $\mathcal{O}\left(N^{0.50}\log N\right)$ respectively.

8 pages, 4 figures, accepted version

References in corpus (10)

• 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
• Faster Search by Lackadaisical Quantum Walk
• Coined Quantum Walks on Weighted Graphs
• Anomalous Diffusion on the Hanoi Networks
• Lackadaisical quantum walk for spatial search
• Complexity Bounds on Quantum Search Algorithms in finite-dimensional Networks
• Quantum Search Algorithms on Hierarchical Networks

Cited by in corpus (4)

• Quantum walk search on a two-dimensional grid with extra edges
• Search by Lackadaisical Quantum Walk with Symmetry Breaking
• Multi-target quantum walk search on Johnson graph
• Quantum walk search for exceptional configurations