CS 867 / QIC 890: Quantum Query and Communication Complexity (Winter 2021)
Course Description
In this course, we will study two fundamental models of quantum computation: quantum query complexity and quantum communication complexity. These models are commonly used to investigate fundamental questions such as when and by how much quantum devices can outperform classical ones. Both of these models are also relatively tractable: they allow us to prove rigorous lower bounds on both classical and quantum computation.
Topics will include basic notions and relationships between complexity measures in the query and communication models, some algorithmic techniques (possibly including quantum walks, learning graphs, and span programs), lower bound techniques (such as the polynomial method, adversary method, and approximate logrank), and potentially other topics such as lifting theorems and quantum information cost.
Logistics
This will be an online course. In a typical week:
- I will post either written lecture notes or a video lecture (or both)
- I will post papers that students should (briefly) read
- We will have a "live" video meeting, in which student volunteers will give a short presentation of the papers
- A recording of the live meeting will be posted.
We will also have one assignment and a course project. Students will give a presentation on their project.
Course Resources and Information
Schedule
- Week 1: query complexity basics. Course notes. Video lecture. (Note that the video lecture does not cover everything in the notes.) Readings: no required readings; optional readings are BdW02, ABK+20. No students will present these papers. Recording of live meeting (took place on the following Monday, Jan 18).
- Week 2: quantum algorithms in query complexity. Course notes. No video lecture this week. Readings: AP20 (required), BHMT00 (optional). Yuming Zhao presented the required reading. Recording of live meeting (took place on the following Monday, Jan 25).
- Week 3: communication complexity basics. Course notes. Video lecture. Readings: KR10, Gav20. To be presented by Abhishek Anand and Andrew Jena respectively. Recording of live meeting (took place on the following Monday, Feb 1).
- Week 4: the polynomial method. Course notes. Video lecture coming soon. Readings: BKT18, AKKT19, BBGK18. To be presented by three students (information coming soon). Live meeting will take place Monday, Feb 8, at 4:30pm EST (link will be posted on Piazza).