Algorithmen für auf adiabatischer Entwicklung basierende Quantenrechner

Klaus Fehlker

Jan 2006 · GRIN Verlag

About this eBook

Diplomarbeit aus dem Jahr 2003 im Fachbereich Informatik - Theoretische Informatik, Note: 1,7, Technische Universität Dortmund (Theoretische Informatik), Sprache: Deutsch, Abstract: Quantenrechner haben in den letzten Jahren einen regelrechten Boom ausgelöst, sowohl bei den Informatikern als auch bei den Physiker. Historisch gesehen sind die Grundlagen bereits seit dem ersten Viertel des zwanzigsten Jahrhunderts bekannt. Eine Ausnutzung der physikalischen Phänomene für Berechnungen wurde allerdings erst in Angriff genommen, als David Deutsch 1985 das Modell des Universellen Quantencomputers (UQC) entwickelte, in welchem beliebige physikalische Systeme, also auch klassische Computer, simuliert werden können. Mit Hilfe dieses theoretischen Modells eines Quantencomputers zeigten Deutsch und Josza [DJ92] an einem einfachen Beispiel, dass ein solcher universeller Quantencomputer bzgl. der Auswertung einer Funktion, man sagt auch die Abfrage eines Orakels, eine stärkere Rechenleistung hat als klassische Rechner, wie z.B. die Turingmaschine. Gegeben sei eine Funktion f:{0,1}n→ {0,1}, welche entweder konstant ist oder deren Anzahl an Eingaben mit Ausgabe 1 und 0 gleich ist. Für diese Funktion kann der UQC mit nur O(1)vielen Funktionsauswertungen entscheiden, welche der beiden Eigenschaften f erfüllt. Im Gegensatz dazu benötigt eine Turingmaschine superpolynomiell viele Funktionsauswertungen. Wesentlich populärer wurden die Quantenrechner, als Peter Shor 1994 einen Algorithmus [Sho97] vorstellte, der sowohl das Problem der Primfaktorzerlegung, als auch das des diskreten Logarithmus mit polynomiell vielen Rechenschritten löste - zwei Probleme, von denen man annimmt, sie haben keine effiziente Lösung auf Turingmaschinen. Damit verbunden ist auch die Unsicherheit des RSA-Kryptosystems, welches auf der Komplexität der Primfaktorzerlegung aufbaut.