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 twice a week:

• Mondays and Wednesdays 1:00-2:20pm, in QNC 1201.

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 will be posted here.