I introduce the abstract notion of a quantum computer, explain why it might be computationally stronger than classical computer and give an overview of its complexity theory (both on what is know and what is conjectured). I also try to adjust some misconceptions about quantum computers - especially that they were essentially non-deterministic Turing machines or that they could be used to solve NP-hard problems.
I finally present shortly two of the three algorithm classes that are faster on a quantum computer than on a classical computer. (The third class follows next week).