Bad Qubits — Learn Quantum by Doing

Multiple choice

Grover's algorithm searches for a marked item among N = 2^n unstructured candidates. How many oracle calls does it need, compared with the classical cost?

O(sqrt(N)) quantum oracle calls, versus O(N) classically
O(log N) quantum oracle calls, versus O(N) classically
O(N) quantum oracle calls, versus O(sqrt(N)) classically
O(1) quantum oracle call, versus O(N) classically