Quantenrechner: Grundlagen der Komplexitätstheorie

Nachdem in den letzten Vorträgen die physikalischen Grundlagen für die
Konstruktion und Analyse von Quantencomputern gelegt wurden, werden
wir nun die Analysemethoden und Resultate der theoretischen Informatik
zur Mächtigkeit von Rechnermodellen und zur Schwierigkeit von
Problemen wiederholen. Die Klasse BPP der in polynomieller Zeit
probabilistisch berechenbaren Sprachen entspricht gegenwärtig am
genausten unserer Vorstellung von effizient auf dem Computer lösbaren
Problemen; an BPP werden Quantenalgorithmen gemessen.