In diesem Vortrag werden zwei Berechnungsmodelle für Quantenrechner
vorgestellt, ihre Äquivalenz und Universalität gezeigt und Zeit- und
Platzkomplexität definiert. Anhand eines künstlichen Problems wird ein
erstes Beispiel für einen exponentiellen Geschwindigkeitsvorteil des
Quantencomputers gegeben.