| Veranstalter: | Martin Sauerhoff, Detlef Sieling |
| Termin: | Dienstag, 12.15-13.45, HG I, HS 1 |
| Donnerstag, 8.30-10.00, GB IV, HS 112 | |
| Beginn der Vorlesung: | 17.4.2001 |
| Übungen: | Montag, 12.15-13.45, GB V, R. 420 |
| Beginn der Übungen: | 30.4.2001 |
Die Quantenmechanik ist eine Theorie der Physik zur Beschreibung von Vorgängen in der Natur. Als Theorie ist sie nicht beweisbar, man hat allerdings beobachtet, dass sie die Vorgänge in der Natur mit hoher Genauigkeit beschreibt. Manche Vorhersagen der Quantenmechanik stimmen allerdings nicht mit alltäglichen Wahrnehmungen überein. Seit etwa 20 Jahren wird daher die Frage untersucht, ob derartige quantenmechanische Effekte benutzt werden können, um Berechnungen effizienter auszuführen. Diese Untersuchungen fanden allerdings erst breitere Beachtung, als Shor 1994 bewiesen hat, dass die Faktorisierung von ganzen Zahlen mit Rechnern, die quantenmechanische Effekte ausnutzen, in polynonieller Zeit möglich ist. Dies ist ein Problem, für das bisher kein (klassischer) polynomieller Algorithmus bekannt ist. Dies stützt die Vermutung, dass die erweiterte Churchsche These, dass alle intuitiv sinnvollen Berechnungsmodelle bis auf polynomielle Faktoren in der Rechenzeit gleich mächtig sind, für Quantenrechner möglicherweise nicht zutrifft. Allerdings befinden sich die Versuche, Quantenrechner praktisch zu realisieren, noch in einem sehr frühen Stadium.
In der Vorlesung sollen zunächst die benötigten Grundlagen der Quantenmechanik vorgestellt werden. Anschließend werden sogenannte Quantenschaltkreise definiert und Algorithmen für Quantenschaltkreise vorgestellt. Dazu gehören auch Shors Algorithmus zur Faktorisierung und kryptographische Probleme wie z.B. der sichere Austausch von geheimen Schlüsseln. Inzwischen wurden auch zahlreiche komplexitätstheoretische Fragenstellungen für den Fall von Quantenrechnern untersucht. Dazu gehört zum Beispiel der Beweis unterer Schranken für eingeschränkte Quantenrechner oder die Untersuchung der Kommunikationskomplexität von Funktionen bei der Verwendung von Quantenrechnern. Zum Ende der Vorlesung sollen auch experimentelle Quantenrechner diskutiert werden.