Introduction

Imagine a black box. You feed it a string of bits and it spits out another string. You are told one thing about it: there is a secret string ss such that two inputs xx and yy collide — give the same output — exactly when y = x XOR s. Every output appears for exactly two inputs, and those two always differ by ss.

Your job is to find ss. You can ask the box anything, as many times as you like. How many questions do you need?

Classically, the box is useless until you stumble on a collision — two different inputs with the same output. Until then, every answer looks random. For an nn-bit string you typically have to probe on the order of 2n/22^{n/2} inputs before two of them happen to match — exponential in nn.

In 1994 Daniel Simon showed that a quantum computer can find ss after only about nn queries. That gap — a handful of questions versus exponentially many — was the first proven exponential separation between quantum and classical computation, and it is the idea that directly inspired Shor's algorithm.

Hunt the Hidden String

Below is a black box hiding a secret string ss over 4-bit inputs (16 possible inputs). Classically, you query inputs one at a time and only learn ss once two of your queries collide — until then the box looks random. Quantumly, each run of Simon's circuit hands you one random equation about ss; a few of those pin it down exactly.

<p class="hint">A black box hides a secret 4-bit string <b>s</b>. Two inputs collide (same output) exactly when they differ by <b>s</b>. <b>Classical query</b> probes inputs one at a time — you only learn s once two queries collide. <b>Quantum run</b> hands you a random equation z·s = 0; a few of those pin s down.</p>
<div class="cols">
  <div class="panel">
    <h4>Classical</h4>
    <div class="meter"><span>Queries</span><b id="cq">0</b></div>
    <div class="log" id="clog"></div>
    <button id="classical" type="button">Classical query</button>
  </div>
  <div class="panel">
    <h4>Quantum (Simon)</h4>
    <div class="meter"><span>Runs</span><b id="qq">0</b></div>
    <div class="log" id="qlog"></div>
    <button id="quantum" type="button">Quantum run</button>
  </div>
</div>
<div class="status" id="status">Press a button to start probing the box.</div>
<div class="btns"><button id="reveal" type="button" class="ghost">New box</button></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.cols { display: grid; grid-template-columns: 1fr 1fr; gap: .8rem; }
.panel { border: 1px solid #cdd9e3; border-radius: 10px; padding: .7rem; background: #f4f8fb; }
.panel h4 { margin: 0 0 .5rem; color: #1d3557; font-size: .95rem; }
.meter { display: flex; justify-content: space-between; font-size: .85rem; color: #444; margin-bottom: .4rem; }
.meter b { font-family: ui-monospace, monospace; color: #1d3557; }
.log { font: 600 12px ui-monospace, monospace; background: #fff; border: 1px solid #e2e8ef;
       border-radius: 6px; height: 132px; overflow-y: auto; padding: .4rem; margin-bottom: .5rem;
       white-space: pre-wrap; line-height: 1.5; }
.log .hit { color: #0a7d33; }
.log .sol { color: #c92f3c; font-weight: 700; }
.status { font-size: 1rem; font-weight: 600; margin: .7rem 0 .4rem; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; width: 100%; }
button.ghost { background: #fff; color: #1d3557; width: auto; }
@media (max-width: 460px){ .cols { grid-template-columns: 1fr; } }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Simon's problem on 4-bit strings. A secret s (s != 0) defines a 2-to-1 box:
// f(x) == f(y)  <=>  y == x XOR s. Classically you must find a COLLISION, which
// takes ~2^(n/2) random queries. Simon's quantum algorithm instead yields, per run,
// a uniformly random z with z·s = 0 (mod 2); ~n-1 independent z's determine s by
// linear algebra over GF(2). This demo simulates both query models.
const N = 4, SIZE = 1 << N;
let s, label, classQueries, classSeen, quantumEqs, basis, solved;

const bits = x => x.toString(2).padStart(N, '0');
const parity = x => { let p = 0; while (x) { p ^= (x & 1); x >>= 1; } return p; }; // popcount mod 2
const dot = (a, b) => parity(a & b); // GF(2) inner product
const hi = x => { let h = 0; while (x) { h = x & -x; x &= x - 1; } return h; }; // highest set bit

function newBox() {
  s = 1 + Math.floor(Math.random() * (SIZE - 1)); // nonzero secret
  // Build a 2-to-1 labelling: pair x with x^s, give each pair a distinct output.
  label = new Array(SIZE).fill(-1);
  let next = 0;
  for (let x = 0; x < SIZE; x++) if (label[x] === -1) {
    label[x] = next; label[x ^ s] = next; next++;
  }
  classQueries = 0; classSeen = new Map(); quantumEqs = []; basis = []; solved = false;
  document.getElementById('cq').textContent = '0';
  document.getElementById('qq').textContent = '0';
  document.getElementById('clog').innerHTML = '';
  document.getElementById('qlog').innerHTML = '';
  setStatus('New box ready. Secret is hidden — go find it.', '');
}
function setStatus(t, cls){ const e = document.getElementById('status'); e.textContent = t; e.className = 'status ' + cls; }
function append(id, html){ const l = document.getElementById(id); l.innerHTML += html; l.scrollTop = l.scrollHeight; }

// CLASSICAL: query a random fresh input, watch for a collision.
function classicalQuery() {
  const tried = classSeen.size;
  if (tried >= SIZE) { setStatus('Exhausted all 16 inputs classically.', ''); return; }
  let x; do { x = Math.floor(Math.random() * SIZE); } while (classSeen.has(x));
  classQueries++;
  const out = label[x];
  document.getElementById('cq').textContent = classQueries;
  // collision = some earlier input gave the same output
  let collided = null;
  for (const [px, po] of classSeen) if (po === out) { collided = px; break; }
  classSeen.set(x, out);
  if (collided !== null) {
    const found = x ^ collided; // equals s
    append('clog', `<span class="hit">f(${bits(x)})=f(${bits(collided)}) → s=${bits(found)}</span>\n`);
    setStatus(fmt('Classical collision after %classQueries% queries → s = %bits%.', { classQueries: classQueries, bits: bits(found) }), 'ok');
  } else {
    append('clog', `f(${bits(x)}) = #${out}\n`);
    setStatus(fmt('Classical: %classQueries% queries, no collision yet.', { classQueries: classQueries }), '');
  }
}

// QUANTUM (Simon): one run yields a uniformly random z with z·s = 0.
function quantumRun() {
  if (solved) return;
  let z; do { z = Math.floor(Math.random() * SIZE); } while (dot(z, s) !== 0); // z·s=0
  document.getElementById('qq').textContent = (+document.getElementById('qq').textContent) + 1;
  // keep only equations that add rank (independent over GF(2))
  const red = reduce(basis, z);
  if (z !== 0 && red !== 0) {
    basis.push(red);   // store reduced echelon row so future tests stay valid
    quantumEqs.push(z);
    append('qlog', fmt('z=%bits%  (z·s=0)', { bits: bits(z) }) + "\n");
  } else {
    append('qlog', fmt('z=%bits%  (redundant)', { bits: bits(z) }) + "\n");
  }
  if (quantumEqs.length >= N - 1) {
    const cand = solveForS(quantumEqs); // unique nonzero s with z·s=0 for all z
    solved = true;
    append('qlog', fmt('<span class="sol">solved: s=%bits%</span>', { bits: bits(cand) }) + "\n");
    setStatus(fmt('Quantum: %length% equations → s = %bits% ✓', { length: quantumEqs.length, bits: bits(cand) }), 'ok');
  } else {
    setStatus(fmt('Quantum: %length% independent equation(s), need %v%.', { length: quantumEqs.length, v: N - 1 }), '');
  }
}
// Reduce v against an echelon basis (rows keyed by highest set bit). Returns the
// reduced row, or 0 if v is linearly dependent on the basis over GF(2).
function reduce(rows, v) {
  let x = v;
  for (const r of rows) { const p = hi(r); if (x & p) x ^= r; }
  return x;
}
// Find the unique nonzero s orthogonal to every equation (null space of the system).
function solveForS(rows) {
  for (let cand = 1; cand < SIZE; cand++) {
    if (rows.every(r => dot(r, cand) === 0)) return cand;
  }
  return 0;
}

document.getElementById('classical').addEventListener('click', classicalQuery);
document.getElementById('quantum').addEventListener('click', quantumRun);
document.getElementById('reveal').addEventListener('click', newBox);
newBox();
Result
Console

Press Classical query repeatedly and watch how long collisions take to appear. Then press Quantum run a few times: each one adds a linear equation, and once you have enough independent equations the secret ss falls out of simple algebra. Count the steps — the asymmetry is the whole point.

The Real Complexity

What makes Simon's result historic is that the speedup is proven, not assumed.

  • Quantum cost: Simon's algorithm runs the box in superposition, then measures. Each run yields a random bit-string zz that satisfies z⋅s=0z \cdot s = 0 (mod 2) — one linear equation about the secret. After about n−1n - 1 independent equations, solving the linear system recovers ss. Total: O(n)O(n) queries and polynomial post-processing.
  • Classical cost: any classical algorithm — deterministic or randomized — needs Ω(2n/2)\Omega(2^{n/2}) queries. This is a real lower bound: until two queries collide, the outputs are indistinguishable from a random one-to-one function, so no clever strategy helps.
  • The separation: that puts a polynomial quantum cost against an exponential classical cost in the black-box (query) model. It was the first proven exponential quantum speedup, announced by Daniel Simon in 1994 (published 1997).

A caveat worth stating: this is an oracle separation, not a statement about P vs NP. It shows quantum beats classical for querying a black box, which is exactly the kind of structured problem Shor would soon turn into something useful.

Where It Matters

Simon's problem looks like a toy, and it is — but its shape is everywhere that matters in quantum algorithms.

  • The blueprint for Shor: finding a hidden XOR-period is a special case of the hidden subgroup problem. Swap XOR for ordinary addition and the same idea becomes period-finding — the heart of Shor's algorithm for factoring and the discrete logarithm.
  • Breaking cryptography: because Shor descends directly from Simon, today's RSA and elliptic-curve systems are at risk once large quantum computers exist — the reason for the post-quantum cryptography migration now underway.
  • Symmetric-key attacks: Simon's algorithm itself has been used to break certain block-cipher modes and message-authentication schemes when a quantum adversary can query them.
  • Teaching quantum advantage: it is the cleanest example of why quantum interference helps — far simpler than Shor or Grover, yet it already shows an exponential gap.

Conclusion

Simon's algorithm answers a deceptively small question — what is the hidden string? — and in doing so settled a much bigger one: there really are problems where a quantum computer is exponentially faster than any classical one. The proof is airtight in the query model, and it needs no unsolved conjecture.

Within months, Peter Shor took the same superposition-and-interference recipe, replaced XOR-periods with number-theoretic periods, and produced an algorithm that breaks the cryptography securing the internet. Simon's little black box was the spark — proof that the strange rules of quantum mechanics buy you genuine, exponential computational power.

Share this article

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

Comments

Loading comments...

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