Kuperberg dihedral hidden-subgroup scope and resource claim

For $n\le 5$, query $F(0,0)$ and the parity-one elements. The left-coset promise gives a unique $b=s$ with $F(0,0)=F(s,1)$, so the direct branch identifies $s$; querying the full group uses at most $2N\le 64$ calls. Now suppose $n\ge 6$, so $m\ge 3$. At recursive exponent $r\le n$ with $r\ge 6$, $1\le r-1\le n-1\le m^2$, hence $1\le t_r=\lceil (r-1)\mathrm{/}m\rceil \le m$. The widths are $m$ until possibly the final stage, whose positive remainder is at most $m$; therefore ${\sum }_{j<t_r}{w}_j=r-1$ and $mj+w_j\le r-1$ at every stage.

For one recursive sieve set $S_j=2^{3m-2j}$, ${ϵ}_j=2^{2j-2m}$, $b_j=2^{j-4m\mathrm{/}3}$, $C_0=3$, and $C_{j+1}=(C_j-{ϵ}_j)(1-b_j)$. For $j\le m-1$, $0\le {ϵ}_j<1$ and $0<b_j<1$. The geometric sums satisfy ${\sum }_{i=0}^j{ϵ}_i<1\mathrm{/}3$ and ${\sum }_{i=0}^{j-1}{b}_i\le 3\mathrm{/}16$: the first is $2^{-2m}(4^{j+1}-1)\mathrm{/}3<1\mathrm{/}3$; for the second set $z=2^{-m\mathrm{/}3}\le 1\mathrm{/}2$, so the full sum through $m-2$ is $z\mathrm{/}2-z^4$, and $3\mathrm{/}16-(z\mathrm{/}2-z^4)=(2z-1)(8z^3+4z^2+2z-3)\mathrm{/}16\ge 0$ because both factors are nonpositive. Expanding the recurrence and using ${\prod }_i(1-b_i)\ge 1-{\sum }_i{b}_i$ gives $C_j-{ϵ}_j\ge 3{\prod }_{i<j}(1-b_i)-{\sum }_{i\le j}{ϵ}_i>39\mathrm{/}16-1\mathrm{/}3=101\mathrm{/}48>2$ for every stage index $j\le t_r-1$; this is the lower bound needed for the subsequent pair count. For the terminal list, expansion through $t=t_r$ gives $C_t=3{\prod }_{i<t}(1-b_i)-{\sum }_{j<t}{ϵ}_j{\prod }_{i=j}^{t-1}(1-b_i)\mathrm{.}$ Writing $z=2^{-m\mathrm{/}3}\le 1\mathrm{/}2$, we have ${\sum }_{i<t}{b}_i\le {\sum }_{i=0}^{m-1}{b}_i=z-z^4\le 7\mathrm{/}16$, since $\frac{7}{16}-z+z^4=(\frac{1}{2}-z)(\frac{7}{8}-\frac{z}{4}-\frac{z^2}{2}-z^3)\ge 0$ with both factors nonnegative; also ${\sum }_{j<t}{ϵ}_j<1\mathrm{/}3$. Since each product factor lies in $[0,1]$, ${\prod }_{i<t}(1-b_i)\ge 1-{\sum }_{i<t}{b}_i\ge 9\mathrm{/}16$, so $C_t\ge 27\mathrm{/}16-1\mathrm{/}3=65\mathrm{/}48>1$.

By [F2], each initial sample has a uniform label and its stated conditional state. If a current label is divisible by $2^{mj}$ and two labels share a bucket, their quotients agree modulo $2^{w_j}$, so their difference is divisible by $2^{mj+w_j}$. By [F3], every retained outcome-1 state has that difference label. Induction over stages proves every label in $L_j$ is divisible by $2^{mj}$ and every final label in $L_{t_r}$ is divisible by $2^{r-1};$ its only possible residues modulo $2^r$ are $0$ and $2^{r-1}$.

Assume $\mathrm{\mid }{L}_j\mathrm{\mid }\ge C_j{S}_j$. The bucket matching is maximal within at most $2^{w_j}$ buckets, each leaving at most one unmatched label, so the number $P_j$ of disjoint pairs satisfies $P_j\ge (\mathrm{\mid }{L}_j\mathrm{\mid }-2^{w_j})\mathrm{/}2\ge (C_j-{ϵ}_j)S_j\mathrm{/}2>101S_j\mathrm{/}96$, since $2^{w_j}\le 2^m={ϵ}_j{S}_j$. Conditional on the complete list of labels, the current qubit registers form a product of the states supplied by [F2]: this holds for the independently prepared initial samples and is preserved by the disjoint pair gates and Lüders branches. For the $P_j$ selected pairs, the joint Lüders branch at any outcome vector $(b_1,\dots ,b_{P_j})$ is the tensor product of the pairwise projected vectors. Each pairwise branch has squared norm $1\mathrm{/}2$ by [F3]; by the product inner product in [F9], the joint branch probability is $2^{-P_j}$. Thus the outcomes are independent Bernoulli$(1\mathrm{/}2)$ variables. If $B_j$ is the number of retained differences, [F4] and binomial symmetry give $\mathrm{Pr}(B_j<(1-b_j)P_j\mathrm{/}2)\le e^{-P_j{b}_j^2\mathrm{/}2}<\exp (-(101\mathrm{/}192)2^{m\mathrm{/}3})$, because $S_j{b}_j^2=2^{m\mathrm{/}3}$. Outside this event, $\mathrm{\mid }{L}_{j+1}\mathrm{\mid }=B_j\ge (C_j-{ϵ}_j)(1-b_j)S_j\mathrm{/}4=C_{j+1}{S}_{j+1}$. Thus the invariant fails at some stage with probability at most $t_r\exp (-(101\mathrm{/}192)2^{m\mathrm{/}3})$.

If all size invariants hold, $\mathrm{\mid }{L}_{t_r}\mathrm{\mid }\ge C_{t_r}{S}_{t_r}>S_{t_r}\ge 2^m$, since $C_{t_r}>1$ by step 1.2 and $t_r\le m$ gives $S_{t_r}=2^{3m-2t_r}\ge 2^m$. The highest label bit is never inspected in bucket assignment or tie-breaking. It is initially an independent fair bit by [F2]; each output pair's highest bit is the difference of its two parent high bits modulo two plus a fixed value determined by lower bits, hence remains fair. Disjoint pairs use disjoint parent samples, and retention is independent of these bits by [F3] and [F9]. Induction shows the final highest bits are independent fair bits conditional on the lower bits and retention decisions. Since each final label is 0 or $2^{r-1}$ by step 2.1, each is the target with probability $1\mathrm{/}2$, independently, and target absence has probability at most $2^{-2^m}$.

Put $X=2^{m\mathrm{/}3}\ge 2$. The stage-failure bound from step 2.2 is at most $m{e}^{-(101\mathrm{/}192)X}$. Its difference from $m{e}^{-X\mathrm{/}2}$ is $m{e}^{-X\mathrm{/}2}(1-e^{-5X\mathrm{/}192})$. From $1-e^{-z}\ge z\mathrm{/}(1+z)$, $m(1-e^{-5X\mathrm{/}192})\ge 15\mathrm{/}101>1\mathrm{/}8$. Also $\ln 2>1\mathrm{/}2$ and $X\ge 2$ imply $\ln 2X^3-X\mathrm{/}2>(X^3-X)\mathrm{/}2\ge 3$, so the target-absence bound from step 3.1 satisfies $2^{-2^m}=e^{-\ln 2X^3}<e^{-X\mathrm{/}2}\mathrm{/}8$. Thus target absence is covered by the slack, and the per-sieve failure is at most $m{e}^{-X\mathrm{/}2}=m\exp (-2^{m\mathrm{/}3-1})$.

The target state is $\mathrm{\mid }{\psi }_{2^{r-1}}⟩=(\mathrm{\mid }0⟩+e^{2\pi is\mathrm{/}2}\mathrm{\mid }1⟩)\mathrm{/}\sqrt{2}=(\mathrm{\mid }0⟩+(-1{)}^s\mathrm{\mid }1⟩)\mathrm{/}\sqrt{2}$ by [F2], so the Lüders measurement in the $\{\mathrm{\mid }+⟩,\mathrm{\mid }-⟩\}$ basis reveals parity exactly. The rotation $x$ has order $2^r$, hence $x^2$ has order $2^{r-1}$. For the even branch, substituting in the product law gives ${\varphi }_0((a^{\mathrm{\prime }},b^{\mathrm{\prime }})(a^{\mathrm{\prime }\mathrm{\prime }},b^{\mathrm{\prime }\mathrm{\prime }}))=(2a^{\mathrm{\prime }}+2(-1{)}^{b^{\mathrm{\prime }}}{a}^{\mathrm{\prime }\mathrm{\prime }},b^{\mathrm{\prime }}+b^{\mathrm{\prime }\mathrm{\prime }}<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>2)={\varphi }_0(a^{\mathrm{\prime }},b^{\mathrm{\prime }}){\varphi }_0(a^{\mathrm{\prime }\mathrm{\prime }},b^{\mathrm{\prime }\mathrm{\prime }})\mathrm{.}$ If ${\varphi }_0(a^{\mathrm{\prime }},b^{\mathrm{\prime }})={\varphi }_0(a^{\mathrm{\prime }\mathrm{\prime }},b^{\mathrm{\prime }\mathrm{\prime }})$, equality of the second coordinates and cancellation of $2$ modulo $2^r$ give $b^{\mathrm{\prime }}=b^{\mathrm{\prime }\mathrm{\prime }}$ and $a^{\mathrm{\prime }}=a^{\mathrm{\prime }\mathrm{\prime }}$ modulo $2^{r-1}$, so ${\varphi }_0$ is injective. It sends child generators $(-1,0),(0,1)$ to $x^2,y$, hence its image is $K_0$. It sends the child reflection coordinate $(u,1)$ to $(2u,1)=(s,1)$. For the odd branch, the product law gives $\begin{array}{rl}{\displaystyle {\varphi }_1((a^{\mathrm{\prime }},b^{\mathrm{\prime }})(a^{\mathrm{\prime }\mathrm{\prime }},b^{\mathrm{\prime }\mathrm{\prime }}))}& {\displaystyle =(2a^{\mathrm{\prime }}+2(-1{)}^{b^{\mathrm{\prime }}}{a}^{\mathrm{\prime }\mathrm{\prime }}+(b^{\mathrm{\prime }}+b^{\mathrm{\prime }\mathrm{\prime }}<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>2),b^{\mathrm{\prime }}+b^{\mathrm{\prime }\mathrm{\prime }}<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>2),}\\ {\displaystyle {\varphi }_1(a^{\mathrm{\prime }},b^{\mathrm{\prime }}){\varphi }_1(a^{\mathrm{\prime }\mathrm{\prime }},b^{\mathrm{\prime }\mathrm{\prime }})}& {\displaystyle =(2a^{\mathrm{\prime }}+b^{\mathrm{\prime }}+(-1{)}^{b^{\mathrm{\prime }}}(2a^{\mathrm{\prime }\mathrm{\prime }}+b^{\mathrm{\prime }\mathrm{\prime }}),b^{\mathrm{\prime }}+b^{\mathrm{\prime }\mathrm{\prime }}<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>2)\mathrm{.}}\end{array}$ The first coordinates agree because $b^{\mathrm{\prime }}+(-1{)}^{b^{\mathrm{\prime }}}{b}^{\mathrm{\prime }\mathrm{\prime }}=b^{\mathrm{\prime }}+b^{\mathrm{\prime }\mathrm{\prime }}<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>2$ as an element of $\{0,1\}$. Equality of images again gives equal parity coordinates and then $2a^{\mathrm{\prime }}\equiv 2a^{\mathrm{\prime }\mathrm{\prime }}(\mathrm{m}\mathrm{o}\mathrm{d}{2}^r)$, hence $a^{\mathrm{\prime }}=a^{\mathrm{\prime }\mathrm{\prime }}(\mathrm{m}\mathrm{o}\mathrm{d}{2}^{r-1})$; so ${\varphi }_1$ is an injective homomorphism. It sends the child generators to $x^2,yx$, its image is $K_1$, and it sends $(u,1)$ to $(2u+1,1)=(s,1)$. Thus each child oracle $F_i=F\circ {\varphi }_i$ hides the child reflection subgroup on left cosets: equality under $F_i$ is ambient left-coset equality, and the group isomorphism identifies that coset relation inside $K_i$. Each child oracle query costs one parent $F$ query plus at most the two CNOT address-copy gates specified in [F7]. The recursive slope is $u$ modulo $2^{r-1}$, so the returned value is $s=2u$ or $s=2u+1$ respectively.

There are at most $n$ non-base recursive calls. Each uses $M$ coset samples and hence $M$ named $F$ queries; the direct terminal branch uses at most 64 more. If $F$ is compiled from $f,g$, [F8] makes each $F$ call four calls. By step 4.1 each recursive call has failure at most $m\exp (-2^{m\mathrm{/}3-1})$; a union bound over at most $n$ calls gives $\min \{1,nm{e}^{-2^{m\mathrm{/}3-1}}\}$. With $M=3\cdot 2^{3m}$, the query bound is $nM+64$.

Each sample uses $r+1$ Hadamards and one exact $r$-qubit QFT with $O(r^2)$ ideal gates by [F5], plus one oracle call. Each pair uses one CNOT and one measurement. At most $M\mathrm{/}2$ pairs occur per stage and at most $m$ stages per recursive call; summing over at most $n$ calls with $r\le n$ gives $O(nM(n^2+m))=O(n^{3}M)$ sample and pair gates. A root-oracle query at recursion depth $d$ passes through at most $d\le n$ coordinate maps, each using at most two CNOTs; over at most $nM+64$ queries this adds $O(n^{2}M)$ gates, also within $O(n^{3}M)$. Gates implementing the named $F$ interface itself are separate: an explicit $F$ circuit with at most $G_F(n)$ gates per call contributes $O((nM+64)G_F(n))$ gates, while the hidden-shift wrapper contributes $O((nM+64)w_F)$ selector gates and four $f\mathrm{/}g$ queries per $F$ call by [F8]. Any explicit circuits implementing $f$ and $g$ have their own separately charged gate costs.

Stable comparison sorting of at most $M$ labels of at most $n$ bits costs $O(Mn\log M)$ bit operations per stage; at most $m$ stages in each of at most $n$ calls give $O(n^{2}mM\log M)=O(n^2{m}^{2}M)$ classical bit operations since $\log M=O(m)$. The active list uses at most $Mn$ classical bits. By the explicit discard before recursion in [F7], only one active list is retained at a time. A nested coordinate-map query uses at most $n$ clean address bits; one sample uses $O(n+w_F)$ further query-register qubits and the supplied or constructed oracle workspace is $a_F$. Total quantum workspace is $O(M+n+w_F+a_F)$. With $m=\mathrm{\Theta }(\sqrt{n})$ and $M=3\cdot 2^{3m}$, the named-query count, internal sieve-gate count and classical list-processing count are $2^{O(\sqrt{n})}=2^{O(\sqrt{{\log }_{2}N})}$ up to polynomial factors in $n$; total workspace and oracle-implementation gate costs retain the interface-dependent terms stated above. These are ideal-gate/query/list-processing bounds; compiling exact controlled phases into a finite gate set requires a separate cost contract and is not asserted.