When Noisy Quantum Order Finding Remains Recoverable for Shor's Algorithm

• URL: http://arxiv.org/abs/2605.16074v1
• Date: Fri, 15 May 2026 15:35:31 GMT
• Title: When Noisy Quantum Order Finding Remains Recoverable for Shor's Algorithm
• Abstract summary: We analyze 680 distributions from IBM quantum systems across problem instances and circuit settings.<n>We find that recoverability is strongly associated with residual comb-like structure in the measured distribution.<n>Some highly distorted distributions remain recoverable when one verified denominator dominates the post-processing mass.
• Score: 0.06610877051761614
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Order finding is the core subroutine of Shor's algorithm. On NISQ hardware, phase estimation output distributions are often distorted by noise, making correct order recovery difficult. We study recoverability in noisy order finding: given a measured precision-register distribution, when does standard classical post-processing still return the true order? We analyze 680 distributions from IBM quantum systems across problem instances and circuit settings. For each distribution, we apply continued-fraction post-processing with modular verification and define recoverability as whether the recovered order equals the true one. We characterize each distribution using four features: autocorrelation peak strength, normalized entropy, dominant verified mass fraction, and verified margin fraction. We evaluate these quantities using marginal feature comparisons, single-feature AUROC analysis, and multivariate tree-based classifiers. We use random-forest permutation importance to assess which quantities contribute distinct predictive information once the other features are known. To make classification behavior interpretable, we train a decision tree that exposes threshold rules for recoverable and non-recoverable distributions. We find that recoverability is strongly associated with residual comb-like structure in the measured distribution and the way verified probability mass is organized across candidate denominators. The dominant verified mass fraction is the strongest single-feature indicator of recoverability, and tree-based analysis shows it also provides the primary split in an interpretable threshold description. Some highly distorted distributions remain recoverable when one verified denominator dominates the post-processing mass, while some visibly structured distributions fail because classical post-processing favors an incorrect verified denominator.

Related papers

• When Does Low-Bit Quantization Preserve the Decisions of Vector Search? [13.71460633144793]
  Low-bit quantization can achieve high recall on some vector representations and fail sharply on others.<n>We study quantized vector search at the level of the comparisons consumed by ranking and graph-pruning algorithms.<n>Across learned, classical, and synthetic embeddings, standardized exact margins predict held-out ranking and pruning flip rates substantially better than global rank correlation.
  arXiv  Detail & Related papers  (2026-09-09T08:06:50Z)
• Information-Calibrated Quantum Diffusion: Aligning Forward Noise with Reverse Recoverability [10.481986290704821]
  We introduce the classical--quantum information decrement $_t=I(X:Q_t-1)-I(X:Q_t) as an intrinsic diffusion coordinate.<n>Along depolarization, equalizing $_t$ yields the unique minimax discretization of the forward information loss.
  arXiv  Detail & Related papers  (2026-08-14T08:44:51Z)
• How Useful is Causal Invariance for Domain Adaptation in Finite-Sample Settings? [58.740078141879984]
  Machine learning models often degrade when they are deployed on a target distribution that differs from the source distributions they were trained on.<n>Recent work in causality-based domain generalization has shown how shared causal structure can induce invariant predictors.<n>In this paper, we study when full or partial causal knowledge can provably improve supervised domain adaptation.
  arXiv  Detail & Related papers  (2026-06-10T21:07:49Z)
• From Order to Distribution: A Spectral Characterization of Forgetting in Continual Learning [28.30104646642165]
  citetevron2022catastrophic analyzes forgetting under random orderings of a fixed task collection.<n>We study an exact-fit linear regime in which tasks are sampled i.i.d. from a task distribution$$, and ask how the generating distribution itself governs forgetting.
  arXiv  Detail & Related papers  (2026-04-15T04:29:00Z)
• Subsystem Statistics and Conditional Self-Similarity of Random Quantum States [0.0]
  We analytically derive the bit-string probability distributions of subsystems of random pure states and depolarized random states.<n>We identify the exact Beta distribution as the universal statistical law of random quantum states.<n>We provide a scalable, rigorous framework for validating random circuit sampling via subsystem or conditional cross-entropy benchmarking.
  arXiv  Detail & Related papers  (2026-02-23T02:38:29Z)
• Shift Before You Learn: Enabling Low-Rank Representations in Reinforcement Learning [56.87989363424]
  We show that a low-rank structure naturally emerges in the shifted successor measure.<n>We quantify the amount of shift needed for effective low-rank approximation and estimation.
  arXiv  Detail & Related papers  (2025-09-05T15:48:20Z)
• Closed-Form Beta Distribution Estimation from Sparse Statistics with Random Forest Implicit Regularization [0.0]
  This work advances distribution recovery from sparse data and ensemble classification through three main contributions.<n>First, we introduce a closed-form estimator that reconstructs scaled beta distributions from limited statistics.<n>Second, we establish a link between classification accuracy and distributional closeness by deriving error bounds.<n>Third, we show that zero-variance features act as an implicit regularizer, increasing selection probability for mid-ranked predictors.
  arXiv  Detail & Related papers  (2025-07-31T17:55:07Z)
• How many measurements are enough? Bayesian recovery in inverse problems with general distributions [0.7366405857677226]
  We study the sample complexity of Bayesian recovery for solving inverse problems with general prior, forward operator and noise distributions.<n>As a key application, we specialize to generative priors, where $mathcalP$ is the pushforward of a latent distribution via a Deep Neural Network (DNN)
  arXiv  Detail & Related papers  (2025-05-15T18:11:54Z)
• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Sampling (AIS) synthesizes weighted samples from an intractable distribution. We propose the Constant Rate AIS algorithm and its efficient implementation for $alpha$-divergences.
  arXiv  Detail & Related papers  (2023-06-27T08:15:28Z)
• Regularized Vector Quantization for Tokenized Image Synthesis [126.96880843754066]
  Quantizing images into discrete representations has been a fundamental problem in unified generative modeling. deterministic quantization suffers from severe codebook collapse and misalignment with inference stage while quantization suffers from low codebook utilization and reconstruction objective. This paper presents a regularized vector quantization framework that allows to mitigate perturbed above issues effectively by applying regularization from two perspectives.
  arXiv  Detail & Related papers  (2023-03-11T15:20:54Z)
• Exact Recovery in the General Hypergraph Stochastic Block Model [92.28929858529679]
  This paper investigates fundamental limits of exact recovery in the general d-uniform hypergraph block model (d-HSBM) We show that there exists a sharp threshold such that exact recovery is achievable above the threshold and impossible below it.
  arXiv  Detail & Related papers  (2021-05-11T03:39:08Z)
• Batch Stationary Distribution Estimation [98.18201132095066]
  We consider the problem of approximating the stationary distribution of an ergodic Markov chain given a set of sampled transitions. We propose a consistent estimator that is based on recovering a correction ratio function over the given data.
  arXiv  Detail & Related papers  (2020-03-02T09:10:01Z)

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.