DefinitionDefinition: Literature-sourcedProof: AI-adaptedPipeline-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 hidden-XOR-period promise

Definition

Fix integers $n \geq 1$ and $m \geq n - 1$ . A total function $f : {0, 1}^{n} \to {0, 1}^{m}$ satisfies the Simon hidden-XOR-period promise if there is a unique nonzero string $s \in {0, 1}^{n}$ such that for all $x, y \in {0, 1}^{n}$ ,

$f (x) = f (y) ⟺ (y = x or y = x \oplus s) .$

For the query algorithms using this promise, the instance is $n, m$ together with black-box access to $f$ : the solver receives no function table or other information depending on $f$ . Each oracle call uses the standard bit-query interface Standard bit-flip query convention. Its witness relation $R (f, s)$ holds exactly when $s$ is the nonzero mask in the displayed iff condition, so the required output is the unique hidden mask. The address operation $\oplus$ is the coordinatewise addition of Binary residue carrier and operations. The output width condition lets the $2^{n - 1}$ fibers receive distinct labels; it does not promise that the image uses every $m$ -bit label. Each fiber is exactly ${x, x \oplus s}$ .

Facts & Assumptions

Given: Integers $n \geq 1$ , $m \geq n - 1$ , and the binary residue operation from Binary residue carrier and operations.

[F1]

Binary residue carrier and operations: addition in $F_{2}$ is the residue operation modulo two, represented on bits by XOR.

Verification

1.1givenF1constructalgebra

Set $s = (1, 0, \dots, 0)$ , which is a nonzero $n$ -bit string because $n \geq 1$ . For every $x$ , $x \oplus s \neq x$ and $(x \oplus s) \oplus s = x$ , so this involution partitions the $2^{n}$ addresses into disjoint two-element fibers; there are $2^{n - 1}$ fibers.

2.1givenstep 1.1constructalgebra

The set of $m$ -bit labels has $2^{m}$ elements: it has one empty word at width zero, and appending either $0$ or $1$ doubles the count at each additional bit. Since $m \geq n - 1$ , there are at least $2^{n - 1}$ labels. Order the fibers by their least address and assign the first $2^{n - 1}$ labels in lexicographic order; this constructs a total oracle satisfying the iff condition, so the promised family is nonempty.

3.1givenstep 1.1algebra∎

The displayed iff condition makes the output fiber of $x$ exactly ${x, x \oplus s}$ . Since $s \neq 0$ , the two members are distinct. For any other nonzero period $t$ , the point $x \oplus t$ is the unique other member of the fiber of $x$ , so $x \oplus t = x \oplus s$ and cancellation gives $t = s$ . This verifies the uniqueness clause in the Definition.

Depends on

Used by

One Simon Fourier-sampling sample Algorithm
Random Simon-oracle distribution for a classical lower bound Definition
Simon independent-sample rank process Definition
Finite Simon rank and sampling examples Example
The Simon annihilator is an (n−1)-dimensional binary subspace Lemma
F2 row reduction returns the unique Simon mask Theorem
Simon query and output measurement produce a coset pair Theorem

Dependency tree · two levels

11 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Ronald de Wolf, Quantum Computing: Lecture Notes (arXiv:1907.09415v6, 2026) (standard reference, not scraped)
John Preskill, Quantum Information, Chapter 6: Quantum Algorithms (updated November 2020) (standard reference, not scraped)
Andrew M. Childs, Lecture Notes on Quantum Algorithms (17 April 2025) (standard reference, not scraped)