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:

- Reed-Solomon codes; Codes on algebraic curves and their decoding
- Rank metric codes
- Expander codes, codes on 2D complexes, and families of good locally testable codes
- Fourier analysis on $\{0,1\}^n$, linear programming, and bounds on codes
- Connections between classical and quantum codes
- Stabilizer codes, CSS codes, Polynomial codes
- 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

Project presentations: May 9, 11, starting at 11:00am.

Madhu Sudan's Lectures 2,3; my paper with G.D. Forney; UMass Lect.7 by Arya Mazumdar.

Forney's notes | My class notes (Lec.11,12,17) | [R], Ch.3; [MS], Sec.4.1-4.3

BW Algorithm in brief | [GRS], Ch.15; Ch.7

[B] Ch.9 (first 4 sections); Sec. 10.3, 10.4

Reading on rank metric codes: Introduction [pdf] | More on parameters [pdf], [pdf]

Reading: Introduction [pdf] [ 2, pp.3-24] | Decoding [pdf] [pdf] |

A survey on expanders [pdf] | Madhu Sudan's lectures 13,14

LTC codes: Dinur et al. [pdf] Leverrier-Zémor [pdf] | Youtube talks: [pdf] [pdf] |

Reading for Fourier transform: [pdf]

Reading: Navon-Samorodnitsky [pdf]

Reading: H. Cohn's lectures [pdf] Lec. 4 | Sphere packigns [pdf]

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)

Daniel Gottesman's lectures.

VVA notes Sec. 3.

Daniel Gottesman's lectures.

Daniel Gottesman's lectures.

Daniel Gottesman's lectures.

Daniel Gottesman's's lectures and VVA notes.

Daniel Gottesman's lectures.

Daniel Gottesman's lectures.

Daniel Gottesman's lectures.

Daniel Gottesman's lectures and VVA notes.

Michael Gullans and Aleksander Kubica notes.

Michael Gullans and Aleksander Kubica notes.