Abstract Quantenkryptographie und Quantencomputer sind zwei Forschungsgebiete der Quanteninformationstechnologie. Die Quantenkryptographie erzeugt Schlüssel, deren Geheimhaltung durch die Quantenmechanik garantiert wird. Erste kommerzielle Realisierungen sind erhältlich. Dagegen ist der Quantencomputer noch weit von der Verwirklichung entfernt, auch wenn die Grundbausteine bereits realisiert wurden. Theoretisch ist erwiesen, dass er manche Probleme wesentlich effizienter als klassische Computer lösen könnte. Das bekannteste Beispiel ist der Shor‐Algorithmus zur Primfaktorzerlegung, womit aktuelle kryptographische Systeme geknackt würden. Gute Chancen als erste praktische Anwendung haben Quantenrechner, die das Verhalten komplexer Quantensysteme simulieren.
Abstract Quantenkryptographie und Quantencomputer sind zwei Forschungsgebiete der Quanteninformationstechnologie. Die Quantenkryptographie erzeugt Schlüssel, deren Geheimhaltung durch die Quantenmechanik garantiert wird. Erste kommerzielle Realisierungen sind erhältlich. Dagegen ist der Quantencomputer noch weit von der Verwirklichung entfernt, auch wenn die Grundbausteine bereits realisiert wurden. Theoretisch ist erwiesen, dass er manche Probleme wesentlich effizienter als klassische Computer lösen könnte. Das bekannteste Beispiel ist der Shor‐Algorithmus zur Primfaktorzerlegung, womit aktuelle kryptographische Systeme geknackt würden. Gute Chancen als erste praktische Anwendung haben Quantenrechner, die das Verhalten komplexer Quantensysteme simulieren.
Abstract Obwohl die Quantenmechanik sämtliche Gebiete der modernen Physik durchzieht, stoßen wir immer wieder auf Probleme, wenn wir ihre Vorhersagen mit unserer klassischen Anschauung zu verstehen versuchen. Seit einigen Jahren geht der Trend dahin, die seltsam anmutenden Eigenheiten der Quantenwelt ‐ Nichtlokalität, Superpositionsprinzip, Unschärferelation ‐ auszunutzen, um Dinge zu realisieren, die innerhalb der klassischen Physik unmöglich sind. Die Quanten‐Informationsverarbeitung, auch Quantenkommunikation genannt, ist aus diesem Ansatz hervorgegangen; erste Demonstrationsexperimente zum Quantencomputer sowie Quantenkryptographie‐Prototypen haben gezeigt, welches Potential diese Entwicklung birgt [1, 2]. In diesem Artikel verdeutlichen wir, wie die Grundprinzipien der Quantentheorie in der Quantenkryptographie zur Anwendung kommen.
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].
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.
Vermutlich ist der Begriff Quantencomputer für viele Leser noch sehr neu. Man könnte dabei an eine neue Technologie denken — vielleicht die jüngste und modernste in der bemerkenswerten Folge, zu der die Berechnung mit Transistoren, integrierten Schaltkreisen oder Siliziumchips gehört. Und es stimmt, auch die schon vorhandene Computertechnologie beruht weitgehend auf mikrophysikalischen quantenmechanischen Prozessen. Wenn sich der Hang zu immer schnellerer, kompakterer Computer-Hardware fortsetzen soll, muß die Technologie immer «quantenmechanischer» werden, weil quantenmechanische Effekte in allen kleinen Systemen überwiegen. Aber wenn das alles wäre, würden Quantencomputer bei grundlegenden Erklärungen in diesem Zusammenhang kaum eine Rolle spielen. Unabhängig davon, welche quantenmechanischen Vorgänge heutige Computer zur Durchführung der Berechnungen nutzen, sie sind alle technologische Verwirklichungen desselben klassischen Grundgedankens, nämlich der universellen Turingmaschine. Deshalb können alle existierenden Computer im wesentlichen dieselben Berechnungen ausführen. Sie unterscheiden sich lediglich in bezug auf die Geschwindigkeit, Speicherfähigkeit und die Modi der Verarbeitung der Eingaben. Selbst ein langsamer Computer mit wenig Speicherplatz läßt sich so programmieren, daß er jedes Problem genausogut lösen und jede Umwelt genausogut simulieren kann wie unsere leistungsfähigsten Computer, wenn nur der Speicherplatz reicht, er lange genug laufen kann und ihm die Hardware zur Verfügung steht, auf der er die Ergebnisse darstellen kann.
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.
Quantenschlusselverteilung erlaubt den Austausch von sicheren Schlusseln basierend auf den Gesetzen der Quantenmechanik. Diese Schlussel werden verwendet, um Nachrichten mithilfe der Vernamchiffre zu kodieren. Unter der Annahme, dass die Theorie der Quantenmechanik korrekt ist und dass der Aufbau korrekt implementiert wird, sind diese kryptografischen Systeme bedingungslos sicher. Bedingungslose Sicherheit bedeutet, dass die Sicherheit nicht von der Rechenleistung und der Angriffsstrategie eines potenziellen Lauschers abhangt. Da die benotigten Qubits als Photonen durch die Glasfaberkabel gesendet werden, ist die Quantenschlusselverteilung aufgrund der Verluste im Kabel leider auf wenige Hundert Kilometer beschrankt. Um dieses Problem zu beheben, wurden Quanten-Repeater eingefuhrt. In der klassischen Telekommunikationstechnik verstarken Repeater das vorhandene Signal; in der Quantentheorie ist jedoch jegliches Kopieren von unbekannten Quantenzustanden durch das no-cloning Theorem verboten. Quanten-Repeater hingegen konnen Verschrankung zwischen Qubits erzeugen, die Hunderte bis Tausende Kilometern entfernt sind. Dabei basieren sie auf fundamentalen Konzepten aus der Quanteninformationstheorie wie Verschrankungstausch und Verschrankungsdestillierung.
Diese Arbeit befasst sich mit zwei Themen aus der Quantenkommunikation: Quantenschlusselverteilung uber weite Strecken mithilfe von Quanten-Repeatern und die Sicherheitsanalyse fur Schlussel im Bereich von endlich vielen Signalen.
Einerseits werden sichere Schlusselraten mithilfe von Quanten-Repeatern fur unendlich viele Signale untersucht. Zu diesem Zweck prasentieren wir Fehlermodelle fur die Komponenten eines Quanten-Repeaters. Wir fuhren eine quantitative Analyse der optimalen sicheren Schlusselraten fur relevante experimentelle Parameter von verschiedenen Implementierungen des Repeaters durch. Unter diesen Implementierungen sind der ursprungliche Quanten-Repeater, der hybride Quanten-Repeater, der Quanten-Repeater bestehend aus atomaren Ensembles und ein Quanten-Repeater basierend auf Fehlerkorrektur-Codes. Wir finden heraus, dass der ursprungliche Quanten-Repeater mehr Gatterfehler als der hybride Quanten-Repeater tolerieren kann und dass der Quanten-Repeater bestehend aus atomaren Ensembles robust gegen realistische Fehler ist. Wir untersuchen auch den Einfluss von unterschiedlichen Destillierungsstrategien (Destillierungsprotokolle und Anzahl der Destillierungsrunden in jedem Zwischenschritt des Quanten-Repeaters) auf den ursprunglichen Quanten-Repeater und konnen quantitative Aussagen uber die Strategien machen, die zu einer maximalen sicheren Schlusselrate fuhren. Wir leiten die Erzeugungsrate fur verschrankte Paare unter Berucksichtigung der klassischen Kommunikationszeit, die fur den Verschrankungstausch und die Verschrankungsdestillierung benotigt wird, her. Des Weiteren analysieren wir, ob verschiedene Destillierungstechniken oder Fehlerkorrektur-Codes von Vorteil bezuglich der sicheren Schlusselrate sind, da der Quanten-Repeater mithilfe von Fehlerkorrektur-Codes weniger klassische Kommunikation braucht. Wir kommen zu dem Ergebnis, dass ersterer Repeater von Vorteil ist fur die hier betrachtete Parameterregion.
Andererseits ist diese Arbeit der Quantenschlusselverteilung ohne Repeater gewidmet. Wir leiten eine Grenze fur die sichere Schlusselrate fur endlich viele Signale unter der Annahme der allgemeinsten Form von Lauschangriffen (koharente Attacke) her. Bisher ist nicht viel uber den Unterschied von sicheren Schlusselraten unter kollektiven und koharenten Lauschangriffen fur eine endliche Anzahl von Signalen bekannt; aber im Limes von unendlich vielen Signalen existiert eine Aquivalenz. Unsere Resultate deuten allerdings darauf hin, dass das fur endlich viele Signale nicht stimmt.