TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedjudge pass (gpt-6-luna)

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.

Hidden shift as generalized-dihedral hidden subgroup

Statement

Let $A$ be a finite abelian group in explicit additive coordinates, and let $f, g : A \to S$ satisfy the hidden-shift promise of Finite abelian hidden-shift promise: both maps are injective and there is a unique $s \in A$ such that $f (a) = g (a + s)$ for every $a$ . Write $D_{A} = A ⋊ Z_{2}$ with

(a, b) (a^{'}, b^{'}) = (a + (- 1)^{b} a^{'}, b + b^{'} m o d 2),

and define $F (a, 0) = f (a)$ and $F (a, 1) = g (a)$ . Then $F$ is constant exactly on the left cosets of the order-two subgroup $H_{s} = {(0, 0), (s, 1)} = ⟨ (s, 1) ⟩$ . The subgroup determines the shift uniquely: $H_{s} = H_{t}$ implies $s = t$ .

If a coherent XOR oracle for this $F$ is directly supplied, one $F$ -oracle query implements one value query. From only coherent XOR oracles for $f$ and $g$ , the $F$ -XOR operation can be implemented with four calls total (two to compute the values into scratch registers and two to uncompute them), plus the controlled output XOR; no controlled call to either oracle is assumed. All gate, workspace, and named-oracle query costs remain separately charged.

Facts & Assumptions

Given: The finite abelian group $A$ , injective fixed-length encodings of the finite set $S$ , coherent XOR oracles for $f, g$ , and the unique shift $s$ satisfying $f (a) = g (a + s)$ .

[F1]

The generalized-dihedral multiplication is the displayed semidirect-product law, and it is a group law ( The generalized dihedral group $Dih (A) = A ⋊ C_{2}$ for an abelian group $A$ , The external semidirect product $N ⋊_{α} H$ , The semidirect-product multiplication makes $N \times H$ a group).

[F2]

The hidden-shift promise gives injectivity of $f, g$ and $f (a) = g (a + s)$ for every $a \in A$ (Finite abelian hidden-shift promise).

[F3]

A coherent function oracle adds the fixed-length output encoding by bitwise XOR and is its own inverse (Coherent XOR function oracle).

[F4]

CNOT and Toffoli implement reversible XOR and controlled conjunction on computational-basis bits (CNOT and Control-Target Order, Toffoli and Fredkin gates).

Proof

1.1givenF1algebra

By [F1], $(s, 1)^{2} = (s - s, 0) = (0, 0)$ , and $(s, 1) \neq (0, 0)$ because its second coordinate is $1$ . Thus $H_{s}$ has the two stated elements. Right multiplication gives

(a, 0) (s, 1) = (a + s, 1), (a + s, 1) (s, 1) = (a, 0) .

Consequently the left coset through $(a, 0)$ is exactly $C_{a} = {(a, 0), (a + s, 1)}$ . Every group element belongs to one such pair, and distinct $a$ give distinct pairs because their parity-zero representatives differ.

2.1F2step 1.1algebra

On the pair $C_{a}$ , [F2] gives $F (a, 0) = f (a) = g (a + s) = F (a + s, 1)$ . If two parity-zero values agree, injectivity of $f$ makes their coordinates equal; if two parity-one values agree, injectivity of $g$ does the same. If $F (a, 0) = F (b, 1)$ , then $f (a) = g (b) = g (a + s)$ , so injectivity of $g$ yields $b = a + s$ and the two inputs lie in $C_{a}$ . Thus equality of $F$ -values occurs exactly within one left coset.

2.2step 1.1algebra

The nonidentity element of $H_{s}$ is $(s, 1)$ , so equality $H_{s} = H_{t}$ forces $(s, 1) = (t, 1)$ and hence $s = t$ .

3.1F3F4step 2.1algebra∎

A direct $F$ -XOR oracle is exactly one value-query interface for the function just defined. Given only $O_{f}, O_{g}$ , compute $f (a)$ and $g (a)$ into two fresh zero scratch registers with one call to each oracle. For each output bit, the selected value is $(1 - b) f (a)_{i} \oplus b g (a)_{i}$ ; CNOT and Toffoli gates from [F4] implement this reversible Boolean-controlled XOR into the target, leaving the input and scratch registers unchanged. Apply $O_{g}$ and then $O_{f}$ again to erase the scratch registers, since [F3] makes each XOR oracle self-inverse and the group input is unchanged. The target has acquired precisely $F (a, b)$ and all scratch bits return to zero, using four calls total. This gives an explicit query account without postulating controlled access to $O_{f}$ or $O_{g}$ .

Depends on

Used by

Power-of-two dihedral hidden-subgroup sieve Algorithm
Hidden-shift left cosets in a generalized dihedral group Example
Kuperberg dihedral hidden-subgroup scope and resource claim Theorem

Dependency tree · two levels

25 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

Greg Kuperberg, A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem (standard reference, not scraped)
Andrew M. Childs, Lecture Notes on Quantum Algorithms (17 April 2025) (standard reference, not scraped)