Quantum Computation

2019-20

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

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

**Class meetings**:
Monday and Wednesday 2:30-3:55 in 107 Downs, beginning 2 October 2019.

**Instructor:
**John Preskill,
206 Annenberg, X-6691, email: preskill(at)caltech(dot)edu

Teaching assistants:

Tian Wang, 232 Annenberg, email: twang3(at)caltech(dot)edu

Office hours: 4-5:30 pm Monday, in weeks when homework is due.

Course information posted by Tian can be accessed on Moodle.

Thom Bohdanowicz, 239 Annenberg, email: thom(at)caltech(dot)edu

**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:
**Topics covered in the tall will include density operators, quantum
operations, quantum entanglement, quantum circuits, and quantum algorithms.

Lecture 1 (Oct 2):** **Introduction (JP Chapter 1).

See also: Quantum computing and the
entanglement frontier, Quantum
computing in the NISQ era and beyond, and Why
I called it “quantum supremacy”

Video: Canadian Summer School on Quantum Information Lecture 1, Lecture 2.

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

Lecture 3 (Oct 9): Convexity, HJW theorem, generalized measurements (JP Chapter 3).

Lecture 4 (Oct 14): Quantum channels, complete positivity (JP Chapter 3).

Lecture 5 (Oct 16): Channel state duality (JP Chapter 3)

Lecture 6 (Oct 21): Qubit channels, master equation (JP Chapter 3)

Lecture 7 (Oct 23): Bell inequalities, CHSH game (JP
Chapter 4)

Lecture 8 (Oct 28): Bell polytope and its dual, quantum vs classical models

Reference: quant-ph/0102024

Lecture 9 (Oct 30): Superdense coding and quantum teleportation (JP Chapter 4)

Lecture 10 (Nov 4): Circuit complexity, P and NP, NP-completeness (JP Chapter 5)

Lecture 11 (Nov 6): BPP and MA, Reversible computing, BQP and QMA (JP Chapter
5)

Lecture 12 (Nov 11): Quantum circuits, universal gates (JP Chapter 5)

Lecture 13 (Nov 13): Universal gates continued, Solovay-Kitaev
theorem (JP Chapter 5)

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

Lecture 15 (Nov. 20): Period finding

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

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

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

Lecture 19 (Dec. 4): Local Hamiltonian problem (KSV Chapter 14, notes
by Richard Kueng, handwritten
notes by JP)

We did not have time to cover this in class, but here are some notes on the abelian and nonabelian hidden subgroup problems.

**Homework assignments:**

All students taking the course for credit are required to do the homework. Unless otherwise announced, homework will be
due on Thursday at 5pm.

Homework should be handed into the box outside of the Ann 232 by the due date, or emailed to Tian <twang3@caltech.edu> if you type it up. Please use a large font or write legibly.

You may receive partial credit if you describe a thoughtful approach to the problem, even if you are unable to solve it completely.

If you have questions, you may post them on Moodle or email them to Tian. Problem solutions will be posted on Moodle.

Problem
Set 1. States and measurements, due Thursday October 24.

Problem
Set 2. Quantum channels and entanglement, due Thursday November 7.

Problem
Set 3. Universal quantum gates, due Thursday November 21.

Problem
Set 4. Quantum algorithms, due Thursday December 5.