Power-of-two dihedral hidden-subgroup sieve

Input an integer $n\ge 1$, $N=2^n$, and either (i) a coherent XOR oracle $O_F$ for a total encoded function $F:D_N\to S$ that is constant on each left coset of the unknown reflection subgroup $H_s=⟨y{x}^s⟩$ and takes distinct values on different left cosets, or (ii) a finite cyclic hidden-shift instance on $A=\mathbb{Z}\mathrm{/}N\mathbb{Z}$ together with its reflection oracle constructed by Hidden shift as generalized-dihedral hidden subgroup. Use coordinates $(a,b)\in \mathbb{Z}\mathrm{/}N\mathbb{Z}\times \mathbb{Z}\mathrm{/}2\mathbb{Z}$ with multiplication $(a,b)(a^{\mathrm{\prime }},b^{\mathrm{\prime }})=(a+(-1{)}^b{a}^{\mathrm{\prime }},b+b^{\mathrm{\prime }})$ and fix $x=(-1,0)$ and $y=(0,1)$; then $y{x}^s=(s,1)$. Charge each supplied or constructed oracle call according to its interface.

Every projective readout below is implemented by the Lüders instrument of its stated projections. Charge each supplied measurement or instrument implementation under its declared interface.

For $n\le 5$, query all group elements (at most $2N\le 64$ values of $F$) and return the unique $s$ for which $F(0,0)=F(s,1)$. For $n\ge 6$, set $m=\lceil \sqrt{n-1}\rceil$ once and retain this $m$ through all recursive calls. The following procedure is run at modulus $2^r$, starting with $r=n$:

1. If $r\le 5$, use the direct-query base case. Otherwise set $t_r=\lceil (r-1)\mathrm{/}m\rceil$ and create a list $L_0$ of $M=3\cdot 2^{3m}$ independent coset samples: prepare the uniform group state with Hadamards on its $r+1$ coordinate bits, evaluate $O_F$, discard the function-output register, apply the positive-sign ${\mathrm{QFT}}_{2^r}$ to the cyclic coordinate and measure that coordinate. Store the measured label $k$ and retain its conditional qubit $\mathrm{\mid }{\psi }_k⟩=(\mathrm{\mid }0⟩+e^{2\pi iks\mathrm{/}{2}^r}\mathrm{\mid }1⟩)\mathrm{/}\sqrt{2}$.

2. For each $j=0,\dots ,t_r-1$, put $w_j=\min (m,r-1-mj)$. The current labels are divisible by $2^{mj}$. Bucket them by the $w_j$ bits of $k\mathrm{/}{2}^{mj}$ immediately above those trailing zeroes, using only the lower $r-1$ bits of $k$. In each bucket, preserve current list order, pair consecutive entries, and leave the last entry unmatched if the bucket has odd size; this is a maximum-cardinality disjoint matching. For each pair, apply the CNOT pair combiner and measure its second qubit with the Lüders instrument. Retain only outcome $1$; the retained state has label $k-\mathrm{\ell }(\mathrm{m}\mathrm{o}\mathrm{d}{2}^r)$. Discard unmatched states and outcome-$0$ states. The next list consists of the retained states.

3. The widths sum to $r-1$, so every final label is $0$ or $2^{r-1}$. If a state with label $2^{r-1}$ occurs, measure its qubit in the $\{\mathrm{\mid }+⟩,\mathrm{\mid }-⟩\}$ basis. Outcome $+$ means $s$ is even; outcome $-$ means $s$ is odd. If the target label is absent, return FAIL.

4. For even $s$, put $r^{\mathrm{\prime }}=r-1$, $x^{\mathrm{\prime }}=x^2$, $y^{\mathrm{\prime }}=y$, and $s^{\mathrm{\prime }}=s\mathrm{/}2$. Identify child coordinates with $K_0=⟨x^2,y⟩$ by ${\varphi }_0:\mathbb{Z}\mathrm{/}{2}^{r^{\mathrm{\prime }}}\mathbb{Z}\times \mathbb{Z}\mathrm{/}2\mathbb{Z}⟶\mathbb{Z}\mathrm{/}{2}^r\mathbb{Z}\times \mathbb{Z}\mathrm{/}2\mathbb{Z},{\varphi }_0(a^{\mathrm{\prime }},b^{\mathrm{\prime }})=(2a^{\mathrm{\prime }},b^{\mathrm{\prime }})(\mathrm{m}\mathrm{o}\mathrm{d}{2}^r)\mathrm{.}$ Use the child oracle $F_0=F\circ {\varphi }_0$ and run this procedure at modulus $2^{r^{\mathrm{\prime }}}$. A coherent $F_0$ query is implemented by appending a fresh clean low address bit $0$ to the $r^{\mathrm{\prime }}$ bits of $a^{\mathrm{\prime }}$, retaining $b^{\mathrm{\prime }}$, and making one parent $O_F$ call.

   For odd $s$, put $r^{\mathrm{\prime }}=r-1$, $x^{\mathrm{\prime }}=x^2$, $y^{\mathrm{\prime }}=yx$, and $s^{\mathrm{\prime }}=(s-1)\mathrm{/}2$. Identify child coordinates with $K_1=⟨x^2,yx⟩$ by ${\varphi }_1:\mathbb{Z}\mathrm{/}{2}^{r^{\mathrm{\prime }}}\mathbb{Z}\times \mathbb{Z}\mathrm{/}2\mathbb{Z}⟶\mathbb{Z}\mathrm{/}{2}^r\mathbb{Z}\times \mathbb{Z}\mathrm{/}2\mathbb{Z},{\varphi }_1(a^{\mathrm{\prime }},b^{\mathrm{\prime }})=(2a^{\mathrm{\prime }}+b^{\mathrm{\prime }},b^{\mathrm{\prime }})(\mathrm{m}\mathrm{o}\mathrm{d}{2}^r)\mathrm{.}$ Use $F_1=F\circ {\varphi }_1$ and recurse at modulus $2^{r^{\mathrm{\prime }}}$. To implement a coherent $F_1$ query, append a fresh clean low address bit $z=0$, copy $b^{\mathrm{\prime }}$ to $z$ by CNOT, make one parent $O_F$ call on the ambient address $(a^{\mathrm{\prime }},z,b^{\mathrm{\prime }})$, and uncopy $z$ by the same CNOT. Thus each child hiding-oracle query uses one parent $F$ query; the odd embedding adds two ordinary CNOT gates per query, and the even embedding adds none beyond the clean address wire. Return $2s^{\mathrm{\prime }}$ in the even branch and $2s^{\mathrm{\prime }}+1$ in the odd branch.

   Before the recursive call, discard the current sample, pair, output, and label registers after recording the parity branch; carry only the classical branch result and recursion parameters. The child call reuses this workspace.

The exact sampling-state law and pair-combination identity are in Fourier sample from a generalized-dihedral reflection coset state and Dihedral hidden-state pair combination. The correctness, error, and resource claims for this locally specified shortened-final-width version are proved in Kuperberg dihedral hidden-subgroup scope and resource claim. The procedure is only specified for power-of-two cyclic orders; no arbitrary-$N$ or arbitrary finite-abelian extension is asserted.