On the success probability of quantum order finding

Abstract

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.

This revision resolves a minor issue in Alg. 4, and addresses a number of other minor issues. It furthermore adds a number of extensions and clarifications, in particular with respect to potential optimizations. No key results or findings in the original version of the manuscript are affected by this revision

References in corpus (5)

• Shor's discrete logarithm quantum algorithm for elliptic curves
• Probability Analysis of a Quantum Computer
• Recovering the Period in Shor's Algorithm with Gauss' Algorithm for Lattice Basis Reduction
• Benchmarks for quantum computers from Shor's algorithm
• On the success probability of the quantum algorithm for the short DLP

Cited by in corpus (2)

• Extending Regev's factoring algorithm to compute discrete logarithms
• Tight Success Probabilities for Quantum Period Finding and Phase Estimation