Recent research strongly suggests that there are problems which can be solved quickly by quantum computers that cannot be solved quickly by classical machines. Most notably, in 1994, P. Shor presented an efficient quantum algorithm for factoring, for which no efficient classical algorithm is known. In this talk, further evidence for the dramatic difference between quantum and classical computing will be discussed, using techniques and results from computational complexity theory.