Bernstein–Vazirani Algorithm: One Query, Full String

Hidden String s

Algorithm

Ready — press Run

Animation speed 1.0×

Readout

state: |00…0⟩ ⊗ superposition register

Quantum queries

0 / 1

Classical queries needed

Hidden s

0000

Measured

—

How it works

Given a black-box oracle computing f(x) = s·x mod 2 for a hidden n-bit string s, the Bernstein–Vazirani algorithm recovers all of s with a single oracle query, versus n queries for the best classical strategy.

1. |0⟩^n |1⟩              — n input qubits + one ancilla in |1⟩
2. Apply H^(n+1)           — uniform superposition over all 2ⁿ states
3. Oracle U_f: |x⟩|y⟩ → |x⟩|y⊕(s·x)⟩
   phase kickback (ancilla in |−⟩) turns this into
   |x⟩ → (−1)^(s·x) |x⟩   for every branch, in one call
4. Apply H^n to the input register
5. Measure → result = s, with probability 1

Step 4 works because the Hadamard transform of a phase-encoded state is (1/2ⁿ) Σ_x (−1)^(s·x) (−1)^(x·y) = δ(y = s): every basis state except y = s cancels by destructive interference, and amplitude 1 survives only at y = s.

Bar grid — one 3D bar per computational basis state 0..2ⁿ−1; height is the outcome probability, color is the sign of the amplitude (purple = +, red = −).
Superposition stage — all bars equal height 1/2ⁿ, all positive.
Oracle stage — heights unchanged, but bars where s·x is odd flip to red (a global phase, invisible to any single measurement, yet exactly what the final Hadamard reads out).
Final Hadamard stage — every bar collapses to zero except the one at index s, which rises to probability 1.

Real-world relevance: this is the canonical textbook proof that quantum query complexity can beat classical query complexity exponentially for a black-box problem — the same phase-kickback trick underlies Simon's algorithm and Shor's period-finding.

Amplitude + Amplitude −

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.