Success probability in Shor's Algorithm

2025/05/01 by Abbassi, Ali, Bayle, Lionel
#81P68 20B05 11Y05 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)

paper · doi:10.48550/arxiv.2505.00433

Abstract

This paper aims to determine the exact success probability at each step of Shor's algorithm. Although the literature usually provides a lower bound on this probability, we present an improved bound. The derived formulas enable the identification of all failure cases in Shor's algorithm, which correspond to a success probability of zero. A simulation routine is provided to evaluate the theoretical success probability for a given integer when its prime factorization is known with potential applications in quantum resource estimation and algorithm benchmarking.

Related

• Asymptotic Vanishing of the Success Probability in Shor's Algorithm
• Sharp probability estimates for Shor's order-finding algorithm
• Benchmarks for quantum computers from Shor's algorithm
• Probability Analysis of a Quantum Computer
• Realization of Shor's Algorithm at Room Temperature