Opening Quantum Query Complexity
Quantum Query Complexity
- Length
- 1 h 21 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2018
Chapter 1 of 11: Introduction to the query complexity model
O'Donnell contrasts Simon's exponential speedup with the Beals et al. polynomial limit for total functions.
Quantum query complexity measures an algorithm's cost by the number of times it applies the input oracle . O'Donnell, in session 21 of CMU 15-859BB, recasts inputs as strings, restricts attention to decision problems and separates total problems from promise problems. He then defines deterministic, randomized and quantum query complexity and tabulates them for Grover search (OR in quantum queries), Simon's problem, the collision problem, element distinctness and recursive majority-3. The second half turns to total functions: Nisan's theorem relating randomized and deterministic complexity, and the 1998 Beals et al. result ruling out exponential quantum speedups. Block sensitivity, defined through disjoint sensitive blocks, ties these measures together. Familiarity with Grover's and Simon's algorithms is assumed.
Quantum query complexity measures an algorithm's cost by the number of times it applies the input oracle . O'Donnell, in session 21 of CMU 15-859BB, recasts inputs as strings, restricts attention to decision problems and separates total problems from promise problems. He then defines deterministic, randomized and quantum query complexity and tabulates them for Grover search (OR in quantum queries), Simon's problem, the collision problem, element distinctness and recursive majority-3. The second half turns to total functions: Nisan's theorem relating randomized and deterministic complexity, and the 1998 Beals et al. result ruling out exponential quantum speedups. Block sensitivity, defined through disjoint sensitive blocks, ties these measures together. Familiarity with Grover's and Simon's algorithms is assumed.
Beals et al. paper (1998)
Nissan '89

This lecture
Lecture 21 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.
Your comment is kept while you sign up.Sign in