On the success probability of quantum order finding
This improves the reliability of quantum factoring algorithms for cryptography, though it is incremental as it builds on Shor's method with classical post-processing enhancements.
The paper tackles the problem of guaranteeing a high success probability for Shor's quantum order-finding algorithm in a single run, proving a lower bound that ensures success probabilities exceeding 1 - 10^{-4} for moderate orders and tending to one asymptotically.
We prove a lower bound on the probability of Shor's order-finding algorithm successfully recovering the order $r$ in a single run. The bound implies that by performing two limited searches in the classical post-processing part of the algorithm, a high success probability can be guaranteed, for any $r$, without re-running the quantum part or increasing the exponent length compared to Shor. Asymptotically, in the limit as $r$ tends to infinity, the probability of successfully recovering $r$ in a single run tends to one. Already for moderate $r$, a high success probability exceeding e.g. $1 - 10^{-4}$ can be guaranteed. As corollaries, we prove analogous results for the probability of completely factoring any integer $N$ in a single run of the order-finding algorithm.