Asymptotic Vanishing of the Success Probability in Shor's Algorithm

• URL: http://arxiv.org/abs/2510.06271v1
• Date: Mon, 06 Oct 2025 11:00:58 GMT
• Title: Asymptotic Vanishing of the Success Probability in Shor's Algorithm
• Authors: João P. da Cruz,
• Abstract summary: As N -> infinity, the multiplicative groups Omega_N = (Z/NZ)x form a non-tight family of probability spaces, and the probability weight associated with successful bases decays as 1/phi(N)<n>Monte Carlo simulations up to N = 106 confirm this decay and the absence of a stationary success probability.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Shor's factoring algorithm guarantees a success probability of at least one half for any fixed modulus N = pq with distinct primes p and q. We show that this guarantee does not extend to the asymptotic regime. As N -> infinity, the multiplicative groups Omega_N = (Z/NZ)^x form a non-tight family of probability spaces, and the probability weight associated with successful bases, proportional to p(success | a', N) p(a' | N), decays as 1/phi(N). The ensemble of uniform measures {mu_N} therefore admits no weak limit, implying an asymptotic loss of ergodicity. Monte Carlo simulations up to N <= 10^6 confirm this decay and the absence of a stationary success probability. These results demonstrate that the "expected polynomial time" in order finding is only locally defined: no global expectation exists once the arithmetic domain expands. The asymptotic vanishing of success probability explains the empirical absence of large-N implementations of Shor's algorithm and sets a fundamental limit on the scalability of quantum factoring.

Related papers

• Quantitative Convergence Analysis of Projected Stochastic Gradient Descent for Non-Convex Losses via the Goldstein Subdifferential [2.179637644332717]
  This paper presents an analysis of projected variance reduction for non-symotic convergence measures.<n> Convergence is a gradient to the SGD Goldstein subdifferential gradient by the constraints.
  arXiv  Detail & Related papers  (2025-10-03T05:35:42Z)
• On the Algorithmic Information Between Probabilities [6.5268245109828005]
  We extend algorithmic conservation inequalities to probability measures. The amount of self information of a probability measure cannot increase when submitted to randomized processing. We show that given a quantum measurement, for an overwhelming majority of pure states, no meaningful information is produced.
  arXiv  Detail & Related papers  (2023-03-13T17:20:27Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  We consider the non-AL equilibrium nonconptotic objective function in two-player zero-sum continuous games. Our novel insights into the particle-based algorithms for continuous distribution strategies are presented.
  arXiv  Detail & Related papers  (2023-03-02T05:08:15Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  We propose algorithms with high-probability convergence results under less restrictive assumptions. These results justify the usage of the considered methods for solving problems that do not fit standard functional classes in optimization.
  arXiv  Detail & Related papers  (2023-02-02T10:37:23Z)
• A lower confidence sequence for the changing mean of non-negative right heavy-tailed observations with bounded mean [9.289846887298854]
  A confidence sequence produces an adapted sequence of sets for a predictable parameter sequence with a time-parametric coverage guarantee. This work constructs a non-asymptotic lower CS for the running average conditional expectation whose slack converges to zero.
  arXiv  Detail & Related papers  (2022-10-20T09:50:05Z)
• On the success probability of quantum order finding [0.0]
  We prove a lower bound on the probability of Shor's order-finding algorithm successfully recovering the order $r$ in a single run. Asymptotically, in the limit as $r$ tends to infinity, the probability of successfully recovering $r$ in a single run tends to one.
  arXiv  Detail & Related papers  (2022-01-19T18:58:18Z)
• Time-uniform central limit theory and asymptotic confidence sequences [34.00292366598841]
  Confidence sequences (CS) provide valid inference at arbitrary stopping times and incur no penalties for "peeking" at the data. CSs are nonasymptotic, enjoying finite-sample guarantees but not the aforementioned broad applicability of confidence intervals. Asymptotic CSs forgo nonasymptotic validity for CLT-like versatility and (asymptotic) time-uniform guarantees.
  arXiv  Detail & Related papers  (2021-03-11T05:45:35Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  We study the problem of solving strongly convex and smooth unconstrained optimization problems using first-order algorithms. We devise a novel, referred to as Recursive One-Over-T SGD, based on an easily implementable, averaging of past gradients. We prove that it simultaneously achieves state-of-the-art performance in both a finite-sample, nonasymptotic sense and an sense.
  arXiv  Detail & Related papers  (2020-08-28T14:46:56Z)
• Free Energy Wells and Overlap Gap Property in Sparse PCA [81.64027805404483]
  We study a variant of the sparse PCA (principal component analysis) problem in the "hard" regime. We show bounds on the depth of free energy wells for various Gibbs measures naturally associated to the problem. We prove that the Overlap Gap Property (OGP) holds in a significant part of the hard regime.
  arXiv  Detail & Related papers  (2020-06-18T17:18:02Z)
• Metrizing Weak Convergence with Maximum Mean Discrepancies [88.54422104669078]
  This paper characterizes the maximum mean discrepancies (MMD) that metrize the weak convergence of probability measures for a wide class of kernels. We prove that, on a locally compact, non-compact, Hausdorff space, the MMD of a bounded continuous Borel measurable kernel k, metrizes the weak convergence of probability measures if and only if k is continuous.
  arXiv  Detail & Related papers  (2020-06-16T15:49:33Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  We study the inequality and non-asymptotic properties of approximation procedures with Polyak-Ruppert averaging. We prove a central limit theorem (CLT) for the averaged iterates with fixed step size and number of iterations going to infinity.
  arXiv  Detail & Related papers  (2020-04-09T17:54:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.