Finite abelian hidden-subgroup common-kernel reconstruction

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.