Part IV. Protocols and Algorithms · Chapter 29

Simon and Hidden Structure

Simon's problem is the bridge between the toy oracles and Shor: a hidden string, a promise about collisions, and a quantum sampler that hands classical algebra exactly the equations it needs.

Steven GellerPublished July 25, 2026Revised August 14, 2026

Lab

In this chapter 8 sections

Reader question. How does Simon's algorithm turn a two-to-one XOR-period promise into linear equations for a hidden string?

The oracle creates paired inputs x and x⊕s with equal outputs; after discarding or measuring the output register and applying Hadamards, samples y satisfy y·s=0 mod 2, so repeated independent samples and classical Gaussian elimination recover s.

Scope and non-goals.

This chapter does not claim an advantage without Simon's exact promise or ignore oracle construction.
It does not substitute one lucky sample for the rank required to recover the hidden string.

Figure 29.1. Notice the division of labor: every run returns one equation about the hidden string, never the string itself. The exponential gap comes from how cheap each equation is to sample; classically, finding even one useful collision costs about

2^{n/2}

queries.

The collision promise

State f(x)=f(x⊕s) and the two-to-one boundary.

Simon's problem hands you a black-box function on $n$ -bit strings with a strict promise: there is a hidden nonzero string $s$ such that

f ( x ) = f ( y ) exactly when y = x ⊕ s

Every output value appears exactly twice, on input pairs separated by $s$ . The task is to recover $s$ . Classically, the only way in is to query inputs and hope for a collision, and the birthday bound says a collision costs on the order of $2^{n/2}$ queries; exponential. Quantumly, about $n$ runs suffice. That is the first clean exponential oracle separation in the standard story, and it is the conceptual ancestor of factoring.

Evidence boundary. Simon's problem has a hidden XOR-period promise yielding an exponential quantum query separation. [Daniel R. Simon] [Ethan Bernstein]

One query creates paired branches

Trace registers through oracle and output measurement.

One run of Simon's circuit prepares a superposition over inputs, evaluates $f$ into an output register, and interferes the inputs. Measuring then returns a uniformly random string $y$ satisfying:

y ⋅ s = 0 ( mod 2 )

Read that carefully: the measurement tells you one equation that $s$ obeys, and nothing else directly. But each run is cheap, the equations are independent with good probability, and after roughly $n − 1$ of them, classical linear algebra pins down $s$ uniquely. Bernstein–Vazirani put the hidden string into phase and read it in one shot; Simon trades that single-shot elegance for a sampling loop plus a classical solver. The trade is the template.

Phase kickback remains the underlying habit; the oracle writes function structure into amplitudes; even though Simon is usually presented with an explicit output register rather than a $\lvert-\rangle$ target. The moral generalizes: structure gets encoded in amplitudes, and interference plus measurement exposes constraints on it.

Evidence boundary. Fourier sampling produces bit strings orthogonal to the hidden period over GF(2). [Michael A. Nielsen] [John Preskill]

Hadamards erase incompatible frequencies

Derive the condition y·s=0.

Evidence boundary. Classical post-processing uses linear algebra over GF(2) and needs enough independent samples. [John Watrous] [Daniel R. Simon]

Bit vectors over GF(2); dot product and XOR explicitly mod 2; matrix rank over GF(2), not real numbers.

Resource account: rank, not shot count, ends sampling

Collect independent equations over GF(2).

Small-instance query, sample, and classical-solver account
Resource	Account	Stopping condition
Oracle queries	One per circuit run	Continue until the sampled equation matrix reaches rank `n-1`.
Measurements	`n` output bits per run	Discard dependent rows; do not count raw shots as information.
Quantum gates	`2n` Hadamards plus one promised oracle implementation per run	Oracle gates remain outside black-box query complexity.
Classical work	Incremental GF(2) elimination, polynomial in `n`	Verify the nonzero nullspace vector with fresh oracle pairs.

Simon's problem is a lesson in problem representation. The same function with no promise is a haystack; the promised collision structure turns it into a system of equations waiting to be sampled. When you audit any algorithm in this family, ask:

What hidden structure is promised, and who guarantees it?
What does one query produce, concretely?
What distribution do the measurements sample from?
What classical processing consumes the samples?
What does the best classical algorithm do with the same oracle access?

These five questions transfer unchanged to period finding, to hidden-subgroup methods, and to a surprising number of application claims.

Recover s and verify the promise

Perform binary elimination and an oracle check.

Each measurement supplies y with y dot s=0 over GF(2). Row-reduce until the sample matrix has rank n-1; its nonzero nullspace vector is the candidate s. Rank deficiency means collect another sample, not guess. Even full rank validates only the equations: query the supplied function on test pairs x and x xor s to confirm the collision promise before accepting the recovered mask.

Simon sampler and GF(2) solver

Acceptance contract for Simon sampler and GF(2) solver
Field	Reader-visible record
Format	Small-n oracle simulator, sample log, and binary elimination library
Verification	Tests every nonzero s for n≤5, validates all sampled orthogonality equations, requires rank n−1, and verifies recovered collisions.
Availability	Source-embedded acceptance record; no separate download is claimed

{
  "artifact": "Simon sampler and GF(2) solver",
  "format": "Small-n oracle simulator, sample log, and binary elimination library",
  "acceptance_test": "Tests every nonzero s for n≤5, validates all sampled orthogonality equations, requires rank n−1, and verifies recovered collisions.",
  "publication_state": "source-embedded contract and worked fixture"
}

Executable reference fixture

Run with Python 3.11 or later. The final assertion is the chapter-level pass condition for this small instance.

import math
import random

def dot2(left, right):
    return (left & right).bit_count() & 1

def promised_oracle(secret):
    return lambda x: min(x, x ^ secret)

def promise_holds(function, secret, input_qubits):
    outputs = {}
    for x in range(1 << input_qubits):
        value = function(x)
        if value in outputs and outputs[value] != (x ^ secret):
            return False
        outputs[value] = x
        if function(x ^ secret) != value:
            return False
    return len(outputs) == 1 << (input_qubits - 1)

def h(state, qubit, count):
    mask = 1 << (count - 1 - qubit)
    output = state[:]
    scale = math.sqrt(0.5)
    for basis in range(len(state)):
        if basis & mask == 0:
            paired = basis | mask
            output[basis] = (state[basis] + state[paired]) * scale
            output[paired] = (state[basis] - state[paired]) * scale
    return output

def simon_distribution(function, input_qubits):
    total = 2 * input_qubits
    state = [0j] * (1 << total)
    state[0] = 1.0
    for qubit in range(input_qubits):
        state = h(state, qubit, total)
    queried = [0j] * len(state)
    output_mask = (1 << input_qubits) - 1
    for basis, amplitude in enumerate(state):
        x = basis >> input_qubits
        output = basis & output_mask
        queried[(x << input_qubits) | (output ^ function(x))] += amplitude
    state = queried
    for qubit in range(input_qubits):
        state = h(state, qubit, total)
    probabilities = [0.0] * (1 << input_qubits)
    for basis, amplitude in enumerate(state):
        probabilities[basis >> input_qubits] += abs(amplitude) ** 2
    return probabilities

def rref(rows, input_qubits):
    reduced = [row for row in rows if row]
    pivots = []
    pivot_row = 0
    for column in range(input_qubits):
        bit = 1 << (input_qubits - 1 - column)
        found = next((index for index in range(pivot_row, len(reduced)) if reduced[index] & bit), None)
        if found is None:
            continue
        reduced[pivot_row], reduced[found] = reduced[found], reduced[pivot_row]
        for index in range(len(reduced)):
            if index != pivot_row and reduced[index] & bit:
                reduced[index] ^= reduced[pivot_row]
        pivots.append(column)
        pivot_row += 1
        if pivot_row == len(reduced):
            break
    return reduced[:pivot_row], pivots

def recover(rows, input_qubits):
    reduced, pivots = rref(rows, input_qubits)
    if len(pivots) != input_qubits - 1:
        raise ValueError("collect samples until GF(2) rank is n-1")
    free_columns = [column for column in range(input_qubits) if column not in pivots]
    if len(free_columns) != 1:
        raise ValueError("expected a one-dimensional nullspace")
    candidate = 1 << (input_qubits - 1 - free_columns[0])
    for row, column in reversed(list(zip(reduced, pivots))):
        pivot_bit = 1 << (input_qubits - 1 - column)
        if dot2(row ^ pivot_bit, candidate):
            candidate |= pivot_bit
    if candidate == 0 or any(dot2(row, candidate) for row in rows):
        raise ValueError("invalid nullspace recovery")
    return candidate

def validate_samples(rows, secret):
    if any(dot2(row, secret) for row in rows):
        raise ValueError("sample violates y dot s = 0")

tested = 0
largest_sample_log = 0
for input_qubits in range(1, 6):
    for secret in range(1, 1 << input_qubits):
        function = promised_oracle(secret)
        assert promise_holds(function, secret, input_qubits)
        probabilities = simon_distribution(function, input_qubits)
        support = [y for y, probability in enumerate(probabilities) if probability > 1e-12]
        expected_support = [y for y in range(1 << input_qubits) if dot2(y, secret) == 0]
        assert support == expected_support
        expected_probability = 1 / (1 << (input_qubits - 1))
        assert all(abs(probabilities[y] - expected_probability) < 1e-12 for y in support)
        assert all(probabilities[y] < 1e-12 for y in range(len(probabilities)) if y not in support)

        rng = random.Random(29000 + 101 * input_qubits + secret)
        rows = []
        while len(rref(rows, input_qubits)[1]) < input_qubits - 1:
            rows.append(rng.choice(support))
            if len(rows) > 200:
                raise AssertionError("seeded sampling failed to reach rank")
        validate_samples(rows, secret)
        recovered = recover(rows, input_qubits)
        assert recovered == secret
        assert all(function(x) == function(x ^ recovered) for x in range(1 << input_qubits))
        largest_sample_log = max(largest_sample_log, len(rows))
        tested += 1

insufficient_rejected = False
try:
    recover([0b0100], 4)
except ValueError:
    insufficient_rejected = True
assert insufficient_rejected

invalid_sample_rejected = False
try:
    validate_samples([0b0001], 0b1011)
except ValueError:
    invalid_sample_rejected = True
assert invalid_sample_rejected

good = promised_oracle(0b1011)
bad = lambda x: 0b1111 if x == 0 else good(x)
assert promise_holds(good, 0b1011, 4)
assert not promise_holds(bad, 0b1011, 4)
bad_probabilities = simon_distribution(bad, 4)
assert any(bad_probabilities[y] > 1e-12 and dot2(y, 0b1011) for y in range(16))
print(f"PASS: 29 Simon recovered={tested} max_samples={largest_sample_log} bad_forbidden_mass={sum(bad_probabilities[y] for y in range(16) if dot2(y, 0b1011)):.6f}")

Scope boundary

This chapter does not claim an advantage without Simon's exact promise or ignore oracle construction.
It does not substitute one lucky sample for the rank required to recover the hidden string.

Depth commitment. One promise, one quantum state derivation, one sample-rank analysis, and one solver.

Practice problem

For n=4 and hidden s=1010, reduce a supplied sample set over GF(2), identify whether rank is sufficient, and recover/verify s.

hidden candidate length n=4
sample rows y: 0100, 0001, 1010
Solve y dot s = 0 over GF(2), exclude s=0000, then verify f(x)=f(x xor s).

Deliverable: Row-reduction transcript, rank, nullspace vector, and two oracle collision checks.
Pass condition: The GF(2) solver reproduces the row operations and rejects any sample not orthogonal to 1010.

Verification record

Expected solution form. Binary Gaussian-elimination solution plus property-based oracle tests.

Model answer. The supplied rows have rank three. Their GF(2) nullspace is {0000,1010}; excluding zero yields s=1010. Every row has y dot s=0, and direct evaluation must still confirm f(x)=f(x xor 1010) on the supplied oracle fixture.

Model result and check. CI checks rank/nullspace, recovered period, and every supplied equation.

Acceptance test. The GF(2) solver reproduces the row operations and rejects any sample not orthogonal to 1010.

Companion work

Artifacts for this chapter

These entries resolve to checked-in local source. Commands are reproduced exactly from the chapter manifest, and source-embedded fixtures are exported as direct downloads.

algorithm fixture
Simon sampler and GF(2) solver
Download fixture (.py)Verification record (.json)
Reproduce or test
python3 tools/validate_briefs.py --briefs data/editorial_briefs_00_35.json --from 0 --through 35 --check-rewritten-sources --execute-artifacts

Provenance

Sources and review

The load-bearing claims in the chapter are mapped inline to this registered source set. A citation supports only the bounded claim beside it.

External review: Open.

How review works Revision history Report or inspect errata

Book contents

Part IV. Protocols and Algorithms

Simon and Hidden Structure

The collision promise

One query creates paired branches

Hadamards erase incompatible frequencies

Resource account: rank, not shot count, ends sampling

Recover s and verify the promise

Simon sampler and GF(2) solver

Artifacts for this chapter

Simon sampler and GF(2) solver

Sources and review

Cite this chapter

The collision promise#

One query creates paired branches#

Hadamards erase incompatible frequencies#

Resource account: rank, not shot count, ends sampling#

Recover s and verify the promise#

Simon sampler and GF(2) solver#

Artifacts for this chapter

Simon sampler and GF(2) solver

Sources and review

Prerequisites for this chapter

Next concepts from this chapter

The collision promise

One query creates paired branches

Hadamards erase incompatible frequencies

Resource account: rank, not shot count, ends sampling

Recover s and verify the promise

Simon sampler and GF(2) solver