Faster search by lackadaisical quantum walk

DOI10.1007/S11128-018-1840-YMaRDI QIDQ1746914zbMATHOpenAlexFDO

Authors Thomas G. Wong

Publication date 26 April 2018

Published in Quantum Information Processing (Search for Journal in Brave)

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

zbMATH Keywords

quantum walkspatial searchlackadaisical quantum walk

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Searching and sorting (68P10) Quantum computation (81P68)

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/logN)$ in $O(sqrtNlogN)$ steps, which with amplitude amplification yields an overall runtime of $O(sqrtNlogN)$. 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(sqrtNlogN)$ steps, thus yielding an $O(sqrtlogN)$ 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.

Recommendations

• Lackadaisical quantum walks with multiple marked vertices
• Grover search with lackadaisical quantum walks
• Lackadaisical quantum walk for spatial search
• Lackadaisical quantum walks on 2D grids with multiple marked vertices
• Faster search of clustered marked states with lackadaisical quantum walks

Cites work

• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 2103521 (Why is no real title available?)
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• Coins make quantum walks faster
• Equivalence of Szegedy's and coined quantum walks
• Faster quantum-walk algorithm for the two-dimensional spatial search
• From quantum cellular automata to quantum lattice gases
• Grover search with lackadaisical quantum walks
• On the absence of homogeneous scalar unitary cellular automata.
• On the hitting times of quantum versus random walks
• Quantum search of spatial regions
• Quantum walks can find a marked element on any graph
• Search by quantum walks on two-dimensional grid without amplitude amplification
• Spatial search and the Dirac equation
• Spatial search on a honeycomb network

Cited in

(26)

• Quantum walk search on a two-dimensional grid with extra edges
• Finding Is as Easy as Detecting for Quantum Walks
• Doubling the success of quantum walk search using internal-state measurements
• Quantum walks for the determination of commutativity of finite dimensional algebras
• Overview: recent development and applications of reduction and lackadaisicalness techniques for spatial search quantum walk in the near term
• scientific article; zbMATH DE number 5320203 (Why is no real title available?)
• Probability and entanglement evolutions for Szegedy's quantum search on the one-dimensional cycle with self-loops
• Grover search with lackadaisical quantum walks
• Quantum abstract detecting systems
• Lackadaisical quantum walk for spatial search
• Lackadaisical quantum walks on 2D grids with multiple marked vertices
• Search via quantum walks with intermediate measurements
• On a poset of quantum exact promise problems
• Coins make quantum walks faster
• Faster quantum-walk algorithm for the two-dimensional spatial search
• Quantum walk and its application domains: a systematic review
• Quantum Walk Based Search Algorithms
• Quantum search on Hanoi network
• Lackadaisical discrete-time quantum walk on Johnson graph
• Faster search of clustered marked states with lackadaisical quantum walks
• Search via Quantum Walk
• Search on vertex-transitive graphs by lackadaisical quantum walk
• Improvement of quantum walks search algorithm in single-marked vertex graph
• Quantum walk search for exceptional configurations
• Search by quantum walks on two-dimensional grid without amplitude amplification
• Search algorithm on strongly regular graph by lackadaisical quantum walk

This page was built for publication: Faster search by lackadaisical quantum walk

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