Simon's Algorithm

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 $s$ such that two inputs $x$ and $y$ collide — give the same output — exactly when y = x XOR s. Every output appears for exactly two inputs, and those two always differ by $s$.

Your job is to find $s$. 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 $n$-bit string you typically have to probe on the order of $2^{n/2}$ inputs before two of them happen to match — exponential in $n$.

In 1994 Daniel Simon showed that a quantum computer can find $s$ after only about $n$ 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.

Below is a black box hiding a secret string $s$ over 4-bit inputs (16 possible inputs). Classically, you query inputs one at a time and only learn $s$ 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 $s$; a few of those pin it down exactly.

<p class="hint">{{hint}}</p>
<div class="cols">
  <div class="panel">
    <h4>{{h_classical}}</h4>
    <div class="meter"><span>{{lbl_queries}}</span><b id="cq">0</b></div>
    <div class="log" id="clog"></div>
    <button id="classical" type="button">{{btn_classical}}</button>
  </div>
  <div class="panel">
    <h4>{{h_quantum}}</h4>
    <div class="meter"><span>{{lbl_runs}}</span><b id="qq">0</b></div>
    <div class="log" id="qlog"></div>
    <button id="quantum" type="button">{{btn_quantum}}</button>
  </div>
</div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns"><button id="reveal" type="button" class="ghost">{{btn_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; } }

// Code not found

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 $s$ falls out of simple algebra. Count the steps — the asymmetry is the whole point.

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 $z$ that satisfies $z \cdot s = 0$ (mod 2) — one linear equation about the secret. After about $n - 1$ independent equations, solving the linear system recovers $s$. Total: $O(n)$ queries and polynomial post-processing.
• Classical cost: any classical algorithm — deterministic or randomized — needs $\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.

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.

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.