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.

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.

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.

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

Lectures

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

• [Slides 1]
• [Slides 2]

2. Tomography of Quantum States. [Video]

• [Slides]
• [Mixed states notes]
• [Tomography notes]

3. Simple tomography algorithm. Haar measure. [Video]

• [Tomography algorithm notes]
• [Haar measure notes]

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

• [Symmetric subspace notes]
• [POVMs, pure state tomography notes]

5. Shadow tomography. [Video]

• [Shadow tomography notes]
• [Q&A]

6. State and unitary synthesis. [Video]

• [State Synthesis Problem]
• [Unitary Synthesis Problem]

7. Quantum programs and learning unitaries. [Video]

• [Quantum programs, Hamiltonian simulation]
• [Learning unitaries]

8. Quantum key distribution and quantum money. [Video]

• [Quantum key distribution]
• [Quantum money]

9. Quantum pseudorandom states. [Video]

• [Definition and properties]
• [Construction of PRS]

10. Applications of quantum pseudorandom states. [Video]

• [Landscape of Cryptography]
• [Commitment schemes]

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

• [Q&A]