|q⟩
Bad Qubits
Play
Quest
Questions
Learn
Playground
☕
← Question Bank
Multiple choice
Per this lesson, Grover's quadratic speedup is optimal: what is the proven lower bound on the number of oracle queries any quantum algorithm needs for unstructured search of N items?
🔬 try it before you answer
Omega(N), the same as the classical bound
Omega(1) — a constant number of queries suffices
Omega(sqrt(N)), proved by Bennett, Bernstein, Brassard, and Vazirani (BBBV)
Omega(log N), proved by BBBV
Check answer