On the success probability of quantum order finding
arXiv:2201.07791 · doi:10.1145/3655026
Abstract
We prove a lower bound on the probability of Shor's order-finding algorithm successfully recovering the order 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 , without re-running the quantum part or increasing the exponent length compared to Shor. Asymptotically, in the limit as tends to infinity, the probability of successfully recovering in a single run tends to one. Already for moderate , a high success probability exceeding e.g. can be guaranteed. As corollaries, we prove analogous results for the probability of completely factoring any integer in a single run of the order-finding algorithm.
arXiv commentThis 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 (11)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Shor's Factoring Algorithm and Modern Cryptography. An Illustration of the Capabilities Inherent in Quantum Computers
- Quantum algorithms for computing short discrete logarithms and factoring RSA integers
- Error bounds for the asymptotic expansion of the Hurwitz zeta function
- Shor's discrete logarithm quantum algorithm for elliptic curves
- A Refinement of Shor's Algorithm
- A Precise Error Bound for Quantum Phase Estimation
- Probability Analysis of a Quantum Computer
- On the success probability of the quantum algorithm for the short DLP
- Benchmarks for quantum computers from Shor's algorithm
- Recovering the Period in Shor's Algorithm with Gauss' Algorithm for Lattice Basis Reduction