Jeder heutige PC kann, so komplex sein Aufbau auch sein mag, im Prinzip noch immer effizient durch eine einfache, rein mechanisch arbeitende "Rechenmaschine" simuliert werden, so wie sie abstrakt durch das Modell der Turingmaschine beschrieben wird. Die formalen Modelle der Informatik, die wir in GTI oder Komplexitätstheorie kennen lernen, basieren letztendlich alle auf klassischer Physik (womit hier im Wesentlichen Mechanik und Elektromechanik gemeint sind). Wir wissen aber seit den 20er Jahren des letzten Jahrhunderts, dass die Natur genauer durch die Gesetze der Quantentheorie beschrieben werden kann und auch muss, wenn wir bestimmte Phänomene zufrieden stellend erklären wollen.

Seit etwa 20 Jahren wird nun intensiv erforscht, ob und wie quantentheoretische Effekte helfen können, Rechner zu realisieren, die effizienter arbeiten als klassische Rechner. Zunächst wurden entsprechende formale Modelle für solche Quantenrechner rein theoretisch diskutiert. Das Gebiet bekam immensen Auftrieb durch die bahnbrechende Entdeckung von Shor (1994), dass Quantenrechner ganze Zahlen in polynomieller Zeit faktorisieren können. Es wird allgemein vermutet, dass dieses Problem auf klassischen Rechnern nur in exponentieller Zeit lösbar ist. Es erscheint also zumindest möglich, dass die uns bekannte erweiterte churchsche These falsch ist, nach der alle intuitiv sinnvollen Rechnermodelle bis auf polynomielle Faktoren in der Rechenzeit äquivalent zur klassischen Turingmaschine sind. Angespornt durch diese theoretischen Entdeckungen sind inzwischen zahlreiche experimentelle Realisierungen von Quantenrechnern vorgeschlagen und auch teilweise praktisch untersucht worden. Trotzdem sind wir noch weit entfernt von der Anwendung von Quantenrechnern auf realistische Probleme, da die auftretenden technischen Schwierigkeiten immens sind. Als ein Meilenstein sei erwähnt, dass es erst vor kurzem (2001) bei einem Experiment gelungen ist, Shors Algorithmus zur Faktorisierung der Zahl 15 einzusetzen.

In der Vorlesung wollen wir uns die nötigen Kenntnisse erarbeiten, um die aktuelle Entwicklung in diesem spannenden Gebiet zu verstehen. Dazu werden zunächst die benötigten physikalischen und mathematischen Grundlagen vorgestellt. Als einfach handhabbares Modell für Quantenrechner benutzen wir Quantenschaltkreise, wie in der Literatur allgemein üblich. Den Kern der Vorlesung bildet die Behandlung der grundlegenden Algorithmen von Shor und Grover. Als weitere interessante Gebiete werden Modelle für endliche Automaten mit Quanteneffekten (QFAs, quantum finite automata) und Quanten-Kommunikationskomplexität diskutiert. Zum Schluss beschäftigen wir uns exemplarisch mit einigen der möglichen experimentellen Realisierungen von Quantenrechnern.

Grundlage der Vorlesung ist das Buch "Quantum Computation and Quantum Information" von Micheal A. Nielsen und Isaac L. Chuang, Cambridge University Press 2000.