### 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.

## Comments

Start the discussion!