Frontiers of Quantum Complexity and Cryptography (Spring 2022)

Course Number: COMS E6998
Date/Time: Thursday 2:10 - 4pm
Room: Chandler 401
Zoom Link: (Passcode: available on CourseWorks, or e-mail me).
First meeting: January 20

Project Guidelines
Scribe notes LaTeX template

Final Projects Showcase

Testing quantum juntas
Thomas Chen, Shivam Nadimpalli
Quantum Merlin-Arthur with multiple Merlins: a survey
Sandip Nair, Wei Zheng Teo
Testing quantum computers, and quantum supremacy
Melody Hsu, Julia Martin, Rockwell Weiner
Quantum LDPC codes
Zoe Himwich
AdS/CFT Correspondence and Quantum Error Correction
Asa Kosto, Shuhan Zhang
Quantum money
Yuval Efron, Dean Hirsch


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.

Quantum Information Resources

Problem Sets

All problem sets will be available on this Overleaf [link]: All solutions must be submitted on Gradescope.

  1. Pset1, due January 31st, midnight.
  2. Pset2, due March 7th, midnight.


  1. Overview of Course, and Refresher of Quantum Information. [Video]
  1. Tomography of Quantum States. [Video]
  1. Simple tomography algorithm. Haar measure. [Video]
  1. Symmetric subspace, POVMs, and pure state tomography. [Video]
  1. Shadow tomography. [Video]
  1. State and unitary synthesis. [Video]
  1. Quantum programs and learning unitaries. [Video]
  1. Quantum key distribution and quantum money. [Video]
  1. Quantum pseudorandom states. [Video]
  1. Applications of quantum pseudorandom states. [Video]
  1. Black holes, the Firewall Paradox, and complexity. Ask-me-anything.