Jérémie Roland - Université Libre de Bruxelles
In this talk, we will give a survey of quantum algorithms based on quantum walks, focusing in particular on search algorithms. The father of almost all quantum search algorithms is Grover's algorithm, which can be seen as a quantum walk on the complete graph. Later on, variations of Grover's algorithm have been proposed for searching on other graphs, such as the grid or the hypercube. Building on those ideas, Ambainis proposed a groundbreaking algorithm for the Element Distinctness problem, based on a quantum walk on the Johnson graph. Shortly afterwards, Szegedy developed a general method to map a classical random walk to a quantum walk on the same graph. These works led to a flurry of results, including conceptual implications such as generic speedups of quantum walks over random walks, as well as concrete applications in the form of new quantum algorithms for various problems.