Quantum Computation

2013-14

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

**Course description: **This
two-term course covers quantum information theory, quantum algorithms, and
quantum error correction.

**Class meetings**:
Monday and Wednesday 2:30-3:55 in 269 Lauritsen.

**Note:** Class will not meet at the
regularly scheduled time the last two weeks of the term. (No class on March 3,
5, 10, 12.) The last two make-up lectures will be **Thursday March 6 and Thursday March 13 at 7:00-8:30 pm in 269 Lauritsen**.

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

Teaching assistant:

Alex Kubica, 235 Annenberg, email: akubica(at)caltech(dot)edu

Michael Beverland, 235 Annenberg, email: mbeverla(at)caltech(dot)edu

Alex and Michael are available to meet with students Mondays at 7 pm in 107 Annenberg on weeks when homework is due, and also every Wednesday 4:00-5:00 pm in 235 Annenberg; if those times don’t work, you can make an appointment by email.

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

Other recommended lecture notes: John Watrous, Umesh
Vazirani, Andrew
Childs, Scott Aaronson

**Course outline for fall term:**

Lecture 1 (Oct. 7):** **Introduction (JP Chapter 1). See also: Quantum computing and the entanglement
frontier , and Can
we exploit the weirdness of quantum mechanics?

Lecture 2 (Oct. 9): Density operators (JP Chapter 2)

Lecture 3 (Oct. 10): HJW theorem, generalized measurements, channels (JP
Chapter 2 and 3)

Lecture notes for Lectures 2-3:
Revised Chapter 2.

Lecture 4 (Oct. 14): Operations, Choi-Jamiolkowski
isomorphism (JP Chapter 3)

Lecture 5 (Oct. 16): Qubit channels (JP Chapter 3)

Lecture 6 (Oct. 17): Master equation, Bell inequalities (JP Chapter 3 and 4)

Lecture 7 (Oct. 21): CHSH game, Local hidden variables, Bell polytope and its
dual. Reference: quant-ph/0102024

Lecture 8 (Oct. 23): Quantum versus classical models, Bell inequality experiments
and loopholes

Lecture 9 (Oct. 28): Quantum entanglement, teleportation, classical
circuits

Lecture 10 (Oct. 30): Complexity classes P, NP, BPP, MA. NP-completeness, Landauer’s principle (JP Chapter 6)

Lecture 11 (Nov. 4): Reversible computing, quantum circuits

Lecture 12 (Nov. 6): Universal quantum gates

Lecture 13 (Nov. 11): Solovay-Kitaev theorem.
Reference: quant-ph/0505030

Lecture notes for Lectures 10-13: Revised Chapter 5.

Lecture 14 (Nov. 13): Black Box model, Deutsch-Jozsa
problem, Simon’s problem (JP Chapter 6)

Lecture 15 (Nov. 18): Period finding

Lecture 16 (Nov. 20): Factoring, public key cryptography, phase estimation

Lecture 17 (Nov. 25): Abelian hidden subgroup problem, discrete logarithm (handwritten
notes – see also notes
on non-abelian HSP)

Lecture 18 (Nov. 27): Quantum searching (handwritten
notes – see also notes
on quantum lower bounds)

Lecture 19 (Dec. 2): Quantum simulation (handwritten
notes)

Lecture 20 (Dec. 4): Local Hamiltonian problem (KSV Chapter 14, handwritten
notes)

**Course outline for winter term:**

A good reference on quantum error correction is this review by Gottesman.
See also JP Chapter 7.

Lecture 1 (Jan. 13): Quantum error-correcting codes

Lecture 2 (Jan. 14): Classical linear codes, quantum CSS codes

Lecture 3 (Jan. 15): Quantum stabilizer codes

Lecture 4 (Jan. 22): Stabilizer codes continued

Lecture 5 (Jan. 27): Existence of good codes, upper bounds on code rate.

Lecture 6 (Jan. 29): Concatenated codes, toric code.

Handwritten
lecture notes on toric code recovery,
fault-tolerant recovery, fault-tolerant gates

Lectures 7-8: Fault-tolerant quantum memory and computation.

Lectures 9-10: Quantum accuracy threshold theorem.

For more details on information theory, see Wilde (also available in an arXiv version).

Handwritten
lecture notes on strong subadditivity of Von
Neumann entropy, Holevo bound, capacities of quantum
channels

Lectures 11-12: Shannon entropy and compression, Von Neumann entropy and
quantum compression.

Lectures 13-14: Strong subadditivity, accessible
information, noisy-channel coding.

Lectures 15-17: Capacities of quantum channels.

**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
the mailbox of Alex Kubica or Michael Beverland, on the 3^{rd} floor of Annenberg.

Problem Set 1. States and measurements. Due Wednesday 23
October 2013. Solutions.

Problem Set 2. Quantum channels and entanglement. Due
Wednesday 6 November 2013. Solutions.

Problem Set 3. Quantum circuits. Due Wednesday 20
November 2013. Solutions.

Problem Set 4. Quantum algorithms. Due Wednesday 4 December 2013. Solutions.

Problem Set 5. Quantum error-correcting codes. Due
Wednesday 5 February 2014. Solutions.

Problem Set 6. Fault-tolerant quantum computing. Due
Wednesday 19 February 2014. Solutions.

Problem Set 7. Entropy and entanglement. Due Wednesday 12
March 2014. Solutions.