Quantum Computation

2006-07

**Go to home page for
Ph219/CS219 in past years.**

**Course description: **The course
covers quantum information, quantum algorithms, quantum error correction, and
quantum cryptography.

**Class meetings**:
Tuesdays and Fridays

**Instructors:
**John Preskill
, 448 Lauritsen, X-6691, email: preskill@theory.caltech.edu

Alexei Kitaev , 280 Jorgensen, X-8760, email: kitaev@cs.caltech.edu

Teaching assistant:

Hui Khoon Ng , 445 Lauritsen, X-2633, email:

**Lectures and references:
**Preskill will lecture the first half of the first term, covering
roughly the material in the first four chapters of his lecture
notes. Kitaev will lecture the second half of the
first term, covering classical and quantum algorithms and complexity; the
primary reference for this portion of the course will be

**Week**** 1 (Sep. 26, 29): **Introduction. Quantum information, entanglement,
quantum algorithms, quantum error
correction.

**Week 2 (Oct. 3, 6): **Density operators. Open systems, Bloch
sphere, Schmidt decomposition, HJW theorem.

**Week 3 (Oct. 10, 13): **Quantum operations. Generalized
measurements, completely positive maps, Kraus operators, decoherence.

**Week 4 (Oct. 17, 20, 24): **Quantum nonlocality.
Hidden variables,

**Oct. 27: **Discussion of computational complexity. Simulating quantum
mechanics requires exponential time but only linear space.

**Oct 31, Nov. 3: **Turing machines and Boolean circuits. Uniform and nonuniform computational
problems; P vs. P/poly. Circuit size and depth; log-depth circuits for
addition and multiplication.

**Nov. 7: **Energy cost of bit erasure. Reversible classical
circuits. Garbage removal.

**Nov. 10: **Examples of quantum gates and circuits. Two-qubit
gates are universal.

(Supplementary material: http://www.arxiv.org/pdf/quant-ph/9503016)

**Nov.14: **Approximate realization of unitary operators. Solovay-Kitaev theorem.

**Nov. 17**: Standard gate sets. Grover's algorithm.

**Nov. 20**: The optimality of Grover's algorithm. Abelian hidden subgroup problem.

**Nov. 27**: Simon's algorithm. Quantum Fourier transform.

**Dec. 1**: Factoring and period finding. Shor's algorithm.

The reference for the first couple of weeks of the second term is Chapter 7
of Preskill’s lecture
notes (“Quantum error correction”).

**Jan. 5**: Concept of a quantum
error-correcting code and the error correction criteria.

**Jan. 9, 12**: Classical binary linear
codes, quantum CSS codes, stabilizer codes.

**Jan. 16**: The five-qubit code, existence of good stabilizer codes.

**Jan. 19**: Concatenated quantum codes,
toric code (reference: quant-ph/0110143).

References for the lectures on fault-tolerant quantum computing: quant-ph/0504218 (referred to
as “AGP” below), and quant-ph/9712048 (referred to as “Pres97”).

**Jan. 23**: Fault-tolerant error
correction (AGP Sec. 2 and Sec. 7; Pres97).

**Jan. 26**: Fault-tolerant Clifford group gates (quant-ph/9807006, quant-ph/9802007).

**Jan. 30 :** Fault-tolerant C_3 gates (quant-ph/0002039).

**Feb. 2 :** Quantum accuracy threshold theorem (AGP Sec.
4, Sec. 5, Sec. 9)

**Homework assignments:**

The course is graded pass/fail, and all students taking the course for credit
are required to do the homework, which will be assigned several times each
term.

Problem Set 1 [PS] [PDF]
(posted

Problem Set 2 [PS] [PDF]
(posted

Problem Set 3 [PS] [PDF]
(posted

Problem Set 4 [PS]
[PDF]
(posted

Problem Set 5 [PS] [PDF]
(posted Monday 22 January 2007; due Tuesday 6 February 2007). Solution: [PS] [PDF]

Problem Set 6 [PS] [PDF]
(posted

Problem Set 7 [PS]
[PDF]
(posted