Finite Abelian Hidden-Subgroup Algorithms

The proofs on this page use one-dimensional characters of finite abelian groups and their subgroup annihilators. They establish no algorithmic claim for a general nonabelian hidden-subgroup problem. General-group query information alone is not used here as a substitute for an efficient circuit or a subgroup-recovery proof.

Let $G$ be a finite abelian group, and let $H⊊K\le G$. Choose a character $\chi$ uniformly from $H^{\perp }$. Then $\mathbb{P}(\chi {\mathrm{\mid }}_K\mathrm{\ne }1)\ge \frac{1}{2}\mathrm{.}$ For every outcome with $\chi {\mathrm{\mid }}_K\mathrm{\ne }1$, the updated common kernel $K\cap \ker \chi$, where $\ker \chi =\{g\in G:\chi (g)=1\}$, contains $H$ and has index at least two in $K$.

The current QA-05 double-annihilator and evaluation-map carriers are draft suppliers. Their actual statements and proofs were inspected for this argument; draft status is not independent acceptance.

Let $G$ be a finite abelian group with $N:=\mathrm{\mid }G\mathrm{\mid }\ge 2$, let $H\le G$, and start with a current subgroup $K_0$ satisfying $H\le K_0\le G$. At each of $M$ fresh independent trials, if the current subgroup $K_{t-1}$ strictly contains $H$, draw a uniform ${\chi }_t\in H^{\perp }$ and replace $K_{t-1}$ by $K_t=K_{t-1}\cap \ker {\chi }_t$; after reaching $H$, leave the subgroup equal to $H$. Each cut reduces the current order by a factor of at least two. For $0<\delta <1$, put $s:=\lceil {\log }_{2}N\rceil ,M:=\lceil 4s+16\ln (1\mathrm{/}\delta )\rceil \mathrm{.}$ Then the failure event $K_M\mathrm{\ne }H$ has probability at most $\delta$. If $H=K_0$, the failure probability is zero.

The failure event is stated as $K_M\mathrm{\ne }H$. “Fewer than $s$ cuts before reaching $H$” would incorrectly count early successful termination as failure.

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.

Inputs are a hiding instance from Finite abelian hidden-subgroup promise and output encoding, a fresh $b$-qubit group register and supplied exact circuits with declared access/costs, where $b$ is the group-code width in that definition:

• $P_G$ prepares the normalized uniform state $\mathrm{\mid }G⟩=N^{-1\mathrm{/}2}{\sum }_{g\in G}\mathrm{\mid }{\mathrm{code}}_G(g)⟩$ on valid group labels and returns its workspace to the declared initial state.
• $O_F$ is the supplied coherent XOR oracle for the total extension $\tilde{F}$ in Finite abelian hidden-subgroup promise and output encoding, acting on the group register and a fresh $m$-qubit output register initialized to the all-zero word $0^m$.
• $Q_G$ is the supplied exact product QFT, with the fixed negative-character convention $Q_G\mathrm{\mid }{\mathrm{code}}_G(g)⟩=N^{-1\mathrm{/}2}{\sum }_{\mathbf{k}}\overline{{\chi }_{\mathbf{k}}(g)}\mathrm{\mid }{\mathrm{code}}_{\widehat{G}}(\mathbf{k})⟩$ on the valid group subspace. It is supplied as a unitary on the full $b$-qubit register, so any extension from the valid-label subspace is part of the circuit input.

If $N=1$, return the unique trivial character without a query. Otherwise:

1. Prepare $\mathrm{\mid }G⟩$ with $P_G$.
2. Apply $O_F$ once to the group register and fresh output register.
3. Discard the output register by the declared partial-trace operation; do not measure it.
4. Apply $Q_G$ to the group register and measure the full $b$-qubit register in its ordered computational basis; the prescribed QFT action places the state in the valid character-code subspace.
5. Decode the measured valid character code as the tuple $\mathbf{k}$ and return ${\chi }_{\mathbf{k}}$.

This procedure assumes the preparation, oracle, and QFT circuits are supplied exactly. It makes no existence, uniformity, or efficiency claim for those circuits.

Let $G$ be finite abelian, $H\le G$, $N=\mathrm{\mid }G\mathrm{\mid }$, and $h=\mathrm{\mid }H\mathrm{\mid }$. Write ${\mathcal{C}}_H:=\{g+H:g\in G\}$ for the set of distinct additive cosets, where $g+H:=\{g+h^{\mathrm{\prime }}:h^{\mathrm{\prime }}\in H\}$. Start with the uniform group state, evaluate an exact hiding oracle into a fresh output register, then discard that register. On the group register the resulting density matrix is ${\rho }_G=\frac{h}{N}{\sum }_{C\in {\mathcal{C}}_H}\mathrm{\mid }C⟩⟨C\mathrm{\mid },\mathrm{\mid }C⟩:=h^{-1\mathrm{/}2}{\sum }_{g\in C}\mathrm{\mid }g⟩\mathrm{.}$ Thus it is the uniform mixture of one normalized coset state for each distinct coset.

The proof uses discard/partial trace. It does not replace discarding by a measured output; a separate measurement branch is unnecessary for this reduced-state identity.

Inputs are a finite abelian hidden-subgroup instance with explicit invariant-factor coordinates, a supplied positive integer $M$, and the exact circuits $P_G$, $O_F$, and $Q_G$ with the access, cost, workspace, and full-register action contracts specified in One finite abelian hidden-subgroup Fourier sample. If $\mathrm{\mid }G\mathrm{\mid }=1$, output the empty character list, which denotes $G$, and make no oracle calls. Otherwise run the exact Fourier-sample procedure One finite abelian hidden-subgroup Fourier sample independently $M$ times, passing those supplied circuits and using fresh registers and a fresh measurement each time. Store the resulting character labels ${\mathbf{k}}^{(1)},\dots ,{\mathbf{k}}^{(M)}$ and output that list as the implicit common-kernel presentation $K={\bigcap }_{j=1}^M\ker {\chi }_{{\mathbf{k}}^{(j)}}\mathrm{.}$ Do not convert $K$ to a generating set. The algorithm consumes $M$ as an integer input; the success theorem specifies a choice of $M$ for each confidence target.

The procedure always outputs a finite constraint list, including on a failure event. Its correctness and repetition bound are separate theorems.

For every finite abelian hidden-subgroup instance with hidden subgroup $H\le G$, one execution of the exact sample procedure returns a valid character code with probability one. Each $\chi \in H^{\perp }$ has probability $1\mathrm{/}\mathrm{\mid }{H}^{\perp }\mathrm{\mid }=\mathrm{\mid }H\mathrm{\mid }\mathrm{/}\mathrm{\mid }G\mathrm{\mid }$, every character outside $H^{\perp }$ has probability zero, and every invalid $b$-bit code has probability zero.

The proof uses the normalized-state amplitude, not the unnormalized indicator coefficient $\mathrm{\mid }H\mathrm{\mid }\mathrm{/}\sqrt{\mathrm{\mid }G\mathrm{\mid }}$. The current QA-05 annihilator-cardinality proof supplies the cardinality used here. The projective-measurement item and the required measurement and circuit page bodies were inspected for the sampling and terminal-readout hypotheses; those suppliers remain draft, and no independent acceptance is claimed.

Let $G$ be finite abelian, let $H\le G$ be hidden by the supplied function, and let $0<\delta <1$. The common-kernel list output by Finite abelian hidden-subgroup common-kernel reconstruction always denotes a subgroup $K$ with $H\le K$. For $\mathrm{\mid }G\mathrm{\mid }=1$ it equals $H=G$ exactly without queries. For $\mathrm{\mid }G\mathrm{\mid }\ge 2$, set $s=\lceil {\log }_2\mathrm{\mid }G\mathrm{\mid }\rceil$ and pass the integer $M=\lceil 4s+16\ln (1\mathrm{/}\delta )\rceil$ to the reconstruction algorithm; its output equals $H$ with probability at least $1-\delta$.

No subgroup generator extraction is used. The confidence integer is supplied to the reconstruction procedure; the theorem does not hide its classical computation.

Let $N=\mathrm{\mid }G\mathrm{\mid }$. For $N\ge 2$, let $M$ be the integer supplied to the reconstruction algorithm. If the supplied preparation and product-QFT circuits make no access to the hiding oracle, then in a named-oracle query model the algorithm makes exactly $M$ coherent hiding-oracle queries; this query count is separate from ordinary gate costs. Let $C_P$ and $C_Q$ be the ordinary gate counts of the supplied exact uniform-state preparation and product-QFT circuits. If the hiding function is instead compiled from an explicit reversible Boolean circuit with $C_F$ gates per evaluation, the total ordinary gate count is $M(C_P+C_Q+C_F)$; a named oracle query is not silently counted as an elementary gate. Each sample measures a $b$-bit character label, where $b={\sum }_i\lceil {\log }_2{n}_i\rceil$. The output list therefore uses $Mb$ bits and writing it costs $O(Mb)=O(M{\log }_{2}N)$ classical bit operations, once $M$ and the circuits are supplied. If a model assigns separate per-sample costs $C_{\mathrm{m}\mathrm{e}\mathrm{a}\mathrm{s}}$ to label measurement and $C_{\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{c}}$ to discarding the output register, the corresponding coordinates are $M{C}_{\mathrm{m}\mathrm{e}\mathrm{a}\mathrm{s}}$ and $M{C}_{\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{c}}$; they remain separate from gates and queries. If supplied invariant-factor circuits satisfy $C_P+C_Q=O({\log }^{2}N)$ and the hiding-oracle circuit has $C_F$ gates per evaluation, the ordinary gate count is $O(M(C_F+{\log }^{2}N))$, while the named-oracle query count remains $M$ under the same no-access condition. For $N=1$ the algorithm uses zero oracle queries and outputs the trivial common kernel with constant control work. Computing the integer $M$, generating circuit descriptions, and converting the implicit list to subgroup generators are separate costs; no polynomial-time implementation claim is made without those explicit inputs and bounds.

The $O({\log }^{2}N)$ premise is conditional on actual exact circuits for the supplied invariant-factor preparation and QFT, including any encoding extension. It does not assert that such circuits exist over an arbitrary fixed finite gate alphabet.