Physics/Computer Science 219
Quantum Computation

Alexei Kitaev

Fall 2009 - Winter 2010

Solutions to problem set 2 have been posted.


Course Description

Basic concepts of quantum mechanics. Introduction into classical complexity theory. Quantum algorithms and quantum complexity. Overview of classical and quantum information theory. Quantum error-correcting codes and fault-tolerant quantum computation. Topological quantum computation. Superconducting qubits.

Class meetings

Monday and Wednesday 1:00-2:30pm, 269 Lauritsen

Instructors

Alexei Kitaev
207 Annenberg
Phone: x8760
Email: kitaev@iqi.caltech.edu

Teaching assistant: Peter Brooks
239 Annenberg
Phone: x3556
Cell Phone: (925)963-5057
Email: pbrooks@caltech.edu
office hours: Friday 3-5pm

Course Requirements

There will be regularly assigned problem sets. The grading is pass/fail.

Prerequisites

I will try to make the course as self-contained as possible. The only essential prerequisites are linear algebra and some basic notion of probability. It would be useful (but not necessary) to have had a previous course on quantum mechanics. In the discussion of Shor's algorithm and its generalizations, we will use some rudimentary group and number theory.

References

Textbooks:   
  • John Preskill,   Lecture notes

  • A.Kitaev, M.Vyalyi, and A.Shen,
    Classical and Quantum computation
    • Other recommended books:   
  • Michael Nielsen and Isaac Chuang,
    Quantum Computation and Quantum Information
    • Research papers:   

    Many original papers on the subject can be found in the e-print archive, section Quantum Physics. Some particular references will be given during the course.

    Note: Most topics are covered by Preskill's lecture notes, which are very nice and relatively easy to read. The book by Kitaev, Vyalyi, and Shen is more mathematical and focused on computational complexity. The complexity theory part of the course will be taught by this book.

    Course Outline

    First term (Fall 2009)

    Foundations of quantum mechanics:
    Quantum states. Measurements and probability. The Schrödinger equation and unitary operators. Tensor product. Quantum gates; basic quantum circuits.
    Quantum mechanics of an open system:
    Density matrix. The Schmidt decomposition and purification. Models of measurement and decoherence; the nature of irreversibility. POVM measurements. Trace distance and fidelity. Superoperators.
    Entanglement:
    The Einstein-Podolsky-Rosen paradox and quantum notion of causality. Bell inequalities. Quantum games without communication. Superdense coding and quantum teleportation.
    Introduction into complexity theory:
    Turing machines and Boolean circuits. Complexity of arithmetic operations; Euclid's algorithm and modular arithmetic. Probabilistic algorithms; primality testing. Complexity classes: P, BPP, NP, PSPACE.
    Quantum circuits:
    Reversible classical computation. Various tricks with quantum gates. Representing unitary operators by two-qubit gates. Precision. Universal gate sets. Quantum Fourier transform.
    Quantum algorithms:
    The class BQP. Grover's search algorithm. Lower bounds for blackbox problems. Simon's and Shor's algorithms. Phase estimation. The hidden subgroup problem.

    Second term (winter 2010)

    Classical and quantum error-correcting codes.
    Elements of classical and quantum information theory.
    Fault-tolerant quantum computation.
    Anyons and other topological approaches to error correction.
    Suprconducting qubits.

    Problem Sets


    Alexei Kitaev 2009-11-20