Shor’s Algorithmen für die Primfaktorzerlegung und für das Problem des diskreten Logarithmus zählen zu den bahnbrechendsten Entwicklungen im Bereich der Quanteninformatik. Sie lösen Probleme in polynomieller Zeit mithilfe eines Quantencomputers, für welche keine effizienten klassischen Algorithmen bekannt sind. Diese Tatsache unterstreicht den Nutzen von Quantencomputern im Allgemeinen. Heutzutage existieren Bibliotheken und Simulatoren, die es ermöglichen, Quantenalgorithmen zu implementieren und zu analysieren. Eine dieser Bibliotheken, welche außerdem noch die Möglichkeit bietet, die Algorithmen auf echten Maschinen auszuführen, ist Qiskit. Qiskit beinhaltet zurzeit jedoch keine Referenzimplementierung für Shor’s Algorithmus für den diskreten Logarithmus. Für eine Implementierung müssen zusätzlich zur allgemeinen Beschreibung des Algorithmus noch Prozeduren für modulare Arithmetik bereitgestellt werden. Für diese Berechnungen gibt es viele unterschiedliche Algorithmen, wobei manche sehr klassischen Prozeduren ähneln und andere wiederum die Eigenheiten von Quantencomputern ausnutzen. Diese Arbeit liefert eine Referenzimplementierung von Shor’s Algorithmus für das Problem des diskreten Logarithmus. Dabei werden drei verschiedene Versionen der benötigten Routinen für modulare Arithmetik verwendet. Da aktuelle Quantencomputer immer noch relativ wenige Quantenbits, oder Qubits, für die Berechnung zur Verfügung stellen, liegt der Hauptfokus der Arbeit auf Möglichkeiten der Implementierung, die eine minimale Anzahl an Qubits benötigen. Mithilfe der Simulationsfunktionen von Qiskit wird zusätzlich zum Vergleich der Implementierungen bezüglich der asymptotischen Zeitkomplexität ein Vergleich der verschiedenen Versionen anhand der konkreten Anzahl an elementaren Operationen für kleine Probleminstanzen vorgenommen. Außerdem wird diese Analyse um eine genaue Untersuchung der Erfolgswahrscheinlichkeit ergänzt, da diese für die Laufzeit insgesamt ausschlaggebend ist.
Shor’s Algorithmen für die Primfaktorzerlegung und für das Problem des diskreten Logarithmus zählen zu den bahnbrechendsten Entwicklungen im Bereich der Quanteninformatik. Sie lösen Probleme in polynomieller Zeit mithilfe eines Quantencomputers, für welche keine effizienten klassischen Algorithmen bekannt sind. Diese Tatsache unterstreicht den Nutzen von Quantencomputern im Allgemeinen. Heutzutage existieren Bibliotheken und Simulatoren, die es ermöglichen, Quantenalgorithmen zu implementieren und zu analysieren. Eine dieser Bibliotheken, welche außerdem noch die Möglichkeit bietet, die Algorithmen auf echten Maschinen auszuführen, ist Qiskit. Qiskit beinhaltet zurzeit jedoch keine Referenzimplementierung für Shor’s Algorithmus für den diskreten Logarithmus. Für eine Implementierung müssen zusätzlich zur allgemeinen Beschreibung des Algorithmus noch Prozeduren für modulare Arithmetik bereitgestellt werden. Für diese Berechnungen gibt es viele unterschiedliche Algorithmen, wobei manche sehr klassischen Prozeduren ähneln und andere wiederum die Eigenheiten von Quantencomputern ausnutzen. Diese Arbeit liefert eine Referenzimplementierung von Shor’s Algorithmus für das Problem des diskreten Logarithmus. Dabei werden drei verschiedene Versionen der benötigten Routinen für modulare Arithmetik verwendet. Da aktuelle Quantencomputer immer noch relativ wenige Quantenbits, oder Qubits, für die Berechnung zur Verfügung stellen, liegt der Hauptfokus der Arbeit auf Möglichkeiten der Implementierung, die eine minimale Anzahl an Qubits benötigen. Mithilfe der Simulationsfunktionen von Qiskit wird zusätzlich zum Vergleich der Implementierungen bezüglich der asymptotischen Zeitkomplexität ein Vergleich der verschiedenen Versionen anhand der konkreten Anzahl an elementaren Operationen für kleine Probleminstanzen vorgenommen. Außerdem wird diese Analyse um eine genaue Untersuchung der Erfolgswahrscheinlichkeit ergänzt, da diese für die Laufzeit insgesamt ausschlaggebend ist.
In dieser Arbeit werden Algorithmen zur Lösung zahlentheoretischer Probleme für klassische Computer und Quantencomputer entwickelt und analysiert sowie ihre Auswirkungen auf Public-Key-Kryptosysteme untersucht. Im Jahr 1994 veröffentliche Shor einen Quantenalgorithmus [Shor, 1994], der das Periodengitter einer gegebenen Funktion in Quanten-Polynomzeit bestimmt. Mit diesem Algorithmus läßt sich das Faktorisierungs- und das Diskreter-Logarithmus-Problems in endlichen abelschen Gruppen in Quanten-Polynomzeit lösen. Dadurch werden die meisten heutzutage verwendeten Public-Key-Kryptoverfahren unsicher, sollten hinreichend große Quantencomputer eines Tages gebaut werden können. Der erste Quantencomputer wurde 1998 gebaut [Chuang/Vandersypen/Zhou/Leung/Lloyd, 1998]. Er bestand aus zwei Qubits. Der größte Quantencomputer, der bis heute gebaut wurde, besteht aus nur sieben Qubits [Vandersypen/Steffen/Breyta/Yannoni/Sherwood/Chuang, 2001]. Es hat sich herausgestellt, daß das Bauen von großen Quantencomputern ein extrem schwieriges Problem ist. Aus diesem Grund kann davon ausgegangen werden, daß die Größe der Quantencomputer, d.h. die Anzahl der Qubits, aus denen ein Quantencomputer besteht, nur langsam wachsen wird. Deshalb ist es von Interesse, Shors Quantenalgorithmus an verschiedene abelsche Gruppen sowie gruppenähnliche Strukturen zu adaptieren und ihre genaue Komplexität zu untersuchen, um daraus die Bedrohungen für die betroffenen Kryptosysteme genau zu bestimmen. In dieser Arbeit werden Quantenalgorithmen zur Lösung des Ordnungsproblems und des DL-Problems in der Klassengruppe der Ideale eines imaginär-quadratischen Zahlkörpers angegeben und ihre Komplexität, d.h. die Anzahl der Qubits und der elementaren Quantenoperationen, bestimmt. Darüberhinaus werden Algorithmen zur Bestimmung des Regulators und zur Lösung des Hauptidealproblems und des erweiterten Diskreter-Logarithmus-Problems in reell-quadratischen Zahlkörpern präsentiert. Shors Algorithmus wird dabei auf Funktionen angewendet, die nicht injektiv innerhalb einer Periode sind. Auch in diesem Fall wird die Komplexität der Algorithmen genau bestimmt. Im Falle von Zahlkörpern eines beliebigen Grades wird eine weitere Modifikation von Shors Algorithmus entwickelt: Es wird das Periodengitter einer Funktion bestimmt, deren Periodengitter irrational ist. Dieser Algorithmus wird benutzt, um die Einheitengruppe eines beliebigen endlich-dimensionalen Zahlkörpers zu berechnen. Als nächstes werden die Auswirkungen von Quantenalgorithmen auf die Sicherheit von Public-Key-Kryptosystemen untersucht. Es wird ein neuer Sicherheitsbegriff eingeführt. Die Sicherheit zweier Kryptosysteme wird als gleich definiert, wenn die Anzahl der Qubits zum Brechen dieser Kryptosysteme gleich ist. Basierend auf der neuen Sicherheitsdefinition wird die Geschwindigkeit und die Schlüsselgröße von einigen Kryptosystemen verglichen. Im letzten Kapitel wird ein deterministischer klassischer Algorithmus zur Berechnung der Struktur einer endlichen abelschen Gruppe aus einem Erzeugendensystem präsentiert, dessen Laufzeit nur linear von der Anzahl der gegebenen Erzeuger abhängt und dessen Speicherplatzkomplexität unabhängig von der Anzahl der gegebenen Erzeuger ist. Das stellt eine exponentielle Verbesserung zu früheren Algorithmen dar, bei denen sowohl die Laufzeit als auch die Speicherplatzkomplexität exponentiell von der Anzahl der Erzeuger im gegebenen Erzeugendensystem abhängt [Buchmann/Jacobson/Teske, 1997].
Diese Bachelorarbeit erläutert die Grundlagen von Quantencomputern und ihr Potential sowie die Vorteile, die eine Auseinandersetzung mit diesem Thema mit sich bringt. Sie richtet sich an Leser ohne Vorwissen auf diesem Gebiet und stellt die Konzepte auf eine Art vor, die für jede Person mit einem Grundwissen im Softwarebereich zugänglich ist. Es werden dabei die Unterschiede zwischen klassischen Computern und Quantencomputern besprochen, sowie die grundlegende Funktionsweise, wie die Basiseinheiten (Qubits) und die Gatter, die auf diese angewendet werden. Um diese Grundbausteine und Funktionsweise zu veranschaulichen sowie die Potentiale von Quantencomputern nachzuvollziehen, werden drei Algorithmen näher besprochen. Der Deutsch-Algorithmus zeigt, dass Quantencomputer manche Probleme schneller als klassische Computer lösen können. Der Shor-Algorithmus kann RSA verschlüsselte Nachrichten schnell entschlüsseln. Der Grover-Algorithmus bietet eine schnelle Methode eine bestimmte Information in unsortierten Daten zu suchen. Die drei Algorithmen decken bereits ein recht breites Spektrum von Anwendungsmöglichkeiten von Quantencomputern ab. Dieses Potential sowie die Wichtigkeit der Auseinandersetzung mit der Mächtigkeit von Quantencomputern und ein kurzer Einblick in mögliche zukünftige Entwicklungen schießen die Arbeit ab. Diese Bachelorarbeit erläutert die Grundlagen von Quantencomputern und ihr Potential sowie die Vorteile, die eine Auseinandersetzung mit diesem Thema mit sich bringt. Sie richtet sich an Leser ohne Vorwissen auf diesem Gebiet und stellt die Konzepte auf eine Art vor, die für jede Person mit einem Grundwissen im Softwarebereich zugänglich ist. Es werden dabei die Unterschiede zwischen klassischen Computern und Quantencomputern besprochen, sowie die grundlegende Funktionsweise, wie die Basiseinheiten (Qubits) und die Gatter, die auf diese angewendet werden. Um diese Grundbausteine und Funktionsweise zu veranschaulichen sowie die Potentiale von Quantencomputern nachzuvollziehen, werden drei Algorithmen näher besprochen. Der Deutsch-Algorithmus zeigt, dass Quantencomputer manche Probleme schneller als klassische Computer lösen können. Der Shor-Algorithmus kann RSA verschlüsselte Nachrichten schnell entschlüsseln. Der Grover-Algorithmus bietet eine schnelle Methode eine bestimmte Information in unsortierten Daten zu suchen. Die drei Algorithmen decken bereits ein recht breites Spektrum von Anwendungsmöglichkeiten von Quantencomputern ab. Dieses Potential sowie die Wichtigkeit der Auseinandersetzung mit der Mächtigkeit von Quantencomputern und ein kurzer Einblick in mögliche zukünftige Entwicklungen schießen die Arbeit ab. Diese Bachelorarbeit erläutert die Grundlagen von Quantencomputern und ihr Potential sowie die Vorteile, die eine Auseinandersetzung mit diesem Thema mit sich bringt. Sie richtet sich an Leser ohne Vorwissen auf diesem Gebiet und stellt die Konzepte auf eine Art vor, die für jede Person mit einem Grundwissen im Softwarebereich zugänglich ist. Es werden dabei die Unterschiede zwischen klassischen Computern und Quantencomputern besprochen, sowie die grundlegende Funktionsweise, wie die Basiseinheiten (Qubits) und die Gatter, die auf diese angewendet werden. Um diese Grundbausteine und Funktionsweise zu veranschaulichen sowie die Potentiale von Quantencomputern nachzuvollziehen, werden drei Algorithmen näher besprochen. Der Deutsch-Algorithmus zeigt, dass Quantencomputer manche Probleme schneller als klassische Computer lösen können. Der Shor-Algorithmus kann RSA verschlüsselte Nachrichten schnell entschlüsseln. Der Grover-Algorithmus bietet eine schnelle Methode eine bestimmte Information in unsortierten Daten zu suchen. Die drei Algorithmen decken bereits ein recht breites Spektrum von Anwendungsmöglichkeiten von Quantencomputern ab. Dieses Potential sowie die Wichtigkeit der Auseinandersetzung mit der Mächtigkeit von Quantencomputern und ein kurzer Einblick in mögliche zukünftige Entwicklungen schießen die Arbeit ab. Diese Bachelorarbeit erläutert die Grundlagen von Quantencomputern und ihr Potential sowie die Vorteile, die eine Auseinandersetzung mit diesem Thema mit sich bringt. Sie richtet sich an Leser ohne Vorwissen auf diesem Gebiet und stellt die Konzepte auf eine Art vor, die für jede Person mit einem Grundwissen im Softwarebereich zugänglich ist. Es werden dabei die Unterschiede zwischen klassischen Computern und Quantencomputern besprochen, sowie die grundlegende Funktionsweise, wie die Basiseinheiten (Qubits) und die Gatter, die auf diese angewendet werden. Um diese Grundbausteine und Funktionsweise zu veranschaulichen sowie die Potentiale von Quantencomputern nachzuvollziehen, werden drei Algorithmen näher besprochen. Der Deutsch-Algorithmus zeigt, dass Quantencomputer manche Probleme schneller als klassische Computer lösen können. Der Shor-Algorithmus kann RSA verschlüsselte Nachrichten schnell entschlüsseln. Der Grover-Algorithmus bietet eine schnelle Methode eine bestimmte Information in unsortierten Daten zu suchen. Die drei Algorithmen decken bereits ein recht breites Spektrum von Anwendungsmöglichkeiten von Quantencomputern ab. Dieses Potential sowie die Wichtigkeit der Auseinandersetzung mit der Mächtigkeit von Quantencomputern und ein kurzer Einblick in mögliche zukünftige Entwicklungen schießen die Arbeit ab.
Diese Arbeit ist eine mathematische Einführung zum Shor-Algorithmus und das dafür nötige Wissen über Quantencomputer. Sie soll die Lücke zwischen der populärwissenschaftlichen Literatur und den Fachschriften, die sich mit spezifischen Teilaspekten beschäftigen, aber keinen einführenden Gesamtüberblick für den mathematisch-informatisch versierten Leser bieten, schließen. Dafür werden nach einer kurzen motivierenden Einführung Quantencomputer mathematisch definiert. Auf dieser Grundlage aufbauend, betrachten wir den Ablauf des Shor-Algorithmus für die Faktorisierung und beweisen dessen Korrektheit. Insbesondere zeigen wir auch, wie wir aus dem Ergebnis der Quantensubroutine des Shor-Algorithmus den gesuchten Faktor berechnen. Ergänzend befindet sich im Appendix die Erklärung, wieso und wie der Shor-Algorithmus auch zur Berechnung des diskreten Logarithmus benutzt werden kann.
Quantencomputer versprechen eine revolutionäre Leistungssteigerung und könnten damit einige aktuelle Paradigmen der Informatik obsolet werden lassen. Diese Technologie ist für Interessierte ohne Vorkenntnisse aus dem Bereich der Quantenphysik jedoch schwer nachzuvollziehen. Die vorliegende Arbeit basiert auf einer Literaturrecherche und wurde verfasst, um die Thematik der Quantencomputer verständlich darzulegen. Zu diesem Zweck wird zuerst eine Beschreibung von relevanten Grundprinzipien der Quantenmechanik gegeben. Neben der Anführung von bestimmten Quantenzahlen und deren Zuständen werden dabei die Konzepte der Superposition und der Verschränkung dieser Zustände erläutert. Danach wird die Funktionsweise eines auf Quantengattern basierenden Computers mathematisch und grafisch nachvollziehbar beschrieben. Operationen, welche durch Transformation von Quantenzuständen ausgeführt werden, und Anwendungen für diese Art von Berechnungen werden vorgestellt. Potenziale und Einschränkungen sind durch das Verständnis der Arbeitsweise eines Quantencomputers eingängig. Der Aufbau eines Quantencomputers, sowie eine Analyse des Fortschritts bei der Realisierung von voll skalierbaren Quantencomputern werden weiters dargelegt. Dabei wird auf die wesentlichen Bestandteile eines Quantenchips näher eingegangen. Für geeignet gehaltene Quantenzustände für die Nutzung als Qubits, sowie Verfahren zur Speicherung und Manipulation von Informationen durch Quantencomputer werden beschrieben. Vor allem die Fehlerrate von Qubits stellt Forscher und Entwickler derzeit noch vor große Herausforderungen. Diese Arbeit gibt deshalb einen Ausblick, welche weiteren Schritte nötig sind, um die Vision von kommerziell einsetzbaren Quantencomputern zu verwirklichen.
Zusammenfassung Quantencomputing ist als Konzept mittlerweile zwar mehrere Jahrzehnte alt und hat von der Idee bis zu den heutigen Noisy Intermediate-Scale Quantum Maschinen verschiedene Phasen stetiger Entwicklung durchlaufen, jedoch insbesondere in den letzten Jahren deutlich an Dynamik gewonnen. Im aktuellen Stadium stehen Quantenrechner zur Verfügung, die zwar noch immer stark limitiert sind, jedoch die Ausführung maßgeschneiderter Algorithmen unterstützen, die bestehende Schwächen dieser Maschinen mit ihrem speziellen Design zu umgehen versuchen. Diese Algorithmen adressieren dabei mit Maschinellem Lernen, kombinatorischer Optimierung und Simulationsanwendungen sowie weiteren potenziellen Anwendungsfeldern Problemstellungen, die praktisch vielfältig relevant und deshalb von breitem, allgemeinen Interesse sind. Das prinzipielle Potenzial des Quantencomputers, in bestimmten Anwendungsfeldern deutlich leistungsfähiger zu sein als klassische Rechner, ruft viel Aufmerksamkeit hervor. Außerdem stellt bereits eine ganze Reihe von prinzipiell für jedermann zugänglichen Softwareframeworks Implementierungen aktueller Quantenalgorithmen zum Test und zur Evaluierung bereit. Der Artikel stellt die bisherige Entwicklung, aktuelle Verfahren sowie weitere Perspektiven der Technologie in Grundzügen dar und informiert über mögliche Anwendungsgebiete aber auch bekannte Grenzen des Quantencomputing-Paradigmas.
Diese Dissertation beschäftigt sich mit der Frage, wie viel Rechenkraft Quantencomputer bieten können. Diese Frage geht in ihrer allgemeinsten Form weit über die aktuellen Möglichkeiten und Methoden der Komplexitätstheorie hinaus. Dennoch liefert die Komplexitätstheorie Beispiele von Problemen, die sogar für Quantencomputer als nicht effizient lösbar gelten. Andererseits können Quantencomputer vermutlich nicht effizient von klassischen Computern simuliert werden. Wir wollen mit dieser Arbeit zum Verständnis des dazwischen liegenden Bereichs von Problemen, die effizient auf Quantencomputern, aber nicht effizient auf klassischen Computern berechnet werden können, beitragen. Um besseren Einblick in die Fragestellung zu erlagen, entwickeln wir in dieser Dissertation klassische und quantenmechanische Algorithmen zur Lösung von Problemen, die unter einschränkenden Annahmen a priori als nicht effizient lösbar geltende Probleme dennoch effizient lösen. Wir erforschen in diesem Sinne also die Grenzen des auf Quantencomputern und klassischen Computern Machbaren, in dem wir Annahmen identifizieren, die dazu geeignet sind grundsätzlich als schwer geltende Probleme in den Bereich des Machbaren zu bringen. Im Speziellen entwickeln wir einen Quantenalgorithmus, der sogenannte Projective Entangled-Pair States (PEPS) effizient herstellen kann, sobald Injektivität und Wohlkonditierung des PEPS gegeben ist. In einem zweiten Schritt erweitern wir diesen Algorithmus auf sogenannte G-injektive PEPS, einer wesentlich allgemeineren Klasse von Quantenzuständen, die auch die exotische Eigenschaft der topologischen Ordnung besitzen können. Weiters entwickeln wir einen Quantenalgorithmus, der das im Allgemeinen für Quantencomputer als schwer geltende Problem den Grundzustand von lokalen Hamiltonoperatoren zu erzeugen löst, sofern diese die Voraussetzungen des (nicht-konstruktiven) Quanten-Lovász-Local-Lemma erfüllen und die Operatoren kommutieren. Unser Quantenalgorithmus kann in diesem Fall auch als unabhängiger, konstruktiver Beweis des Quanten-Lovász-Local-Lemmas betrachtet werden. Um die Grenze zu klassischen Computern zu erforschen, entwickeln wir einen klassischen Algorithmus, der das sehr allgemeine Problem Quantenschaltkreise zu simulieren unter gewissen Annahmen effizient lösen kann. Wäre es in voller Allgemeinheit lösbar, würden Quantencomputer keinen Vorteil bieten. Unser Algorithmus kann Quantenschaltkreise simulieren, die in ihrer Struktur jener des Quantenalgorithmus von Shor zur Faktorisierung ganzer Zahlen, der als exponentiell schneller als der schnellste bekannte klassische Faktorisierungsalgorithmus gilt, sehr ähnlich sind. Weiters treffen wir die Annahme, dass die erzeugte Wahrscheinlichkeitsverteilung annähernd dünn-besetzt ist. Unser Ergebnis impliziert daher, dass die von Algorithmen dieser Struktur erzeugte Wahrscheinlichkeitsverteilung notwendigerweise dicht-besetzt sein muss, um einen exponentiellen Geschwindigkeitsvorteil erzielen zu können.