Quantenrechner sind ein Berechnungsmodell, von dem vermutet wird, dass man damit manche algorithmischen Probleme effizienter als mit gewöhnlichen klassischen Rechnern lösen kann. Beispielsweise kennt man zurzeit für das Problem der Faktorisierung von ganzen Zahlen keinen effizienten Algorithmus für klassische Rechner, wohl aber einen effizienten Algorithmus für Quantenrechner. Allerdings können derzeit nur winzig kleine Quantenrechner praktisch realisiert werden; an der Realisierung von größeren Quantenrechnern wird intensiv geforscht.

Die Sicherheit der meisten bekannten kryptographischen Systeme beruht auf Annahmen, dass bestimmte mathematische Probleme keine effizienten Algorithmen haben. Aus solchen Annahmen kann man dann folgern, dass es auch für das Brechen des jeweiligen kryptographischen Systems keinen effizienten Algorithmus gibt, das System also sicher ist. Insbesondere die Sicherheit des RSA-Systems beruht auf der Annahme, dass es keinen effizienten Algorithmus für das Faktorisieren von ganzen Zahlen gibt. Ob diese Annahme stimmt, ist derzeit unbekannt. Aber selbst wenn das Faktorisierungsproblem keinen effizienten Algorithmus für gewöhnliche Rechner hat, könnte es irgendwann einmal Quantenrechner geben, mit denen das RSA-System gebrochen werden kann.

In der Quantenkryptographie versucht man dieses Problem durch die Konstruktion von beweisbar sicheren kryptographischen Protokollen zu vermeiden. Für den Beweis der Sicherheit derartiger Protokolle benötigt man keine Annahmen über die Nichtexistenz von effizienten Algorithmen mehr. Die einzige Annahme, die für den Beweis der Sicherheit noch benötigt wird, besteht darin, dass die derzeit bekannten Naturgesetze, insbesondere die Quantentheorie, zutreffend sind.

In der Vorlesung sollen zunächst die Grundlagen für die Beschreibung von Quantenalgorithmen erarbeitet werden. Danach sollen die bekannten Quantenalgorithmen vorgestellt werden, nämlich der bereits erwähnte Faktorisierungsalgorithmus und ein Algorithmus für ein bestimmtes Suchproblem. Anschließend wird das BB84-Protokoll aus der Quantenkryptographie zusammen mit einem Beweis seiner Sicherheit behandelt.

Inhalt der Vorlesungen

• 16.10.2007: Einführung, historische Entwicklung, Qubits, Messungen, EPR-Paare
• 18.10.2007: Systeme mit n Qubits, Tensorprodukt, Blochsphäre, unitäre und normerhaltende Operationen, Operationen auf einem Qubit, CNOT
• 23.10.2007: Quantenschaltkreise, No-Cloning-Theorem, Quantum Teleportation
• 25.10.2007: Simulation von klassischen Schaltkreisen, Deutsch-Algorithmus, Deutsch-Jozsa-Algorithmus, Einführung lineare Algebra: Hilberträume
• 30.10.2007: Äußeres Produkt, adjungierte Operatoren, Projektionen, Eigenwerte, Spur, Wurzeln aus linearen Operatoren, Einführung Quantentheorie: Postulat zur Beschreibung von Zuständen
• 06.11.2007: Reine und gemischte Zustände, zusammengesetzte Systeme, partielle Spur
• 08.11.2007: Unitäre Zustandsentwicklung, Dekohärenz, Messungen
• 13.11.2007: Filtermessungen, universelle Bausteinsätze für Quantenschaltkreise
• 19.11.2007: Quanten-Fourier-Transformation: Definition, Produktformel, Quantenschaltkreis; Phasenbestimmung für Phasen mit endlicher Binärdarstellung
• 20.11.2007: Approximation von Phasen ohne endliche Binärdarstellung, Ordnungsproblem, Formulierung des Ordnungsproblems als Phasenbestimmung, Erzeugung der benötigten Eigenvektoren
• 22.11.2007: Realisierung der benötigten unitären Transformation mit Quantenschaltkreisen, Kettenbruchmethode, Fehlermöglichkeiten beim vorgestellten Algorithmus und Abschätzung der Erfolgswahrscheinlichkeit (Anmerkung), erste Ideen für die Reduktion des Faktorisierungsproblems auf die Ordnungsberechnung
• 27.11.2007: Reduktion des Faktorisierungsproblems auf die Ordnungsberechnung, Abschätzung der Versagenswahrscheinlichkeit
• 29.11.2007: Abschätzung der Erfolgswahrscheinlichkeit des gesamten Algorithmus und der benötigten Iterationen, Faktorisierung von 21, Brechen des RSA-Systems mit nur einer Ordnungsberechnung, Einführung Quantensuchalgorithmen, Ablauf des Grover-Algorithmus
• 04.12.2007: Geometrische Interpretation der Grover-Iteration, Bestimmung der Anzahl der Iterationen und Abschätzung der Fehlerwahrscheinlichkeit, Abschätzung von M mit dem Quantenschaltkreis für die Phasenbestimmung
• 06.12.2007: Fehlerabschätzung für die Kombination aus Phasenbestimmung und Grover-Algorithmus, Berechnung des Minimums, Überblick über Teil 2 der Vorlesung
• 11.12.2007: Einführung und Überblick zur klassischen Kryptographie, die Cäsar-Chiffre, die Vernam-Chiffre und ihre Sicherheit
• 13.12.2007: Schlüssellänge bei informationstheoretischer Sicherheit, das Diffie-Hellman-System zum Schlüsselaustausch, Authentifizierung mit stark universellen Hashfunktionen, Schritte 1 und 2 der Konstruktion von geeigneten Hashfunktionen
• 18.12.2007: Vervollständigung der Konstruktion von Hashfunktionen, Entropie, gegenseitige Information, Privacy Amplification
• 20.12.2007: Bit Commitment mit quadratischen Resten, POVMs, Einführung in die Abstandsmaße Trace-Distanz und Fidelity
• 08.01.2008: Eigenschaften der Trace-Distanz, die Fidelity von einem reinen und einem gemischten Zustand
• 14.01.2008: Satz von Uhlmann, Minimierung der Fehlerwahrscheinlichkeit bei der Unterscheidung von nichtorthogonalen Zuständen
• 15.01.2008: Konstruktion einer Messung mit minimaler Fehlerwahrscheinlichkeit, lineare Codes, Einführung CSS-Codes
• 17.01.2008: Fehlerkorrektur bei CSS-Codes, Eigenschaften von CSS_u,v, Einführung Quantenkryptographieprotokolle, Verwendung von nichtorthogonalen Zuständen
• 24.01.2008: Locking, Schlüsselerzeugung aus EPR-Paaren, ein hinreichendes Kriterium für die Sicherheit
• 25.01.2008: Das EPR-Protokoll, kommutierende Messungen, die EPR-Basis und Messungen für Bit-Flips und Phase-Flips
• 29.01.2008: Lokale Realisierungen der Messungen, ein Random-Sampling-Ansatz zur Verringerung der Anzahl der Messungen
• 31.01.2008: Lokale Messungen auf den Testqubits, Fehlerkorrektur, Verschiebung der Hadamard-Transformationen. Prepare-and-Measure-Protokolle: Vermeidung der Erzeugung von EPR-Paaren, Verzicht auf die Phasenkorrektur
• 05.02.2008: Verzicht auf die Erzeugung von u, Modifikation der Erzeugung von k, das BB84-Protokoll
• 07.02.2008: Realisierung des BB84-Protokolls mit Photonen und denkbare Angriffe gegen die Realisierung, ein Protokoll für Quantum Bit Commitment und ein gegen dieses Protokoll

Übungen

Literatur

• M.A. Nielsen, I.L. Chuang, Quantum Computation and Quantum Information. Cambridge University Press 2000.
• M. Sauerhoff, Skript zur Vorlesung Quantenrechner: Algorithmen und Komplexität, 2003. Erhältlich unter http://ls2-www.cs.uni-dortmund.de/lehre/sommer2003/QR/
• D. Sieling, Begleitmaterial zum Teil Quantenkryptographie, 2007. Korrekturen und Ergänzungen zum Begleitmaterial.