The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



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


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.


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 ∧