Simon's Algorithm

Simon's algorithm is the moment the case for quantum computing stopped being a curiosity and became an argument. Deutsch–Jozsa and Bernstein–Vazirani had already beaten deterministic classical machines, but a coin-flipping classical machine solves both in a handful of queries — so the separation evaporates the instant you allow randomness. Daniel Simon's 1994 construction closed that loophole. It hands you a black box $f$ that hides a secret string $s$ , and finds $s$ with about $n$ quantum queries while any classical strategy — deterministic or randomized, with any allowed error — provably needs on the order of $2^{n/2}$ . That is not a polynomial saving; it is an exponential wall, and the first time anyone drew it cleanly. The promise is deliberately spare. The oracle computes $f:\{0,1\}^n\to\{0,1\}^n$ with the guarantee that $f(x)=f(y)$ exactly when $x\oplus y$ is either the all-zeros string or the hidden mask $s$ . So $f$ is two-to-one, and every colliding pair differs by the same $s$ . Classically you learn nothing until you stumble on a collision, which the birthday bound puts roughly $2^{n/2}$ queries away. The quantum machine instead manufactures a collision on demand: one oracle call in superposition, a measurement of the output register, and the input register is left holding both preimages at once. A second layer of Hadamards turns that hidden symmetry into a visible constraint — each run donates one random linear equation $y\cdot s=0$ over the two-element field, and $n-1$ independent equations pin down $s$ . Structurally this is the abelian hidden subgroup problem, the same skeleton Shor would wrap around factoring within months.

Key takeaways

Simon's problem: given a black box $f:\{0,1\}^n\to\{0,1\}^n$ promised to be two-to-one with $f(x)=f(y)\iff x\oplus y\in\{0^n,s\}$ , find the hidden mask $s$ .
The quantum algorithm uses $O(n)$ oracle queries; every classical algorithm needs $\Omega(2^{n/2})$ — the first clean, provable exponential quantum–classical query separation.
One run: Hadamard the input register, call the oracle once, measure the output register, Hadamard again, and read a string $y$ that is guaranteed to satisfy $y\cdot s=0\bmod 2$ .
Collect $n-1$ linearly independent samples and solve the resulting linear system over $\mathbb{F}_2$ by Gaussian elimination to recover $s$ ; a batch of $n-1$ samples is independent with probability at least $0.2888$ .
The Hadamard layer is the quantum Fourier transform over $(\mathbb{Z}_2)^n$ , and the whole procedure is the abelian hidden subgroup recipe that Shor's factoring algorithm inherits.
Key idea: measuring the output register collapses the input register onto the two-element coset $\tfrac{1}{\sqrt2}(|x_0\rangle+|x_0\oplus s\rangle)$ ; a Hadamard transform of that $s$ -periodic state has amplitude only on strings orthogonal to $s$ , so each measurement returns a uniformly random vector in the hyperplane $s^{\perp}$ , and $n-1$ of them determine $s$ .

The core insight

Measuring the output register leaves the input register in the coset state $\tfrac{1}{\sqrt2}(|x_0\rangle+|x_0\oplus s\rangle)$ ; the Hadamard transform of this $s$ -periodic state is supported only on strings $y$ with $y\cdot s=0\bmod2$ , so each run samples a uniformly random vector from the hyperplane $s^{\perp}$ , and $n-1$ independent samples fix $s$ by linear algebra over $\mathbb{F}_2$ .

Where this lives today

Simon's algorithm is small enough to be a favourite hardware demonstration: two- and three-bit instances have run on ion-trap, superconducting, and photonic processors and on IBM's public devices, precisely because a working run shows entanglement, oracle queries, and Fourier sampling in one compact circuit. But its living importance is conceptual and cryptographic. Conceptually, it is the template for the abelian hidden subgroup problem — prepare a coset state, Fourier-sample its dual, recover the subgroup — which unifies Simon's problem, order-finding, period-finding, and the discrete logarithm under one algorithm, and whose non-abelian generalizations (graph isomorphism, unique shortest vector) remain among the most-studied open problems in quantum algorithms. Cryptographically, Simon's period-finding drives a family of quantum attacks: Kuwakado and Morii (2010–2012) showed the three-round Feistel construction and the Even–Mansour cipher expose a Simon-type hidden period to an adversary with superposition query access, and Kaplan and co-authors (2016) extended this to break many message-authentication codes and modes of operation in polynomial time. These attacks are why post-quantum symmetric-key design now explicitly asks whether a construction hides an XOR period — a present-day consequence of a 1994 black-box result.

The physical picture

Classically, learning $s$ means catching a collision — two distinct inputs with the same output — with no way to steer toward one; you throw queries at the box and wait for a coincidence. The quantum trick is to stop searching and start manufacturing. Put the input register into a uniform superposition over all $2^n$ strings, fire the oracle once, and every input sits entangled with its own image. Now measure only the output register. You land on some value $z$ , and because the promise makes $f$ exactly two-to-one, that value has precisely two preimages, $x_0$ and $x_0\oplus s$ . The measurement cannot tell you which, so it leaves the input register holding both — coherently, at equal amplitude. You have conjured a collision pair for free, but as a superposition you cannot read directly.

Figure

One run of Simon's algorithm: Hadamard the n-qubit input register, call the oracle once, measure the output register to collapse the input onto the coset of x₀ and x₀⊕s, Hadamard again, and measure a string y that always satisfies y·s = 0. Each allowed y appears with probability 2^-(n-1)

The second Hadamard layer is where the hidden symmetry surfaces. The coset state $\tfrac{1}{\sqrt2}(|x_0\rangle+|x_0\oplus s\rangle)$ is invariant under the shift $x\mapsto x\oplus s$ — a periodic state, with period $s$ , on the Boolean cube. Fourier analysis has one iron law: transforming a periodic function concentrates its weight on the dual of that period. Here the transform $H^{\otimes n}$ is exactly the quantum Fourier transform over $(\mathbb{Z}_2)^n$ , and the dual of $\{0^n,s\}$ is the annihilator $s^{\perp}=\{y:y\cdot s=0\}$ . Constructive interference survives only where the phases $(-1)^{y\cdot x_0}$ and $(-1)^{y\cdot(x_0\oplus s)}$ agree; everywhere else they cancel exactly. So the measured $y$ is forced, uniformly, into the hyperplane orthogonal to $s$ . Each run is thus a single coin flip handing you one random linear equation $y\cdot s=0$ over $\mathbb{F}_2$ . One equation cannot reveal $s$ — it only rules out half the candidates. Recovering $s$ is a coupon-collector problem in linear algebra: sample vectors from the $(n-1)$ -dimensional space $s^{\perp}$ until $n-1$ of them are independent, then the orthogonal complement is one line and its unique nonzero member is $s$ . The cost of collecting enough is linear in $n$ , setting the whole quantum query budget against the exponential classical wall drawn below.

Figure

Quantum versus classical query cost for Simon's problem on a logarithmic scale: the quantum algorithm needs about n queries while any classical method needs about 2^(n/2). At n = 40 that is roughly 40 quantum queries against 2^20 ≈ 1.05×10⁶ classical queries — an exponential gap that widens without bound

The core equations

The promise is the whole problem. It is a structural guarantee on $f$ — not a property you can read off any single value, but a symmetry that ties every pair of colliding inputs to the same hidden offset $s$ .

f:\{0,1\}^n\to\{0,1\}^n,\qquad f(x)=f(y)\iff x\oplus y\in\{0^n,s\} \qquad (1)

where: $s$ — the hidden mask in $\{0,1\}^n$ to determine; $\oplus$ — bitwise XOR, i.e. addition in $(\mathbb{Z}_2)^n$ ; $0^n$ — the all-zeros string. Reading: if $s=0^n$ the function is one-to-one; if $s\neq0^n$ it is exactly two-to-one, and the two preimages of every output differ by $s$ . The oracle is reversible, so it cannot simply overwrite the answer register — it XORs the result in. Initialized with the answer register at $|0^n\rangle$ , one call writes $f(x)$ while leaving the input untouched.

U_f\,|x\rangle|a\rangle=|x\rangle|a\oplus f(x)\rangle \qquad (2)

where: $|x\rangle$ — the $n$ -qubit input register; $|a\rangle$ — the $n$ -qubit answer register, set to $|0^n\rangle$ ; $\oplus$ — XOR, which keeps $U_f$ unitary. Reading: $U_f$ is its own inverse, and one query costs one application regardless of superposition on $|x\rangle$ . The Hadamard layer is not incidental — it is the Fourier transform for this group. Its matrix elements are the characters of $(\mathbb{Z}_2)^n$ , the sign patterns $(-1)^{x\cdot y}$ .

H^{\otimes n}|x\rangle=\frac{1}{\sqrt{2^n}}\sum_{y\in\{0,1\}^n}(-1)^{x\cdot y}\,|y\rangle \qquad (3)

where: $x\cdot y=\sum_i x_i y_i\bmod2$ — the $\mathbb{F}_2$ inner product; $(-1)^{x\cdot y}$ — the character indexed by $y$ . Reading: this is a genuine quantum Fourier transform, which is why "apply Hadamards" and "Fourier-sample the hidden subgroup" are the same instruction. After the output-register measurement, the input register is left in a two-element coset — the algorithm's engine. It is an $s$ -periodic state: shifting every label by $s$ maps it to itself.

|\psi_{\text{coset}}\rangle=\frac{1}{\sqrt2}\big(|x_0\rangle+|x_0\oplus s\rangle\big) \qquad (4)

where: $x_0$ — one preimage of the measured output $z=f(x_0)$ ; $x_0\oplus s$ — the other preimage, guaranteed by the promise. Reading: the measurement outcome $z$ is discarded; all that matters is that the input register now carries the hidden symmetry. Transforming that coset state and squaring the amplitudes gives the sampling law — the single most important line in the article. The probability is flat on $s^{\perp}$ and exactly zero off it.

\Pr[\,y\,]=\frac12\left|\frac{1}{\sqrt{2^n}}\big((-1)^{y\cdot x_0}+(-1)^{y\cdot(x_0\oplus s)}\big)\right|^2=\begin{cases}2^{-(n-1)} & y\cdot s=0\\[2pt]0 & y\cdot s=1\end{cases} \qquad (5)

where: $y\cdot s$ — the linear constraint harvested each run. Reading: every measurement is a uniformly random draw from the $2^{n-1}$ strings orthogonal to $s$ ; the outcome carries exactly one bit of information about $s$ (or zero bits when $y=0^n$ ). Stacking $n-1$ independent samples as rows of a matrix gives a homogeneous linear system whose one-dimensional solution space is spanned by $s$ .

y_j\cdot s=0\pmod2,\quad j=1,\dots,n-1\ \ \Longrightarrow\ \ s=\text{unique nonzero vector in }\{y_1,\dots,y_{n-1}\}^{\perp} \qquad (6)

where: $y_j$ — the $j$ -th sampled row; $n-1$ — the number of independent constraints that pin $s$ to a line. Reading: Gaussian elimination over $\mathbb{F}_2$ solves this in $O(n^3)$ classical operations, which never touches the oracle and so is irrelevant to the query count. The headline is the gap between the two query costs — the first provable exponential separation in the black-box model.

Q_{\text{quantum}}=O(n)\qquad\text{versus}\qquad Q_{\text{classical}}=\Omega\!\left(2^{n/2}\right) \qquad (7)

where: $Q$ — oracle queries needed to identify $s$ with bounded error. Reading: one call per run and $O(n)$ runs on the quantum side; the birthday bound on the classical side. The ratio grows without limit — at $n=40$ it is already about $2^{20}/40\approx2.6\times10^4$ .

Derivation AState evolution and the orthogonality constraint

The goal is to follow both registers through a single run — start, superposition, query, output measurement, second Hadamard — and prove that the interference makes every allowed outcome $y$ satisfy $y\cdot s=0$ with equal probability $2^{-(n-1)}$ . This is the core mechanism, and every later claim about query counts rests on the flat sampling law derived here, so we track amplitudes explicitly rather than gesturing at "interference".

Step 1. Begin in $|0^n\rangle|0^n\rangle$ and apply $H^{\otimes n}$ to the input register, giving the uniform superposition $\tfrac{1}{\sqrt{2^n}}\sum_x|x\rangle|0^n\rangle$ . Why: a single Hadamard layer spreads amplitude equally over all $2^n$ inputs, so one oracle call can act on the entire domain of $f$ at once.

Step 2. Apply $U_f$ to reach $\tfrac{1}{\sqrt{2^n}}\sum_x|x\rangle|f(x)\rangle$ . Why: the reversible XOR oracle entangles each input with its own image, correlating the two registers without collapsing the input superposition.

Step 3. Measure the output register and observe some value $z$ . By the promise, exactly two inputs map to $z$ — call them $x_0$ and $x_0\oplus s$ — so the input register collapses to $\tfrac{1}{\sqrt2}(|x_0\rangle+|x_0\oplus s\rangle)\otimes|z\rangle$ . Why: the two-to-one structure guarantees precisely two preimages, so the measurement manufactures the $s$ -periodic coset state that the rest of the algorithm exploits.

Step 4. Apply $H^{\otimes n}$ to the surviving input register: $H^{\otimes n}\tfrac{1}{\sqrt2}(|x_0\rangle+|x_0\oplus s\rangle)=\tfrac{1}{\sqrt{2^{n+1}}}\sum_y\big((-1)^{y\cdot x_0}+(-1)^{y\cdot(x_0\oplus s)}\big)|y\rangle$ . Why: this is the Fourier transform over $(\mathbb{Z}_2)^n$ applied to a periodic state, the step that converts a hidden symmetry into an observable constraint.

Step 5. Factor the common phase: the amplitude of $|y\rangle$ is $(-1)^{y\cdot x_0}\big(1+(-1)^{y\cdot s}\big)/\sqrt{2^{n+1}}$ , which equals $\pm2/\sqrt{2^{n+1}}$ when $y\cdot s=0$ and is exactly $0$ when $y\cdot s=1$ . Squaring gives $\Pr[y]=2^{-(n-1)}$ on $s^{\perp}$ and $0$ elsewhere. Why: the two preimages differ by $s$ , so their characters agree precisely on the annihilator $s^{\perp}$ — constructive interference there, total cancellation off it.

Go deeper · Derivation B · 1 minWhy order n runs recover the hidden string

Derivation BWhy order n runs recover the hidden string

The goal is to show a linear number of runs suffices: treat each nonzero sample as a uniformly random vector in the $(n-1)$ -dimensional space $s^{\perp}\cong(\mathbb{Z}_2)^{n-1}$ and lower-bound the probability that $n-1$ such draws are linearly independent, since only then does their orthogonal complement collapse to the single line containing $s$ . The punchline is a universal constant, independent of $n$ , which is what keeps the query count at $O(n)$ .

Step 1. After collecting $j-1$ independent vectors, their span contains $2^{j-1}$ of the $2^{n-1}$ vectors in $s^{\perp}$ , so a fresh uniform sample lands outside the span with probability $1-2^{j-1}/2^{n-1}=1-2^{\,j-1-(n-1)}$ . Why: independence fails only if the new vector happens to lie in the already-spanned subspace, whose relative size is $2^{j-1-(n-1)}$ .

Step 2. Multiply these probabilities for $j=1,\dots,n-1$ and re-index with $i=n-j$ to get $\Pr[\text{all independent}]=\prod_{i=1}^{n-1}\big(1-2^{-i}\big)$ . Why: the draws are independent, so the joint success probability is the product, and the re-indexing exposes a partial product of the same universal series for every $n$ .

Step 3. This partial product increases with $n$ and is bounded below by its infinite limit $\prod_{i=1}^{\infty}(1-2^{-i})\approx0.2887880951$ , the Euler function $\phi(1/2)$ . Why: each additional factor is closer to $1$ , so a batch of $n-1$ samples is fully independent with probability at least $0.288$ no matter how large $n$ is.

Step 4. If one batch fails, repeat: after $m$ batches the failure probability is at most $(1-0.288)^m$ , which drops below any fixed $\varepsilon$ after a constant number of batches — i.e. $O(n)$ total queries. Why: a constant per-batch success probability turns "recover $s$ with high probability" into $O(1)$ batches, keeping the query budget linear in $n$ .

Go deeper · Derivation C · 1 minThe classical birthday lower bound

Derivation CThe classical birthday lower bound

The goal is to establish the other half of the separation — that no classical algorithm, even a randomized one allowed to err, finds $s$ with fewer than order $2^{n/2}$ queries. The argument is information-theoretic: a classical machine learns about $s$ only when it witnesses a collision, and collisions are exponentially rare until the number of queried inputs nears the square root of the domain size — the birthday phenomenon.

Step 1. Suppose the algorithm has queried $t$ distinct inputs and seen no collision. Every output observed so far is distinct, and the transcript is consistent with $f$ being injective ( $s=0^n$ ) or with a huge number of possible masks $s$ — one for each way of pairing up the unqueried, as-yet-unseen inputs. Why: without a repeated output the data has not distinguished any candidate mask from any other, so no information about $s$ has been extracted.

Step 2. For a fixed pair of queried inputs $x,x'$ , the chance they collide is the chance $x\oplus x'=s$ , which for an unknown $s$ is about $2^{-n}$ . Across $t$ queries there are $\binom{t}{2}\approx t^2/2$ pairs, so the expected number of collisions is roughly $t^2/2^{\,n+1}$ . Why: collisions accumulate with the number of pairs, not the number of queries, which is the source of the square-root behaviour.

Step 3. To expect even one collision — the minimum needed to learn anything — requires $t^2/2^{\,n+1}\gtrsim1$ , i.e. $t\gtrsim2^{(n+1)/2}=\Omega(2^{n/2})$ . Why: below this threshold the expected collision count is exponentially small, so with high probability the machine sees only distinct outputs and outputs a guess no better than chance.

Step 4. Randomization does not help: the argument bounds the probability of any collision appearing, so a coin-flipping machine also fails with high probability below $2^{n/2}$ queries, giving the bounded-error lower bound $Q_{\text{classical}}=\Omega(2^{n/2})$ . Why: the obstruction is the absence of collisions in the transcript, which no internal randomness can conjure, so the exponential wall stands against all classical strategies. *At $n=40$ the birthday threshold gives $t\sim2^{20}\approx1.05\times10^6$ classical queries.*

Limiting cases

Behaviour at the edges of the promise and the resource counts:

Case	Result	Meaning
Trivial mask $s=0^n$	$f$ injective $\Rightarrow y\cdot s=0$ for all $y$	Every $y\in\{0,1\}^n$ is sampled uniformly, so the constraints span all of $\{0,1\}^n$ and force the unique solution $s=0^n$ — the algorithm correctly reports "no nontrivial period".
All-zeros outcome $y=0^n$	$0^n\cdot s=0$ for every $s$	An uninformative constraint occurring with probability $2^{-(n-1)}$ ; discard it and re-run. Its rarity is why occasional wasted rounds do not spoil the $O(n)$ scaling.
Independent samples	$\Pr[n-1\text{ independent}]\ge0.2888$	Each nonzero draw is uniform in $s^{\perp}\cong(\mathbb{Z}_2)^{n-1}$ ; a batch is fully independent with probability at least the constant $0.288$ , so $O(1)$ batches — $O(n)$ queries — succeed with overwhelming probability.
Classical lower bound	$Q_{\text{classical}}=\Omega(2^{n/2})$	A randomized classical machine gains information only on seeing a collision; the birthday bound forces $\sim2^{n/2}$ queries, establishing the exponential separation.
Quantum query count	$Q_{\text{quantum}}=O(n)$	One oracle call per run, $O(n)$ runs. The $O(n^3)$ Gaussian elimination is classical post-processing and does not enter the query separation.

Worked examples

1 · Recovering a hidden mask by hand (n = 3, fully worked)

Take $n=3$ with hidden mask $s=110$ . The oracle pairs inputs that differ by $s$ : $\{000,110\}$ , $\{001,111\}$ , $\{010,100\}$ , $\{011,101\}$ , assigning each pair a distinct output. Run the subroutine, collect samples, and solve for $s$ .

Step 1. Identify the target hyperplane. A string $y=y_1y_2y_3$ satisfies $y\cdot s=0$ when $y_1\cdot1+y_2\cdot1+y_3\cdot0=y_1\oplus y_2=0$ , i.e. $y_1=y_2$ . So $s^{\perp}=\{000,001,110,111\}$ — exactly $2^{n-1}=\mathbf{4}$ strings, matching the count in equation (5), and each is sampled with probability $2^{-(n-1)}=\mathbf{1/4}$ .

Step 2. Run the subroutine once. Suppose the output-register measurement lands on the value shared by $010$ and $100$ , leaving the input register in $\tfrac{1}{\sqrt2}(|010\rangle+|100\rangle)$ . The final Hadamard yields a $y\in\{000,001,110,111\}$ ; say we read $y_1=\mathbf{001}$ . This is one equation: $s_3=0$ .

Step 3. Run again. Say we now read $y_2=\mathbf{110}$ , the equation $s_1\oplus s_2=0$ , i.e. $s_1=s_2$ . A third run returning $000$ or a repeat of $001$ is discarded as dependent. Two independent constraints suffice for $n-1=2$ .

Step 4. Solve the system. From $s_3=0$ and $s_1=s_2$ , the nonzero solutions collapse to $s_1=s_2=1,\,s_3=0$ , giving $s=\mathbf{110}$ — the hidden mask, recovered from just two informative measurements. Had every draw been $000$ we would simply have re-run; the expected number of runs to get here is a small constant above $2$ .

2 · Sizing the exponential gap (n = 40)

A hidden-mask problem has $n=40$ . Estimate the quantum and classical query costs and the speedup factor, using $Q_{\text{quantum}}\approx n$ and $Q_{\text{classical}}\approx2^{n/2}$ .

Step 1. Quantum cost. One oracle call per run and roughly $n$ runs to gather $n-1$ independent constraints (plus a small constant for repeats) gives $Q_{\text{quantum}}\approx\mathbf{40}$ queries. Even generously padding for failed batches leaves it well under $100$ .

Step 2. Classical cost. The birthday bound gives $Q_{\text{classical}}\approx2^{n/2}=2^{20}=\mathbf{1\,048\,576}\approx1.05\times10^6$ queries — over a million evaluations of the black box just to expect a single collision.

Step 3. Speedup. The ratio is $2^{20}/40\approx\mathbf{2.6\times10^4}$ at $n=40$ alone. Double $n$ to $80$ and the classical cost squares to $2^{40}\approx1.1\times10^{12}$ while the quantum cost merely doubles to $\approx80$ — the gap is exponential, not a fixed constant, which is the entire point of Simon's result. At n = 40: about 40 quantum queries versus 1.05×10⁶ classical, a factor of ~2.6×10⁴.

Physics of the portrait

Simon's algorithm is a piece of theoretical computer science, but it earned its place in every physics-flavoured quantum course because it was the first proof that the quantum advantage is real and exponential in a setting where you can prove a matching classical lower bound — no hand-waving, no reliance on unproven complexity assumptions.

Origins · 1 minDaniel Simon and how this was discovered

Daniel Simon

active 1990s, then Microsoft Research and industry cryptography · the first provable exponential quantum–classical query separation

Daniel R. Simon devised his algorithm in 1993–1994, and its reception is part of the lore: the paper was initially rejected before appearing at the 1994 IEEE Symposium on Foundations of Computer Science. Its influence was immediate and specific. Peter Shor has repeatedly credited Simon's construction as the direct spark for his factoring algorithm: Simon showed how to reduce a hidden-period problem to Fourier sampling over an abelian group, and Shor recognized that order-finding modulo $N$ is the same maneuver transplanted from $(\mathbb{Z}_2)^n$ to $\mathbb{Z}_N$ , with the quantum Fourier transform over $\mathbb{Z}_N$ replacing the Hadamard layer and continued fractions replacing Gaussian elimination. Within months of Simon's talk, Shor had factoring and discrete logarithm. The algorithm now anchors two lineages: the pedagogical ladder Deutsch–Jozsa → Bernstein–Vazirani → Simon → Shor, and the general theory of the hidden subgroup problem, where Simon's problem is the cleanest nontrivial abelian instance. Its afterlife includes a modern twist — Simon's period-finding is the engine of quantum attacks on symmetric cryptographic constructions with a hidden XOR structure, so a 1994 toy problem now shapes how "quantum-safe" ciphers are designed.

History

1985

— Deutsch poses the first oracle problem separating quantum from deterministic classical computation

1992

— Deutsch and Jozsa give an exact quantum speedup, but randomized classical machines match it

1993

— Bernstein and Vazirani formalize quantum query complexity and a recursive super-polynomial separation

1994

— Simon presents the first provable exponential quantum–classical query separation at FOCS

1994

— Shor, directly inspired, announces polynomial-time quantum factoring and discrete logarithm

Going further

Texts. Nielsen & Chuang, Quantum Computation and Quantum Information (10th anniversary ed.), §1.4.4 and the Simon's-problem exercises · Preskill, Lecture Notes for Physics 219, Chapter 6 (Quantum Algorithms) · Watrous, The Theory of Quantum Information and his complexity lecture notes on Simon's problem · Kitaev, Shen, Vyalyi, Classical and Quantum Computation · Mermin, Quantum Computer Science, Chapter 2 · Kaye, Laflamme, Mosca, An Introduction to Quantum Computing, §6.4 · D. R. Simon, On the Power of Quantum Computation, SIAM J. Comput. 26(5):1474–1483 (1997). The sampling law (5) and the coset-state evolution follow directly from $U_f$ , $H^{\otimes n}$ , and the promise. The independence constant $\prod_{i\ge1}(1-2^{-i})=0.2887880951\ldots$ is the Euler function $\phi(1/2)$ . The query bounds are $O(n)$ versus $\Omega(2^{n/2})$ . The identity "Hadamard = QFT over $(\mathbb{Z}_2)^n$ " follows by tensoring single-qubit Hadamards. For the worked $n=3$ , $s=110$ example, $s^{\perp}=\{000,001,110,111\}$ ; at $n=40$ the classical cost is $2^{20}\approx1.05\times10^6$ queries.

Prerequisites. Quantum Parallelism and the Oracle Model · Bernstein–Vazirani Algorithm · Deutsch–Jozsa Algorithm. Leads to. Order Finding and Period Finding · Shor's Factoring Algorithm · Hidden Subgroup Problem · Quantum Fourier Transform.

Ask the tutor: Ask me to run the $n=3$ , $s=110$ example end to end — coset state, Hadamard, and the Gaussian elimination that pins down $s$ — or to show exactly how Simon's circuit morphs into Shor's order-finding.

Is Simon's algorithm the same kind of speedup as Deutsch–Jozsa or Bernstein–Vazirani?

No, and the difference is the whole point. Deutsch–Jozsa and Bernstein–Vazirani beat only deterministic classical algorithms; a randomized classical machine solves both with a couple of queries and bounded error, so their separation vanishes once you allow coin flips. Simon's problem is engineered to defeat randomized machines too: no classical strategy, however randomized, finds $s$ with fewer than about $2^{n/2}$ queries. That is why Simon's is billed as the first exponential quantum–classical separation, while the earlier two are exponential only against the weaker deterministic model.

If each run only gives one equation, how can the total cost be O(n)?

Each run costs a single oracle query and yields one random constraint $y\cdot s=0$ . You need $n-1$ independent constraints, and a fresh sample is independent of the previous ones with high probability as long as they have not yet spanned $s^{\perp}$ . The linear-algebra argument shows a batch of $n-1$ samples is fully independent with probability at least $0.288$ , a constant that does not shrink with $n$ , so a constant number of batches — hence $O(n)$ runs and queries — recovers $s$ with overwhelming probability. The exponential-looking part (a space of size $2^{n-1}$ ) is tamed because you only need a basis, and $n-1$ vectors suffice.

Why does measuring the output register help, when Deutsch–Jozsa never measures it?

Because that measurement is what creates the periodic state. In Deutsch–Jozsa the output register only supplies a phase kickback and is discarded unmeasured. In Simon's algorithm the output measurement projects the input register onto exactly the two-element coset $\{x_0,x_0\oplus s\}$ — a state invariant under the shift by $s$ . Without that projection the input register would still carry the full image structure of $f$ , and the subsequent Hadamard would not concentrate amplitude on $s^{\perp}$ . The collapse manufactures the $s$ -periodicity that the Fourier transform then reads out. It is the one design choice that distinguishes Simon's circuit from its phase-kickback predecessors.

What is the role of the all-zeros outcome y = 0?

It is a wasted run. The constraint $0^n\cdot s=0$ holds for every $s$ , so it rules out nothing and contributes no row to your system; you discard it and sample again. It occurs with probability $2^{-(n-1)}$ , so for any reasonable $n$ it is negligible, and a few such outcomes only add a small constant to the expected number of runs. It never threatens the $O(n)$ scaling — it just means the number of runs is a random variable slightly larger than $n-1$ .

How exactly does Simon's algorithm foreshadow Shor's?

They share one skeleton: hide a period in a function, query it in superposition, measure the output register to obtain a periodic coset state, Fourier-transform to sample the dual of the period, and post-process classically. Simon works over $(\mathbb{Z}_2)^n$ with period $s$ ; the transform is $H^{\otimes n}$ and the post-processing is Gaussian elimination over $\mathbb{F}_2$ . Shor's order-finding works over $\mathbb{Z}_N$ with period $r$ ; the transform is the quantum Fourier transform over $\mathbb{Z}_N$ and the post-processing is the continued-fraction algorithm. Recognizing that "find the hidden XOR mask" and "find the hidden multiplicative period" are the same abelian-group problem is the cleanest route into Shor's logic — Simon is the training-wheels version whose only simplification is that the group is a Boolean cube.

Does Simon's exponential speedup mean quantum computers beat classical ones in practice?

Not by itself. Simon's separation is relative to an oracle — it proves there exists a black box relative to which the quantum class BQP contains a problem outside BPP. That is a statement about query complexity, not about a concrete function you can download. When you replace the oracle with actual code, the separation can survive (Shor's factoring, contingent on factoring being classically hard) or evaporate (if the hidden structure is efficiently computable classically). So Simon's result is best read as an existence proof and a template: it shows exponential quantum advantage is possible and reveals the mechanism that delivers it, which is why it mattered historically even though the oracle itself is artificial.