Instructor: Makrand Sinha (msinha@illinois.edu)
Credits: 4
Time: Mondays and Wednesdays 2:00 - 3:15 pm
Location: 1302 Siebel Center
Office Hours: after class or by appointment
Discussion Forum: Ed Discussion. You will automatically be enrolled based on your @illinois.edu email. All course announcements, policies, discussions and homeworks will be available only on Ed Discussion. Instead of sending emails, students are encouraged to send direct messages to the course staff via the chat feature on Ed Discussion. If you sign up late, please send an email to msinha@illinois.edu to be enrolled in Ed Discussion and Gradescope.
Homework Submission: Gradescope
Class Recordings: Mediaspace (UIUC restricted)
This is an advanced, PhD-level topics class in quantum complexity theory — the study of the fundamental capabilities and limitations of quantum computers. The course will explore four different themes:
The goal is to explore the results and (more importantly) the questions in this field to bring the students to the research frontier. A highly-tentative list of topics includes:
The key prerequisite for this course is mathematical maturity. During this course, we will touch upon fairly advanced topics that incoporate ideas from diverse mathematical fields. Having taken a few 400 or 500 level (proof-based) math or theoretical computer science courses is strongly recommended. While we will quickly cover the necessary quantum computing and complexity background, some familiarity with classical complexity classes (P, NP) and basic quantum computing is beneficial. Those without sufficient background are recommended to work on supplementary material to internalize the ideas.
| Date | Topic | Notes | Additional Resources |
|---|---|---|---|
| Jan 17 | Course Overview, Quantum Information Refresher | Introduction, Quantum Refresher |
Quantum Information Fundamentals |
| Jan 22 | Quantum Information Refresher (contd), Complexity Basics | Complexity Basics | Chapters 1 and 2 in Arora-Barak textbook |
| Jan 24 | BQP and its properties | Notes | Quantum Complexity Theory by Ethan Bernstein and Umesh Vazirani |
| Jan 29 | BQP and its properties (contd) | Notes | |
| Jan 31 | Oracles, BQP vs BPP | Notes | Chapter 3 in Ronald de Wolf's lecture notes |
| Feb 5 | Oracle Separation, BQP vs NP | Notes | Chapter 7 in Ronald de Wolf's lecture notes |
| Feb 7 | Quantum Lower Bounds via Polynomials | Notes | Survey on Approximate Degree |
| Feb 12 | BQP vs PH (part 1) | Notes | Oracle Separation of BQP and PH by Ran Raz and Avishay Tal |
| Feb 14 | BQP vs PH (part 2) | Notes | |
| Feb 19 | Quantum Speedups and Structure, Separation of BQP and BPP with Search problems |
Notes | The Need for Structure in Quantum Speedups by Scott Aaronson and Andris Ambainis Verifiable Quantum Advantage without Structure by Takashi Yamakawa and Mark Zhandry |
| Feb 21 | Separation of BQP and BPP with Search problems (contd) | Notes | |
| Feb 26 | Near-term Quantum Advantage | Notes | Paper on Random Circuit Sampling by Adam Bouland, Bill Fefferman, Chinmay Nirkhe and Umesh Vazirani |
| Feb 28 | Near-term Quantum Advantage (contd), QMA and its properties | Notes | |
| Mar 4 | Properties of QMA, Error Reduction in QMA | Notes | |
| Mar 6 | Witness-preserving QMA Error Reduction | Notes | Quantum Arthur-Merlin Games by Chris Marriott and John Watrous |
| Mar 11 | Spring Break | ||
| Mar 13 | Spring Break | ||
| Mar 18 | Local Hamiltonian Problem | Notes | |
| Mar 20 | Local Hamiltonian Problem (contd), QMA(2) | Notes | |
| Mar 25 | Short QMA(2) proofs for NP | Notes | A quantum characterization of NP by Hugue Blier and Alain Tapp |
| Mar 27 | QMA(2) and Detecting Entanglement, Complexity of Ground States | Notes | |
| Apr 1 | Quantum PCP Conjecture | Notes | Survey on the Quantum PCP Conjecture by Dorit Aharonov, Itai Arad and Thomas Vidick |
| Apr 3 | Tensor Networks and Matrix Product States | Notes | Hand-waving and Interpretive Dance: An Introductory Course on Tensor Networks by Jacob Bridgeman and Christopher Chubb |
| Apr 8 | No class | ||
| Apr 10 | Area Laws | Notes | Lecture Notes from a course by Thomas Vidick |
| Apr 15 | Area Laws (contd), State Synthesis | Notes | |
| Apr 17 | State and Unitary Synthesis | Notes | A one-query lower bound for unitary synthesis and breaking quantum cryptography by Alex Lombardi, Fermi Ma and John Wright |
| Apr 22 | Unitary Synthesis Lower Bound Pseudorandom States and Designs |
Notes | Pseudorandom States, Non-Cloning Theorems and Quantum Money by Zhengfeng Ji, Yi-Kai Liu and Fang Song |
| Apr 24 | Applications and Constructions of Pseudorandom States and State Designs | Notes | (Pseudo) Random Quantum States with Binary Phase by Zvika Brakerski and Omri Shmueli |
| Apr 29 | Pseudorandom States (contd) Pseudorandom Unitaries and Unitary Designs |
Notes | Simple constructions of linear-depth t-designs and pseudorandom unitaries by Tony Metger, Alexander Poremba, Makrand Sinha and Henry Yuen |
| May 1 | Jeopardy |