CPSC 648: Quantum Codes and Applications to Complexity

Lecturer: Gaurav Mahajan (gaurav.mahajan@yale.edu)
Office Hours: Tuesday 1-2 PM. Kline Tower, KT 1319
Location: Thursday 1:30-3:20PM. Kline Tower, KT 1327
Canvas: https://yale.instructure.com/courses/100565
Scribe List: link to google sheet
Project List: link to google sheet
Lecture Notes: link to overleaf for scribe

Course Description

The course will cover the theory of quantum error correction and its applications to quantum complexity theory. We will start with basic quantum codes and then progress towards more advanced code constructions, particularly focusing on good quantum low-density parity-check codes. In the latter half of the course, we will discuss various applications of quantum codes in quantum complexity.

Deadlines

Sep 21st: Project selection due
Oct 21st: Rough draft due
Nov 21st: Project presentations
Dec 06th: Final report due

Lectures

Chapter 1 (Week 1): Basics of Quantum Computation
  • Quantum bits, multiple qubits, gates, and measurement
Chapter 2 (Week 2): Introduction to Quantum Codes
  • Repetition code, quantum noise, fixing bit flip and phase errors, 9-qubit Shor code
Chapter 3 (Week 3): Knill-Laflamme Conditions
  • Quantum noise model, error-correcting codes, Knill-Laflamme conditions, distance of a code
Chapter 4 (Week 4): Stabilizer Codes
  • Pauli group, stabilizer codes, dimension and distance of stabilizer codes, logical operators
Chapter 5 (Week 5): Calderbank-Shor-Steane Codes
  • Classical linear codes, distance of classical linear codes, CSS code, distance of CSS code
Chapter 6 (Week 6): Toric Code
  • Stars and plaquettes, closed loop and boundary, distance of toric code
Chapter 7 (Week 7): Chain Complexes
  • Chain complexes, homology, dual chain
Chapter 8 (Week 8): Hypergraph Product Codes
  • Classical codes as chain complexes, hypergraph product code
Chapter 9 (Week 8): Tanner Codes
  • Distance of Tanner codes, expander graphs
Chapter 10 (Week 9): Quantum Tanner Codes
  • Left-right Cayley complex, quantum Tanner code, dimension of the code
Chapter 11 (Week 10): Distance of Quantum Tanner Code
  • Product expansion, minimal representation, minimum distance