PCMI Graduate Summer School (July 24-28, 2023)

Quantum Query Complexity

Course description

Quantum query complexity offers one of the most fruitful models of computation for the study of quantum algorithms. It has featured many significant quantum speedups, from the Bernstein-Vazirani algorithm to the recent Yamakawa-Zhandry supremacy breakthrough. The limits of quantum queries have been questioned since the early days of quantum computing. This led to the development of two fundamental lower bound techniques: the polynomial and the adversary methods. The focus of this course will be to introduce these methods and to present some of their new variants, such as the quantum query recording technique. We will also consider the role of duals in these methods and how they can lead to tight bounds or even new algorithms.


Instructor: Yassine Hamoudi
Teaching assistant: Angelos Pelecanos
Schedule for lectures: Mon-Fri, 11am-12pm
Schedule for problem sessions: Mon,Tue,Thu,Fri, 1pm-2pm


Proof sketches: [PDF]

Problem sessions

Suggested references

Theme's credit