CS 867 / QIC 890: Quantum Query and Communication Complexity

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.

Format

(Details are subject to change.)

This will be an in-person course, with lectures once a week:

• Wednesdays 1:30-4:20pm, in DC 2585.

The lectures will not be recorded. Some reading material will be posted here on the course website.

The course outline is here.

Please sign up for Piazza!

Readings:

• Week 1 (May 4): Lecture notes on query complexity basics. For next week, consider looking at the surveys BdW02, Amb17, or Aar21

• Week 2 (May 11): We covered some stuff from week 1’s lecture notes, plus the Hybrid method. For next week, the assigned reading was YZ22.

• Week 3 (May 18): We briefly covered the polynomial method. We covered only the first 5 pages or so of these course notes, but the rest may be helpful for some of the readings. For next week, there were two readings: AA09 and BKT19.

• Week 4 (May 25): We covered a bit more polynomial method (see notes from Week 3). We also started covering communication complexity, but very briefly. Reading: ABT18. Consider also reading parts of GPW15, some of which can function as a survey of communication complexity classes.

• Week 5 (June 1): We covered lifting theorems and the relationship between the rank of a matrix and its communication complexity. Reading: LS08

• Week 6 (June 8): We covered the “gamma 2” norm and a bit of the adversary method. Reading: LMRSS11

• Week 7 (June 15): Likely reading: SS05

• Week 8 (June 22): Likely reading: JKM12, possible reading: S08

• Week 9 (June 29):

• Week 10 (July 6):

• Week 11 (July 13): No readings assigned this week.

• Week 12 (July 20): Reserved for project presentations.