Classical and Quantum Codes

Spring 2022

ENEE729C, CMSC858Q, MATH729C, PHYS899C


Instructors :
  Victor V. Albert
    (*)Joint Center for Quantum Information and Computer Science, (*)Department of Physics
    E-mail: vva at  umd  dot edu
  Alexander Barg
    (*)Department of ECE, (*)Inst. for Systems Research, (*)Department of CS, (*)Department of Mathematics
     E-mail: abarg at  umd  dot edu

Class times:
Lectures: MW 11:00 - 12:15 PHY 2124
Instructor availability outside class hours: Please send us an email, including an online meeting request

Course Homepage: Syllabus: http://www.ece.umd.edu/~abarg/CQC;   Lecture notes: Canvas

Course description: This is an Advanced Topics graduate-level course covering several important aspects of classical and quantum coding theory from a unified perspective. We discuss basic principles of and connections between classical and quantum coding theory. On the classical part, we discuss families of algebraic codes and their decoding, spherical codes and combinatorial constructions, and the results of the last decade relating to achieving Shannon capacity of basic communication channels.On the quantum side, we describe why quantum error correction is possible, go over basic constructions such as the stabilizer formalism, CSS codes, and toric/surface codes, and touch upon related continuous-variable error-correcting codes.

Prerequisites The course focuses on mathematical reasoning, so general mathematical maturity and previous experience of similar kind is essential. Most of the results are established from the first principles, so no specific background is required (except for good knowledge of basic linear algebra). Information theory or quantum mechanics are not among prerequisites; the material will be discussed from the first principles.

Textbook: No required textbook. The lectures draw on multiple sources, some of which are listed below.

Grading: Homeworks (1/3), Final exam (1/3), Course project/End of course presentation (1/3)
Project topics and materials will be distributed halfway into the course (please wait for the announcement).

Course contents: We plan to cover the following topics:

  1. Reed-Solomon codes; Codes on algebraic curves and their decoding
  2. Rank metric codes
  3. Expander codes, codes on 2D complexes, and families of good locally testable codes
  4. Fourier analysis on $\{0,1\}^n$, linear programming, and bounds on codes
  5. Connections between classical and quantum codes
  6. Stabilizer codes, CSS codes, Polynomial codes
  7. Toric/surface codes and topological error correction

Assignments: There will be two home assignments in addition to the assignment described in the next paragraph.
    Home assignment 1 [pdf] [solutions]
    Home assignment 2 [pdf] [solutions]
    Final exam [pdf] Due date May 15

  • You will provide three entries into the EC Zoo --- an online database of classical and quantum error-correcting codes. An entry can be a single code or a family of codes. Entries will include a description of the code, its error-correcting properties, protected gates, rate, threshold, decoder, encoder, and other properties. Entries can be related to topics chosen for the course project.


  • Course project A list of topics for the course project is posted here
    Project presentations: May 9, 11, starting at 11:00am.

    Detailed contents of the course: (tentative outline; will be adjusted as we progress)

       Basic coding theory
    Lecture 1. (1/24) Metric spaces of Coding Theory, Linear codes and their duals.
    Lecture 2. (1/26) Shannon's perspective of packing: Capacity of the BSC and BEC.
        Madhu Sudan's Lectures 2,3; my paper with G.D. Forney; UMass Lect.7 by Arya Mazumdar.
        Exercises: Problems 1-8, 10,11 in this list (not collected or graded). Check your answers here.

       Classical code families
    Lecture 3. (1/31) Fundamentals of finite fields
        Forney's notes | My class notes (Lec.11,12,17) | [R], Ch.3; [MS], Sec.4.1-4.3
        Exercises: Problems 31, 32, 34 in this list (not collected or graded). Check your answers here.
    Lecture 4. (2/2) Reed-Solomon (RS) codes; their properties, and their decoding
    Lecture 5. (2/7) Interpolation decoding of Reed-Solomon codes: Unique and List
        BW Algorithm in brief | [GRS], Ch.15; Ch.7
    Lecture 6. (2/9) Interpolation list decoding. Limits to list decoding. Codes on algebraic curves.
    Lecture 7. (2/14) Codes on algebraic curves; Hermitian codes, their parameters
        [B] Ch.9 (first 4 sections); Sec. 10.3, 10.4
        Exercises: [click here] (not collected or graded)
    Lecture 8 (2/16) Hermitian codes. Coding in the matrix space: Rank metric codes.
        Reading on rank metric codes: Introduction [pdf] | More on parameters [pdf], [pdf]
    Lecture 9 (2/21) Maximum rank distance codes: construction and Welch-Berlekamp decoding
        Reading: Introduction [pdf] [ 2, pp.3-24] | Decoding [pdf] [pdf] |
    Lecture 10. (2/23) Expander graphs: Spectral expanders. Expander codes, parameters and decoding
        A survey on expanders [pdf] | Madhu Sudan's lectures 13,14
    Lecture 11. (2/28) Expander codes, codes on 2D complexes, and families of good locally testable codes (LTCs).
        LTC codes: Dinur et al. [pdf] Leverrier-Zémor [pdf] | Youtube talks: [pdf] [pdf] |
    Lecture 12. (3/2) Locally testable codes (LTC) on 2D complexes. Fourier transforms and duality of codes
        Reading for Fourier transform: [pdf]
    Lecture 13. (3/7) Delsarte inequalities. Linear programming bounds for binary codes.
        Reading: Navon-Samorodnitsky [pdf]
    Lecture 14. (3/9) Linear programming bounds for codes and sphere packings.
        Reading: H. Cohn's lectures [pdf] Lec. 4 | Sphere packigns [pdf]
    Lecture 15. (3/14) Achieving the Shannon capacity: Polar codes.
       Eren Sasoglu's tutorial | Arikan's 2009 paper | Youtube lectures of Telatar and Urbanke | My notes
        [GRS] Ch.11 (more detailed than we did in class)
    Lecture 16. (3/16) Proof of polarization.
    Lecture 16a Polar codes and Reed-Muller codes (Recording posted to ELMS)

    March 21-25 Spring break

       Quantum code families
    Lecture 17. (3/28) Noisy quantum mechanics, QECC Basics.
        Daniel Gottesman's lectures.
    Lecture 18. (3/30) Bit and phase-flip codes, 4- and 9-qubit codes, QECC conditions.
        VVA notes Sec. 3.
    Lecture 19. (4/4) Stabilizer codes I: basic properties, CSS codes.
        Daniel Gottesman's lectures.
    Lecture 20. (4/6) Stabilizer codes II: symplectic representation, codes over GF(4).
        Daniel Gottesman's lectures.
    Lecture 21. (4/11) Stabilizer codes II: symplectic representation, codes over GF(4).
        Daniel Gottesman's lectures.
    Lecture 22. (4/13) Qudit stabilizer codes, polynomial codes, GKP codes.
        Daniel Gottesman's's lectures and VVA notes.
    Lecture 23. (4/18) Bounds on QECCs: quantum Singleton bound, quantum Hamming, quantum Gilbert-Varshamov, quantum MacWilliams identity.
        Daniel Gottesman's lectures.
    Lecture 24. (4/20) Clifford group: connection to symplectic representation4
        Daniel Gottesman's lectures.
    Lecture 25. (4/25) Clifford group: connection to symplectic representation, Gottesman-Knill theorem.
        Daniel Gottesman's lectures.
    Lecture 26. (4/27) Clifford group II: , group generators, oscillator version.
        Daniel Gottesman's lectures and VVA notes.
    Lecture 27. (5/2) Toric/surface code I: topological codes.
        Michael Gullans and Aleksander Kubica notes.
    Lecture 28. (5/4) Toric/surface code II: threshold, connection to statistical mechanics.
        Michael Gullans and Aleksander Kubica notes.

    References:
  • [ECT] Concise encyclopedia of coding theory, Taylor and Francis, 2021
  • [R] Ron M. Roth, Introduction to Coding Theory, Cambridge University Press, 2006, ISBN 978-0521845045
  • [MS] F. MacWilliams and N. Sloane, The Theory of Error-Correcting Codes, North-Holland (many editions).
  • [B] R. E. Blahut, Algebraic Codes on Lines, Planes, and Curves, Cambridge University Press, 2008, ISBN 978-0521771948.
  • [GRS] V. Guruswami, A. Rudra, and M. Sudan, Essential Coding Theory, book draft (2019)