Title	Quadratic speedup for finding marked vertices by quantum walks
Creator	Ambainis, Andris
Publisher	Banff International Research Station for Mathematical Innovation and Discovery
Date Issued	2019-04-24T09:03
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. <BR> Joint work with AndrÃ¡s GilyÃ©n, Stacey Jeffery, Martins Kokainis, arxiv preprint 1903.07493.
Extent	56.0 minutes
Subject	Mathematics; Quantum theory; Mathematical physics
Type	Moving Image
File Format	video/mp4
Language	eng
Notes	Author affiliation: University of Latvia
Series	BIRS Workshop Lecture Videos (Banff, Alta)
Date Available	2019-10-22
Provider	Vancouver : University of British Columbia Library
Rights	Attribution-NonCommercial-NoDerivatives 4.0 International
DOI	10.14288/1.0384619
URI	http://hdl.handle.net/2429/72020
Affiliation	Non UBC
Peer Review Status	Unreviewed
Scholarly Level	Faculty
Rights URI	http://creativecommons.org/licenses/by-nc-nd/4.0/
Aggregated Source Repository	DSpace

Open Collections

BIRS Workshop Lecture Videos

Quadratic speedup for finding marked vertices by quantum walks Ambainis, Andris

Description

Item Metadata

Item Media

Item Citations and Data

Rights