Term: Semester B
Lectures: Tuesday 11:15-13:00, Ziskind Room 155
Instructor: Thomas Vidick
Office Hour: Tuesdays 16:00-17:00, Ziskind Room 204
Course description
This course will cover the theory of quantum error correction. We will start with the basics: how to model errors on a quantum computer, what is a quantum error correcting codes, elementary examples and constructions. We will progressively work our way towards more advanced code constructions and in particular constructions of good quantum low-density parity-check codes. We will illustrate unique quantum features of these constructions by discussing entanglement and applications to quantum complexity theory.
Course outline
The course has 3 main parts:
- Part 1 (~4 lectures): Introduction to quantum error correction. The quantum formalism, sources of quantum error. Basics of quantum codes, CSS codes. Topological examples.
- Part 2 (~2 lectures): Fault tolerance. The model, approaches, fault-tolerance threshold.
- Part 3 (~4 lectures): Asymptotic constructions of families of good quantum codes. Quantum LDPC codes. Application to the NLTS conjecture.
We have 11-12 lectures in total, so the above breakdown is approximate.
Prerequisites
The most important prerequisites are: (1) a familiarity with basic linear algebra (finite-dimensional vector spaces, matrices, singular value decomposition, etc.), which is required to work with the quantum formalism, and (2) some experience in (classical) algorithms and complexity, which is useful at a conceptual level. The required notions in error correction and in quantum computing will be introduced in the course. In particular we aim to make the course accessible without any background in quantum computing; students with no such background will be given additional reading to help them catch up over the first few lectures.
Evaluation & workload
Attendance to lecture is mostly required. We will provide pointers to material available online that is equivalent to the material covered in lecture, but we do not have lecture notes or a book that we follow closely. The workload is divided between reading & digestion of lecture, and some problem sets. There will be 3 problem sets. Each set can be solved over the course of ~2 weeks.
Schedule of lectures
Indicative and continuously updated:
- Lecture 1 (18/04): Introduction to error correction. Introduction to the quantum formalism; basics of classical and quantum error correction.
Reading: See this book chapter for basics of the quantum formalism (ignore sections 1.7, 1.8). See Bacon's notes Sections 2.1 and 2.2 for an introduction to QEC and the Shor code.
- Lecture 2 (02/05): Stabilizer codes. For a leisurely introduction, see Sections 10.5.1 and 10.5.2 in the book by Nielsen and Chuang. For a more dense description, continue with Bacon's notes, Sections 2.9.1, 2.9.2 and 2.9.3 (these presuppose a little bit on the theory of errors which we will cover in the following lecture).
- Lecture 3 (09/05): CSS codes. Example: the Steane code. Knill-Laflamme criteria for quantum error correction.
For a good explanation of the Knill-Laflamme conditions for error correction, see Section 7.2 in Preskill's notes. Sections 7.5 and 7.6 from the same notes discuss CSS codes, and Section 7.7 presents the Steane code.
- Lecture 4 (16/05) General quantum maps, Krauss operators. Necessity and sufficiency of the Knill-Laflamme criteria.
For an introduction to the formalism of density matrices, the partial trace, and general measurements, see Sections 2.1 to 2.4 in this book chapter. For general channels/CPTP maps, see Section3.3. The Knill-Laflamme conditions are discussed in Section 7.2 of Preskill's notes.
- HW1 due by 5pm on May 21st.
- Lecture 5 (06/06) Distance of stabilizer codes. Error detection and recovery for stabilizer codes. Existence of good quantum codes.
Some useful background on the stabilizer formalism is in Section 10.5.1 of the Nielsen & Chuang book. Section 10.5.8 discusses error detection (syndrome measurement) and recovery. The Quantum Gilbert-Varshamov bound is presented in Section 2.5 of this thesis. See these notes for a succinct discussion of some bounds I had planned to, but did not cover in class.
- Lecture 6 (13/06): First constructions of asymptotic families of quantum codes with growing distance! Topological codes. The toric code and more general surface codes. We followed relatively closely the notes by Bombin, stopping roughly at the end of Section 4.2; with some additional material on homology.
- Lecture 7 (20/6): Distance of a CSS code. Application to the Toric code. Decoding for the Toric code.
- Lecture 8 (27/06) Hypergraph product codes. I am not aware of good lecture notes on this topic. For a succinct presentation based on chain complexes, close to what we did in class, see Section 4 of this paper. In particular, Theorem 4.2 specialized to the case where X_2=0 recovers the main parameters (rate and distance) of the construction. For a different presentation than we took in class, see the original paper by Tillich and Zémor.
(Classical) expander codes: definition and properties. We covered roughly the notes by Guruswami (Section 2.2 and 3 excluded).
- HW2 due by 10pm on June 27th.
- Lecture 9 (04/07) Quantum Tanner codes: definition and dimension. The paper introducing the codes we discussed is this one. The presentation we gave in class is based on this paper, Specifically, the construction, using very similar notation to the one we used, is detailed in Section 2. You may find some of the pictures there useful.
- Lecture 10 (09/07): Quantum Tanner codes: distance and decoding. We will prove a linear lower bound on the minimal distance, roughly following the argument in Section 3 here. Time permitting we will briefly discuss decoding, with a view towards the application to the NLTS construction.
- Lecture 11 (17/07): Applications to complexity. The class QMA, the local Hamiltonian problem and the quantum PCP conjecture: see this survey for much more on the topic. We sketched the NLTS construction which appears in this paper. For a recent talk describing the argument, and some motivation for the NLTS notion, see here.
- HW3 due by 5pm on July 25th.
Resources
The standard textbook for quantum information and computation is the book by Nielsen and Chuang, which is available online. Section 10 is on error correction, and we will cover most of the topics there (though not necessarily in the same order/with the same presentation. The most relevant introductory sections to quantum computing are 2.1 to 2.4; a good understanding of the material presented there will ultimately be needed to follow the course.
A good introduction to quantum error correction, aimed at a computer science audience, is in Chapter 2 of the book by Lidar and Brun, which is written by Dave Bacon. These notes by Gottesman are also good. For a somewhat more physical perspective, there are some excellent lecture notes by Girvin. And of course, the notes by Preskill are an extensive reference.
For topological codes, the notes by Bombin (which also appear in a chapter of the book by Lidar and Brun) provide a great introduction.