Query Complexity Lower Bounds
HardDerivationquery complexityadversary methodlower bounds
Related module: Search and amplitude amplification
Problem statement
Grover's algorithm finds a marked item among with queries. The BBBV theorem proves this is optimal.
- State the quantum query complexity model.
- Why is a lower bound for unstructured search?
- What does this imply about the power of quantum computers?
Hints
Learn the foundations
The Quantum Computing track covers this topic and more in depth.