Saltar al contenido ForoHackers

Grover's algorithm: a quadratic speed-up, not magic

AlgoritmosAlgoritmos cuánticosComputación cuántica
#1160 · quantum_tunnel_rat · · Denunciar

Grover's algorithm is the other famous quantum algorithm, and probably the most misunderstood.

The problem: you have an unstructured space of N items and a function f(x) that answers "is this the one?". Classically, you try items one at a time, and on average you check N/2, worst case N. Grover finds the item with about (π/4) √N evaluations of f.

Three honest caveats:

  1. It is quadratic, not exponential. N becomes √N. For a brute-force search over 2^n keys, that is 2^(n/2) steps: a real gain, but you can respond by doubling the key length.
  2. You can overshoot. The algorithm rotates the state towards the answer in small steps. Run too many iterations and you rotate past it, and the success probability goes down again. You need to know N and the number of solutions to stop at the right time.
  3. The "oracle" is not free. Somebody has to implement f as a quantum circuit, and its cost is part of the cost of each iteration. If checking a candidate is expensive, the speed-up is applied to an expensive thing.

The structure is lovely: repeat "flip the sign of the right answer's amplitude", then "reflect all amplitudes about their average". Each round nudges the amplitude of the right answer up a bit. Interference again.

And, a result worth knowing: for unstructured search, √N is optimal. No quantum algorithm can do better without structure to exploit.

#1951 · byte_sized_owl · · Denunciar

Teacher's analogy for the overshoot: you are pushing a swing. Push at the right moments and it goes higher. Keep pushing at the wrong moment and it comes back down. Grover's iterations are pushes, and you have to stop when the swing is at the top.

#1952 · overfit_otter · · Denunciar

The oracle-cost caveat is the one that gets dropped in headlines. "Quadratic speed-up" quietly assumes f is a black box with unit cost. In real problems the box is a circuit, and I would want a baseline comparison against the best classical heuristic, not against brute force.

#1953 · quantum_tunnel_rat · · Denunciar

Agreed, and that is the right instinct. The fair comparison is always against the best classical method for the structured version of the problem, and for a lot of interesting problems, that classical method already exploits structure that Grover cannot.

#1954 · bayes_and_bagels · · Denunciar

If you like numbers: with one solution among N items, let sin θ = 1/√N. After k iterations the chance of measuring the right answer is sin²((2k+1)θ). It peaks near k ≈ (π/4)√N and then falls again. So the overshoot is a sine wave, and the swing analogy is literally correct.

Inicia sesión o únete para responder.