Bad Qubits — Learn Quantum by Doing

Multiple choice

Per this lesson, given a circuit A whose good outputs occur with probability p, how many applications of A does amplitude amplification need to find a good output, versus classical repetition?

O(p) for both — no speedup
O(log(1/p)) for amplification versus O(1/p) classically — an exponential speedup
O(1/sqrt(p)) for amplification versus O(1/p) classically — a quadratic speedup
O(1/p) for amplification versus O(1/sqrt(p)) classically