Opening The Adversary Method in Quantum Query Complexity
The Adversary Method in Quantum Query Complexity
- Length
- 1 h 1 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2018
Chapter 1 of 7: Quantum query model
Quantum query complexity lower bounds via the adversary method, introduced by Andris Ambainis in 2000, are the subject of this session of CMU 15-859BB. O'Donnell defines the quantum query model, which counts only oracle queries, and casts decision problems as sets of yes and no inputs. He reviews the hybrid and polynomial methods before building a progress measure from inner products of states on hard input pairs. The super-basic adversary theorem follows, yielding lower bounds for Grover's OR problem, the k-ones threshold problem and a nested AND-OR formula. A proof bounding how slowly the measure decays per query leads to Ambainis's basic adversary method.

Your comment is kept while you sign up.Sign in
O'Donnell proves the super-basic adversary bound , then applies it to Grover search and AND-OR formulas.
Quantum query complexity lower bounds via the adversary method, introduced by Andris Ambainis in 2000, are the subject of this session of CMU 15-859BB. O'Donnell defines the quantum query model, which counts only oracle queries, and casts decision problems as sets of yes and no inputs. He reviews the hybrid and polynomial methods before building a progress measure from inner products of states on hard input pairs. The super-basic adversary theorem follows, yielding lower bounds for Grover's OR problem, the k-ones threshold problem and a nested AND-OR formula. A proof bounding how slowly the measure decays per query leads to Ambainis's basic adversary method.
Bennett-Bernstein-Brassard-Vazirani paper
Beals et al. paper
Ambainis paper
Høyer, Lee, and Špalek paper
Reichardt paper
Ambainis '00
Quantum lower bounds by adversary method
Ambainis 2000
This lecture
Lecture 22 of 27 of Quantum Computation and Quantum Information.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.