QIC 890/CO 781/CS 867:

Quantum Error Correction and Fault Tolerance, Winter 2012


Debbie Leung

Email: wcleung(at)uwaterloo(dot)ca

Daniel Gottesman

Email: dgottesman(at)perimeterinstitute(dot)ca


T 3:30-6:20pm, RAC1 2009


Surviving as a Quantum Computer in a Classical World, Daniel Gottesman, to be handed out in class

For creditors: Please enroll to reserve a copy.

For auditors, email the instructors.

For the first installment (Chaps 1-6): if you did not pick up a copy during the first class, you can pick up a copy from Monica Dey Jan 9-10 (while supply lasts).

Instructor office hours:

T 2:25-3:25pm, RAC1 1007


7 assignments (70%)

1 project resulting in a term paper and a presentation (30%)


Posted Dec 29, 2011, 3:22pm

Webpage is set up.

Tentative class and assignment schedule:

Lecture 1, January 03, 2012.

Administrative introduction, quantum operations and channels, quantum codes correcting bit flip errors and phase flip errors, the 9-qubit Shor code.

Correcting for a combination of quantum errors, definition of a quantum error correcting code, degenerate and nondegenerate codes, quantum error correction criterion, definition of distance.

Lecture 2, January 10, 2012.

Stabilizer codes (definition of stabilizer, basic properties of stabilizer, 5-qubit code), classical linear codes (generator and parity check matrices, Hamming codes), CSS codes (definition and the 7-qubit code).

Stabilizer codes as GF(4) codes, perfect codes, quantum Hamming bound, quantum Gilbert-Varshamov bound, quantum singleton bound.

Problem set 1 out (covering lectures 1 and 2), due next lecture.

Lecture 3, January 17, 2012

Encoded operations for stabilizer codes and CSS codes. The Clifford group and general properties of conjugation maps.

Efficient simulation of Clifford group circuits, efficient simulation of Pauli measurements, Gottesman-Knill theorem, generators for Clifford group, encoding circuits for stabilizer codes.

Problem set 2 out (covering lecture 3), due next lecture.

Lecture 4, January 24, 2012

Introduction to fault-tolerance, definition of transversal gates, definition of fault-tolerant gates, transversal Pauli and Clifford gates for the 7-qubit code and CSS codes. Definition of fault-tolerant measurements. Fault-tolerant measurement of logical Z for CSS codes.

Problem set 3 out (covering lecture 4), due next lecture.

Lecture 5, January 31, 2012

Shor error correction, fault-tolerant measurement of stabilizers, fault-tolerant state preparation, gate teleportation, fault-tolerant Clifford gates for stabilizer codes, non Clifford gates for 7-bit code.

Magic state distillation, Steane error correction.

Problem set 4 out (covering lecture 5), due lecture 7.

Lecture 6, Feburary 07, 2012

Assumptions for fault tolerance, extended rectangles, good, bad, and correct rectangles

Equivalence of fault-tolerant circuits to less noisy unencoded circuits, threshold theorem, calculation of the threshold

Lecture 7, Feburary 14, 2012

Circuit assumptions for fault-tolerance re-examined (other universal gate sets, local gates, fresh ancillas, no measurements, parellelism)

Error assumptions for fault-tolerance re-examined (other error models, correlated errors, leakage errors, coherent and non-Markovian errors)

Problem set 5 out (covering lecture 6 and 7), due next lecture.

Lecture 8, Feburary 28, 2012

Toric codes

Problem set 6 out (covering lecture 8), due lecture March 13.

Lecture 9, March 06, 2012

Local stabilizer codes in three dimensions without string logical operators

Lecture 10, March 13, 2012

Anyonic quantum computation

Problem set 7 out (covering lecture 10), due next lecture.

Lecture 11, March 20, 2012

Special topics, chosen from: fault-tolerance in measurement based quantum computation, Shor-Bacon code, approximate error correction, entanglement purification and error correction codes, channel capacities

Lecture 12, March 27, 2012

Student presentations

Term paper due.


Assignment 1, due Jan 17, 2012 in class.

Assignment 2, due Jan 24, 2012 in class.

Assignment 3, due Jan 31, 2012 in class.

Assignment 4 part I and part II. Due Feb 14, 2012.

Assignment 5, due Feb 28, 2012 in class.

Assignment 6, due Mar 13, 2012 in class.

Assignment 7, due Mar 20, 2012 in class.

Possible project topics:

Coding theory:

Qudit QECCs

Quantum Turbo codes

Quantum LDPC codes

Codeword-stabilized codes

Subsystem codes

Degenerate codes

Decoherence-free subspaces

Approximate error correction

Dynamical decoupling.


Knill FT scheme

Comparison of thresholds from different codes

Upper bounds on the threshold

Magic state distillation protocols

Threshold theorem for non-Markovian noise

Other topics:

Quantum channel capacity

Experimental quantum error correction

Shor-Preskill QKD proof

Quantum secret sharing

Multi-party secure quantum computation

Measurement-based quantum computation

The above is not an exhaustive list. Students can suggest further topics related to the course by email to both instructors.

Each student should choose a project topic by the end of Feburary (via email to both instructors). Upon approval of the topic by the instructors, the student will select some research papers related to the topic in consultation with the instructors, and will be presenting the results in the assigned papers in lecture 12. A term paper is due end of March.