# Frontiers of Quantum Complexity and Cryptography (Spring 2022)

*Course Number*: COMS E6998

*Date/Time*: Thursday 2:10 - 4pm

*Room*: Chandler 401

*Zoom Link*:
https://columbiauniversity.zoom.us/j/98981313319 (Passcode: available on CourseWorks, or e-mail me).

*First meeting*: January 20

## Description

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.*

- 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
*un*entanglement - 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: https://www.scottaaronson.com/barbados-2016.pdf.

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.

## Prerequisites

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.