We want to find , with , given the Unitary Operator , where . Grover’s algorithm solves this when has a single element by:

  1. Getting our system into the superposition .
  2. Apply the loop
    1. Apply our oracle .
    2. Invert amplitudes around the mean through the diffusion operator .
  3. After iterations we moved our Quantum state in the direction of the solution, reaching an angle of from the non-solutions, as derived below. We choose to make this as close as possible to .
  4. Measure in the computational basis. The amplitude is now concentrated on , the set where .

Geometry of the iteration

Let and define the orthonormal states

Then with . On the plane spanned by , which the algorithm never leaves:

Hence , and a measurement finds a solution with probability .

Known number of solutions

The derivation above never used . Choose

so the final angle is within of and the success probability is at least . If , guessing classically already succeeds with probability above ; alternatively double the search space with an ancilla qubit, which halves . Overshooting is harmful: iterating past rotates away from again, since the success probability is periodic in .

Unknown number of solutions

Because overshooting is harmful, cannot simply be taken large. Two standard fixes, both with expected queries (Boyer, Brassard, Høyer and Tapp, “Tight bounds on quantum searching”, arXiv:quant-ph/9605034, Fortschritte der Physik 1998):

  • Randomised schedule: start with ; at each round pick uniformly in , run Grover iterations, measure and check the result with one classical call to . If it fails, set with . For a random the average success probability is , which is at least once , so the expected cost is .
  • Quantum counting: has eigenvalues on the search plane, and is a superposition of the two eigenvectors, so phase estimation of returns , hence , and then the known recipe applies.

Non-unitary oracles and noise

Within closed system quantum mechanics, the oracle and diffusion are unitaries (indeed reflections, ), and the speed-up relies on amplitudes adding coherently over rotations. If the oracle is a non-unitary channel, the coherent rotation is damped. For an oracle that fails, independently at each call, with constant probability , Regev and Schiff proved that any algorithm needs more than queries, so the quadratic speed-up is lost completely (“Impossibility of a quantum speed-up with a faulty oracle”, arXiv:1202.1027). This holds for a true black box; if the oracle is a circuit we can run fault-tolerantly, error correction restores the speed-up.