Quantum search on Hanoi network

DOI10.1142/S0219749919500606MaRDI QIDQ5219344zbMATH OpenOpenAlexFDO

Authors Pulak Ranjan Giri, Vladimir E. Korepin

Publication date 11 March 2020

Published in International Journal of Quantum Information (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1903.08020

zbMATH Keywords

lackadaisical quantum walkquantum algorithmquantum walk

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Sums of independent random variables; random walks (60G50) Searching and sorting (68P10) Quantum computation (81P68)

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 $mathcalOleft(N^{0.79}sqrtlogNight)$ and $mathcalOleft(N^{0.65}sqrtlogNight)$ respectively. And for the search by lackadaisical quantum walks the running time scales as $mathcalOleft(N^{0.57}logNight)$ and $mathcalOleft(N^{0.50}logNight)$ respectively.

Recommendations

• Lackadaisical quantum walk for spatial search
• Faster search by lackadaisical quantum walk
• Spatial search on a honeycomb network
• Spatial quantum search in a triangular network
• Search via Quantum Walk

Cites work

• Coins make quantum walks faster
• Faster quantum-walk algorithm for the two-dimensional spatial search
• Faster search by lackadaisical quantum walk
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 2103521 (Why is no real title available?)
• Lackadaisical quantum walk for spatial search
• Quantum partial search for uneven distribution of multiple target items
• Quantum search of spatial regions
• Quantum walks and search algorithms
• Search by quantum walks on two-dimensional grid without amplitude amplification
• Spatial quantum search in a triangular network
• Spatial search and the Dirac equation
• Spatial search on a honeycomb network

Cited in

(5)

• HIERARCHICAL QUANTUM SEARCH
• Quantum walk search on a two-dimensional grid with extra edges
• Quantum walk search for exceptional configurations
• Parrondo's game on exceptional configurations of quantum walk search
• Multi-target quantum walk search on Johnson graph

This page was built for publication: Quantum search on Hanoi network

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5219344)