In the end of the last century unexpected relations between physics and computer science were revealed. It turned out that efficiency of manipulating data depends on laws of Nature. As a striking example, there are quantum algorithms for integer factoring that are much faster than classical ones.

Two major questions stem from these discoveries: what is an exact power of quantum algorithms? is it possible to build up a quantum computer? The questions have been studied intensively in last two decades. Interesting and intriguing partial answers were obtained. But in general the questions remain widely open.

This course is devoted to basic ideas of design and analysis of quantum algorithms. The prerequisites are basic theoretical computer science and basic linear algebra.