Period, Hidden-Shift, and Number-Theoretic Algorithms

Input an integer $n\ge 2$ and the least residue $c\in \{0,\dots ,n-1\}$. Set $(r_{-1},r_0)=(n,c)$ and $(s_{-1},s_0)=(0,1)$. For $i=0,1,\dots$, divide

and update $s_{i+1}$ to the least residue of $s_{i-1}-a_i{s}_i$ modulo $n$. Stop at the first index $i$ for which $r_{i+1}=0$. Return the least residue $s_i$ if $r_i=1$, and return NO_INVERSE otherwise. For $c=0$, the first division has zero divisor under this indexing; handle it separately by returning NO_INVERSE.

The algorithm uses binary integer arithmetic. Its correctness and $O(B^3)$ bit bound for $B=\lceil {\log }_2(n+1)\rceil$ are proved in Correctness and bit cost of the modular inverse recurrence.

The required number-theoretic result on this page is finite cyclic discrete logarithm with an explicit element encoding and an explicit group-operation or coherent-function access profile. The page makes no generic polynomial-time claim for an abstract cyclic group. Each such claim needs a reversible encoding, operation circuits, and their gate and bit costs.

Elliptic-curve and number-field/Pell discussions are context only. They do not supply an elliptic-curve algorithm, a number-field algorithm, or a complexity bound here. Childs §7.1 gives the algebraic addition formulas and says an explicit check (for example, with Mathematica) can establish commutativity, closure, and associativity, but does not carry out that check. In Proos–Zalka §3, the authors state the elliptic-curve group result and refer to [14], J. Chahal's Topics in Number Theory, for a proof. Neither passage supplies a detailed local proof that this library can use as an established proof supplier. A future elliptic-curve branch needs local proofs of the nonsingular-cubic group law and associativity, explicit point and field encodings, reversible addition, subgroup-order hypotheses, and gate and bit costs. Number-field branches likewise need explicit representations, arithmetic, reduction, and classical output procedures.

For $n\ge 2$ and $0\le c<n$, Extended-Euclidean modular inverse with bounded bit cost returns NO_INVERSE exactly when $c$ is not a unit modulo $n$, and otherwise returns the unique $u\in \{0,\dots ,n-1\}$ with $cu\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}n)$. With $B=\lceil {\log }_2(n+1)\rceil$, the algorithm uses $O(B^3)$ bit operations.

Let $N\ge 2$, $s\in \mathbb{Z}\mathrm{/}N\mathbb{Z}$, and

for $k\in \mathbb{Z}\mathrm{/}N\mathbb{Z}$. On two ordered qubits define $C\mathrm{\mid }a,b⟩=\mathrm{\mid }a,b\oplus a⟩$ for $a,b\in \{0,1\}$. Apply $C$ to $\mathrm{\mid }{\psi }_k⟩\otimes \mathrm{\mid }{\psi }_{\mathrm{\ell }}⟩$ and projectively measure the second qubit in its computational basis. Each outcome has probability $1\mathrm{/}2$. After discarding the measured qubit, outcome $0$ leaves the first qubit in $\mathrm{\mid }{\psi }_{k+\mathrm{\ell }}⟩$; outcome $1$ leaves it in $\mathrm{\mid }{\psi }_{k-\mathrm{\ell }}⟩$ up to a global phase. The readout is implemented by the Lüders projective instrument of the stated computational-basis projections, so the conditional-state claims refer to its normalized branches.

Write $A=\mathbb{Z}\mathrm{/}N\mathbb{Z}$ additively, $N\ge 2$, and identify its generalized-dihedral group with $A\times \mathbb{Z}\mathrm{/}2\mathbb{Z}$ under

Let $H_s=\{(0,0),(s,1)\}$ and let a total encoded function $F$ be constant on each left coset of $H_s$ and distinct on different left cosets. Start in the uniform state on the $2N$ group elements, evaluate the coherent XOR oracle for $F$ into a zero output register, discard that register, apply the positive-sign ${\mathrm{QFT}}_N$ to the first coordinate, and measure that coordinate. The measured $k\in \mathbb{Z}\mathrm{/}N\mathbb{Z}$ is uniform. Conditional on $k$, the remaining qubit is, up to a global phase,

The coordinate readout uses the Lüders projective instrument for the projections ${\mathrm{\Pi }}_k=\mathrm{\mid }k⟩⟨k\mathrm{\mid }\otimes I_2$. The stated conditional qubit is the post-measurement state after discarding the measured coordinate.

The input group is a finite abelian group $A$ supplied in explicit invariant-factor coordinates $A=\mathbb{Z}\mathrm{/}{n}_1\mathbb{Z}\times \cdots \times \mathbb{Z}\mathrm{/}{n}_d\mathbb{Z}$, with componentwise addition and the empty product allowed. The finite set $S$ is supplied with an injective fixed-length bit encoding. The input functions $f,g:A\to S$ are injective and have coherent XOR oracles with explicitly declared access and costs.

The promise is that there is a unique $s\in A$ such that

The output is the coordinate encoding of $s$. The definition makes no claim that a group presented only by black-box operations comes with invariant-factor coordinates, efficient uniform preparations, efficient group operations, or an efficient implementation of either oracle.

A finite cyclic discrete-logarithm instance consists of a cyclic group $G=⟨g⟩$ of known exact order $q\ge 2$ and an element $x\in G$. Its answer is the unique integer $a\in \{0,\dots ,q-1\}$ satisfying $g^a=x$. Uniqueness follows because $g^u=g^v$ exactly when $u\equiv v(\mathrm{m}\mathrm{o}\mathrm{d}q)$.

For a quantum or bit-cost claim, the instance additionally declares an injective fixed-length encoding $\mathrm{enc}:G\to \{0,1{\}}^w$, with $w\ge \lceil {\log }_{2}q\rceil$, and one of the following operation profiles:

1. explicit reversible circuits for multiplication, equality, and any controlled multiplication used by the algorithm, with gate and clean-work costs; or
2. named group-operation oracles with a separate query charge for each operation. A controlled call is available only if that controlled operation is explicitly supplied and charged.

The associated hidden-subgroup function is $f:{\mathbb{Z}}_q\times {\mathbb{Z}}_q\to G$, $f(u,v)=g^u{x}^v$. A direct coherent XOR oracle for its fixed-length encoding is a separate supplied interface; if it is supplied, one call costs one $f$ query. Group-operation oracles do not automatically supply this function oracle, a controlled call, an inverse call, a gate implementation, or a classical bit-cost bound. No efficient implementation is asserted for every abstract finite cyclic group.

The problem definition does not require $q$ to be prime. For $x=g^a$, the function $f$ is analyzed by the separate hidden-subgroup lemma on this page.

Let $A$ be a finite abelian group in explicit additive coordinates, and let $f,g:A\to S$ satisfy the hidden-shift promise of Finite abelian hidden-shift promise: both maps are injective and there is a unique $s\in A$ such that $f(a)=g(a+s)$ for every $a$. Write $D_A=A⋊{\mathbb{Z}}_2$ with

and define $F(a,0)=f(a)$ and $F(a,1)=g(a)$. Then $F$ is constant exactly on the left cosets of the order-two subgroup $H_s=\{(0,0),(s,1)\}=⟨(s,1)⟩$. The subgroup determines the shift uniquely: $H_s=H_t$ implies $s=t$.

If a coherent XOR oracle for this $F$ is directly supplied, one $F$-oracle query implements one value query. From only coherent XOR oracles for $f$ and $g$, the $F$-XOR operation can be implemented with four calls total (two to compute the values into scratch registers and two to uncompute them), plus the controlled output XOR; no controlled call to either oracle is assumed. All gate, workspace, and named-oracle query costs remain separately charged.

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.

Let $G=⟨g⟩$ have order $q\ge 2$, let $c\in G$, and let valid fixed-length codes occupy a subset $V\subseteq \{0,1{\}}^w$. Suppose total Boolean circuits are supplied for functions $h_c,h_{c^{-1}}:\{0,1\}\times \{0,1{\}}^w\to \{0,1{\}}^w$, where $h_c(b,z)=\{\begin{array}{ll}z,& b=0,\\ \mathrm{enc}(uc),& b=1,z=\mathrm{enc}(u)\in V,\\ z,& b=1,z\mathrm{\notin }V,\end{array}\mathrm{.}$ For each fixed control $b$, the maps $z\mapsto h_c(b,z)$ and $z\mapsto h_{c^{-1}}(b,z)$ are inverse permutations; the full controlled permutation preserves $b$. Then reversible embedding supplies a clean-ancilla circuit that acts on a control bit and accumulator by

If the two Boolean circuits have at most $S$ non-input nodes and $E$ port uses each, the construction uses at most $12S+8E+5w$ elementary gates and at most $2(S+E)+w$ clean work wires. The gate charge counts each supplied $X$, CNOT, and Toffoli as one gate; no cost for constructing the Boolean descriptions is inferred.

Let $G=⟨g⟩$ have exact order $q\ge 2$, let $x=g^a$, and define $f:{\mathbb{Z}}_q\times {\mathbb{Z}}_q\to G$ by $f(u,v)=g^u{x}^v$. Then

Thus the fibers of $f$ are exactly the additive cosets of the rank-one subgroup $H$ in the finite abelian group ${\mathbb{Z}}_q^2$.

Let $n\ge 1$ and $N=2^n$. Let $F:D_N\to S$ be a total encoded function that is constant on each left coset of $H_s=⟨y{x}^s⟩$ and takes distinct values on different left cosets, accessed by a coherent XOR oracle either directly or through Hidden shift as generalized-dihedral hidden subgroup. Equivalently, $F(u)=F(v)$ exactly when $u{H}_s=v{H}_s$, as required by Power-of-two dihedral hidden-subgroup sieve. Use the Lüders instruments specified there for the projective readouts. For $n\le 5$ the direct branch succeeds exactly with at most $64$ $F$ queries. For $n\ge 6$, put $m=\lceil \sqrt{n-1}\rceil$ and $M=3\cdot 2^{3m}$. The locally specified shortened-final-width sieve has failure probability at most $\min \{1,nm\exp (-2^{m\mathrm{/}3-1})\}\mathrm{.}$ It uses at most $nM+64$ named $F$-oracle queries, $O(n^{3}M)$ ideal gates for sieve control and recursive coordinate maps, $O(n^2{m}^{2}M)$ classical bit operations for label sorting and list processing, $O(M+n+w_F+a_F)$ quantum workspace, and $O(nM)$ bits to store all active labels. Here $w_F$ is the output-register width and $a_F$ is additional workspace for the supplied or constructed $F$ implementation. The $O(n^{3}M)$ gate count excludes the implementation of the named $F$ interface itself. An explicit $F$ circuit using $G_F(n)$ gates per call adds $O((nM+64)G_F(n))$ gates. If $F$ is constructed from only the two coherent XOR oracles for a hidden-shift pair, each call uses four $f\mathrm{/}g$ oracle calls and adds $O(w_F)$ ordinary gates for controlled output selection; add $O((nM+64)w_F)$ selector gates, and charge any explicit circuits implementing $f$ and $g$ separately.

Since $m=\mathrm{\Theta }(\sqrt{n})$, the named $F$-query count, sieve gate count, and classical label-processing count are $2^{O(\sqrt{n})}=2^{O(\sqrt{{\log }_{2}N})}$ up to polynomial factors in $n$. The total workspace and any oracle-implementation gate costs retain the explicit interface-dependent terms above. The theorem is confined to power-of-two cyclic orders and supplied exact interfaces. It proves no polynomial-time claim, no arbitrary-$N$ version, and no algorithm for arbitrary finite abelian hidden shift.