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.

Finite Abelian Hidden-Subgroup Algorithms — Examples

1 · Prerequisites

2 · Summary

These finite examples calculate a cyclic annihilator distribution and show two explicit character constraints reducing a product-group candidate subgroup to the hidden subgroup.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

Common-kernel subgroup recovery in a product of cyclic groups

Example

Take the invariant-factor group $G = Z / 2 Z \times Z / 6 Z$ and the trivial subgroup $H = {(0, 0)}$ . The characters are $χ_{a, b} (x, y) = \exp (2 π i (a x / 2 + b y / 6))$ . Two possible Fourier samples, $χ_{1, 0}$ followed by $χ_{0, 1}$ , reduce the initial candidate group $G$ to $H$ .

Facts & Assumptions

Given: The character labels of a product of cyclic groups and the common-kernel output convention.

[F1]

Cyclic characters are indexed by residues and product characters factor by coordinates. (A cyclic group of order n has exactly n additive characters, Characters of a finite product factor coordinatewise)

[F2]

A sample is uniform on $H^{⊥}$ , and independent repetitions use fresh samples. (Fourier samples are uniform in the annihilator, Finite abelian hidden-subgroup common-kernel reconstruction)

[F3]

The output list represents the intersection of the sampled character kernels. (Finite abelian hidden-subgroup common-kernel reconstruction)

Verification

Given: The group and subgroup in the Example, with additive coordinates reduced modulo $2$ and $6$ .

1.1givenF1algebra

Since $H$ is trivial, every character is trivial on $H$ . The labels are $a \in {0, 1}$ and $b \in {0, 1, 2, 3, 4, 5}$ , so $∣ H^{⊥} ∣ = 12$ and both $(1, 0)$ and $(0, 1)$ label allowed outcomes.

1.2F2algebra

By [F2], the probability that two independent samples occur in the specified order is $(1 / 12) (1 / 12) = 1 / 144$ . The first sampled character has kernel ${0} \times Z / 6 Z$ , since $χ_{1, 0} (x, y) = (- 1)^{x}$ .

1.3F3algebra

The second character has kernel $Z / 2 Z \times {0}$ , since $χ_{0, 1} (x, y) = \exp (2 π i y / 6)$ equals $1$ exactly for $y \equiv 0 (m o d 6)$ . Intersecting the two kernels gives ${(0, 0)} = H$ .

2.1F1F3step 1.3∎

Each constraint kernel contains $H$ , and the ordered sample list therefore presents the exact hidden subgroup without converting it to generators.

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

Fourier sampling for a cyclic subgroup

Example

Let $G = Z / 12 Z$ and $H = 3 Z / 12 Z = {0, 3, 6, 9}$ . Its annihilator has the three character labels $0, 4, 8$ , so a Fourier sample is uniform on those labels.

Facts & Assumptions

Given: The additive cyclic group $Z / 12 Z$ , its subgroup $H$ , and the negative-character QFT convention.

[F1]

The characters are $χ_{k} (x) = \exp (2 π i k x / 12)$ for $k \in Z / 12 Z$ , and these are all twelve characters. (A cyclic group of order n has exactly n additive characters)

[F2]

$H^{⊥}$ consists of the characters trivial on every element of $H$ . (Character annihilator of a subgroup)

[F3]

The normalized transform of a coset state has equal-modulus amplitudes exactly on $H^{⊥}$ . (Normalized Fourier transform on a finite abelian group, Fourier samples are uniform in the annihilator)

[F4]

Character values on finite groups have modulus one. (Values of additive characters of finite abelian groups have modulus one)

Verification

Given: The coset state $∣ a + H ⟩ = \frac{1}{2} \sum_{j = 0}^{3} ∣ a + 3 j ⟩$ for any $a \in Z / 12 Z$ .

1.1givenF1F2algebra

A character $χ_{k}$ is trivial on $H$ exactly when $χ_{k} (3) = \exp (2 π i k / 4) = 1$ , which holds exactly when $4 ∣ k$ . Among residues modulo $12$ this gives $k \in {0, 4, 8}$ , so $∣ H^{⊥} ∣ = 3$ .

1.2F1F3F4algebra

The amplitude of label $k$ after the normalized QFT is $\frac{1}{\sqrt{48}} \sum_{j = 0}^{3} \overline{χ_{k} (a + 3 j)} = \frac{\overline{χ_{k} (a)}}{\sqrt{48}} \sum_{j = 0}^{3} \exp (- 2 π i k j / 4)$ . If $4 ∣ k$ , the sum is $4$ and the amplitude has modulus $4 / \sqrt{48} = 1 / \sqrt{3}$ by [F4]. If $4 ∤ k$ , the ratio $q = \exp (- 2 π i k / 4)$ is a nontrivial fourth root of unity, so $(1 - q) \sum_{j = 0}^{3} q^{j} = 1 - q^{4} = 0$ and the sum vanishes.

2.1F2F3step 1.2∎

Squaring the amplitudes in step 1.2 gives probability $1 / 3$ for each of $k = 0, 4, 8$ and zero for the other nine labels. These probabilities sum to one and agree with the uniform annihilator law.

Finite Abelian Hidden-Subgroup Algorithms — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

Common-kernel subgroup recovery in a product of cyclic groups

Example

Facts & Assumptions

Verification

Fourier sampling for a cyclic subgroup

Example

Facts & Assumptions

Verification

Sources