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: We will also have one assignment and a course project. Students will give a presentation on their project.

Course Resources and Information

Schedule