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.

Information

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

Lectures

• Lecture 1: Introduction & The hybrid method [Slides] [Video]
• Lecture 2: The polynomial method [Slides] [Video]
• Lecture 3: The recording method [Slides] [Video]
• Lecture 4: The adversary method [Slides] [Video]
• Lecture 5: Algorithmic dual to the adversary method [Slides] [Video]

Proof sketches: [PDF]

Problem sessions

• Problems 1: Basics of query complexity & The hybrid method [Problems] [Solutions]
• Problems 2: The polynomial method [Problems] [Solutions]
• Problems 3: The recording and adversary methods [Problems] [Solutions]
• Problems 4: The adversary method and its dual [Problems] [Solutions]

Suggested references

• Lecture notes by: R. de Wolf, A. Childs, S. Ben-David
• Surveys and Textbooks:
  • “Complexity Measures and Decision Tree Complexity: A Survey”. H. Buhrman and R. de Wolf. [Link]
  • “Analysis of Boolean Functions”. R. O’Donnell. [Link]
  • “Approximate Degree in Classical and Quantum Computing”. M. Bun and J. Thaler. [Link]
• Research papers on the adversary method:
  • “Strengths and Weaknesses of Quantum Computing”. C. Bennett, E. Bernstein, G. Brassard, U. Vazirani. [Link]
  • “Quantum Lower Bounds by Quantum Arguments”. A. Ambainis. [Link]
  • “Negative Weights Make Adversaries Stronger”. P. Høyer, T. Lee, R. Špalek. [Link]
  • “All Quantum Adversary Methods are Equivalent”. R. Špalek and M. Szegedy. [Link]
  • “Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function”. B. Reichardt. [Link]
  • “Span-Program-Based Quantum Algorithm for Evaluating Formulas”. B. Reichardt and R. Špalek. [Link]
  • “Span Programs and Quantum Algorithms for st-Connectivity and Claw Detection”. A. Belovs and B. Reichardt. [Link]
  • “Applications of the Adversary Method in Quantum Query Algorithms”. A. Belovs. [Link]
• Research papers on the polynomial method:
  • “Quantum Lower Bounds by Polynomials”. R. Beals, H. Buhrman, R. Cleve, M. Mosca, R. de Wolf. [Link]
  • “Quantum Lower Bounds for the Collision and the Element Distinctness Problems”. S. Aaronson, Y. Shi. [Link]
  • “The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials”. M. Bun, R. Kothari, J. Thaler. [Link]
  • “Quantum Query Algorithms are Completely Bounded Forms”. S. Arunachalam, J. Briët, C. Palazuelos. [Link]
• Research papers on the recording method:
  • “How to Record Quantum Queries, and Applications to Quantum Indifferentiability”. M. Zhandry. [Link]
  • “On Finding Quantum Multi-collisions”. Q. Liu and M. Zhandry. [Link]
  • “Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs”. Y. Hamoudi and F. Magniez. [Link]
  • “Tight Quantum Time-Space Tradeoffs for Function Inversion”. K. Chung, S. Guo, Q. Liu, L. Qian. [Link]

---

Theme's credit