Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Simon’s Algorithm and Finite-Field Recovery — Examples

1 · Prerequisites

2 · Summary

The companion computes the zero-query $n = 1$ boundary and an explicit $n = 2$ oracle with hidden mask $11$ . It writes both conditional coset states, verifies the uniform rows $00$ and $11$ , computes the exact rank-rise probability and performs the row reduction by hand. A four-sample cap at $δ = 1 / 2$ has exact failure probability $1 / 16$ .

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Finite Simon rank and sampling examples

Example

One address bit

Take $n = 1$ , hidden mask $s = 1$ , output width $m = 0$ , and the constant map from the two one-bit addresses to the unique empty output string. The two addresses are exactly the single coset ${0, 1}$ . Here $d = n - 1 = 0$ , the only sample row is $0$ , and the recovery algorithm's zero-rank branch returns $1$ with no query.

Two address bits

Take $n = 2$ , $m = 1$ , $s = 11$ , and define

f (00) = f (11) = 0, f (01) = f (10) = 1.

The fibers are the two cosets of ${00, 11}$ . The output measurement has two outcomes, each with probability $1 / 2$ . Conditional on outcome $0$ , the address state before the final Hadamards is $(∣ 00 ⟩ + ∣ 11 ⟩) / \sqrt{2}$ ; conditional on outcome $1$ , it is $(∣ 01 ⟩ + ∣ 10 ⟩) / \sqrt{2}$ .

The equation $s \cdot y = 0$ gives $s^{⊥} = {00, 11}$ . Each sample is uniform on these two rows. At rank zero, the next row raises rank exactly when it is $11$ , so the exact rank-rise probability is $1 / 2$ . The matrix $Y = [11]$ has rank $1 = n - 1$ ; the row-reduction procedure chooses column $0$ as pivot, sets the sole free coordinate $x_{1} = 1$ , solves $x_{0} = 1$ , and returns $s = 11$ .

For failure tolerance $δ = 1 / 2$ , the finite cap is $M = ⌈ 2 (1) / (1 / 2) ⌉ = 4$ . The cap fails precisely when all four rows are $00$ , an event of probability $1 / 16$ ; hence this instance succeeds with probability $15 / 16$ and uses at most four queries.

Facts & Assumptions

Given: The finite Simon instances displayed above.

[F1]

Simon hidden-XOR-period promise: equal function values occur exactly on pairs whose addresses differ by the hidden mask.

[F2]

Binary dot product as parity: $s \cdot y$ is the parity of the coordinatewise products.

[F3]

Simon query and output measurement produce a coset pair: each target outcome has probability $2^{1 - n}$ and leaves the address in its normalized two-address coset state.

[F4]

Simon samples uniformly from s-perp and Simon independent-sample rank process: samples are uniform on $s^{⊥}$ , and newly initialized runs are independent.

[F5]

Simon rank growth probability: at rank $k < d$ , the rise probability is $1 - 2^{k - d}$ .

[F6]

F2 row reduction returns the unique Simon mask: full-rank rows in $s^{⊥}$ yield the unique nonzero kernel vector $s$ .

[F7]

Budgeted Simon recovery with explicit failure branch: for $d = 0$ return $1$ without queries; otherwise use $M = ⌈ 2 d / δ ⌉$ trials and return FAIL if rank remains incomplete.

[F8]

Simon recovery succeeds with probability at least 1-delta: the cap's failure probability is at most $δ$ and its query count is at most $M$ .

Verification

1.1givenF1F7algebra

At $n = 1$ , XOR with $s = 1$ pairs the only two addresses, and the unique output string labels their single coset. Since $d = 0$ , [F7] returns $1$ before any sample; it is the only nonzero one-bit mask.

1.2givenF1F2F3algebra

At $n = 2$ , the table pairs exactly $00$ with $11$ and $01$ with $10$ , so it obeys [F1] and has hidden mask $11$ . The dot-product parity [F2] gives $11 \cdot 00 = 11 \cdot 11 = 0$ and $11 \cdot 01 = 11 \cdot 10 = 1$ . By [F3], both output branches have probability $1 / 2$ and the address states are $(∣ 00 ⟩ + ∣ 11 ⟩) / \sqrt{2}$ and $(∣ 01 ⟩ + ∣ 10 ⟩) / \sqrt{2}$ , as displayed.

1.3F4F5algebra

By [F4], the two allowed rows are equiprobable; at rank zero only row $11$ is nonzero and outside the zero span, so the rank-rise probability is $1 / 2$ , also the value $1 - 2^{0 - 1}$ from [F5].

1.4F6algebra

Row $11$ has pivot column $0$ ; the row equation is $x_{0} \oplus x_{1} = 0$ . Setting the unique free coordinate $x_{1} = 1$ gives $x_{0} = 1$ , so the nonzero kernel vector is $11$ by direct calculation, agreeing with [F6].

2.1F4F7F8algebra∎

For $δ = 1 / 2$ , [F7] gives $M = 4$ . The cap fails exactly when its first four independent potential rows are all $00$ , an event of probability $(1 / 2)^{4} = 1 / 16$ by [F4]; therefore its success probability is $15 / 16$ , consistent with the general lower bound [F8].