Spezialvorlesung
"Quantenrechner: Algorithmen und Komplexität"
Wintersemester
2004/2005
Veranstalter:
Detlef Sieling
Termin:
Montag, 16.15-17.45 Uhr,
HG I, HS 3
Donnerstag, 14.15-15.45
Uhr, HG I, HS 2
Beginn der
Vorlesung:
11.10.2004
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. Für dieses Problem ist bisher kein
(klassischer) polynomieller Algorithmus bekannt. 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 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
so genannte Quantenschaltkreise definiert und Algorithmen für
Quantenschaltkreise vorgestellt. Den Kern der Vorlesung bilden der
Algorithmus von Shor zur Faktorisierung von ganzen Zahlen und der
Suchalgorithmus von Grover. Als weitere Gebiete werden endliche
Automaten mit Quanteneffekten (QFAs, quantum finite automata) und
Quanten-Kommunikationskomplexität diskutiert.
Die Vorlesung basiert zum größten Teil auf dem Buch "Quantum
Computation and Quantum
Information" von M.A. Nielsen und I.L. Chuang und dem Vorlesungsskript
von Martin Sauerhoff.
Literatur zur Vorlesung:
L. E. Ballentine, "Quantum Mechanics - A Modern Development",
World Scientific Publishing, 1998.
J. Gruska, "Quantum Computing", McGraw-Hill, 1999.
M. Hirvensalo, "Quantum Computing", Springer-Verlag, 2001.
A. Yu. Kitaev, A. Shen und M. N. Vyalyi, "Classical and Quantum
Computation", American Mathematical Society, 2002.
M. A. Nielsen und I. L. Chuang, "Quantum Computation and Quantum
Information", Cambridge University Press, 2000.
A. Peres, "Quantum Theory: Concepts and Methods", Kluwer
Academic Publishers, 1995.
J. Preskill, "Quantum Information and Computation", Vorlesungsskript.
M. Sauerhoff, Skript zur Vorlesung Quantenrechner: Algorithmen
und Komplexität, Sommersemester 2003, erhätlich als PS-File
und PDF-File.