Finite abelian hidden-subgroup promise and output encoding

An input group is given in explicit invariant-factor coordinates $G={\prod }_{i=1}^r\mathbb{Z}\mathrm{/}{n}_i\mathbb{Z},2\le n_1\mid n_2\mid \cdots \mid n_r,$ with componentwise addition and $N:=\mathrm{\mid }G\mathrm{\mid }={\prod }_i{n}_i$. The empty product has $G=\{0\}$ and $N=1$. No procedure for finding these coordinates from a black-box group is included. A character label is a tuple $\mathbf{k}=(k_1,\dots ,k_r)$ with $k_i\in \mathbb{Z}\mathrm{/}{n}_i\mathbb{Z}$, representing ${\chi }_{\mathbf{k}}(\mathbf{g}):={\prod }_{i=1}^r\exp (2\pi i{k}_i{g}_i\mathrm{/}{n}_i)\mathrm{.}$ The cyclic-character and product-character suppliers identify these labels with all of $\widehat{G}$.

The hiding input is a finite set $S$, an injective encoding $\eta :S\to \{0,1{\}}^m$, and a total function $F:G\to S$ for which there is an unknown subgroup $H\le G$ such that $F(\mathbf{g})=F({\mathbf{g}}^{\mathrm{\prime }})⟺\mathbf{g}-{\mathbf{g}}^{\mathrm{\prime }}\in H\mathrm{.}$ This is the hiding promise. Put $b_i:=\lceil {\log }_2{n}_i\rceil$ and $b:={\sum }_i{b}_i$. Encode $g_i\in \mathbb{Z}\mathrm{/}{n}_i\mathbb{Z}$ by the $b_i$-bit big-endian binary word of its least residue in $\{0,\dots ,n_i-1\}$, and encode $\mathbf{g}$ by concatenating these words in coordinate order; denote this injective code by ${\mathrm{code}}_G(\mathbf{g})$. This uses the first-wire-most-significant-bit convention of Big-endian encoding of ordered bit strings. Use the same coordinate widths and convention to encode character labels $\mathbf{k}$ as ${\mathrm{code}}_{\widehat{G}}(\mathbf{k})$.

The hiding input also supplies a total Boolean function $\tilde{F}:\{0,1{\}}^b\to \{0,1{\}}^m$ agreeing with $\eta \circ F$ on valid group codes; its values on invalid bit strings are part of the declared extension. The coherent XOR oracle acts by $O_{\tilde{F}}\mathrm{\mid }x,y⟩=\mathrm{\mid }x,y\oplus \tilde{F}(x)⟩$ on all ordered input and target bit-string basis states. In particular, on valid codes it adds $\eta (F(\mathbf{g}))$ to the target. A named oracle call is charged as one query; a Boolean-circuit implementation is charged for its reversible gates. The model makes no claim that an arbitrary function has an efficient circuit.

The recovery algorithm outputs a finite list of character labels ${\mathbf{k}}^{(1)},\dots ,{\mathbf{k}}^{(M)}$. It denotes the constraint set $K:=\{\mathbf{g}\in G:{\chi }_{{\mathbf{k}}^{(j)}}(\mathbf{g})=1\text{ for every }1\le j\le M\}={\bigcap }_{j=1}^M\ker {\chi }_{{\mathbf{k}}^{(j)}},$ where $\ker \chi :=\{\mathbf{g}:\chi (\mathbf{g})=1\}$ and the empty intersection is defined to be $G$. Success means $K=H$. The output remains this implicit common-kernel presentation; converting it to subgroup generators is outside the definition.

Character-coordinate labels and the exact extension of the oracle on invalid encodings are input-model data. Their existence or efficient construction is not inferred from query access.