Quantenkomplexitätstheorie

In Analogie zur Komplexitätsklasse BPP der Sprachen, die von
probabilistischen Turingmaschinen in Polynomialzeit mit beschränktem
Fehler erkannt werden können, definiert man BQP als die Sprachen,
welche von Quantenturingmaschinen in Polynomialzeit mit beschränktem
Fehler erkannt werden. Wir zeigen, BQP umfaßt BPP, ist aber in PSPACE
enthalten --- mehr als exponentiellen Vorteil können Quantencomputer
also nicht haben. In einem zweiten Teil wird auf die Mächtigkeit von
Quantencomputern im Orakelmodell eingegangen und bewiesen, daß hier
nur eine polynomielle Beschleunigung möglich ist.