Current Trends in Theory and Practice of Computer Science  
Track filter:   
Invited Talk
Computing by Nature

Thursday, January 24, 8:30 - 10:00

Andris Ambainis

Quantum Random Walks—New Method for Designing Quantum Algorithms

Quantum walks are quantum counterparts of random walks. In the last 5 years, they have become one of main methods of designing quantum algorithms. Quantum walk based algorithms include element distinctness, spatial search, quantum speedup of Markov chains, evaluation of Boolean formulas and search on "glued trees" graph. In this talk, I will describe the quantum walk method for designing search algorithms and show several of its applications.

The talk does not require any prior background in quantum information or quantum physics.
SOFSEM 2008, January 19-25, High Tatras, Slovakia