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
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
AdS/CFT Correspondence and Quantum Error Correction
Asa Kosto, Shuhan Zhang
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: 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
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.
- 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.