Quantum algorithms

In this introductionary talk to quantum algorithms, we introduce the so-called black box model. We discuss how to compare the complexity of quantum algorithms to that of classical algorithms. We give and analyze a set of simple quantum algorithms. We then give an efficient quantum algorithm for a group-theoretical problem called Simon's problem, ideas from which lead to an efficient quantum algorithm for Integer Factorization. We finally show how to implement the quantum fourier transform efficiently.