Skip to content

MQI

Seminar

Lecture 1 - Quantum walk and learning graph based algorithms (a tutorial)

Santha, M (Université Paris 7 - Denis-Diderot)
Thursday 05 September 2013, 15:30-16:30

Seminar Room 1, Newton Institute

Abstract

In this talk I survey two generic methods to design quantum algorithms. I give an intuitive treatment of the discrete time quantization of classical Markov chains, and I describe nested walks, an extension of the model using quantum data structures. I explain the relatively recent idea of learning graphs, a combinatorial way to conceive quantum query algorithms. With several examples, including triangle and 3-collision finding, I illustrate the power of these methods. Finally I discuss time efficient implementations of learning graphs by quantum walks.

Video

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧