Bounded-error success of Shor factoring

If $N$ is even or a perfect power, preprocessing returns a proper factor by [F1], so the theorem holds with probability one. Otherwise $N$ is odd, composite, and not a perfect power, so [F3] applies.

By [F4], the sampler halts almost surely and has uniform finite output law. For each unit representative $a$, let $Y_a$ be the finite set of order-finding measurement transcripts and ${\mu }_a$ its probability mass function; for a nonunit use a singleton $Y_a$ of mass one. One attempt has finite terminal outcome space ${\mathrm{\Omega }}_N=\{(a,y):1\le a<N,y\in Y_a\}$ with weights $w_N(a,y)={\mu }_a(y)\mathrm{/}(N-1)$: the sampler marginal is [F4], the subsequent fresh measurement law is ${\mu }_a$, and these weights sum to one. All conditioning here is on this finite space as in [F7]. Conditional on the unit event $U$, [F2] makes $[a{]}_N$ uniform in the unit group. Let $G\subseteq U$ be the representatives whose true-order reduction succeeds, so [F3] gives $\mathbb{P}(G\mid U)\ge 1\mathrm{/}2$. For each $a\in G$, [A2] gives exact-order probability at least $3\mathrm{/}4$; summing its transcript weights gives $\mathbb{P}(G\text{ and exact order}\mid U)\ge (3\mathrm{/}4)\mathbb{P}(G\mid U)\ge 3\mathrm{/}8$. On that event the algorithm returns a proper factor. This uses a pointwise order-finding bound, without assuming independence between the unit and its measurement outcome.

Let $p$ be the probability that a sampled residue is a unit. The attempt succeeds with probability at least $(1-p)+p(3\mathrm{/}8)=1-5p\mathrm{/}8\ge 3\mathrm{/}8$. Any output is correct by [F5]; a nonminimal or otherwise unsuccessful order candidate can only cause this attempt to continue.

Preassign $T$ independent terminal records with the finite product law $w_N^{\otimes T}$. By the fresh randomness in [F6], this is the joint terminal law of the actual attempts; stopping at the first success simply leaves subsequent records unused. The event that any of these finitely many samplers does not halt has probability zero by [F4]. Let $B_i$ be the coordinate event that attempt $i$ returns no factor. Step 2.1 gives $\mathbb{P}(B_i)\le 5\mathrm{/}8$, and finite coordinate independence [F6] gives $\mathbb{P}({\bigcap }_{i=1}^T{B}_i)={\prod }_{i=1}^T\mathbb{P}(B_i)\le (5\mathrm{/}8{)}^T\le \delta$. Thus the probability of returning a proper factor is at least $1-\delta$.