Quantum Information in TCS - CS 598 MRT, Fall Semester 2024

Course Description

This course will explore the fundamental concepts in the theory of quantum information and their applications in fields like complexity theory, statistics, and cryptography.

We shall study how information processing tasks become fundamentally different in a quantum world.

This course is aimed at master's and graduate students who have a research interest in quantum information science or theoretical computer science. Prior knowledge of linear algebra concepts is necessary.

Topics

• Entropic quantities and their operational meaning: We will delve into the applications of information measures in quantum statistics and quantum cryptographic protocols, such as quantum key distribution.

• Quantum error correction: We will discuss strategies for safeguarding quantum information against interference and noise.

• Symmetry in quantum information processing: We will investigate mathematical objects such as geometric designs that respect certain symmetries in a quantum system, and study their applications in complexity theory and cryptography.

Time and Location

Lectures:
Room: Siebel 1214
Time: MW at 11:00-12:15

Office hours:
Room: Siebel 4211
Time: Wednesdays 13:00-14:00

Schedule

• Lecture 1 (Aug 26): Linear algebra review

• Lecture 2 (Aug 28): Quantum hypothesis testing

• Lecture 3 (Sep 4): Tensors and introduction to quantum channels

• Lecture 4 (Sep 9): Quantum channels

• Lecture 5 (Sep 11): Data processing inequality and its applications (notes)

• Lecture 6 (Sep 16): Classical channel coding (notes)

• Lecture 7 (Sep 18): Quantum channel coding (notes)

• Lecture 8 (Sep 23): Quantum channel coding (notes)

• Lecture 9 (Sep 25): Privacy amplification and extractors (notes)

• Lecture 10 (Sep 30): Privacy amplification and extractors (notes (together with Lecture 11 notes))

• Lecture 11 (Oct 2): Privacy amplification and extractors

• Lecture 12 (Oct 7): Duality of channel coding and random extraction / Review of classical codes (notes)

• Lecture 13 (Oct 9): Basics of quantum error corrections (notes)

• Lecture 14 (Oct 14): CSS codes

• Lecture 15 (Oct 16): Stabilizer codes

• Lecture 16 (Oct 21): Haar measure and its applications (notes)

• Lecture 17 (Oct 23): No class

• Lecture 18 (Oct 28): Haar measure over sphere and its applications (notes)

• Lecture 19 (Oct 30): Haar measure over sphere and its applications (notes)

• Lecture 20 (Nov 4): Presentation 1: Many-body quantum magic

• Lecture 21 (Nov 6): Presentation 2: Quantum Boolean Functions

• Lecture 22 (Nov 11): Presentation 3: Quantum Encryption with Certified Deletion

• Lecture 23 (Nov 13): Presentation 4: Randomizing Quantum States: Constructions and Applications

• Lecture 24 (Nov 18): Presentation 5: Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography

• Lecture 25 (Nov 20): Presentation 6: NLTS Hamiltonians from Good Quantum Codes

• Lecture 26 (Dec 2): Presentation 7: The Spectra of Density Operators and the Kronecker Coefficients of the Symmetric Group

• Lecture 27 (Dec 4): Presentation 8: Uncloneable Quantum Encryption via Oracles

• Lecture 28 (Dec 9): Presentation 9: Good Quantum LDPC Codes with Linear Time Decoders

• Lecture 29 (Dec 11): Presentation 10: Monogamy of quantum entanglement and other correlations

Grading

• Homeworks (50%)
  

  • Homework 1 (Deadline: Oct 4)
    

  • Homework 2 (Deadline: Dec 1)
    

• Project (50%) (See instructions)

Resources

Quantum Computation and Quantum Information by Nielson and Chuang
The Theory of Quantum Information by John Watrous
John Preskill's Lecture Notes
Tensor diagrams cheat sheet (From Maris Ozols's Twitter)
Random extractor