Faster search by lackadaisical quantum walk

DOI10.1007/S11128-018-1840-YzbMATH Open1386.81051arXiv1706.06939OpenAlexW2654805423MaRDI QIDQ1746914FDOQ1746914

Thomas G. Wong

Publication date: 26 April 2018

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Faster quantum-walk algorithm for the two-dimensional spatial search
• From quantum cellular automata to quantum lattice gases
• On the hitting times of quantum versus random walks
• Quantum walks can find a marked element on any graph
• Coins make quantum walks faster
• Spatial search and the Dirac equation
• Grover search with lackadaisical quantum walks
• Equivalence of Szegedy's and coined quantum walks
• On the absence of homogeneous scalar unitary cellular automata.
• Spatial search on a honeycomb network
• Search by Quantum Walks on Two-Dimensional Grid without Amplitude Amplification

Cited In (18)

• Faster search of clustered marked states with lackadaisical quantum walks
• Quantum walk and its application domains: a systematic review
• Quantum abstract detecting systems
• Quantum walk search on a two-dimensional grid with extra edges
• Search on vertex-transitive graphs by lackadaisical quantum walk
• Lackadaisical discrete-time quantum walk on Johnson graph
• Quantum walk search for exceptional configurations
• Lackadaisical quantum walk for spatial search
• Search via Quantum Walk
• Title not available (Why is that?)
• Quantum search on Hanoi network
• On a poset of quantum exact promise problems
• Lackadaisical quantum walks on 2D grids with multiple marked vertices
• Quantum Walk Based Search Algorithms
• Finding Is as Easy as Detecting for Quantum Walks
• 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
• Probability and entanglement evolutions for Szegedy's quantum search on the one-dimensional cycle with self-loops

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)