THE FOLD / CHEAT / THE SHORTCUT / THE GROVER
THE GROVER
search N items in √N — the quantum shortcut
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Grover’s algorithm searches an unsorted database of N items for a marked one in about √N steps — a quadratic speedup over the N/2 a classical scan needs on average. It works by amplitude amplification.
Start with all N items in equal superposition, each amplitude 1/√N. Repeat two moves: an oracle that flips the sign of the marked item’s amplitude, and a diffusion that reflects every amplitude about their average. Each round rotates the state a little closer to the marked item; its probability grows as sin²((2k+1)θ) with sinθ = 1/√N, reaching nearly 1 after about (π/4)√N rounds. The catch: don’t overshoot — keep going and the probability comes back down. For 16 items the peak is at 3 rounds; for a million, about 785. Grover found it in 1996; it is the general-purpose quantum speedup for brute-force search.
LIT verified live: simulating the oracle-plus-diffusion rounds, the marked probability follows sin²((2k+1)θ) exactly and peaks near 0.96 at 3 rounds for N=16 — where a classical search averages 8 (window.__grover). FIG no framing; the amplitude curve, the √N peak, and the overshoot are exact.
Start with all N items in equal superposition, each amplitude 1/√N. Repeat two moves: an oracle that flips the sign of the marked item’s amplitude, and a diffusion that reflects every amplitude about their average. Each round rotates the state a little closer to the marked item; its probability grows as sin²((2k+1)θ) with sinθ = 1/√N, reaching nearly 1 after about (π/4)√N rounds. The catch: don’t overshoot — keep going and the probability comes back down. For 16 items the peak is at 3 rounds; for a million, about 785. Grover found it in 1996; it is the general-purpose quantum speedup for brute-force search.
LIT verified live: simulating the oracle-plus-diffusion rounds, the marked probability follows sin²((2k+1)θ) exactly and peaks near 0.96 at 3 rounds for N=16 — where a classical search averages 8 (window.__grover). FIG no framing; the amplitude curve, the √N peak, and the overshoot are exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE SHORTCUT — the cheat domain of reaching the end by a hidden path. Grover is the archetypal shortcut: the whole haystack searched in the square root of the time, by turning the amplitudes rather than checking the items. AVAN (AI) built the instrument: the amplitude bars, the rotation view, the overshoot inverse.
The weave: David names the seat (the square-root path); I make oracle-and-diffusion rounds amplify the marked amplitude to near-certainty in √N steps — the amplitudes in 1D, the amplification in 2D, the stop-at-the-peak inverse in 3D. The sphere is the seam. Credit: Lov K. Grover (1996).
The weave: David names the seat (the square-root path); I make oracle-and-diffusion rounds amplify the marked amplitude to near-certainty in √N steps — the amplitudes in 1D, the amplification in 2D, the stop-at-the-peak inverse in 3D. The sphere is the seam. Credit: Lov K. Grover (1996).
3 ONE DIMENSION
The N amplitudes as a row of bars. The oracle drives the marked bar negative; the diffusion — reflect about the average — then pumps it tall and shrinks the rest. Two moves, and the needle stands a little higher than the hay.
4 TWO DIMENSIONS · INTERACTIVE
Step the rounds and watch the marked amplitude grow toward certainty, its probability tracing sin²((2k+1)θ). Reach the peak near √N — then keep going and watch it fall. In Grover, more work past the optimum makes things worse.
5 THREE DIMENSIONS + AVAN’S INVERSE
The state as a vector in the plane of ‘marked’ and ‘everything else’ — the green forward step: each round rotates it by a fixed angle 2θ toward the marked axis.
AVAN’s addition (the inverse-companion): the magenta is the same rotation carried too far. Grover is not an accumulation that only ever helps — it is a rotation, and a rotation can turn past its target. Up to the peak near (π/4)√N, each round swings the state closer to the marked axis; one round beyond, and it swings away, the probability falling exactly as it rose. So the inverse of ‘search more’ here is ‘search worse’ — unlike a classical scan, where extra checks never cost you, extra Grover rounds undo your progress. You must stop at the right moment, because the algorithm has no notion of ‘good enough and holding’; it simply keeps turning. The magenta over-rotation is the honest price of amplitude amplification: the quadratic shortcut is a pendulum, not a ramp, and knowing when to measure is as essential as the amplification itself. Green rotates toward the answer; magenta rotates past it; the peak is a knife-edge you aim for, not a plateau you climb onto.
LIT Genuine Grover's algorithm (Lov K. Grover 1996). Verified live: simulating oracle (flip marked sign) plus diffusion (invert about mean), the marked probability follows sin^2((2k+1)theta) exactly and peaks at ~0.96 at 3 rounds for N=16 = round((pi/4)sqrt(16)), then falls if continued, while a classical search averages N/2=8 (window.__grover.closedFormMatches && peakIter near optimalIters && overshoots). The amplitude curve, the sqrt(N) peak, and the overshoot are exact.
FIG No framing: the amplitude amplification, the sin^2((2k+1)theta) curve, the sqrt(N) peak, and the overshoot (probability falls past the optimum) are all simulated exactly in-browser. The AVAN inverse is genuine — Grover is a rotation by 2theta per round in the marked/unmarked plane, so continuing past the peak rotates away and reduces the probability; unlike classical search, more rounds can make it worse, and knowing when to stop is essential.
FIG No framing: the amplitude amplification, the sin^2((2k+1)theta) curve, the sqrt(N) peak, and the overshoot (probability falls past the optimum) are all simulated exactly in-browser. The AVAN inverse is genuine — Grover is a rotation by 2theta per round in the marked/unmarked plane, so continuing past the peak rotates away and reduces the probability; unlike classical search, more rounds can make it worse, and knowing when to stop is essential.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE SHORTCUT · David Lee Wise (ROOT0), with AVAN