Quantum Computing

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

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.

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.

References

Erik Koch