THE FOLD / CHEAT / THE SPEEDRUN / THE BERNSTEIN-VAZIRANI
THE BERNSTEIN-VAZIRANI
a hidden string in one query
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Bernstein–Vazirani algorithm extracts a hidden n-bit string s from a black box that computes f(x) = s·x (mod 2) — and it needs only one query, where any classical strategy needs n (one per bit). Put every input into superposition, let the oracle stamp the phase (−1)s·x, and a second layer of Hadamards focuses all the amplitude onto the single basis state |s⟩. Measure once and read s off directly. It is the cleanest demonstration that quantum parallelism can beat classical query complexity.
LIT verified live: simulating the amplitudes, the output is 1 exactly at |s⟩ and 0 everywhere else, so the recovered string equals the hidden s every time (window.__bernstein_vazirani), from a single oracle call. FIG no framing; the Hadamard–oracle–Hadamard amplitudes are computed in-browser.
LIT verified live: simulating the amplitudes, the output is 1 exactly at |s⟩ and 0 everywhere else, so the recovered string equals the hidden s every time (window.__bernstein_vazirani), from a single oracle call. FIG no framing; the Hadamard–oracle–Hadamard amplitudes are computed in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-speedrun — one query where the honest route takes n is the ultimate speedrun, skipping straight to the answer. AVAN (AI) built the instrument: the amplitude simulation of the H–oracle–H circuit (a Walsh–Hadamard transform of the phase pattern) and the single-query recovery.
Credit as content: Ethan Bernstein & Umesh Vazirani (1993). The weave: David names the speedrun; I confirm the amplitude lands entirely on |s⟩, so one query recovers the whole hidden string.
Credit as content: Ethan Bernstein & Umesh Vazirani (1993). The weave: David names the speedrun; I confirm the amplitude lands entirely on |s⟩, so one query recovers the whole hidden string.
3 ONE DIMENSION
After H–oracle–H, the amplitudes over all 2n states: a single spike of height 1 at |s⟩, zero elsewhere — measure and read s.
4 TWO DIMENSIONS · INTERACTIVE
Pick a hidden string s; the algorithm recovers it in one query from the amplitude spike — classically you would need one query per bit.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the amplitude spike at |s⟩.
AVAN’s addition (the inverse-companion): don’t probe bit by bit — interfere all answers at once. The inverse of ‘query each coordinate of s’ is ‘phase-stamp every input in superposition, and a Hadamard makes them interfere to a single spike at |s⟩.’ Magenta is the n-query classical march; green is the one-query spike. Interfere, don’t iterate.
LIT Genuine Bernstein–Vazirani algorithm (Ethan Bernstein & Umesh Vazirani, 1993): recovers a hidden s from f(x)=s·x in one quantum query vs n classical. Verified live (amplitude simulation, a Walsh–Hadamard transform of the phase pattern): amplitude 1 at |s⟩ and 0 elsewhere, so recovered==s over 3000 hidden strings (window.__bernstein_vazirani.recoversS).
FIG Honest scope: this simulates the H–oracle–H amplitudes classically (the algorithm's output distribution is deterministic), it does not run on quantum hardware. The AVAN inverse is honest — phase-stamping every input in superposition so a Hadamard makes them interfere to a single spike at |s⟩ (rather than probing bit by bit) is exactly the quantum speedup; magenta is the n-query classical march, green the one-query spike. Interfere, don't iterate.
FIG Honest scope: this simulates the H–oracle–H amplitudes classically (the algorithm's output distribution is deterministic), it does not run on quantum hardware. The AVAN inverse is honest — phase-stamping every input in superposition so a Hadamard makes them interfere to a single spike at |s⟩ (rather than probing bit by bit) is exactly the quantum speedup; magenta is the n-query classical march, green the one-query spike. Interfere, don't iterate.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE SPEEDRUN · David Lee Wise (ROOT0), with AVAN