For best experience please turn on javascript and use a modern browser!

Speaker: Stacey Jeffery (CWI and QuSoft)

Detail Summary
Date 20 March 2019
Time 16:00 - 16:45
Location Science Park 107


Quadratic speedup for finding marked vertices by quantum walks


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, quadratically faster than the corresponding classical random walk.

This is joint work with Andris Ambainis, Andras Gilyen, and Martins Kokainis.


KdVI meeting room, room F3.20

Science Park 107

Room Location: KdVI meeting room, Science Park 107, room F3.20

Science Park 107
1098 XG Amsterdam