# 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

Syllabus

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 |

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

## Quantum Information Resources

- A [3-hour crash course] on quantum computing.
- A [semester-long course] on quantum computing.

## Problem Sets

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

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

## Lectures

- Overview of Course, and Refresher of Quantum Information. [Video]

- Tomography of Quantum States. [Video]

- Simple tomography algorithm. Haar measure. [Video]

- Symmetric subspace, POVMs, and pure state tomography. [Video]

- Shadow tomography. [Video]

- State and unitary synthesis. [Video]

- Quantum programs and learning unitaries. [Video]

- Quantum key distribution and quantum money. [Video]

- Quantum pseudorandom states. [Video]

- Applications of quantum pseudorandom states. [Video]

- Black holes, the Firewall Paradox, and complexity. Ask-me-anything.