Bad Qubits — Learn Quantum by Doing

Multiple choice

Ambainis's quantum walk on a Johnson graph solves the element distinctness problem (are any two of n numbers equal?) with how many queries, compared with the classical Theta(n)?

O(sqrt(n)) queries, matching the Grover lower bound
O(log n) queries, an exponential improvement
O(n^(2/3)) queries, which is tight (no quantum algorithm does better)
O(n^2) queries, slower than the classical algorithm