Simon’s Algorithm

Simon’s problem hides an XOR period $s\in\mathbb F_2^n$ in a promised many-bit function and asks for the complete word $s$. A quantum value query creates a coset state; a Hadamard transform returns one random linear equation orthogonal to $s$; and repeated equations recover a candidate that two further value queries can verify.

For any fixed error below $1/2$, the quantum query complexity is $\Theta(n)$ while the matched classical query complexity is $\Theta(2^{n/2})$. This is an exponential black-box separation in the address length $n$, not a one-query algorithm, an end-to-end runtime theorem, a factoring lower bound, or a proof that BQP differs from BPP.

Required background. Quantum Oracles supplies the complete coherent interface and its construction boundary. Algorithmic Primitives supplies the access–processing–interference–readout vocabulary and multi-currency resource ledger used below.

Helpful background. The Quantum Algorithms and Complexity guide supplies the common claim record; Query Complexity fixes query and error conventions; Deutsch–Jozsa shows a neighboring Boolean decision problem; and Bernstein–Vazirani shows exact recovery of one hidden linear character.

The Hidden XOR-Period Promise

Let

$$n\ge1, \qquad G=\mathbb F_2^n, \qquad N=|G|=2^n, \qquad s\in G,$$

where addition in $G$ is bitwise XOR. Define $H_s=\{0,s\}$. The oracle is selected from the family of functions $f:G\to G$ satisfying

$$f(x)=f(x') \quad\Longleftrightarrow\quad x\mathbin\oplus x'\in H_s.$$

The biconditional is the promise. It says not merely that $s$ is a period but that there are no other collisions. The required search output is the complete word $s$; the associated decision problem asks whether $s=0^n$.

The promise includes two branches. If $s=0^n$, then $H_s=\{0\}$ and $f$ is injective. If $s\ne0^n$, the fibers are exactly the two-element cosets

$$x+H_s=\{x,x\mathbin\oplus s\},$$

so $f$ is exactly two-to-one. The mask is unique: the fiber of $f(0)$ is $H_s$, and equality of two promised functions’ collision relations would force their fibers at zero, hence their masks, to agree.

Some textbook presentations promise $s\ne0$ from the outset. That restricted problem is useful for deriving the sampling pattern, but it omits the injective branch and cannot by itself justify an injective-versus-two-to-one decision claim. This page retains the unified promise throughout.

The Ten-Field Simon Claim Record

The complete record keeps the oracle theorem separate from implementation claims and from historical interpretation.

1. Problem family and size. $\operatorname{Simon}_n$ is a search family with address length $n$ and domain size $N=2^n$; its output is one $n$-bit mask.
2. Promise and instance. A unique $s\in\mathbb F_2^n$ determines the collision relation $f(x)=f(x')$ exactly when $x\oplus x'\in\{0,s\}$. The branch $s=0$ is injective.
3. Access and encoding. One quantum query is the full $2n$-qubit XOR action $O_f|x,z\rangle=|x,z\oplus f(x)\rangle$. A matched classical query returns the complete $n$-bit value $f(x)$ at one selected address.
4. Output and use. The output is the full word $s$, which identifies the promised XOR period. It neither reconstructs the truth table nor tests an arbitrary function for the promise.
5. Success and error. $Q_E$, $Q_0$, and fixed-constant $Q_\varepsilon$ are each $\Theta(n)$; deterministic exact and fixed-constant randomized classical costs are each $\Theta(2^{n/2})$ under the conventions below.
6. Algorithmic idea. A value query entangles each address coset with one output value. Fourier sampling over $(\mathbb Z_2)^n$ cancels characters outside $H_s^\perp$ and returns random linear constraints on $s$.
7. Executable procedure. Reinitialize two registers, create a uniform address state, query $O_f$, optionally measure or discard the output, Hadamard-transform and measure the address, row-reduce retained samples, and verify a candidate with $f(0)$ and $f(t)$ under a declared stopping rule.
8. Resource ledger. Each sample uses one abstract query, $2n$ visible logical qubits plus hidden workspace, $2n$ Hadamards, and $n$ measured data bits. Sampling, verifier calls, binary elimination, memory, oracle realization, and physical costs remain separate.
9. Classical comparator. Exact difference covers and randomized birthday search use $\Theta(\sqrt N)$ matched value queries; pairwise-difference and Yao arguments give the corresponding lower bounds.
10. Evidence and limits. The query separation is a proved oracle theorem, with exact finite audits below. It is not a total-runtime or hardware result, a factoring lower bound, an unrelativized class separation, or an attack through classical-only API access.

The remaining sections prove the distribution, recovery rule, guarantee regimes, and matched lower bounds recorded here.

The Complete Many-Bit Value Oracle

Let $X$ be an $n$-qubit address register and $Z$ an $n$-qubit value register, in tensor order $X\otimes Z$. The licensed query acts on every computational-basis state as

$$O_f|x,z\rangle = |x,z\mathbin\oplus f(x)\rangle, \qquad x,z\in G.$$

This map permutes the computational basis and is therefore unitary. It is also self-inverse:

$$O_f^2|x,z\rangle = |x,z\mathbin\oplus f(x)\mathbin\oplus f(x)\rangle = |x,z\rangle.$$

Defining only $|x,0^n\rangle\mapsto|x,f(x)\rangle$ would not specify a coherent full-space operation. Conversely, knowing the complete XOR action does not reveal how $f$ is constructed, grant controlled access, or make its hidden workspace and physical realization free.

One ordinary sample executes:

1. prepare $|0^n\rangle_X|0^n\rangle_Z$;
2. apply $H^{\otimes n}$ to $X$;
3. call $O_f$ once;
4. optionally measure $Z$, or leave it unmeasured and later discard it;
5. apply $H^{\otimes n}$ to $X$; and
6. measure $X$ to obtain one word $y$.

Unlike the Boolean routines on the neighboring pages, the standard Simon kernel does not prepare a one-qubit minus state. Its interference arises from entanglement with a many-bit value register and cancellation between addresses in the same fiber. Phase kickback is therefore a useful contrast, not the operative mechanism.

Coset States from One Quantum Query

After address preparation and one value query, the joint state is

$$|\Psi_f\rangle = \frac1{\sqrt N}\sum_{x\in G}|x,f(x)\rangle.$$

For $s\ne0$, measuring $Z$ and obtaining the value $f(t)$ leaves

$$|t+H_s\rangle = \frac{|t\rangle+|t\mathbin\oplus s\rangle}{\sqrt2}$$

in the address register. The probability of each distinct oracle value is $2/N$, and the representative $t$ is irrelevant up to its coset. In the injective branch, measuring $Z$ leaves a single basis state $|t\rangle$.

The output measurement is optional. If $Z$ is ignored, the probability of measuring $y$ after the final Hadamards is

$$\begin{aligned} p(y) &= \left\langle y\middle| H^{\otimes n}\operatorname{Tr}_Z \bigl(|\Psi_f\rangle\langle\Psi_f|\bigr) H^{\otimes n} \middle|y\right\rangle\\ &= \frac1{N^2} \sum_{\substack{x,x'\\ f(x)=f(x')}} (-1)^{(x\oplus x')\cdot y}. \end{aligned}$$

Only equal-output pairs survive the partial trace. For a nonzero mask, each $x$ contributes the two differences $0$ and $s$, giving

$$p(y) = \frac1N\left[1+(-1)^{s\cdot y}\right].$$

This equals $2/N$ when $s\cdot y=0$ and zero otherwise. For $s=0$, only $x=x'$ survives, so $p(y)=1/N$ for every $y$. Measuring the value register reveals a convenient conditional coset state; it does not create the period relation or change the address marginal.

Fourier Samples in the Orthogonal Subspace

The $n$-fold Hadamard transform is the Fourier transform over the product group $(\mathbb Z_2)^n$:

$$H^{\otimes n}|x\rangle = \frac1{\sqrt N} \sum_{y\in G}(-1)^{x\cdot y}|y\rangle, \qquad x\cdot y=\bigoplus_{j=1}^n x_jy_j.$$

Applying it to a nontrivial coset state gives

$$\begin{aligned} H^{\otimes n}|t+H_s\rangle &= \frac1{\sqrt{2N}}\sum_y \left[ (-1)^{t\cdot y} +(-1)^{(t\oplus s)\cdot y} \right]|y\rangle\\ &= \frac1{\sqrt{2N}}\sum_y (-1)^{t\cdot y} \left[1+(-1)^{s\cdot y}\right]|y\rangle\\ &= \sqrt{\frac2N} \sum_{y:s\cdot y=0} (-1)^{t\cdot y}|y\rangle. \end{aligned}$$

Character cancellation removes every $y$ with $s\cdot y=1$. Define the annihilator

$$H_s^\perp = \{y\in G:y\cdot h=0\text{ for every }h\in H_s\}.$$

Both promise branches are then summarized by

$$\Pr(Y=y) = \begin{cases} |H_s|/N,&y\in H_s^\perp,\\ 0,&y\notin H_s^\perp. \end{cases}$$

For $s\ne0$, $H_s^\perp=s^\perp$ has dimension $n-1$ and contains $N/2$ words, each with probability $2/N$. For $s=0$, it is all of $G$ and each word has probability $1/N$. Each sample supplies one homogeneous binary equation $y\cdot s=0$; it does not normally determine $s$ by itself.

The transform here is not the cyclic $F_{2^n}$ circuit used in number-theoretic phase and period estimation. The distinction is structural: $(\mathbb Z_2)^n$ has binary characters implemented by independent Hadamards.

Binary Rank Recovery and Candidate Verification

Place retained samples into a binary matrix

$$M= \begin{pmatrix} y_1^{\mathsf T}\\ \vdots\\ y_m^{\mathsf T} \end{pmatrix}.$$

For a nonzero mask, every row lies in $s^\perp$. Once $\operatorname{rank}M=n-1$, the nullspace is the two-element set $\{0,t\}$ for a unique nonzero word $t$. Under the nonzero branch alone, $t=s$. Under the unified promise, the injective branch can also happen to produce a rank-$(n-1)$ matrix, so the candidate must be checked:

$$\widehat s= \begin{cases} t,&f(0^n)=f(t),\\ 0^n,&f(0^n)\ne f(t). \end{cases}$$

The biconditional promise makes this decisive. Equality for nonzero $t$ means $t=s$; inequality rules out $t$ and therefore identifies the injective branch once the sample span has codimension at most one.

If $m$ vectors are sampled independently and uniformly from a $d$-dimensional binary space, the probability of spanning it is

$$P_{d,m} = \prod_{r=0}^{d-1}\left(1-2^{r-m}\right).$$

One way to see this is to transpose the $m$ samples into a $d\times m$ matrix. Its first row must avoid the zero span, its second must avoid a one-dimensional span, and so on. The failure probability obeys

$$\begin{aligned} 1-P_{d,m} &= \Pr(\text{some independent direction is missed})\\ &\le \sum_{r=0}^{d-1}2^{r-m} = 2^{d-m}-2^{-m} <2^{d-m}. \end{aligned}$$

When the current span has rank $r<d$, a fresh sample increases the rank with probability $1-2^{r-d}$. Summing the corresponding geometric waiting times gives

$$\begin{aligned} \mathbb E T_d &= \sum_{r=0}^{d-1}\frac1{1-2^{r-d}}\\ &= d+\sum_{k=1}^{d}\frac1{2^k-1} <d+1.607. \end{aligned}$$

These are exact sampling laws. Row reduction must still be performed over $\mathbb F_2$, not over the real numbers, and a verifier call remains part of the executable algorithm.

The Injective Branch, Verification, and Exact Algorithms

Different stopping conventions support different complexity claims.

Expected stopping. Repeatedly sample until the row rank reaches $n-1$, compute the nonzero null vector, and verify it. In the nonzero branch the expected sample count is below $n+0.607$ because $d=n-1$; the two verifier calls give an always-correct expected $O(n)$-query procedure. In the injective branch, this rule also reaches rank $n-1$ in finite expected time and the verifier returns zero. It has no deterministic query cap.

Fixed-cap zero error. Take $m=n$ Fourier samples. Return zero immediately at rank $n$; at rank $n-1$, verify the unique nonzero null vector; below rank $n-1$, return ?. For a nonzero mask, the failure bound with $d=n-1$ is below $1/2$. For the injective branch, dependence among the first $n-1$ samples has probability at most

$$\sum_{r=0}^{n-2}2^{r-n} = \frac12-2^{-n},$$

so the inconclusive probability is also below $1/2$. The deterministic cap is $n+2$ value queries.

Fixed-cap bounded error. Take $m=n+1$ samples, use the same rank and verifier rules, and return zero on an unresolved lower-rank outcome. The injective branch is always correct. In the nonzero branch the failure probability is below

$$2^{(n-1)-(n+1)}=\frac14.$$

The cap is $n+3$ queries, already below the conventional $1/3$ error threshold.

Exact fixed cap. The random-rank loop is not an exact fixed-cap algorithm. Brassard and Høyer gave a separate construction that forces a new independent annihilator element, or certifies that none remains, using exact amplification; their formulation includes the trivial subgroup. Cai and Qiu later supplied another optimal exact ordinary-oracle construction for the restricted nonzero-mask problem. It must not be applied silently to the $s=0$ branch. Together with the transparent zero-error and bounded-error procedures, the applicable upper bounds are $O(n)$.

For the associated injective-versus-two-to-one decision problem, Koiran, Nesme, and Portier proved, for sufficiently large $n$,

$$T(n) \ge \frac{n+2+\log_2(2-4\varepsilon)}8 \qquad (0\le\varepsilon<1/2).$$

A full-mask search procedure also solves the decision problem. For zero error, replacing an inconclusive result of probability at most $1/2$ by an independent fair decision bit produces error at most $1/4$, so the lower bound transfers under the fixed-cap convention. Consequently, for every fixed $\varepsilon<1/2$,

$$\begin{aligned} Q_E(\operatorname{Simon}_n)&=\Theta(n)=\Theta(\log N),\\ Q_0(\operatorname{Simon}_n)&=\Theta(n)=\Theta(\log N),\\ Q_\varepsilon(\operatorname{Simon}_n)&=\Theta(n)=\Theta(\log N). \end{aligned}$$

The equality is asymptotic. The explicit $n+2$ and $n+3$ caps above belong to the transparent verifier-based procedures, not to the cited exact construction’s optimized constants.

Classical Collision Search and Lower Bounds

A classical query returns one complete value $f(x)$. Under a nonzero mask, the first observed collision identifies it:

$$f(x)=f(x'), \qquad x\ne x', \quad\Longrightarrow\quad s=x\mathbin\oplus x'.$$

An exact deterministic schedule follows from a difference cover. Write $n=a+b$ with $a=\lfloor n/2\rfloor$ and query every address in

$$A=\{(u,0^b):u\in\mathbb F_2^a\}, \qquad B=\{(0^a,v):v\in\mathbb F_2^b\}.$$

Their intersection is $\{0^n\}$. Every nonzero $s=(u,v)$ equals $(u,0^b)\oplus(0^a,v)$, so a hidden mask forces a collision among the queried addresses. No collision proves the injective branch. Hence

$$D(\operatorname{Simon}_n) \le 2^{\lfloor n/2\rfloor} +2^{\lceil n/2\rceil} -1.$$

Conversely, $q$ queried addresses determine at most $\binom q2$ nonzero pairwise XOR differences. If some nonzero word is missing, an injective transcript can be completed either as an injective oracle or as a two-to-one oracle with that hidden mask, so an exact algorithm cannot distinguish them. Therefore

$$\binom q2\ge N-1, \qquad D(\operatorname{Simon}_n) \ge \left\lceil \frac{1+\sqrt{8N-7}}2 \right\rceil.$$

Random queries give the matched bounded-error upper bound. For a fixed nonzero mask, the domain is partitioned into $N/2$ pairs. Sampling $q\le N/2$ distinct addresses without seeing both members of any pair has probability

$$p_{\mathrm{miss}}(N,q) = \frac{2^q\binom{N/2}{q}}{\binom Nq}.$$

The numerator chooses $q$ distinct pairs and one endpoint from each. Choosing $q=\Theta(\sqrt N)$ makes the miss probability a fixed constant below one; a collision returns its XOR difference, while no collision returns zero.

For a lower bound, mix a uniformly random injective oracle with equal probability against an oracle with a uniformly random nonzero mask and random distinct fiber labels. Until a collision, their distinct output transcripts can be coupled. The queried addresses expose at most $\binom q2$ candidate masks, so any deterministic decision tree has distributional success at most

$$\frac12+\frac{\binom q2}{2(N-1)}.$$

Yao’s minimax principle then gives $\Omega(\sqrt N)$ randomized query complexity for the associated decision task at every fixed error below $1/2$. Any full-mask search algorithm decides whether $s=0^n$, so the lower bound transfers to search. A randomized fixed-cap procedure at $\varepsilon=0$ cannot use random coins to evade the exact worst-case difference-cover requirement. Thus, for every fixed $0\le\varepsilon<1/2$,

$$\begin{aligned} D(\operatorname{Simon}_n)&=\Theta(2^{n/2})=\Theta(\sqrt N),\\ R_\varepsilon(\operatorname{Simon}_n) &=\Theta(2^{n/2})=\Theta(\sqrt N). \end{aligned}$$

Query Separation and Resource Boundaries

Combining the matched theorems gives

$$\Theta(n)\text{ quantum queries} \quad\text{versus}\quad \Theta(2^{n/2})\text{ classical queries}.$$

The exponential is in the address length $n=\log_2N$. Both sides receive the same complete value at a selected address; the quantum side additionally receives the promised coherent extension because coherent access is the resource being compared.

One ordinary Fourier sample uses:

• one call to $O_f$;
• $2n$ visible logical qubits plus unspecified oracle workspace;
• $n$ address Hadamards before and $n$ after the query;
• $n$ measured address bits, with output-register measurement optional;
• register reset or reinitialization before another sample; and
• storage for one additional $n$-bit row.

With $m=O(n)$ retained rows, straightforward binary elimination costs $O(n^3)$ bit operations and $O(n^2)$ memory. The verifier adds at most two value calls. Oracle construction, gate synthesis, connectivity, noise, calibration, error correction, classical control, readout latency, and wall-clock time are unspecified rather than zero.

This ledger prevents several invalid transfers. One sample does not reveal all $f(x)$ values or normally recover $s$. A compiled toy oracle can test the circuit identity while exposing the mask in its gate list, which removes the black-box premise for a classical observer. If source code or an implementation directly reveals $s$, the collision lower bound is irrelevant.

The result is a proved oracle separation and supports a qualified relativized separation. It does not prove BQP $\ne$ BPP, establish a classical lower bound for factoring, or guarantee a hardware advantage. Off-promise and noisy observations may fail to lie in one hyperplane, so a computed null vector must not be treated as a true period without a declared robustness model and verification procedure.

Two Worked Claim Audits

Four-bit coset and Fourier-support audit

Take $n=4$, $s=1011$, and, with $x_1$ the most significant bit,

$$f(x_1x_2x_3x_4) = (x_2,\ x_1\oplus x_3,\ x_1\oplus x_4,\ 0).$$

Its kernel is $\{0000,1011\}$, and exhaustive evaluation gives:

Inputs	Output
0000, 1011	0000
0001, 1010	0010
0010, 1001	0100
0011, 1000	0110
0100, 1111	1000
0101, 1110	1010
0110, 1101	1100
0111, 1100	1110

The exact Fourier support is

0000  0011  0100  0111  1001  1010  1101  1110

with probability $1/8$ on every listed word and zero elsewhere. The independent rows 0011, 0100, and 1001 have nullspace $\{0000,1011\}$.

1. Problem family and size. This is the $n=4$, $N=16$ Simon search instance.
2. Promise and instance. The displayed linear map has the unique mask $1011$ and exactly the eight promised fibers tabulated above.
3. Access and encoding. The audit assumes the complete eight-qubit XOR value oracle and evaluates its induced character sums exactly.
4. Output and use. The recovered nonzero null word is $1011$, identifying the promised period.
5. Success and error. The exhaustive support and nullspace checks are exact; no shot noise or floating-point tolerance is involved.
6. Algorithmic idea. Equal-output address pairs cancel outside $s^\perp$ and reinforce within it.
7. Executable procedure. Enumerate the truth table, group equal outputs, sum all equal-output character terms, and row-reduce the three selected samples over $\mathbb F_2$.
8. Resource ledger. One physical sample would use one abstract query, eight visible qubits, eight Hadamards, and four measured address bits; the exhaustive classical audit is a separate finite verification.
9. Classical comparator. The matched exact four-bit value-query cost is six, proved in the second audit.
10. Evidence and limits. This is exact finite mathematical evidence for one promised oracle, not an asymptotic or implementation benchmark.

Four-bit rank and collision audit

For a three-dimensional sample space, exact enumeration of all $8^m$ ordered sequences gives:

$m$	Full-rank sequences	$P_{3,m}$
3	$168/512$	$21/64$
4	$2520/4096$	$315/512$
5	$26040/32768$	$3255/4096$

The expected spanning time is

$$\mathbb E T_3 = \frac87+\frac43+2 = \frac{94}{21}.$$

For $q=4,5,6$ uniformly selected distinct addresses at $N=16$,

$$p_{\mathrm{miss}}(16,4)=\frac8{13}, \qquad p_{\mathrm{miss}}(16,5)=\frac{16}{39}, \qquad p_{\mathrm{miss}}(16,6)=\frac{32}{143}.$$

The six-query collision probability is therefore $111/143>2/3$. Exact recovery needs six queries as well: the pair-count lower bound gives $\binom q2\ge15$, and

$$C=\{0000,1000,0100,0010,0001,1111\}$$

has every nonzero four-bit word among its fifteen pairwise XOR differences. Thus $D(\operatorname{Simon}_4)=6$. For $s=1011$, the cover contains the colliding pair 0100 and 1111.

1. Problem family and size. The rank experiment uses $d=3$, while the birthday and difference-cover calculations use the $n=4$, $N=16$ Simon family.
2. Promise and instance. Rank samples are uniform on a promised three-dimensional annihilator; collision calculations compare the injective branch with any nonzero hidden mask.
3. Access and encoding. Quantum rows come from complete XOR-oracle calls; classical addresses receive complete four-bit values under matched access.
4. Output and use. Full rank licenses one candidate null direction, while a collision licenses the XOR mask; the exact cover also certifies zero after no collision.
5. Success and error. Rank and miss probabilities are exact rational values. Six random queries collide with probability $111/143$, whereas the six-address cover is exact.
6. Algorithmic idea. Quantum recovery accumulates independent orthogonality equations; classical recovery waits for, or guarantees, one repeated fiber label.
7. Executable procedure. Enumerate ordered rank sequences, evaluate the closed-form miss fraction, enumerate all pairwise cover differences, and compare with the lower bound.
8. Resource ledger. The table counts retained Fourier samples or distinct classical value calls; elimination, storage, oracle realization, and physical costs remain separate.
9. Classical comparator. The exact finite value is six, and the random-query success at the same cap is $111/143$ on nonzero instances.
10. Evidence and limits. These exhaustive finite checks support the formulas but do not replace the asymptotic lower-bound theorems.

The following exact-integer JavaScript reproduces both audits. It performs no random sampling.

const assert = (condition, message) => {
  if (!condition) throw new Error(message);
};
const parity = x => {
  let p = 0;
  for (; x; x >>= 1) p ^= x & 1;
  return p;
};
const word = (x, width = 4) => x.toString(2).padStart(width, "0");
const simon4 = x => {
  const x1 = (x >> 3) & 1;
  const x2 = (x >> 2) & 1;
  const x3 = (x >> 1) & 1;
  const x4 = x & 1;
  return (x2 << 3) | ((x1 ^ x3) << 2) | ((x1 ^ x4) << 1);
};

const fibers = new Map();
for (let x = 0; x < 16; x++) {
  const value = simon4(x);
  if (!fibers.has(value)) fibers.set(value, []);
  fibers.get(value).push(x);
}
const pairs = [...fibers.entries()]
  .sort((a, b) => a[0] - b[0])
  .map(([value, xs]) => [xs.map(x => word(x)), word(value)]);
const expectedPairs = [
  [["0000", "1011"], "0000"],
  [["0001", "1010"], "0010"],
  [["0010", "1001"], "0100"],
  [["0011", "1000"], "0110"],
  [["0100", "1111"], "1000"],
  [["0101", "1110"], "1010"],
  [["0110", "1101"], "1100"],
  [["0111", "1100"], "1110"]
];
assert(JSON.stringify(pairs) === JSON.stringify(expectedPairs), "wrong fibers or outputs");
assert(pairs.length === 8, "wrong fiber count");
assert(pairs.every(([xs]) => xs.length === 2), "fiber is not a pair");
assert(pairs.every(([xs]) =>
  (parseInt(xs[0], 2) ^ parseInt(xs[1], 2)) === 0b1011
), "wrong hidden difference");

const characterSums = [];
for (let y = 0; y < 16; y++) {
  let sum = 0;
  for (let x = 0; x < 16; x++) {
    for (let xp = 0; xp < 16; xp++) {
      if (simon4(x) === simon4(xp)) {
        sum += parity((x ^ xp) & y) ? -1 : 1;
      }
    }
  }
  characterSums.push(sum);
}
const support = characterSums
  .map((sum, y) => [sum, y])
  .filter(([sum]) => sum !== 0)
  .map(([, y]) => word(y));
assert(
  support.join(" ") === "0000 0011 0100 0111 1001 1010 1101 1110",
  "wrong Fourier support"
);
assert(characterSums.every(sum => sum === 0 || sum === 32), "wrong character sum");

const selectedRows = [0b0011, 0b0100, 0b1001];
const nullspace = [...Array(16).keys()]
  .filter(t => selectedRows.every(y => parity(y & t) === 0))
  .map(t => word(t));
assert(nullspace.join(" ") === "0000 1011", "wrong nullspace");

const gf2Rank = (rows, width) => {
  const a = rows.slice();
  let rank = 0;
  for (let bit = width - 1; bit >= 0; bit--) {
    const pivot = a.findIndex((row, i) => i >= rank && ((row >> bit) & 1));
    if (pivot < 0) continue;
    [a[rank], a[pivot]] = [a[pivot], a[rank]];
    for (let i = 0; i < a.length; i++) {
      if (i !== rank && ((a[i] >> bit) & 1)) a[i] ^= a[rank];
    }
    rank++;
  }
  return rank;
};
const fullRankCount = m => {
  let count = 0;
  for (let code = 0; code < 8 ** m; code++) {
    let rest = code;
    const rows = [];
    for (let i = 0; i < m; i++) {
      rows.push(rest % 8);
      rest = Math.floor(rest / 8);
    }
    if (gf2Rank(rows, 3) === 3) count++;
  }
  return [count, 8 ** m];
};
const rankCounts = [3, 4, 5].map(fullRankCount);
assert(
  JSON.stringify(rankCounts) === JSON.stringify([[168, 512], [2520, 4096], [26040, 32768]]),
  "wrong rank counts"
);
assert(8 * 3 + 4 * 7 + 2 * 21 === 94, "wrong expected spanning time");

const choose = (n, k) => {
  let value = 1;
  for (let j = 1; j <= k; j++) value = value * (n - k + j) / j;
  return value;
};
const gcd = (a, b) => b ? gcd(b, a % b) : a;
const reducedMiss = q => {
  const numerator = 2 ** q * choose(8, q);
  const denominator = choose(16, q);
  const divisor = gcd(numerator, denominator);
  return [numerator / divisor, denominator / divisor];
};
const missFractions = [4, 5, 6].map(reducedMiss);
assert(
  JSON.stringify(missFractions) === JSON.stringify([[8, 13], [16, 39], [32, 143]]),
  "wrong birthday fractions"
);
assert(111 * 3 > 143 * 2, "six-query collision probability is not above two thirds");

const cover = [0b0000, 0b1000, 0b0100, 0b0010, 0b0001, 0b1111];
const differences = new Set();
for (let i = 0; i < cover.length; i++) {
  for (let j = i + 1; j < cover.length; j++) differences.add(cover[i] ^ cover[j]);
}
assert(differences.size === 15 && !differences.has(0), "not a difference cover");
assert((0b0100 ^ 0b1111) === 0b1011, "missing concrete collision");

console.log({ pairs, support, nullspace, rankCounts, missFractions, differences: differences.size });

Hidden Subgroups, History, and Canonical Ownership

Simon introduced the problem in 1994 and gave its journal treatment in 1997. It provided an early exponential separation between quantum and bounded-error randomized classical query complexity for a black-box problem and helped expose a general pattern: prepare superpositions of cosets, Fourier-sample characters trivial on the hidden subgroup, and recover the subgroup from classical constraints. Jozsa later emphasized the common Fourier viewpoint.

Here the group is $(\mathbb Z_2)^n$ and the hidden subgroup is $H_s=\{0,s\}$. The independent Hadamards implement its group Fourier transform. The Quantum Fourier Transform page owns the cyclic transform conventions used by phase and order finding; the two transforms must not be identified merely because both are called Fourier transforms.

Shor’s Algorithm owns the number-theoretic reductions, cyclic period finding, rational reconstruction, verification, and complexity qualifications for factoring and discrete logarithms. Simon’s algorithm is a conceptual predecessor, not a proof of Shor’s correctness or of a classical factoring lower bound.

Quantum Complexity Classes owns the relativization interpretation and the distinction between an oracle separation and BQP versus BPP. Classical Information Review owns general matched data and total-cost comparisons; Claims, Hype, and Evidence Standards owns evidence-language calibration; and Circuit Model owns general register and measurement semantics.

Brassard–Høyer own the unified exact construction, while Cai–Qiu own a specialist exact construction for the restricted nonzero-mask formulation. Koiran–Nesme–Portier own the linear quantum lower bound, while Nayak gives a modern deterministic hidden-subgroup treatment. This page assembles those results only to state Simon’s matched query theorem.

Any proposed application must supply the same coherent map $O_f$ used by the theorem. An ordinary remote classical API supplies classical value queries, not that coherent interface, so the oracle result alone does not license a quantum-query conclusion in that setting.

Common Simon-Algorithm Failures

Silently excluding the injective branch. The common nonzero-mask derivation is not the unified search problem. State whether $s=0$ is allowed and include candidate verification when it is.

Calling one sample the algorithm. One oracle call normally returns one random equation $y\cdot s=0$. Recovery requires repeated samples, binary elimination, and verification under a declared stopping rule.

Treating output measurement as the source of the speedup. Measuring the value register is optional. Tracing it out gives the same address distribution because the promise already fixes the equal-output coherences.

Replacing the value oracle with Boolean phase kickback. Simon’s standard kernel uses an $n$-bit value register and coset entanglement. A minus-state Boolean target is the mechanism on different neighboring pages.

Calling expected stopping exact fixed-cap complexity. An always-correct random loop can have an unbounded tail. The exact $O(n)$ theorem uses a separate construction; the transparent fixed-cap routine is zero-error with ?.

Comparing with generic collision finding. The XOR-period promise constrains every collision and makes one collision identify the mask. Bounds for arbitrary collision problems do not transfer without preserving that structure.

Turning a query theorem into a runtime or class theorem. Coherent oracle construction, gates, data movement, noise, and classical processing remain outside the query count. The result is a relativized black-box separation, not a proof that BQP differs from BPP.

Ignoring off-promise or noisy samples. A collection of rows need not share one codimension-one nullspace away from the ideal promise. A candidate null vector is not evidence of a physical or cryptographic period without a declared noise model and verifier.

Exercises

Exercise 1 — Uniqueness and the two promise branches

Prove that the mask $s$ is unique. Then derive the injective branch for $s=0$ and the exact two-to-one coset structure for $s\ne0$.

Solution

The fiber of $f(0)$ is

$$\{x:f(x)=f(0)\} = \{x:x\oplus0\in\{0,s\}\} = \{0,s\}.$$

If the same collision relation had masks $s$ and $t$, these fibers would obey $\{0,s\}=\{0,t\}$, hence $s=t$. When $s=0$, equality of outputs implies $x\oplus x'=0$ and therefore $x=x'$, so $f$ is injective. When $s\ne0$, each $x$ shares its value exactly with $x\oplus s$, and the two addresses are distinct. The fibers are therefore the two-element cosets of $\{0,s\}$.

Exercise 2 — Full-space action and optional measurement

Show that $O_f$ is unitary on the whole computational basis. Starting from $|\Psi_f\rangle$, derive the address distribution without measuring the value register and compare it with the conditional-coset derivation.

Solution

For each fixed $x$, the map $z\mapsto z\oplus f(x)$ is a permutation and its own inverse. The full basis map is therefore a permutation, so $O_f$ is unitary and $O_f^\dagger=O_f$.

Tracing out $Z$ gives

$$\rho_X = \frac1N \sum_{\substack{x,x'\\f(x)=f(x')}}|x\rangle\langle x'|.$$

After $H^{\otimes n}$,

$$p(y) = \frac1{N^2} \sum_{\substack{x,x'\\f(x)=f(x')}} (-1)^{(x\oplus x')\cdot y}.$$

For $s\ne0$, each $x$ has equal-output partners $x$ and $x\oplus s$, so $p(y)=N^{-1}[1+(-1)^{s\cdot y}]$. This is $2/N$ on $s^\perp$ and zero elsewhere, exactly the distribution obtained by first conditioning on any coset state. For $s=0$, only diagonal pairs remain and $p(y)=1/N$.

Exercise 3 — Character cancellation

Derive the Hadamard transform of $|t+H_s\rangle$ and prove that the result is uniform on $H_s^\perp$. Include the $s=0$ branch.

Solution

For $s\ne0$,

$$\begin{aligned} H^{\otimes n}|t+H_s\rangle &= \frac1{\sqrt{2N}}\sum_y (-1)^{t\cdot y} \left[1+(-1)^{s\cdot y}\right]|y\rangle\\ &= \sqrt{\frac2N} \sum_{y:s\cdot y=0} (-1)^{t\cdot y}|y\rangle. \end{aligned}$$

There are $N/2$ supported words and every squared amplitude is $2/N$, so the distribution is normalized and uniform. If $s=0$, a measured output selects one basis state $|t\rangle$ because $f$ is injective. Its Hadamard transform has amplitude magnitude $1/\sqrt N$ at every $y$, which is the same rule with $H_0^\perp=G$ and $|H_0|=1$.

Exercise 4 — The complete four-bit audit

For the displayed $n=4$ function, reproduce all fibers, the eight-point Fourier support, and the nullspace of rows 0011, 0100, and 1001.

Solution

Evaluating the four output coordinates gives the eight pairs in the first audit, each separated by

$$1011.$$

The equal-output character sum is

$$\sum_{\substack{x,x'\\f(x)=f(x')}} (-1)^{(x\oplus x')\cdot y} = 16\left[1+(-1)^{1011\cdot y}\right],$$

so it is $32$ on words orthogonal to 1011 and zero otherwise. Dividing by $N^2=256$ gives probability $1/8$ on

0000  0011  0100  0111  1001  1010  1101  1110

The three chosen equations are independent. Solving them over $\mathbb F_2$ leaves one free bit and gives precisely $t=0000$ or $t=1011$.

Exercise 5 — Rank probability and expected stopping

Derive $P_{d,m}$, its failure bound, and $\mathbb E T_d$. Evaluate the three probabilities and the expected time for $d=3$, then identify how the kernel and rank language transfers to its Mathematical Toolkit owner.

Solution

A $d\times m$ binary matrix has full row rank when its ordered rows successively avoid spans of sizes $1,2,\ldots,2^{d-1}$. Out of $2^m$ possible rows at each step,

$$P_{d,m} = \prod_{r=0}^{d-1}\frac{2^m-2^r}{2^m} = \prod_{r=0}^{d-1}(1-2^{r-m}).$$

A union bound over the failed independence steps gives

$$1-P_{d,m} \le \sum_{r=0}^{d-1}2^{r-m} <2^{d-m}.$$

At rank $r$, the probability of increasing rank is $1-2^{r-d}$, so

$$\mathbb E T_d = \sum_{r=0}^{d-1}\frac1{1-2^{r-d}} = d+\sum_{k=1}^d\frac1{2^k-1}.$$

For $d=3$, the products give $21/64$, $315/512$, and $3255/4096$ at $m=3,4,5$, while

$$\mathbb E T_3 = \frac87+\frac43+2 = \frac{94}{21}.$$

This is the finite-field instance of the kernel, image, rank, and rank–nullity language developed in Mathematical Toolkit Linear Maps. The present exercise specializes that structure to row reduction over $\mathbb F_2$.

Exercise 6 — The birthday comparator

Derive the exact no-collision probability for $q$ distinct random addresses and explain why it gives an $O(\sqrt N)$ bounded-error algorithm.

Solution

For fixed nonzero $s$, the $N$ addresses form $N/2$ disjoint pairs. A collision-free $q$-subset chooses $q$ of those pairs and one of two endpoints in each, so the number of favorable subsets is $2^q\binom{N/2}{q}$. Dividing by all $\binom Nq$ subsets gives

$$p_{\mathrm{miss}}(N,q) = \frac{2^q\binom{N/2}{q}}{\binom Nq}.$$

Equivalently,

$$p_{\mathrm{miss}}(N,q) = \prod_{j=0}^{q-1}\frac{N-2j}{N-j}.$$

For $q=c\sqrt N$, its logarithm is bounded above by

$$-\sum_{j=0}^{q-1}\frac{j}{N-j} = -\Theta(c^2),$$

so a sufficiently large constant $c$ makes the miss probability at most any fixed error. A collision reveals $s$; without one the procedure returns zero.

Exercise 7 — Deterministic lower and upper bounds

Prove the pairwise-difference lower bound and split-subspace upper bound. Then establish $D(\operatorname{Simon}_4)=6$.

Solution

With $q$ queried addresses, at most $\binom q2$ nonzero XOR differences have been exposed. If this is less than $N-1$, some nonzero $s$ is absent, and a collision-free transcript is compatible with both an injective oracle and a promised oracle having mask $s$. Thus

$$\binom q2\ge N-1.$$

For the upper bound, query

$$A=\mathbb F_2^{\lfloor n/2\rfloor}\times\{0\}, \qquad B=\{0\}\times\mathbb F_2^{\lceil n/2\rceil}.$$

Every $s=(u,v)$ is the difference of $(u,0)\in A$ and $(0,v)\in B$, and the union has $2^{\lfloor n/2\rfloor}+2^{\lceil n/2\rceil}-1$ elements.

At $n=4$, the lower bound requires $\binom q2\ge15$, hence $q\ge6$. The set

$$\{0000,1000,0100,0010,0001,1111\}$$

has six elements and fifteen distinct nonzero pairwise XOR differences, so it attains the bound. Therefore $D(\operatorname{Simon}_4)=6$.

Exercise 8 — Repair an exponential-speedup overclaim

Repair the statement “Simon’s one-query circuit proves an exponential runtime speedup and explains factoring.” Give a complete claim record and resource boundary.

Solution

1. Problem family and size. The claim concerns $\operatorname{Simon}_n$ with address length $n$ and domain size $N=2^n$.
2. Promise and instance. The many-bit function is promised injective or exactly two-to-one with one unique XOR mask; the algorithm does not test arbitrary functions.
3. Access and encoding. Quantum access is the complete coherent XOR oracle, while the comparator receives matched classical value queries. Oracle construction is not free.
4. Output and use. The procedure must return the full mask $s$, not one Fourier sample or a truth table.
5. Success and error. For fixed error below $1/2$, $Q_E$, $Q_0$, and $Q_\varepsilon$ are each $\Theta(n)$; $D$ and $R_\varepsilon$ are each $\Theta(2^{n/2})$ under their stated conventions.
6. Algorithmic idea. Each value query creates coset coherence, and a Hadamard transform returns one random equation in $s^\perp$.
7. Executable procedure. Repeat the sampling kernel, row-reduce over $\mathbb F_2$, verify a candidate with two value calls, and use the stopping rule appropriate to the claimed guarantee.
8. Resource ledger. Count all $O(n)$ oracle calls, $2n$ visible qubits plus hidden workspace, Hadamards, resets, measurements, $O(n^3)$ straightforward elimination work, $O(n^2)$ memory, and excluded implementation costs separately.
9. Classical comparator. Difference-cover and birthday algorithms use $\Theta(\sqrt N)$ value queries, with matching difference-count and Yao lower bounds.
10. Evidence and limits. The result is an exponential oracle-query separation in $n$. It is not a one-query or runtime theorem, does not prove BQP $\ne$ BPP, and only supplies historical and structural context for Shor’s distinct number-theoretic algorithm.

A defensible replacement is: “Under the promised coherent value-oracle model, Simon’s problem has $\Theta(n)$ quantum and $\Theta(2^{n/2})$ classical query complexity for fixed error below $1/2$. This oracle separation helped motivate later Fourier-sampling algorithms, but it does not establish their classical lower bounds or implementation performance.”

References

• G. Brassard and P. Høyer, “An Exact Quantum Polynomial-Time Algorithm for Simon’s Problem,” Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems, 12–23 (1997), doi:10.1109/ISTCS.1997.595153.
• G. Cai and D. Qiu, “Optimal Separation in Exact Query Complexities for Simon’s Problem,” Journal of Computer and System Sciences 97, 83–93 (2018), doi:10.1016/j.jcss.2018.05.001.
• A. M. Childs and W. van Dam, “Quantum Algorithms for Algebraic Problems,” Reviews of Modern Physics 82, 1–52 (2010), doi:10.1103/RevModPhys.82.1.
• R. Jozsa, “Quantum Algorithms and the Fourier Transform,” Proceedings of the Royal Society A 454, 323–337 (1998), doi:10.1098/rspa.1998.0163.
• P. Koiran, V. Nesme, and N. Portier, “A Quantum Lower Bound for the Query Complexity of Simon’s Problem,” Automata, Languages and Programming, LNCS 3580, 1287–1298 (2005), doi:10.1007/11523468_104.
• A. Nayak, “Deterministic Algorithms for the Hidden Subgroup Problem,” Quantum Information and Computation 22, 755–769 (2022), doi:10.26421/QIC22.9-10-3.
• M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th Anniversary Edition, Cambridge University Press (2010), doi:10.1017/CBO9780511976667.
• P. W. Shor, “Algorithms for Quantum Computation: Discrete Logarithms and Factoring,” Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 124–134 (1994), doi:10.1109/SFCS.1994.365700.
• D. R. Simon, “On the Power of Quantum Computation,” Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 116–123 (1994), doi:10.1109/SFCS.1994.365701.
• D. R. Simon, “On the Power of Quantum Computation,” SIAM Journal on Computing 26, 1474–1483 (1997), doi:10.1137/S0097539796298637.