Success probability and repetition for modular order finding

By [F1], $r$ is a positive integer and $r\le \phi (N)\le N$: write $\phi (N)=dr$ with integer $d$ by divisibility in [F1]. The group contains its identity, so $\phi (N)>0$; since $r>0$, $d>0$ and thus $d\ge 1$. Consequently $r\le \phi (N)$, while the group counts only standard residue representatives and so $\phi (N)\le N$. The orbit $\mathrm{\mid }{x}^s<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>N⟩$, $0\le s<r$, consists of distinct valid computational-basis vectors, since equality of two residues would imply a smaller positive power of $x$ is $1$.

The algorithm starts with $a_0=x$ and $b_0=x^{-1}$ in standard representatives. Suppose $a_j\equiv x^{2^j}$ and $a_j{b}_j\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}N)$. Squaring the first identity gives $a_{j+1}\equiv x^{2^{j+1}}$, and the two loop updates give $a_{j+1}{b}_{j+1}\equiv (a_j{b}_j{)}^2\equiv 1$. Induction proves both identities for all $j<m$; every constant remains in $[0,N)$ and is a unit with the supplied inverse. On valid residues, repeated application of [F2] therefore gives $U_x^{2^j}\mathrm{\mid }z⟩=\mathrm{\mid }{a}_{j}z<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>N⟩$; on invalid encodings both this power and the multiplier are identity. Thus each controlled multiplier in the QPE gate list is the required controlled power on the full data register, with its work returned clean.

Define $\mathrm{\mid }{\psi }_k⟩=r^{-1\mathrm{/}2}{\sum }_{s=0}^{r-1}{e}^{-2\pi iks\mathrm{/}r}\mathrm{\mid }{x}^s<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>N⟩$ for $0\le k<r$. The shift action in [F2] gives $U_x\mathrm{\mid }{\psi }_k⟩=e^{2\pi ik\mathrm{/}r}\mathrm{\mid }{\psi }_k⟩$, including the wrap from $s=r-1$ to $s=0$. By [F11] and [F3] these are orthonormal unit vectors; the same character sum gives $\mathrm{\mid }1⟩=r^{-1\mathrm{/}2}{\sum }_{k=0}^{r-1}\mathrm{\mid }{\psi }_k⟩$.

Apply the QPE circuit from [F4] to this decomposition. Its outcome law is the uniform mixture over $k=0,\dots ,r-1$, each phase being $k\mathrm{/}r$; this uses the superposition law in [F4], rather than an eigenvector promise for $\mathrm{\mid }1⟩$. There are exactly $\phi (r)$ indices with $\gcd (k,r)=1$, counted by [F5].

For each coprime $k$, [F4] gives probability at least $4\mathrm{/}{\pi }^2$ to a nearest grid label. Here $m=2n+3$, $Q=2^m>4N^2$, and $r\le N$ by step 1.1, so the reconstruction correctness theorem applies and returns reduced denominator $r$ on that event. By [F6], $x^r=1$; hence the algorithm's exact verification retains this denominator. Summing the disjoint eigenspace-mixture probabilities gives one-sample success at least $(4\mathrm{/}{\pi }^2)\phi (r)\mathrm{/}r$. By [F5] and $r\le N$, this is at least $4\mathrm{/}[{\pi }^2(1+{\log }_{2}N)]$.

Every retained $q$ passes $x^q=1$, so [F6] implies $r\mid q$. If the exact denominator $r$ is ever retained, no retained candidate is smaller than $r$ and $r$ itself is present; the algorithm's minimum rule therefore returns $r$.

First put $\theta =\pi \mathrm{/}4$. Since $\pi >0$ by [F9], $0<\theta <\pi \mathrm{/}2$. The cofunction law [F8] gives $\sin \theta =\cos \theta$; strict monotonicity and the endpoint values in [F9] show both are positive. Thus [F10] gives $\tan (\pi \mathrm{/}4)=1$, and [F7] at $s=4$ gives $2\pi <O_4=8\tan (\pi \mathrm{/}4)=8$, so $\pi <4$. Now put $n=\lceil {\log }_{2}N\rceil$ and $u=1\mathrm{/}[4(n+1)]$. The one-sample lower bound in step 4.1 and $\pi <4$, together with $1+{\log }_{2}N\le n+1$, give $p\ge u$. Independent resets make the $t=4(n+1)b$ samples independent, hence the probability that no successful sample occurs is at most $(1-u{)}^t$. Since $1-u\le (1+u{)}^{-1}$, and with integer $K=4(n+1)$ the binomial expansion gives $(1+1\mathrm{/}K{)}^K\ge 1+K(1\mathrm{/}K)=2$, we obtain $(1-u{)}^{Kb}\le 2^{-b}$. By step 5.1, the output is the exact order except on this event.

For arbitrary $0<\delta <1$, choosing $b=\lceil {\log }_2(1\mathrm{/}\delta )\rceil$ gives $2^{-b}\le \delta$. Thus the stated guarantee follows without using an inexact floating-point threshold.