Frontiers of Quantum Complexity and Cryptography (Spring 2022)

Course Number: COMS E6998
Date/Time: Thursday 2:10 - 4pm
Room: Chandler 401
First meeting: January 20


This is an advanced, PhD-level topics class in the theory of quantum computing, focusing in particular on cutting-edge topics in quantum complexity theory and quantum cryptography. The theme of the topics this year will be

Complexity of quantum states and state transformations.

An $n$-qubit quantum state appears to be exponentially more complex than an $n$-bit string; a classical description of such a state requires writing down $2^n$ complex amplitudes in general. Here are some questions that will motivate our explorations:
  • How does this complexity manifest itself in different information-processing tasks?
  • How can we quantify this complexity?
  • Can this complexity be used for cryptographic applications?
  • Does the complexity of quantum states relate to traditional concepts in complexity theory such as circuit complexity or space complexity or time complexity?

A list of possible topics:

  • Shadow tomography of quantum states
  • Quantum state synthesis/unitary synthesis
  • Hamiltonian learning
  • Quantum key distribution/quantum money
  • QMA(2) and the power of unentanglement
  • State complexity, AdS/CFT, and quantum gravity
  • Quantum state complexity and statistical zero knowledge
  • Pseudorandom states and unitaries
  • Classical vs. quantum proofs

The following notes from Scott Aaronson will be frequently consulted:

The goal is to explore the results and (more importantly) the questions in this field. Course work may include: scribe notes, a few assignments, and a course project.


Must have taken: Basic linear algebra and basic probability theory.

You must have taken at least one of:

  • An upper-level CS theory course such as complexity theory/cryptography/algorithms, or
  • Quantum computing, or
  • Quantum physics.

It is not required that you have taken a course in quantum computing/quantum information before, but it would definitely be helpful. The lectures will introduce the concepts as needed, but will go rather quickly.

The course will expect high levels of mathematical maturity and comfort with proofs. To get a sense of what this course is like, take a look at the lecture notes from this Fall 2020 topics course.