CS 598QC: Frontiers of Quantum Complexity
(Spring 2024)

Course Information

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)

Course Description

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.

Tentative Schedule (subject to changes)

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
Mar 6
Mar 11 Spring Break
Mar 13 Spring Break
Mar 18
Mar 20
Mar 25
Mar 27
Apr 1
Apr 3
Apr 8
Apr 10
Apr 15
Apr 17
Apr 22
Apr 24
Apr 29
May 1

Additional Resources for Prerequisites

Grading Policy