|q⟩
Bad Qubits
Play
Quest
Questions
Learn
Playground
☕
← Question Bank
Multiple choice
Per this lesson, what is the worst-case classical query complexity of unstructured search over N items, and how does Grover's algorithm compare?
🔬 try it before you answer
Classical needs Theta(log N) queries; Grover needs O(1)
Both need Theta(N) — Grover gives no asymptotic advantage
Classical needs Theta(N) queries; Grover needs O(sqrt(N)) — a quadratic speedup
Classical needs Theta(sqrt(N)) queries; Grover needs O(log N)
Check answer