# 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

## Final Projects Showcase

Testing quantum juntas
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

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

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

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

## Lectures

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]