Decoherence is an ubiquitous effect observed in quantum mechanics, driving quantum systems towards the classical regime. It is detrimental to quantum computers, and for a long time was thought to be a fundamental obstacle to the physical realization of quantum computation. However, it turns out that decoherence is NOT a fundamental obstacle, rather it can be overcome by the techniques of quantum error-correction and fault-tolerant quantum computation.
This course teaches those techniques and how to apply them. The capstone result presented is the so-called Threshold Theorem of Fault-tolerant Quantum Computation (TT). It says that arbitrarily long quantum algorithms can be run efficiently on imperfect quantum computer hardware, as long this hardware matches a certain accuracy threshold. Slightly simplified, if the logical error introduced by decoherence per quantum gate is below a critical threshold, then the faulty gates are pretty much as good as prefect gates.
After presenting the TT, the course addresses questions regarding the value of the threshold, the scaling of the overhead for error correction, and fault-tolerance in the presence of architectural constraints (short range entangling gates, magic state factories, etc.)
Announcements:
Audience: The course is intended for graduate and senior undergraduate students of Physics, Computer Science, Engineering and Mathematics.
Time and location: Term 2 (Jan 11, 2021 to Apr 14, 2021). The class takes place Monday + Wednesday 2pm-3:30pm, location: Zoom.
Credits: 3.
Grading: 1/3 homework assignments, 1/3 written exam, 1/3 essay/ oral presentation.
Office hour: My office hour takes place Friday 6-7 PM (Zoom).
The Lecture Notes (under construction) can be found here.
Homework Assignment 1: Posted Jan 24, due Feb 8, 6 PM.
Homework Assignment 2: Posted Feb 14, due Mar 1, 6 PM.
Homework Assignment 3: Posted Mar 7, due Mar 22, 6 PM.
Homework Assignment 4: Posted Mar 27, due April 6, 6 PM.
Homework Assignment 5, supplemental python file Posted April 9, due April 20, 6 PM.
Recording of office hour 1: (Friday, Jan 22, 2021).
Recording of office hour 2: (Friday, Jan 29, 2021).
Recording of office hour 3: (Friday, Feb 5, 2021).
Recording of office hour 4: (Friday, Feb 12, 2021).
Recording of office hour 5: (Friday, Feb 26, 2021).
Recording of office hour 6: (Friday, Mar 5, 2021).
Recording of office hour 7: (Friday, Mar 12, 2021).
Recording of office hour 8: (Friday, Mar 19, 2021).
Recording of office hour 9: (Friday, Mar 26, 2021).
Recording of office hour 10: (Thursday, Apr 1, 2021).
Recording of office hour 11: (Friday, Apr 9, 2021).
Lecture 1 [01/11/21] Slides, lecture recording. Background of quantum mechanics: Quantum states, evolution and observation. (a) Quantum states: pure states and Hilbert spaces, the inner product, mixed states and density matrices, entanglement. (b) Evolution according to the Schroedinger equation, unitarity. (c) [coming up] Quantum measurement: the Dirac projection postulate and the Born rule.
Lecture 2 [01/13/21] Slides, lecture recording. Finishing with the background of quantum mechanics: (c) Quantum measurement: the Dirac projection postulate and the Born rule. Background on quantum computation: universality, and the teleportation protocol.
Lecture 3 [01/18/21] Slides, lecture recording. Definition of quantum code, CPTP map, and error recovery procedure. The repetition code, first application of the definition of the recovery procedure.
Lecture 4 [01/22/21] Slides, lecture recording. The 9-qubit Shor code, threshold behaviour, code concatenation, a decoherence model with no non-zero threshold (long-range interaction), error discretization.
Lecture 5 [01/25/21] Slides, lecture recording. Quantum operations and the Kraus representation; unitary freedom in the Kraus representation. Definition of "set of correctable errors" and "error recovery map". General error correction condition.
Lecture 6 [01/27/21] Slides, lecture recording - Part 1, Part 2. Proof of the general error correction condition. Proof of the fact that an error recovery map that corrects a set {E_i} of errors also corrects all errors in Span({E_i}). [This is the general foundation of the phenomenon of error discretization]
Lecture 7 [02/01/21] Slides, lecture recording. Stabilizer codes and stabilizer states.
Lecture 8 [02/03/21] Slides, lecture recording. Quantum error correction condition for stabilizer codes. Stabilizer generator matrix. (Anti)commutation among Pauli operators and linear algebra mod 2.
Lecture 9 [02/08/21] Slides, lecture recording. The CSS construction. Examples of stabilizer codes: (repitition code, Shor code), 5-qubit code, Steane code, surface codes.
Lecture 10 [02/10/21] Slides, lecture recording. Surface codes: definition, geometric interpretation of errors and syndrome; what is topological here?; the use of boundaries.
Lecture 11 [02/22/21] Slides, lecture recording. Stabilizer states, Clifford unitaries and Pauli measurements. The Gottesman-Knill theorem.
Lecture 12 [02/24/21] Slides, lecture recording. The Gottesman-Knill theorem: stabilizer update under Pauli measurements. Start of Section 4: Overview of the techniques for fault-tolerant quantum computation - transversal gates, magic state injection, circuits for stabilizer measurement.
Lecture 13 [03/01/21] Slides, lecture recording. Transversal encoded gates, fault tolerant measurement of code stabilizer, magic states - use and preparation.
Lecture 14 [03/03/21] Slides, lecture recording. The threshold theorem of fault-tolerant quantum computation.
Lecture 15 [03/08/21] Slides, lecture recording. Reed-Muller codes and transversal quantum gates. Part 1: Definition of the classical Reed Muller codes, and the Theorem of Ax.
Lecture 16 [03/10/21] Slides, lecture recording. Reed-Muller codes and transversal quantum gates. Part 2: The Eastin-Knill theorem, and how to circumvent it. Transversal quantum gates for the 15 qubit Reed-Muller CSS code: T (main topic), CNOT, cPhase, Hadamard (the latter invoking transversal measurement).
Lecture 17 [03/15/21] Slides, lecture recording. Magic state distillation based on Reed Muller codes.
Lecture 18 [03/17/21] Slides, lecture recording. Quantum computer architecture. Fault-tolerant quantum computation within a local 2D architecture, Part I.
Lecture 19 [03/22/21] Slides, lecture recording. Quantum computer architecture. Fault-tolerant quantum computation within a local 2D architecture, Part II: Topological gates, topological circuit for magic state injection.
Lecture 20 [03/24/21] Slides, lecture recording. Introduction to measurement-based quantum computation.
Lecture 21 [03/29/21] Slides, lecture recording. Measurement-based quantum computation: proof of universality.
Lecture 22 [03/31/21] Slides, lecture recording. Lecture by Xiruo Yan on error mitigation in the NISQ era; Part I.
Lecture 23 [04/07/21] Slides, lecture recording. Lecture by Xiruo Yan on error mitigation in the NISQ era; Part II.
Student presentations, Part I [04/12/21] Presentation recording.
Student presentations, Part II [04/14/21] Presentation recording.
In this course we address the questions of which physical systems, from the current perspective, are suitable for building a quantum computer; and how to counteract the effects of decoherence. The course outline is as follows:
Elements of quantum computation
Quantum codes
Fundamental techniques for fault-tolerant quantum computation
Fault-tolerance and quantum computer architecture
Error mitigation in the NISQ era
Student Presentations: Monday April 12 and Wednesday April 14, in class (plan for 2hrs). Schedule TBA.
Instructor: Robert Raussendorf, Department of Physics and Astronomy, raussen[at]phas.ubc.ca
Teaching Assistant: Xiruo Yan, Department of Physics and Astronomy, xyan[at]phas.ubc.ca