Quantum Computation

2008-09

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

**Course description: **This is a
three-term course covering quantum information, quantum algorithms, quantum error
correction, and quantum cryptography.

**Class meetings**:
Monday and Wednesday 1:00-2:30 in 269 Lauritsen,
beginning 29 September 2008

**Note:** **There will be no lecture on May 27. The
last lecture of the year is on June 1. **

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

Teaching assistant:

Prabha Mandayam, 449 Lauritsen, X-6595, email: prabhamd@caltech.edu

**Lectures and references:
**The primary reference for most of the lectures will be these lecture
notes (JP). Other useful references are

Supplementary handwritten notes (scanned 3.6 MB pdf file)

**Jan. 5, Jan. 7:** Quantum
algorithms. Deutsch and Deutsch-Jozsa
problems, Simon’s problem, period finding. (JP, 6.3 and 6.9)

**Jan. 21, Jan. 26**: Factoring
algorithm, public key cryptosystems, eigenvalue
estimation (JP, 6.10, 6.11)

**Jan. 28, Feb. 2**: Hidden subgroup
problem for finitely generated abelian groups (handwritten
notes, 2.5 MB)

**Feb. 9**: Nonabelian
subgroup problem (handwritten
notes), **Feb. 11**: Quantum
searching (handwritten
notes)

**Feb. 18, Feb. 23**: Lower bounds on
quantum query complexity (updated handwritten
notes)

**Feb. 25, Mar. 2**: Simulating quantum
evolution, estimating energy eigenvalues (updated handwritten
notes)

**Mar. 4, 9, 11**: Complexity of
estimating ground state energy of classical and quantum Hamiltonians. (KSV
Chap. 14, handwritten
notes)

The reference for the first five lectures of the second term is JP, Chapter
7 (“Quantum error correction”), Sec. 1-10, 14, 15.1.

**Mar. 30**: Concept of a quantum
error-correcting code and the error correction criteria.

**Apr. 1, 6**: Classical binary linear
codes, quantum CSS codes, stabilizer codes.

**Apr. 8**: The five-qubit
code, existence of good stabilizer codes.

**Apr. 13**: Concatenated quantum codes, toric
code (reference: quant-ph/0110143, Sec. III, IV.C, and V).

A good reference for the next few lectures is this recent review.

**Apr. 15, 20**: Toric
code recovery, fault-tolerant recovery (updated
handwritten notes)

**Apr. 22, 25**: Fault-tolerant quantum
gates (handwritten
notes)

**Apr. 29**: Quantum accuracy threshold
theorem (arXiv:0904.2557, Sec. 5)

The reference for the next few lectures is JP, Chapter 5 (Quantum
Information Theory).

**May 4, 6**:

**May 11, 13**: Von Neumann entropy,
Schumacher compression, entanglement cost and distillable entanglement for
bipartite pure states (Sec. 5.2, 5.3, 5.5).

**May 18, 20**: Strong subadditivity, accessible information, capacities of
quantum channels (updated
handwritten notes)

**June 1**: Mother and father protocols
and their children (handwritten
notes)

Other references for June 1 lecture: quant-ph/0308044, quant-ph/0505062, quant-ph/0606225

**Homework assignments:**

All students taking the course for credit are required to do the homework,
which will be assigned several times each term.
You can hand in the homework in class on the due date, or leave it in Prabha Mandayam’s mailbox,
outside 452 Lauritsen.

Problem Set 1 [PDF]
(posted Tuesday 14 October 2008; due Wednesday 29 October 2008). Solution: [PDF]

Problem Set 2 [PDF]
(posted Tuesday 28 October 2008; due Wednesday 12 November 2008). Solution: [PDF]

Problem Set 3 [PDF]
(posted Tuesday 11 November 2008; due Wednesday 26 November 2008). Solution: [PDF]

Problem Set 4 [PDF]
(posted Tuesday 9 January 2009; Prob. 4.4c corrected 20 January; due Wednesday
28 January 2009). Solution: [PDF]

Problem Set 5 [PDF]
(posted Monday 2 February 2009; due Wednesday 11 February 2009). Solution: [PDF]

Problem Set 6 [PDF]
(posted Tuesday 17 February 2009; due Wednesday 4 March 2009). Solution: [PDF]

Problem Set 7 [PDF]
(posted Tuesday 14 April 2009; due Wednesday 29 April 2009). Solution: [PDF]

Problem Set 8 [PDF]
(posted Thursday 30 April 2009; due Wednesday 13 May 2009). Solution: [PDF]

Problem Set 9 [PDF]
(posted Sunday 17 May 2009; due Monday 1 June 2009). Solution: [PDF]