Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Zur Lösung von zahlentheoretischen Problemen mit klassischen und Quantencomputern

Schmidt, Arthur

Published Jan 1, 2008• 1 citation
Publisher

Abstract

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].

DOI
10.26083/tuprints-00000855

Related papers

Foundation and principles of quantum computing

Matthias J. Moser

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.

•Jan 1, 2020•0 citations

Eine musterbasierte Methode für die Entwicklung und den Betrieb hybrider Quantenanwendungen

Martin Beisel

Quantencomputer ermöglichen es, bestimmte Berechnungen schneller, genauer und energieeffizienter durchzuführen als klassische Computer, indem sie quantenmechanische Phänomene ausnutzen. Da die Umsetzung der meisten Quantenalgorithmen allerdings Operationen benötigt für die Quantencomputer ungeeignet sind, z. B. Datenbankzugriffe, werden Quantencomputer typischerweise als Spezialprozessoren in hybriden Quantenanwendungen verwendet. Die Entwicklung und der Betrieb dieser hybriden Anwendungen sind komplex und erfordern eine enge interdisziplinäre Zusammenarbeit. Dabei wird tiefgreifendes Wissen aus unterschiedlichen Domänen benötigt, beispielsweise aus der Mathematik, Physik und Softwareentwicklung. Zusätzlich wird die Entwicklung und der Betrieb von Quantenanwendungen durch weitere Faktoren erschwert: (i) Die aktuelle Quantensoftwarelandschaft und die verfügbaren Quanten-Clouddienste, die Zugriff auf unterschiedliche Quantencomputer geben, sind sehr heterogen. (ii) Die schnellen Fortschritte im Quanten-Software-Engineering führen zur Einführung neuer Techniken, welche die Ausführung von Quantenschaltkreisen verbessern können, allerdings aktuell eine komplexe, manuelle Integration erfordern. (iii) Das Fehlen geeigneter Abstraktionsebenen führt dazu, dass die Entwicklung von Quantenanwendungen, insbesondere für Entwickler, die wenig Erfahrung mit Quantencomputing haben, zeitaufwändig und fehleranfällig ist. Um diese Probleme zu lösen, wird in dieser Arbeit die PASTA-Methode präsentiert. Diese basiert auf der Quantencomputingmustersprache, welche etablierte Konzepte und Best Practices in der Quantencomputingdomäne intuitiv verständlich dokumentiert, und stellt einen ganzheitlichen Prozess für diemusterbasierten Entwicklung und den Betrieb von Quantenanwendungen vor. Die Methode beinhaltet alle notwendigen Schritte von der Auswahl der zu verwendenden Quantencomputingmuster, über die Generierung der ausführbaren Quantenanwendung auf Basis wiederverwendbarer Lösungen sowie die Bereitstellung der erforderlichen Softwareartefakte, bis hin zur Überwachung und Analyse der Ausführung hybrider Quantenanwendungen. Zur Umsetzung der PASTA-Methode wird im Rahmen dieser Arbeit die Quantencomputingmustersprache um mehrere Muster erweitert, welche Best Practices für den Betrieb von hybriden Quantenanwendungen sowie etablierte Methoden zur Abschwächung und Korrektur von Quantenfehlern dokumentieren. Um die vom Nutzer ausgewählten Muster in einen ausführbaren Quantenworkflow transformieren zu können, werden eine Vielzahl neuer Workflowmodellierungskonstrukte eingeführt, welche die Spezifikation verschiedener, häufig auftretender Aktivitäten in Quantenworkflows vereinfachen. Weiterhin wird ein Ansatz für die automatische und dynamische Bereitstellung von hybriden Quantenanwendungen auf Grundlage von Nutzeranforderungen vorgestellt. Auf diesen Konzepten aufbauend werden neue Sichten auf Quantenworkflows eingeführt, welche die Überwachung und Analyse von hybriden Quantenanwendungen vereinfachen. Die Sichten ermöglichen es unterschiedlichen Nutzergruppen, wie beispielsweise Quantenexperten und dem Betriebspersonal, Quantenanwendungen auf verschiedenen Abstraktionsebenen zu analysieren und bieten zusätzliche, für die jeweilige Nutzergruppe relevante Informationen. Zur Demonstration der praktischen Umsetzbarkeit der PASTA-Methode wird das PASTA-Framework eingeführt, welches die in dieser Arbeit eingeführten Konzepte prototypisch implementiert. Die Nutzbarkeit der Methode und des Frameworks werden anhand mehrerer Anwendungsfälle evaluiert, für welche eine Laufzeitanalyse sowie eine Nutzerstudie durchgeführt wird.

•Jan 1, 2025•0 citations

Cryptographic Protocols from Physical Assumptions

Alexander Koch

Moderne Kryptographie erlaubt nicht nur, personenbezogene Daten im Internet zu schützen oder sich für bestimmte Dienste zu authentifizieren, sondern ermöglicht auch das Auswerten einer Funktion auf geheimen Eingaben mehrerer Parteien, ohne dass dabei etwas über diese Eingaben gelernt werden kann (mit der Ausnahme von Informationen, die aus der Ausgabe und eigenen Eingaben effizient abgeleitet werden können). Kryptographische Protokolle dieser Art werden sichere Mehrparteienberechnung genannt und eignen sich für ein breites Anwendungsspektrum, wie z.B. geheime Abstimmungen und Auktionen. Um die Sicherheit solcher Protokolle zu beweisen, werden Annahmen benötigt, die oft komplexitätstheoretischer Natur sind, beispielsweise, dass es schwierig ist, hinreichend große Zahlen zu faktorisieren. Sicherheitsannahmen, die auf physikalischen Prinzipien basieren, bieten im Gegensatz zu komplexitätstheoretischen Annahmen jedoch einige Vorteile: die Protokolle sind meist konzeptionell einfacher, die Sicherheit ist unabhängig von den Berechnungskapazitäten des Angreifers, und die Funktionsweise und Sicherheit ist oft für den Menschen leichter nachvollziehbar. (Zum Beispiel forderte das Bundesverfassungsgericht: „Beim Einsatz elektronischer Wahlgeräte müssen die wesentlichen Schritte der Wahlhandlung und der Ergebnisermittlung vom Bürger zuverlässig und ohne besondere Sachkenntnis überprüft werden können.“ (BVerfG, Urteil des Zweiten Senats vom 03. März 2009)). Beispiele für solche Annahmen sind physikalisch getrennte oder unkorrumpierbare Hardware-Komponenten (vgl. Broadnax et al., 2018), Write-Only-Geräte für Logging, oder frei zu rubbelnde Felder, wie man sie von PIN-Briefen kennt. Auch die aus der Quantentheorie folgende Nicht-Duplizierbarkeit von Quantenzuständen ist eine physikalische Sicherheitsannahme, die z.B. verwendet wird, um nicht-klonbares „Quantengeld“ zu realisieren. In der vorliegenden Dissertation geht es neben Protokollen, die die Sicherheit und Isolation bestimmter einfacher Hardware-Komponenten als Vertrauensanker verwenden, im Besonderen um kryptographischen Protokolle für die sichere Mehrparteienberechnung, die mit Hilfe physikalischer Spielkarten durchgeführt werden. Die Sicherheitsannahme besteht darin, dass die Karten ununterscheidbare Rückseiten haben und, dass bestimmte Mischoperationen sicher durchgeführt werden können. Eine Anwendung dieser Protokolle liegt also in der Veranschaulichung von Kryptographie und in der Ermöglichung sicherer Mehrparteienberechnungen, die gänzlich ohne Computer ausgeführt werden können. Ein Ziel in diesem Bereich der Kryptographie ist es, Protokolle anzugeben, die möglichst wenige Karten benötigen – und sie als optimal in diesem Sinne zu beweisen. Abhängig von Anforderungen an das Laufzeitverhalten (endliche vs. lediglich im Erwartungswert endliche Laufzeit) und an die Praktikabilität der eingesetzten Mischoperationen, ergeben sich unterschiedliche untere Schranken für die mindestens benötigte Kartenanzahl. Im Rahmen der Arbeit wird für jede Kombination dieser Anforderungen ein UND-Protokoll – ein logisches UND zweier in Karten codierter Bits; dieses ist zusammen mit der Negation und dem Kopieren von Bits hinreichend für die Realisierung allgemeiner Schaltkreise – konstruiert oder in der Literatur identifiziert, das mit der minimalen Anzahl an Karten auskommt, und dies auch als Karten-minimal bewiesen. Insgesamt ist UND mit vier (für erwartet endliche Laufzeit (Koch, Walzer und Härtel, 2015; Koch, 2018)), fünf (für praktikable Mischoperationen oder endliche Laufzeit (Koch, Walzer und Härtel, 2015; Koch, 2018)) oder sechs Karten (für endliche Laufzeit und gleichzeitig praktikable Mischoperationen (Kastner et al., 2017)) möglich und optimal. Für die notwendigen Struktureinsichten wurden so-genannte „Zustandsdiagramme“ mit zugehörigen Kalkülregeln entwickelt, die eine graphenbasierte Darstellung aller möglichen Protokolldurchläufe darstellen und an denen Korrektheit und Sicherheit der Protokolle direkt ablesbar sind (Koch, Walzer und Härtel, 2015; Kastner et al., 2017). Dieser Kalkül hat seitdem eine breite Verwendung in der bereichsrelevanten Literatur gefunden. (Beweise für untere Schranken bzgl. der Kartenanzahl werden durch den Kalkül zu Beweisen, die zeigen, dass bestimmte Protokollzustände in einer bestimmten kombinatorischen Graphenstruktur nicht erreichbar sind.) Mit Hilfe des Kalküls wurden Begriffe der Spielkartenkryptographie als C-Programm formalisiert und (unter bestimmten Einschränkungen) mit einem „Software Bounded Model Checking“-Ansatz die Längenminimalität eines kartenminimalen UND-Protokolls bewiesen (Koch, Schrempp und Kirsten, 2019). Darüber hinaus werden konzeptionell einfache Protokolle für den Fall einer sicheren Mehrparteienberechnung angegeben, bei der sogar zusätzlich die zu berechnende Funktion geheim bleiben soll (Koch und Walzer, 2018), und zwar für jedes der folgenden Berechnungsmodelle: (universelle) Schaltkreise, binäre Entscheidungsdiagramme, Turingmaschinen und RAM-Maschinen. Es wird zudem untersucht, wie Karten-basierte Protokolle so ausgeführt werden können, dass die einzige Interaktion darin besteht, dass andere Parteien die korrekte Ausführung überwachen. Dies ermöglicht eine (schwach interaktive) Programm-Obfuszierung, bei der eine Partei ein durch Karten codiertes Programm auf eigenen Eingaben ausführen kann, ohne etwas über dessen interne Funktionsweise zu lernen, das über das Ein-/Ausgabeverhalten hinaus geht. Dies ist ohne derartige physikalische Annahmen i.A. nicht möglich. Zusätzlich wird eine Sicherheit gegen Angreifer, die auch vom Protokoll abweichen dürfen, formalisiert und es wird eine Methode angegeben um unter möglichst schwachen Sicherheitsannahmen ein passiv sicheres Protokoll mechanisch in ein aktiv sicheres zu transformieren (Koch und Walzer, 2017). Eine weitere, in der Dissertation untersuchte physikalische Sicherheitsannahme, ist die Annahme primitiver, unkorrumpierbarer Hardware-Bausteine, wie z.B. einen TAN-Generator. Dies ermöglicht z.B. eine sichere Authentifikation des menschlichen Nutzers über ein korrumpiertes Terminal, ohne dass der Nutzer selbst kryptographische Berechnungen durchführen muss (z.B. große Primzahlen zu multiplizieren). Dies wird am Beispiel des Geldabhebens an einem korrumpierten Geldautomaten mit Hilfe eines als sicher angenommenen zweiten Geräts (Achenbach et al., 2019) und mit möglichst schwachen Anforderungen an die vorhandenen Kommunikationskanäle gelöst. Da das angegebene Protokoll auch sicher ist, wenn es beliebig mit anderen gleichzeitig laufenden Protokollen ausgeführt wird (also sogenannte Universelle Komponierbarkeit aufweist), es modular entworfen wurde, und die Sicherheitsannahme glaubwürdig ist, ist die Funktionsweise für den Menschen transparent und nachvollziehbar. Insgesamt bildet die Arbeit durch die verschiedenen Karten-basierten Protokolle, Kalküle und systematisierten Beweise für untere Schranken bzgl. der Kartenanzahl, sowie durch Ergebnisse zur sicheren Verwendung eines nicht-vertrauenswürdigen Terminals, und einer Einordnung dieser in eine systematische Darstellung der verschiedenen, in der Kryptographie verwendeten physikalischen Annahmen, einen wesentlichen Beitrag zur physikalisch-basierten Kryptographie.

•Jan 1, 2019•19 citations

Sicherheitsmodelle für das Ajtai-Dwork-Kryptosystem

Pape Sebastian

Beim Entwurf von Kryptosystemen versucht man deren Sicherheit mittels Reduktionen auf gewisse mathematische Basisprobleme zu grunden. Wer das Kryptosystem brechen kann ist damit auch in der Lage, das Basisproblem zu losen. Wird dem Angreifer nicht zugestanden, das Basisproblem zu losen, gilt das Kryptosystem als sicher. Ein Problem dieser Beweisfuhrung ist jedoch, dass Basisprobleme meist nur im Allgemeinen schwer sind. Bei der Reduktion von Kryptosystemen treten jedoch typischerweise durchschnittliche Probleminstanzen auf, die unter Umstanden sehr viel leichter zu losen sind. Deshalb erregte das Public-Key Kryptosystem von Ajtai und Dwork einiges an Aufsehen. Ihnen war es erstmals gelungen, eine Worst-Case / Average-Case Aquivalenz zwischen dem Kryptosystem und dem zugrunde liegenden Basisproblem zu zeigen. Ajtai und Dwork beschrankten sich allerdings auf den Reduktionsbeweis. Eine formalere Beschreibung der Annahmen uber die Fahigkeiten und Absichten eines potentiellen Angreifers liefern Sicherheitsmodelle. In diesem Buch wird daher untersucht, in welchen Sicherheitsmodellen das Ajtai-Dwork-Kryptosystem als sicher gelten kann.

VDM Verlag Dr. Müller eBooks•Oct 29, 2008•0 citations

Verschränkung und Korrelationen in Vielteilchensystemen

Matthias Maximilian Englbrecht

Verschränkung ist nicht nur notwendig für die Beschreibung des Verhaltens von quantenmechanischen Systemen, sondern ist auch essentiell für einige vielversprechende Anwendungen der Quantenmechanik. Motiviert durch die Bedeutung von Verschränkung werden in dieser Arbeit Themen aus der Vielteilchenverschränkungstheorie behandelt. Der erste Teil der Arbeit besteht aus zwei Unterteilen. Im ersten Unterteil werden separable Kanäle (SEP) betrachtet, d.h., Kanäle, die mittels separabler Krausoperatoren dargestellt werden können. SEP bildet eine strikte übermenge der Menge der Quantenoperationen, die mittels lokaler Operationen und klassischer Kommunikation implementiert werden können (LOCC). Dabei ist LOCC genau die Menge von Quantenoperationen, mittels welcher keine Verschränkung erzeugt werden kann. Separable Transformationen erlauben es notwendige Bedingung für LOCC-Transformationen herzuleiten. Wir zeigen, dass es nicht hinreichend ist nur Kanäle zu betrachten, die mittels separabler und invertierbarer Krausoperatoren dargestellt werden können (SEP1), um zu entscheiden ob zwei reine Zustände mit SEP ineinander transformiert werden können. Dieses Resultat wirft die Frage auf, ob Transformationen mittels SEP1 notwendig sind für LOCC-Transformationen. Während die Relation von SEP1 und LOCC nicht abschließend geklärt werden konnte, wird im Folgenden gezeigt, dass SEP1-Transformationen notwendig sind für Transformationen mittels LOCC-Protokollen, die nur aus endlich vielen Runden klassischer Kommunikation bestehen (LOCCN), also solche LOCC-Protokolle, die physikalisch relevant sind. Darüber hinaus werden notwendige und hinreichende Bedingungen dafür hergeleitet, wann eine Transformation zwischen zwei reinen Zuständen mittels SEP möglich ist (siehe auch [Gour et al. New Journal of Physics 13(7), 073013 (2011)]). Im zweiten Unterteil wird die Verschränkung von Stabilizerzuständen untersucht, da diese Zustände viele Anwendungen in der Quanteninformationstheorie besitzen. Dazu werden lokale Transformationen dieser Zustände betrachtet. Als Voraussetzung dafür werden zunächst alle lokalen Symmetrien von Stabilizerzuständen charakterisiert. Zudem wird ein Algorithmus hergeleitet, um diese für einen gegebenen Zustand zu bestimmen. Diese Ergebnisse werden dann verwendet um LOCCN-Transformatio- nen innerhalb der äquivalenzklasse zu analysieren, die von einem Stabilizerzustand und allen Zuständen, die unter probabilistischen LOCC-Transformationen von diesem erreicht werden können, gebildet wird (SLOCC). Zudem werden Anwendungen von Stabilizerzuständen diskutiert, die aus den Eigenschaften ihrer lokalen Symmetriegruppe abgeleitet werden können. Um einen vergröberten Blick auf die Verschränkung von Stabilizerzuständen zu erhalten, werden dann Cliffordtransformationen zwischen diesen Zuständen untersucht, die lokal bezüglich einer fixierten Menge von Parteien wirken (PLC). Eine solche Partei kann dabei aus mehr als einem Qubit bestehen. Zunächst wird gezeigt, dass PLC Transformationen zwischen Graphenzuständen durch eine verallgemeinerte Form von lokaler Komplementierung beschrieben werden kann. Letztere beschreibt Transformationen zwischen Graphenzuständen mittels lokaler Cliffordoperatoren. Um die entstehenden Äquivalenzklassen zu charakterisieren wird die so genannte verschränkung-generierende Menge (EGS) verwendet [Bravyi et al., J. Math. Phys. 47, 062106 (2006)]. Diese Menge enthält für bis zu drei Parteien nur endlich viele Zustände [Bravyi et al., J. Math. Phys. 47, 062106 (2006)]. Im Folgenden wird gezeigt, dass das EGS für vier und mehr Parteien unendlich viele Elemente enthält. Im zweiten Teil der Arbeit wird die partielle Unterscheidbarkeit von identischen Teilchen in Interferenzexperimenten untersucht, in welchen einige Freiheitsgrade der Teilchen nicht verändert und nicht detektiert werden. Dabei werden insbesondere Bosonen betrachtet. Anwendungen solcher Interferenzexperimente benötigen meist ununterscheidbare Teilchen. Deshalb spielt die Charakterisierung von partieller Unterscheidbarkeit sowie deren Quantifizierung eine wichtige Rolle. Zunächst wird in diesem Teil der Arbeit Literatur zusammengefasst, die für die weiteren Kapitel besonders relevant ist. Diese Literatur beschäftigt sich hauptsächlich mit bestimmten Teilmengen von Zuständen, die relevant sind für Experimente. Ausgehend von dieser Zusammenfassung wird dann eine Definition von Ununterscheidbarkeit und Unterscheidbarkeit für Teilchen formuliert, die durch allgemeine Zustände beschrieben werden. Diese basiert alleinig auf den Informationen über die Teilchen, welche auch in den betrachteten Experimenten zugänglich sind. Die zugehörigen Mengen von Zuständen werden mittels Darstellungstheorie charakterisiert. Darüber hinaus wird eine effiziente Methode hergeleitet um eine obere und eine untere Schranke an ein Ununterscheidbarkeitsmaß mittels Interferenzexperimenten zu bestimmen, welches sich von der Definition von Ununterscheidbarkeit ableitet.

•Jan 1, 2023•0 citations

Numerische und Analytische Lösungen für Quanteninformatisch-relevante Probleme

Andreas K. Spörl

Quantencomputer stellen eine der nachsten technologischen Entwicklungsstufen der modernen Computerwissenschaften dar. In der vorliegenden Arbeit sollen einige Aspekte vorgestellt und untersucht werden, die bei der Implementierung von Quantenoperationen (als Bausteine von Quantenalgorithmen) und der Simulation von Quantensystemen relevant sind. Es werden ausgepragte numerischen Untersuchungen zur Implementierung verschiedenster Quantenoperationen auf einer Reihe von Systemen (NMR-Systeme, Josephson-Elemente, u.a. ) vorgestellt. Um solche Operationen (beispielsweise QuantenFourierTransformationen, SWAP- oder vielfach-kontrollierte NOT-Operationen) auch noch auf groseren Systemen untersuchen zu konnen, wurde ein parallelisiertes C++-Programm entwickelt und optimiert. Neben einer hohen Qualitat der Operationen wird ein besonderes Augenmerk auf die minimale Implementierungsdauer gelegt. Die minimalen Zeiten stellen sowohl fur den Experimentator sowie fur den Mathematiker eine interessante Grose dar. Der Erste versucht durch die schnelle Umsetzungen dissipative Effekte zu minimieren, wahrend der Zweite aus dieser Kenngrose Ruckschlusse uber die analytischen Losungen ziehen kann. Dissipative Effekte konnen jedoch auch direkt in die Optimierung mit einbezogen werden. Die so erhaltenen Losungen sind sowohl relaxations- als auch zeitoptimiert. Fur Systeme mit 3 linear gekoppelten Spin-1/2-Qubits lassen sich fur die Simulation indirekter Ising-Kopplungen oder trilinearer Wechselwirkungen auch analytische Losungen finden. Weiter wurde untersucht, in wie weit sich ein erschopfender Satz von einfachen Kriterien aufstellen lasst, um Systeme zu identifizieren deren Dynamik sich durch lokale Operationen invertieren lasst. Als Letztes wurde ein vollstandiger Quantenalgorithmus zur Unterscheidung von zwei Knoten auf einem Spin-1/2-System implementiert. Die notwendigen Quantenoperation wurden in diesem Fall analytisch berechnet. Die erhaltenen Resultate weisen eine hohe Ubereinstimmung mit theoretischen Werten auf.

•Jan 1, 2008•2 citations
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.
Quantencomputer ermöglichen es, bestimmte Berechnungen schneller, genauer und energieeffizienter durchzuführen als klassische Computer, indem sie quantenmechanische Phänomene ausnutzen. Da die Umsetzung der meisten Quantenalgorithmen allerdings Operationen benötigt für die Quantencomputer ungeeignet sind, z. B. Datenbankzugriffe, werden Quantencomputer typischerweise als Spezialprozessoren in hybriden Quantenanwendungen verwendet. Die Entwicklung und der Betrieb dieser hybriden Anwendungen sind komplex und erfordern eine enge interdisziplinäre Zusammenarbeit. Dabei wird tiefgreifendes Wissen aus unterschiedlichen Domänen benötigt, beispielsweise aus der Mathematik, Physik und Softwareentwicklung. Zusätzlich wird die Entwicklung und der Betrieb von Quantenanwendungen durch weitere Faktoren erschwert: (i) Die aktuelle Quantensoftwarelandschaft und die verfügbaren Quanten-Clouddienste, die Zugriff auf unterschiedliche Quantencomputer geben, sind sehr heterogen. (ii) Die schnellen Fortschritte im Quanten-Software-Engineering führen zur Einführung neuer Techniken, welche die Ausführung von Quantenschaltkreisen verbessern können, allerdings aktuell eine komplexe, manuelle Integration erfordern. (iii) Das Fehlen geeigneter Abstraktionsebenen führt dazu, dass die Entwicklung von Quantenanwendungen, insbesondere für Entwickler, die wenig Erfahrung mit Quantencomputing haben, zeitaufwändig und fehleranfällig ist. Um diese Probleme zu lösen, wird in dieser Arbeit die PASTA-Methode präsentiert. Diese basiert auf der Quantencomputingmustersprache, welche etablierte Konzepte und Best Practices in der Quantencomputingdomäne intuitiv verständlich dokumentiert, und stellt einen ganzheitlichen Prozess für diemusterbasierten Entwicklung und den Betrieb von Quantenanwendungen vor. Die Methode beinhaltet alle notwendigen Schritte von der Auswahl der zu verwendenden Quantencomputingmuster, über die Generierung der ausführbaren Quantenanwendung auf Basis wiederverwendbarer Lösungen sowie die Bereitstellung der erforderlichen Softwareartefakte, bis hin zur Überwachung und Analyse der Ausführung hybrider Quantenanwendungen. Zur Umsetzung der PASTA-Methode wird im Rahmen dieser Arbeit die Quantencomputingmustersprache um mehrere Muster erweitert, welche Best Practices für den Betrieb von hybriden Quantenanwendungen sowie etablierte Methoden zur Abschwächung und Korrektur von Quantenfehlern dokumentieren. Um die vom Nutzer ausgewählten Muster in einen ausführbaren Quantenworkflow transformieren zu können, werden eine Vielzahl neuer Workflowmodellierungskonstrukte eingeführt, welche die Spezifikation verschiedener, häufig auftretender Aktivitäten in Quantenworkflows vereinfachen. Weiterhin wird ein Ansatz für die automatische und dynamische Bereitstellung von hybriden Quantenanwendungen auf Grundlage von Nutzeranforderungen vorgestellt. Auf diesen Konzepten aufbauend werden neue Sichten auf Quantenworkflows eingeführt, welche die Überwachung und Analyse von hybriden Quantenanwendungen vereinfachen. Die Sichten ermöglichen es unterschiedlichen Nutzergruppen, wie beispielsweise Quantenexperten und dem Betriebspersonal, Quantenanwendungen auf verschiedenen Abstraktionsebenen zu analysieren und bieten zusätzliche, für die jeweilige Nutzergruppe relevante Informationen. Zur Demonstration der praktischen Umsetzbarkeit der PASTA-Methode wird das PASTA-Framework eingeführt, welches die in dieser Arbeit eingeführten Konzepte prototypisch implementiert. Die Nutzbarkeit der Methode und des Frameworks werden anhand mehrerer Anwendungsfälle evaluiert, für welche eine Laufzeitanalyse sowie eine Nutzerstudie durchgeführt wird.
Moderne Kryptographie erlaubt nicht nur, personenbezogene Daten im Internet zu schützen oder sich für bestimmte Dienste zu authentifizieren, sondern ermöglicht auch das Auswerten einer Funktion auf geheimen Eingaben mehrerer Parteien, ohne dass dabei etwas über diese Eingaben gelernt werden kann (mit der Ausnahme von Informationen, die aus der Ausgabe und eigenen Eingaben effizient abgeleitet werden können). Kryptographische Protokolle dieser Art werden sichere Mehrparteienberechnung genannt und eignen sich für ein breites Anwendungsspektrum, wie z.B. geheime Abstimmungen und Auktionen. Um die Sicherheit solcher Protokolle zu beweisen, werden Annahmen benötigt, die oft komplexitätstheoretischer Natur sind, beispielsweise, dass es schwierig ist, hinreichend große Zahlen zu faktorisieren. Sicherheitsannahmen, die auf physikalischen Prinzipien basieren, bieten im Gegensatz zu komplexitätstheoretischen Annahmen jedoch einige Vorteile: die Protokolle sind meist konzeptionell einfacher, die Sicherheit ist unabhängig von den Berechnungskapazitäten des Angreifers, und die Funktionsweise und Sicherheit ist oft für den Menschen leichter nachvollziehbar. (Zum Beispiel forderte das Bundesverfassungsgericht: „Beim Einsatz elektronischer Wahlgeräte müssen die wesentlichen Schritte der Wahlhandlung und der Ergebnisermittlung vom Bürger zuverlässig und ohne besondere Sachkenntnis überprüft werden können.“ (BVerfG, Urteil des Zweiten Senats vom 03. März 2009)). Beispiele für solche Annahmen sind physikalisch getrennte oder unkorrumpierbare Hardware-Komponenten (vgl. Broadnax et al., 2018), Write-Only-Geräte für Logging, oder frei zu rubbelnde Felder, wie man sie von PIN-Briefen kennt. Auch die aus der Quantentheorie folgende Nicht-Duplizierbarkeit von Quantenzuständen ist eine physikalische Sicherheitsannahme, die z.B. verwendet wird, um nicht-klonbares „Quantengeld“ zu realisieren. In der vorliegenden Dissertation geht es neben Protokollen, die die Sicherheit und Isolation bestimmter einfacher Hardware-Komponenten als Vertrauensanker verwenden, im Besonderen um kryptographischen Protokolle für die sichere Mehrparteienberechnung, die mit Hilfe physikalischer Spielkarten durchgeführt werden. Die Sicherheitsannahme besteht darin, dass die Karten ununterscheidbare Rückseiten haben und, dass bestimmte Mischoperationen sicher durchgeführt werden können. Eine Anwendung dieser Protokolle liegt also in der Veranschaulichung von Kryptographie und in der Ermöglichung sicherer Mehrparteienberechnungen, die gänzlich ohne Computer ausgeführt werden können. Ein Ziel in diesem Bereich der Kryptographie ist es, Protokolle anzugeben, die möglichst wenige Karten benötigen – und sie als optimal in diesem Sinne zu beweisen. Abhängig von Anforderungen an das Laufzeitverhalten (endliche vs. lediglich im Erwartungswert endliche Laufzeit) und an die Praktikabilität der eingesetzten Mischoperationen, ergeben sich unterschiedliche untere Schranken für die mindestens benötigte Kartenanzahl. Im Rahmen der Arbeit wird für jede Kombination dieser Anforderungen ein UND-Protokoll – ein logisches UND zweier in Karten codierter Bits; dieses ist zusammen mit der Negation und dem Kopieren von Bits hinreichend für die Realisierung allgemeiner Schaltkreise – konstruiert oder in der Literatur identifiziert, das mit der minimalen Anzahl an Karten auskommt, und dies auch als Karten-minimal bewiesen. Insgesamt ist UND mit vier (für erwartet endliche Laufzeit (Koch, Walzer und Härtel, 2015; Koch, 2018)), fünf (für praktikable Mischoperationen oder endliche Laufzeit (Koch, Walzer und Härtel, 2015; Koch, 2018)) oder sechs Karten (für endliche Laufzeit und gleichzeitig praktikable Mischoperationen (Kastner et al., 2017)) möglich und optimal. Für die notwendigen Struktureinsichten wurden so-genannte „Zustandsdiagramme“ mit zugehörigen Kalkülregeln entwickelt, die eine graphenbasierte Darstellung aller möglichen Protokolldurchläufe darstellen und an denen Korrektheit und Sicherheit der Protokolle direkt ablesbar sind (Koch, Walzer und Härtel, 2015; Kastner et al., 2017). Dieser Kalkül hat seitdem eine breite Verwendung in der bereichsrelevanten Literatur gefunden. (Beweise für untere Schranken bzgl. der Kartenanzahl werden durch den Kalkül zu Beweisen, die zeigen, dass bestimmte Protokollzustände in einer bestimmten kombinatorischen Graphenstruktur nicht erreichbar sind.) Mit Hilfe des Kalküls wurden Begriffe der Spielkartenkryptographie als C-Programm formalisiert und (unter bestimmten Einschränkungen) mit einem „Software Bounded Model Checking“-Ansatz die Längenminimalität eines kartenminimalen UND-Protokolls bewiesen (Koch, Schrempp und Kirsten, 2019). Darüber hinaus werden konzeptionell einfache Protokolle für den Fall einer sicheren Mehrparteienberechnung angegeben, bei der sogar zusätzlich die zu berechnende Funktion geheim bleiben soll (Koch und Walzer, 2018), und zwar für jedes der folgenden Berechnungsmodelle: (universelle) Schaltkreise, binäre Entscheidungsdiagramme, Turingmaschinen und RAM-Maschinen. Es wird zudem untersucht, wie Karten-basierte Protokolle so ausgeführt werden können, dass die einzige Interaktion darin besteht, dass andere Parteien die korrekte Ausführung überwachen. Dies ermöglicht eine (schwach interaktive) Programm-Obfuszierung, bei der eine Partei ein durch Karten codiertes Programm auf eigenen Eingaben ausführen kann, ohne etwas über dessen interne Funktionsweise zu lernen, das über das Ein-/Ausgabeverhalten hinaus geht. Dies ist ohne derartige physikalische Annahmen i.A. nicht möglich. Zusätzlich wird eine Sicherheit gegen Angreifer, die auch vom Protokoll abweichen dürfen, formalisiert und es wird eine Methode angegeben um unter möglichst schwachen Sicherheitsannahmen ein passiv sicheres Protokoll mechanisch in ein aktiv sicheres zu transformieren (Koch und Walzer, 2017). Eine weitere, in der Dissertation untersuchte physikalische Sicherheitsannahme, ist die Annahme primitiver, unkorrumpierbarer Hardware-Bausteine, wie z.B. einen TAN-Generator. Dies ermöglicht z.B. eine sichere Authentifikation des menschlichen Nutzers über ein korrumpiertes Terminal, ohne dass der Nutzer selbst kryptographische Berechnungen durchführen muss (z.B. große Primzahlen zu multiplizieren). Dies wird am Beispiel des Geldabhebens an einem korrumpierten Geldautomaten mit Hilfe eines als sicher angenommenen zweiten Geräts (Achenbach et al., 2019) und mit möglichst schwachen Anforderungen an die vorhandenen Kommunikationskanäle gelöst. Da das angegebene Protokoll auch sicher ist, wenn es beliebig mit anderen gleichzeitig laufenden Protokollen ausgeführt wird (also sogenannte Universelle Komponierbarkeit aufweist), es modular entworfen wurde, und die Sicherheitsannahme glaubwürdig ist, ist die Funktionsweise für den Menschen transparent und nachvollziehbar. Insgesamt bildet die Arbeit durch die verschiedenen Karten-basierten Protokolle, Kalküle und systematisierten Beweise für untere Schranken bzgl. der Kartenanzahl, sowie durch Ergebnisse zur sicheren Verwendung eines nicht-vertrauenswürdigen Terminals, und einer Einordnung dieser in eine systematische Darstellung der verschiedenen, in der Kryptographie verwendeten physikalischen Annahmen, einen wesentlichen Beitrag zur physikalisch-basierten Kryptographie.
Beim Entwurf von Kryptosystemen versucht man deren Sicherheit mittels Reduktionen auf gewisse mathematische Basisprobleme zu grunden. Wer das Kryptosystem brechen kann ist damit auch in der Lage, das Basisproblem zu losen. Wird dem Angreifer nicht zugestanden, das Basisproblem zu losen, gilt das Kryptosystem als sicher. Ein Problem dieser Beweisfuhrung ist jedoch, dass Basisprobleme meist nur im Allgemeinen schwer sind. Bei der Reduktion von Kryptosystemen treten jedoch typischerweise durchschnittliche Probleminstanzen auf, die unter Umstanden sehr viel leichter zu losen sind. Deshalb erregte das Public-Key Kryptosystem von Ajtai und Dwork einiges an Aufsehen. Ihnen war es erstmals gelungen, eine Worst-Case / Average-Case Aquivalenz zwischen dem Kryptosystem und dem zugrunde liegenden Basisproblem zu zeigen. Ajtai und Dwork beschrankten sich allerdings auf den Reduktionsbeweis. Eine formalere Beschreibung der Annahmen uber die Fahigkeiten und Absichten eines potentiellen Angreifers liefern Sicherheitsmodelle. In diesem Buch wird daher untersucht, in welchen Sicherheitsmodellen das Ajtai-Dwork-Kryptosystem als sicher gelten kann.
Verschränkung ist nicht nur notwendig für die Beschreibung des Verhaltens von quantenmechanischen Systemen, sondern ist auch essentiell für einige vielversprechende Anwendungen der Quantenmechanik. Motiviert durch die Bedeutung von Verschränkung werden in dieser Arbeit Themen aus der Vielteilchenverschränkungstheorie behandelt. Der erste Teil der Arbeit besteht aus zwei Unterteilen. Im ersten Unterteil werden separable Kanäle (SEP) betrachtet, d.h., Kanäle, die mittels separabler Krausoperatoren dargestellt werden können. SEP bildet eine strikte übermenge der Menge der Quantenoperationen, die mittels lokaler Operationen und klassischer Kommunikation implementiert werden können (LOCC). Dabei ist LOCC genau die Menge von Quantenoperationen, mittels welcher keine Verschränkung erzeugt werden kann. Separable Transformationen erlauben es notwendige Bedingung für LOCC-Transformationen herzuleiten. Wir zeigen, dass es nicht hinreichend ist nur Kanäle zu betrachten, die mittels separabler und invertierbarer Krausoperatoren dargestellt werden können (SEP1), um zu entscheiden ob zwei reine Zustände mit SEP ineinander transformiert werden können. Dieses Resultat wirft die Frage auf, ob Transformationen mittels SEP1 notwendig sind für LOCC-Transformationen. Während die Relation von SEP1 und LOCC nicht abschließend geklärt werden konnte, wird im Folgenden gezeigt, dass SEP1-Transformationen notwendig sind für Transformationen mittels LOCC-Protokollen, die nur aus endlich vielen Runden klassischer Kommunikation bestehen (LOCCN), also solche LOCC-Protokolle, die physikalisch relevant sind. Darüber hinaus werden notwendige und hinreichende Bedingungen dafür hergeleitet, wann eine Transformation zwischen zwei reinen Zuständen mittels SEP möglich ist (siehe auch [Gour et al. New Journal of Physics 13(7), 073013 (2011)]). Im zweiten Unterteil wird die Verschränkung von Stabilizerzuständen untersucht, da diese Zustände viele Anwendungen in der Quanteninformationstheorie besitzen. Dazu werden lokale Transformationen dieser Zustände betrachtet. Als Voraussetzung dafür werden zunächst alle lokalen Symmetrien von Stabilizerzuständen charakterisiert. Zudem wird ein Algorithmus hergeleitet, um diese für einen gegebenen Zustand zu bestimmen. Diese Ergebnisse werden dann verwendet um LOCCN-Transformatio- nen innerhalb der äquivalenzklasse zu analysieren, die von einem Stabilizerzustand und allen Zuständen, die unter probabilistischen LOCC-Transformationen von diesem erreicht werden können, gebildet wird (SLOCC). Zudem werden Anwendungen von Stabilizerzuständen diskutiert, die aus den Eigenschaften ihrer lokalen Symmetriegruppe abgeleitet werden können. Um einen vergröberten Blick auf die Verschränkung von Stabilizerzuständen zu erhalten, werden dann Cliffordtransformationen zwischen diesen Zuständen untersucht, die lokal bezüglich einer fixierten Menge von Parteien wirken (PLC). Eine solche Partei kann dabei aus mehr als einem Qubit bestehen. Zunächst wird gezeigt, dass PLC Transformationen zwischen Graphenzuständen durch eine verallgemeinerte Form von lokaler Komplementierung beschrieben werden kann. Letztere beschreibt Transformationen zwischen Graphenzuständen mittels lokaler Cliffordoperatoren. Um die entstehenden Äquivalenzklassen zu charakterisieren wird die so genannte verschränkung-generierende Menge (EGS) verwendet [Bravyi et al., J. Math. Phys. 47, 062106 (2006)]. Diese Menge enthält für bis zu drei Parteien nur endlich viele Zustände [Bravyi et al., J. Math. Phys. 47, 062106 (2006)]. Im Folgenden wird gezeigt, dass das EGS für vier und mehr Parteien unendlich viele Elemente enthält. Im zweiten Teil der Arbeit wird die partielle Unterscheidbarkeit von identischen Teilchen in Interferenzexperimenten untersucht, in welchen einige Freiheitsgrade der Teilchen nicht verändert und nicht detektiert werden. Dabei werden insbesondere Bosonen betrachtet. Anwendungen solcher Interferenzexperimente benötigen meist ununterscheidbare Teilchen. Deshalb spielt die Charakterisierung von partieller Unterscheidbarkeit sowie deren Quantifizierung eine wichtige Rolle. Zunächst wird in diesem Teil der Arbeit Literatur zusammengefasst, die für die weiteren Kapitel besonders relevant ist. Diese Literatur beschäftigt sich hauptsächlich mit bestimmten Teilmengen von Zuständen, die relevant sind für Experimente. Ausgehend von dieser Zusammenfassung wird dann eine Definition von Ununterscheidbarkeit und Unterscheidbarkeit für Teilchen formuliert, die durch allgemeine Zustände beschrieben werden. Diese basiert alleinig auf den Informationen über die Teilchen, welche auch in den betrachteten Experimenten zugänglich sind. Die zugehörigen Mengen von Zuständen werden mittels Darstellungstheorie charakterisiert. Darüber hinaus wird eine effiziente Methode hergeleitet um eine obere und eine untere Schranke an ein Ununterscheidbarkeitsmaß mittels Interferenzexperimenten zu bestimmen, welches sich von der Definition von Ununterscheidbarkeit ableitet.
Quantencomputer stellen eine der nachsten technologischen Entwicklungsstufen der modernen Computerwissenschaften dar. In der vorliegenden Arbeit sollen einige Aspekte vorgestellt und untersucht werden, die bei der Implementierung von Quantenoperationen (als Bausteine von Quantenalgorithmen) und der Simulation von Quantensystemen relevant sind. Es werden ausgepragte numerischen Untersuchungen zur Implementierung verschiedenster Quantenoperationen auf einer Reihe von Systemen (NMR-Systeme, Josephson-Elemente, u.a. ) vorgestellt. Um solche Operationen (beispielsweise QuantenFourierTransformationen, SWAP- oder vielfach-kontrollierte NOT-Operationen) auch noch auf groseren Systemen untersuchen zu konnen, wurde ein parallelisiertes C++-Programm entwickelt und optimiert. Neben einer hohen Qualitat der Operationen wird ein besonderes Augenmerk auf die minimale Implementierungsdauer gelegt. Die minimalen Zeiten stellen sowohl fur den Experimentator sowie fur den Mathematiker eine interessante Grose dar. Der Erste versucht durch die schnelle Umsetzungen dissipative Effekte zu minimieren, wahrend der Zweite aus dieser Kenngrose Ruckschlusse uber die analytischen Losungen ziehen kann. Dissipative Effekte konnen jedoch auch direkt in die Optimierung mit einbezogen werden. Die so erhaltenen Losungen sind sowohl relaxations- als auch zeitoptimiert. Fur Systeme mit 3 linear gekoppelten Spin-1/2-Qubits lassen sich fur die Simulation indirekter Ising-Kopplungen oder trilinearer Wechselwirkungen auch analytische Losungen finden. Weiter wurde untersucht, in wie weit sich ein erschopfender Satz von einfachen Kriterien aufstellen lasst, um Systeme zu identifizieren deren Dynamik sich durch lokale Operationen invertieren lasst. Als Letztes wurde ein vollstandiger Quantenalgorithmus zur Unterscheidung von zwei Knoten auf einem Spin-1/2-System implementiert. Die notwendigen Quantenoperation wurden in diesem Fall analytisch berechnet. Die erhaltenen Resultate weisen eine hohe Ubereinstimmung mit theoretischen Werten auf.