Quantum Computing

Mi 13:30-15:00 (V) und 15:15-16:00 (Ü), Hösaal 28 B 110   CAMPUS

Vorlesung am 11. Nov. 2009 fällt aus

Grundlegende Eigenschaften der Quantenmechanik wie die Superposition oder die Verschränktheit von Zuständen widersetzen sich hartnäckig der Anschauung (Schrödingersche Katze, EPR-Paradox). Nach anfänglichem Staunen werden diese Eigenschaften jetzt zunehmend praktisch genutzt, etwa in neuen Konzepten zur Informationsübetragung oder bei der Entwicklung schneller Algorithmen für Quantencomputer. Neben dem praktischen Aspekt effizienter Algorithmen gibt die Untersuchung der Grundlagen der Quanteninformation also eine gute Gelegenheit, unser Verständnis der Quantenmechanik zu vertiefen.

In der Vorlesung werden zunächst grundlegende Fragen der Quantenmechanik (Verschränktheit, EPR-Paradox, Bellsche Ungleichungen) sowie der Informationstheorie (Berechenbarkeit, Komplexität, reversible Logik) besprochen. Darauf aufbauend wird gezeigt, wie sich daraus neue Ansätze für die Quanteninformationsverarbeitung ergeben. Einfache Anwendungen sind etwa das No-Cloning Theorem für Quantenzustände oder die Teleportation. Im Anschluss werden Konzepte für Quantencomputer erläutert und wichtige Quantenalgorithmen (z.B. Shorscher Faktorisierungsalgorithmus und Groverscher Suchalgorithmus) erklärt.

Vorlesungen

  1. overview lecture: slides
  2. Einführung
    • Folien
    • Claude E. Shannon: A Mathematical Theory of Communication
      The Bell System Technical Journal 27 379-423, 623-656 (1948)
    • Häufigkeitsverteilung von Buchstaben in Texten: JavaScript Programm (works in Firefox 3.5)
    • A Series of Approximations to English: JavaScript Programm
    • Übungen
      1. Lesen Sie diesen Artikel und zeigen Sie, dass sich mittels Datenkompression (zip/gzip etc.) die Sprache bzw. der Autor eines Textes bestimmen lässt. Beispiel-Texte finden Sie z.B. auf Project Gutenberg.
        Beispiel: bash Skript zur Sprach-Identifizierung
      2. Besuchen Sie den Vortrag
        Trapping and counting photons in vivo: a non-destructive way to look at light
        von S. Haroche im Physikalischen Kolloquium am Montag dem 26. Oktober 2010 um 17:15 in Hörsaal 28 D001
  3. Einfürung und Unschärfe
  4. Verschräkung: Bellsche Ungleichung, GHZ Zustand
    • Übungen
      Es gibt immer wieder Versuche Bell-artige Experimente klassisch zu erklären. Als Beispiel, vollziehen Sie die Argumentation in
      K. De Raedt, K. Keimpema, H. De Raedt, K. Michielsen, S. Miyashita
      A local realist model for correlations of the singlet state
      Eur. Phys. J. B 53, 139-142 (2006)
      nach.

      Falls Ihnen einzelne Punkte unklar sind, finden Sie ähnliche Argumente in

      Was ist das physikalische Argument, um Teilchen eines Paares per Koinzidenz nachzuweisen? Welche Voraussetzung geht hier ein? Was ist die Rolle des time delay? Wie ändert sich die Analyse, wenn die Quelle Paare mit einer sehr geringen Rate, d.h. mit großem zeitlichen Abstand, aussendet? Was liefert das local realist model bei Anwendung auf ein GHZ Experiment?

  5. Anwendungen von Unschärfe und Verschränktheit
    • N.D. Mermin: Quantum cryptography and some simple uses of entanglement
    • Übungen:
      • Lesen Sie W.K. Wootters and W.H. Zurek
        A single quantum cannot be cloned
        Nature 299, 802 (1982)
      • Klassische Information lässt sich kopieren. Gibt es eine reversible Operation, die ein Cbit kopiert? Finden Sie eine reversible Operation, die zwei Cbits vertauscht: (a,b) -> (b,a). Funktioniert das auch für Qbits? Zeigen Sie, dass die Vertauschungsoperation aus controlled NOT Gattern konstruiert werden kann.
      • Zeigen Sie, dass man mit Hadamard Transformation und controlled NOT aus dem Zustand |00> einen Verschräkten Zustand erzeugen kann. Welche Zustände erhalten Sie, wenn Sie die Operation auf die restlichen Basiszuständen |01>, |10> und |11> andwenden?
  6. Berechenbarkeit und Komplexität
    • Übung: Dichte Codierung
      Alice möchte Bob eine von vier Botschaften (=2 Bits) senden, hat aber nur die Möglichkeit ein Qbit zu übertragen. Wie geht sie vor? (Hinweis: zu Beginn seien Alice und Bob im Besitz je eines Qbit eines verschränkten Paares)
  7. Reversible Logik
    • T. Toffoli: Reversible Computing
    • E. Fredkin and T. Toffoli: Conservative Logic
    • Übungen
      • Drücken Sie das Toffoli Gatter mittels eines Fredkin- und 2-Bit Gattern aus.
      • Konstruieren Sie mittels 1-Bit- und cNOT-Operationen aus |000> einen GHZ Zustand.
  8. Quanten Gatter
    • Übungen: reversibler Volladdierer
      Konstruieren Sie einen reversiblen Volladdierer a+b=c (siehe Vorlesungsskript)
      • Konstruieren Sie zunächst einen Volladdierer für nur eine Binärstelle i der Zahlen a und b:
        Input: ci (Übertrag aus der nächst niedrigeren Stelle), ai, bi und ci+1=0
        Output: in ci wird die i-ten Stelle der Summe (a+b)i geschrieben, ai und bi bleiben unverädert, und ci+1 enthält den Übertrag in die nächst höhere Stelle.
      • Setzen Sie aus diesen Elementen einen Addierer für n-Stellige Binärzahlen zusammen. Die n+1 Bits c0 ... cn werden mit 0 initialisiert und enthalten nach Abschluss der Rechnung die Summe a+b.
  9. Einfache Quantenalgorithmen
  10. Quanten Fourier-Transformation
    • N.D. Mermin: Breaking RSA Encryption with a Quantum Computer
    • Übungen:
      Gegeben sei ein 10-Qbit Quanten Register mit Amplituden as=as+p=as+2p=... für gegebenen offset s und Periode p. Alle anderen Amplituden seien Null. Bestimmen Sie die Amplituden der Quanten-Fourier Transformation für verschiedene s und zwei verschiedene Perioden p, wobei eine ein Teiler von 210 sein soll und die andere 210 nicht teile.
  11. Shor Algorithmus
  12. Grover Algorithmus

References

Spezialvorlesung, Universität Stuttgart, WS 2002/03, Do 11:30-13:00, V 57.04
E. Koch, MPI-FKF

Contents of Lectures

  1. Introduction
    Information is physical: Cbits and Qbits
    The concept of quantum computing: Quantum parallelism and measurment
    Example: The Deutsch Algorithm
    J.Rink: Quäntchen für Quäntchen
    c't 16/98, S.150
    M.A. Nielsen: Rules for a complex quantum world
    Scientific American, Nov. 2002, pp. 49
  2. Quantum weirdness: Uncertainty and Entanglement
    How real are Observables? Uncertainty relations
    EPR argument, Bell's inequalities, GHZ experiment
    F. Laloë: Do we really understand quantum mechanics?
    Am.J.Phys. 69 655-701 (2001)
    N.D. Mermin: What is quantum mechanics trying to tell us?
    Am.J.Phys. 66 753-767 (1998)
    A. Zeilinger: Experiment and the foundations of quantum mechanics
    Rev.Mod.Phys. 71 S288-S297 (1999)
  3. Applications of uncertainty and entanglement
    Quantum cryptography
    Bit commitment (an why it doesn't work)
    No-cloning theorem
    Teleportation
  4. Computability and Computational Complexity
    Computability: Church-Turing thesis, Halting problem
    Complexity: Polynomial vs. exponential, NP-completeness
    S. Mertens: Computational complexity for physicists
  5. Reversible Logics and Quantum Gates
    Boolean logics and normal forms
    Reversible logics and Toffoli gate
    Conservative logics and Fredkin gate
    Example: Full-adder in reversible logics
    V. Vedral, A. Barenco, and A. Ekert: Quantum networks for elementary arithmetic operations
    Phys.Rev. A 54 147 (1996)
  6. Quantum Gates
    Generalizing reversible gates
    Sleater-Weinfurter construction: Toffoli gate from 2-Qbit gates
    Universal quantum gates
    A.Barenco et al.: Elementary gates for quantum computation
    Phys.Rev.A 52 3457 (1995)
  7. Simple Quantum Algorithms
    Deutsch-Jozsa algorithm
    Bernstein-Vazirani algorithm
    Simon's algorithm
  8. The Discrete Fourier-Transform with Quantum Gates
  9. Shor Algorithm and RSA Encryption
    slide
    A. Ekert and R. Jozsa: Quantum computation and Shor's factoring algorithm
    Rev.Mod.Phys. 68 733-753 (1996)
  10. Grover Algorithm (Amplitude Amplification)
    slides
  11. Simulating Physical Systems
    Analog computation
    Classical systems: Verlet algorithm
    Quantum dynamics: Trotter decomposition
  12. Decoherence: Measurement problem and classical states
    Theory of measurements: Kopenhagen and von Neumann interpretations
    Entanglement with environment: Decoherence
    Why do classical particles appear localized?
    A. Armour: Notes on decoherence
    H.D. Zeh: The meaning of decoherence
    W.H. Zurek: Decoherence, einselection, and the quantum origins of the classical
  13. Quantum Error Correction: Bit Errors
    Cbit: Hamming code
    Qbit: Decoherence, discrete error states (Pauli matrices)
    MultiQbit codes: error states and error syndrom
    Example: 5-Qbit code
    J. Preskill: Reliable quantum computers
    Proc.Roy.Soc. Lond. A 454 385-410 (1998)
  14. What makes quantum computers powerful?
    Summary and overview

Landauer's disclaimer (Nature 400 720 (1999)):
This proposal, like all proposals for quantum computation, relies on speculative technology, does not in its current form take into account all possible sources of noise, unreliability and manufacturing error, and probably will not work.

Erik Koch