6533b7d4fe1ef96bd1261e00

RESEARCH PRODUCT

Quadratic speedup for finding marked vertices by quantum walks

Andris AmbainisStacey JefferyAndrás GilyénMartins Kokainis

subject

FOS: Computer and information sciencesQuadratic growthQuantum PhysicsQuantum algorithmsSpeedupMarkov chainMarkov chainsProbability (math.PR)FOS: Physical sciencesRandom walkVertex (geometry)CombinatoricsQuadratic equationSearch by random walkQuantum searchComputer Science - Data Structures and AlgorithmsFOS: MathematicsData Structures and Algorithms (cs.DS)Quantum walkQuantum algorithmQuantum Physics (quant-ph)Mathematics - ProbabilityMathematicsQuantum walks

description

A quantum walk algorithm can detect the presence of a marked vertex on a graph quadratically faster than the corresponding random walk algorithm (Szegedy, FOCS 2004). However, quantum algorithms that actually find a marked element quadratically faster than a classical random walk were only known for the special case when the marked set consists of just a single vertex, or in the case of some specific graphs. We present a new quantum algorithm for finding a marked vertex in any graph, with any set of marked vertices, that is (up to a log factor) quadratically faster than the corresponding classical random walk.

yearjournalcountryeditionlanguage
2020-06-08
10.1145/3357713.3384252https://ir.cwi.nl/pub/30189