CS 860: Quantum Lower Bounds (Spring 2020)
Course Description
This course is about what we cannot do with computers we do not have.
We will explore different methods for proving the nonexistence of quantum algorithms, within concrete computational models where such nonexistence theorems can be formally proved.
We will start with the "big three" lower bound techniques (hybrid method, polynomial method, and adversary method),
and subsequently explore other topics such as dual polynomials, negative- and multiplicative-weight adversaries, gamma 2 norms (filtered and approximate),
"ironic" lower bounds, quantum information cost, etc.
Logistics
Due to the COVID-19 situation, this course will take place exclusively online in asynchronous form (meaning there will be no live lectures).
Here are some logistical details.
- Instructor: Shalev Ben-David
- Piazza: piazza.com/uwaterloo.ca/spring2020/cs860. All students, auditors, and anyone interested should join the Piazza site.
- The current plan for the course is that I will post course notes and link to papers all students should read. Students will take turns posting "reviews" of one of the papers on Piazza, which will hopefully stir some discussion.
- Additionally, there will be two assignments students may work on in groups. There will also be a final project; students will need to make a short presentation and submit a short report about their final project.
- Pending on some Piazza discussions with the class, I may post some videos to complement the course notes and readings.
Schedule
In lieu of live lectures, regular course notes and/or readings will be posted here.