Introduction

Imagine a black box that knows a secret nn-bit string s=sn−1…s1s0s = s_{n-1} \dots s_1 s_0. You can query it: hand it any nn-bit string xx and it returns the inner product f(x)=s⋅x=(sn−1xn−1+⋯+s0x0) mod 2f(x) = s \cdot x = (s_{n-1} x_{n-1} + \dots + s_0 x_0) \bmod 2. One bit out. Your job is to figure out all nn bits of ss.

Classically, the strategy is obvious: send x=10…0x = 10\dots0, x=010…0x = 010\dots0, and so on — each query peels off one bit of ss. After nn queries you know ss exactly. And it is provably necessary: any deterministic or randomized algorithm needs at least nn queries, because each query yields at most one bit of information.

A quantum computer does it in one query. This is the Bernstein-Vazirani algorithm, published by Ethan Bernstein and Umesh Vazirani in 1993 and the companion paper in 1997. It was one of the earliest demonstrations that quantum computers can solve natural problems exponentially faster than classical ones — not just asymptotically faster in an abstract setting, but with a provably exact separation: 1 versus nn.

The trick is superposition. A quantum computer does not ask "what is f(10…0)f(10\dots0)?" and then "what is f(010…0)f(010\dots0)?" — it asks all nn questions simultaneously in a single coherent query, and interference does the rest.

Try It

Pick a secret bit-string (or use the random one). The oracle computes f(x)=s⋅x mod 2f(x) = s \cdot x \bmod 2. Try querying it classically — you will need one bit at a time. Then press Run quantum query to see the Hadamard trick recover all bits in one shot.

<!-- Main layout: secret selector, classical panel, quantum panel -->
<div class="bv-wrap">
  <div class="secret-row">
    <span class="label">Secret s =</span>
    <div id="secret-bits" class="bit-row"></div>
    <button id="btn-random" type="button" class="ghost sm">Random</button>
  </div>
  <hr class="divider"/>
  <div class="panel">
    <div class="panel-head">Classical: n queries</div>
    <p class="panel-desc">Each query uses a basis vector to reveal one bit. Click to step through.</p>
    <div id="classical-queries" class="query-log"></div>
    <div class="panel-actions">
      <button id="btn-classical-step" type="button">Query next bit</button>
      <button id="btn-classical-reset" type="button" class="ghost sm">Reset</button>
    </div>
    <div class="result-row" id="classical-result"></div>
  </div>
  <hr class="divider"/>
  <div class="panel">
    <div class="panel-head">Quantum: 1 query</div>
    <p class="panel-desc">Hadamard + phase kickback + Hadamard reveals all bits at once.</p>
    <div id="quantum-visual" class="hadamard-vis"></div>
    <div class="panel-actions">
      <button id="btn-quantum" type="button">Run quantum query</button>
      <button id="btn-quantum-reset" type="button" class="ghost sm">Reset</button>
    </div>
    <div class="result-row" id="quantum-result"></div>
  </div>
</div>

/* Base layout styles */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 14px 4px; }
.bv-wrap { max-width: 520px; margin: 0 auto; }
.secret-row { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; margin-bottom: .3rem; }
.label { font-size: .85rem; font-weight: 700; color: #444; white-space: nowrap; }
.bit-row { display: flex; gap: 4px; flex-wrap: wrap; }
/* Bit toggle button styles */
.bit { width: 34px; height: 34px; display: flex; align-items: center; justify-content: center;
       font: 700 16px ui-monospace, monospace; border-radius: 6px; cursor: pointer; user-select: none;
       border: 2px solid #adb1b8; background: #e4e7eb; transition: all .15s; }
.bit.on { background: #1d3557; border-color: #1d3557; color: #fff; }
.bit.off { background: #e4e7eb; color: #555; }
.divider { border: none; border-top: 1px solid #dde3ea; margin: .8rem 0; }
.panel { margin-bottom: .4rem; }
.panel-head { font-size: .9rem; font-weight: 700; color: #1d3557; margin-bottom: .2rem; }
.panel-desc { font-size: .82rem; color: #555; margin: 0 0 .4rem; line-height: 1.45; }
/* Query log styles */
.query-log { font: 13px/1.55 ui-monospace, monospace; min-height: 1.6em; color: #333;
             background: #f4f6f8; border-radius: 6px; padding: .35rem .55rem; margin-bottom: .4rem; }
.q-row { display: flex; gap: .5rem; align-items: baseline; }
.q-x { color: #1d3557; }
.q-eq { color: #888; }
.q-val { color: #0a7d33; font-weight: 700; }
.panel-actions { display: flex; gap: .4rem; flex-wrap: wrap; margin-bottom: .3rem; }
.result-row { font-size: .9rem; font-weight: 600; min-height: 1.4em; }
.result-row.ok { color: #0a7d33; }
.result-row.progress { color: #555; }
/* Hadamard visualizer styles */
.hadamard-vis { font: 13px/1.6 ui-monospace, monospace; background: #f4f6f8;
                border-radius: 6px; padding: .35rem .55rem; margin-bottom: .4rem; min-height: 2.5em; }
.h-step { color: #666; }
.h-step .hi { color: #1d3557; font-weight: 700; }
.h-step .hval { color: #0a7d33; font-weight: 700; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button.sm { font-size: 12px; padding: .3rem .6rem; }
button:disabled { opacity: .45; cursor: default; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Bernstein-Vazirani demo: classical vs quantum query comparison
// Oracle: f(x) = s · x mod 2 (bitwise dot product mod 2)
// Classical approach: send basis vectors e_i to learn s[i] one at a time
// Quantum approach: Hadamard + oracle (phase kickback) + Hadamard = s in 1 query

const N = 5; // number of bits in the secret string
let secret = [1, 0, 1, 1, 0]; // default secret (user can toggle bits or randomize)

// Oracle function: dot product of secret and x, mod 2
function oracle(x) {
  let dot = 0;
  for (let i = 0; i < N; i++) dot ^= (secret[i] & x[i]);
  return dot;
}

// Render the secret bit-string as clickable toggles
function renderSecret() {
  const row = document.getElementById('secret-bits');
  row.innerHTML = '';
  for (let i = 0; i < N; i++) {
    const d = document.createElement('div');
    d.className = 'bit ' + (secret[i] ? 'on' : 'off');
    d.textContent = secret[i];
    d.dataset.idx = i;
    d.addEventListener('click', () => {
      secret[i] ^= 1;
      resetAll();
      renderSecret();
    });
    row.appendChild(d);
  }
}

// Classical solver state: how many bits found so far
let classicalStep = 0;
let classicalFound = [];

function runClassicalStep() {
  if (classicalStep >= N) return;
  // Build the i-th basis vector (all zeros except position i)
  const x = Array(N).fill(0);
  x[classicalStep] = 1;
  const bit = oracle(x);
  classicalFound.push(bit);
  const log = document.getElementById('classical-queries');
  const row = document.createElement('div');
  row.className = 'q-row';
  row.innerHTML =
    '<span class="q-x">f(' + x.join('') + ')</span>' +
    '<span class="q-eq"> = </span>' +
    '<span class="q-val">' + bit + '</span>' +
    '<span class="q-eq"> &rarr; s[' + classicalStep + '] = ' + bit + '</span>';
  log.appendChild(row);
  classicalStep++;
  updateClassicalResult();
}

function updateClassicalResult() {
  const el = document.getElementById('classical-result');
  if (classicalStep < N) {
    el.textContent = fmt('Queried %classicalStep% of %N% bits — keep stepping.', { classicalStep: classicalStep, N: N });
    el.className = 'result-row progress';
    document.getElementById('btn-classical-step').disabled = false;
  } else {
    el.textContent = fmt('Done in %classicalFound% queries. Secret = %N%', { classicalFound: classicalFound.join(''), N: N });
    el.className = 'result-row ok';
    document.getElementById('btn-classical-step').disabled = true;
  }
}

// Quantum algorithm: simulate the three-step Hadamard procedure
function runQuantum() {
  const vis = document.getElementById('quantum-visual');
  vis.innerHTML = '';
  // Step 1: apply H to all input qubits (uniform superposition)
  appendStep(vis, '<span class=’hi’>Step 1:</span> H⊗n applied — qubits enter uniform superposition over all 2^n inputs.');
  // Step 2: oracle encodes s into phases via phase kickback
  appendStep(vis, '<span class=’hi’>Step 2:</span> Oracle query — phase kickback encodes (−1)^(s·x) into every amplitude simultaneously.');
  // Step 3: second Hadamard layer decodes phases back to s
  appendStep(vis, '<span class=’hi’>Step 3:</span> H⊗n applied again — phases interfere constructively only at x = s.');
  // Measurement collapses to |s> with probability 1
  appendStep(vis, fmt('<span class=’hi’>Measure:</span> collapses to |<span class="hval">%secret%</span>⟩ with probability 1.', { secret: secret.join('') }));

  const el = document.getElementById('quantum-result');
  el.textContent = fmt('Secret revealed in 1 query: s = %secret%', { secret: secret.join('') });
  el.className = 'result-row ok';
  document.getElementById('btn-quantum').disabled = true;
}

function appendStep(container, html) {
  const d = document.createElement('div');
  d.className = 'h-step';
  d.innerHTML = html;
  container.appendChild(d);
}

// Reset helper functions
function resetClassical() {
  classicalStep = 0;
  classicalFound = [];
  document.getElementById('classical-queries').innerHTML = '';
  document.getElementById('classical-result').textContent = '';
  document.getElementById('classical-result').className = 'result-row';
  document.getElementById('btn-classical-step').disabled = false;
}

function resetQuantum() {
  document.getElementById('quantum-visual').innerHTML = '';
  document.getElementById('quantum-result').textContent = '';
  document.getElementById('quantum-result').className = 'result-row';
  document.getElementById('btn-quantum').disabled = false;
}

function resetAll() {
  resetClassical();
  resetQuantum();
}

// Wire up the random-secret button and all other controls
document.getElementById('btn-random').addEventListener('click', () => {
  secret = Array.from({ length: N }, () => Math.random() < 0.5 ? 1 : 0);
  resetAll();
  renderSecret();
});

document.getElementById('btn-classical-step').addEventListener('click', runClassicalStep);
document.getElementById('btn-classical-reset').addEventListener('click', resetClassical);
document.getElementById('btn-quantum').addEventListener('click', runQuantum);
document.getElementById('btn-quantum-reset').addEventListener('click', resetQuantum);

renderSecret();
updateClassicalResult();
Result
Console

Notice the asymmetry. Each classical query learns exactly one bit of ss — and you need all nn. The quantum query puts xx into uniform superposition over all 2n2^n inputs simultaneously, applies the oracle coherently, and a final Hadamard layer reads out ss all at once. The oracle is called once, no matter how large nn is.

The Real Complexity

The algorithm is three steps, each essential:

  1. Prepare a uniform superposition. Apply a Hadamard gate HH to each of the nn input qubits (all starting in ∣0⟩|0\rangle) and one ancilla qubit (starting in ∣−⟩=∣0⟩−∣1⟩2|{-}\rangle = \frac{|0\rangle - |1\rangle}{\sqrt{2}}). The nn qubits now simultaneously represent every string x∈{0,1}nx \in \{0,1\}^n with equal amplitude.

  2. Query the oracle. The oracle maps ∣x⟩∣y⟩↦∣x⟩∣y⊕f(x)⟩|x\rangle|y\rangle \mapsto |x\rangle|y \oplus f(x)\rangle. Because the ancilla is in state ∣−⟩|{-}\rangle, the phase kickback trick applies: the net effect is ∣x⟩↦(−1)f(x)∣x⟩=(−1)s⋅x∣x⟩|x\rangle \mapsto (-1)^{f(x)}|x\rangle = (-1)^{s \cdot x}|x\rangle. The oracle runs once; its output is encoded in the phases of every amplitude simultaneously.

  3. Read out ss by a second Hadamard layer. The state after the oracle is 12n∑x(−1)s⋅x∣x⟩\frac{1}{\sqrt{2^n}}\sum_{x} (-1)^{s \cdot x}|x\rangle. Applying H⊗nH^{\otimes n} transforms this to ∣s⟩|s\rangle — exactly the secret string, with probability 1. Measure and you have ss.

Why does this work? The Hadamard transform is its own inverse on phase-encoded strings. Encoding ss into phases by the inner product, then transforming back, is precisely Fourier analysis over (Z/2Z)n(\mathbb{Z}/2\mathbb{Z})^n. The phases interfere constructively at x=sx = s and destructively everywhere else.

The separation is exact and unconditional. Classically, nn queries are necessary (each query is one bit of information; you need nn bits). Quantum mechanically, 1 query is sufficient. This is a query complexity result: it counts oracle calls, not elementary gates. The circuit itself uses O(n)O(n) gates, so the overall complexity is efficient. This places the problem in BQP (quantum polynomial time) with a 1-query algorithm, while the classical lower bound says no classical algorithm — deterministic or randomized — can do better than nn queries.

Bernstein-Vazirani also has a recursive variant (recursive BV): apply the trick in layers to create a problem that separates BQP from BPP (classical randomized poly-time) by a super-polynomial factor, foreshadowing Shor's algorithm which separates them exponentially for factoring.

Where It Matters

The algorithm is simple, but the ideas behind it reappear throughout quantum computing and beyond:

  • Blueprint for quantum algorithm design. Phase kickback + Hadamard readout is the core template for Deutsch-Jozsa, Simon's algorithm, and ultimately Shor's period-finding. Understanding BV is the cleanest entry point to why Hadamard-based algorithms work.
  • Oracle separations and complexity theory. BV gives the cleanest unconditional proof that quantum query complexity can beat classical query complexity by a linear factor. Relativized separations of this kind are a primary tool for understanding the BQP vs. P/BPP landscape.
  • Learning Parity with Noise (LPN). The noiseless version of the BV oracle is exactly the parity learning problem. Its noisy extension — LPN — is a central hardness assumption in post-quantum cryptography. The speed with which quantum algorithms can attack noiseless parity is why LPN needs noise to remain hard.
  • Quantum machine learning. BV is a textbook example of quantum-enhanced linear algebra: you evaluate a linear function over all inputs at once. This intuition motivates quantum approaches to gradient estimation and Fourier-based learning.
  • Teaching tool. Because the speedup is exact (not asymptotic) and the proof is fully self-contained at the undergraduate level, BV is the first algorithm taught in virtually every quantum computing course.

Conclusion

The Bernstein-Vazirani algorithm carries a clean and powerful message: quantum superposition is not just a metaphor — it is a computational resource that changes what is possible. Learning a secret nn-bit string takes exactly nn classical queries and exactly 1 quantum query, and no cleverness on the classical side can close that gap.

The mechanism — prepare uniform superposition, query with phase kickback, decode with Hadamard — is the same skeleton that underlies Shor's algorithm, the greatest quantum speedup known. Bernstein-Vazirani is where that skeleton first appears in its purest form: no approximations, no probability to amplify, just a single shot at the full secret.

If you want to understand why physicists believe quantum computers are genuinely more powerful than classical ones, this is the right place to start.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/bernstein-vazirani/Content licensed under CC BY-NC 4.0.