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.
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.
Order finding is the core subroutine of Shor’s algorithm. On NISQ hardware, its 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 collected from IBM quantum systems across multiple problem instances and circuit settings. For each distribution, we apply continued-fraction post-processing with modular verification and define recoverability as a binary outcome according to whether the recovered order equals the true one. We then 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 further use random-forest permutation importance to assess which quantities contribute distinct predictive information once the other features are known. To make the resulting classification behavior interpretable, we also train a decision tree that exposes threshold rules for recoverable and non-recoverable distributions. We find that recoverability is strongly associated with both 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 the tree-based analysis shows that 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.
Shor's algorithm contains a classical post-processing part for which we aim to create an efficient, understandable method aside from continued fractions. Let r be an unknown positive integer. Assume that with some constant probability we obtain random positive integers of the form x=[ N k/r ] where [.] is either the floor or ceiling of the rational number, k is selected uniformly at random from {0,1,...,r-1}, and N is a parameter that can be chosen. The problem of recovering r from such samples occurs precisely in the classical post-processing part of Shor's algorithm. The quantum part (quantum phase estimation) makes it possible to obtain such samples where r is the order of some element a of the unit group of Z_n and n is the number to be factored. Shor showed that the continued fraction algorithm can be used to efficiently recover r, since if N>2r^2 then k/r appears in lowest terms as one of the convergents of x/N due to a standard result on continued fractions. We present here an alternative method for recovering r based on the Gauss algorithm for lattice basis reduction, allowing us to efficiently find the shortest nonzero vector of a lattice generated by two vectors. Our method is about as efficient as the method based on continued fractions, yet it is much easier to understand all the details of why it works.
Many quantum algorithms for classically difficult optimization tasks must return high-quality bitstrings from finitely many circuit executions, whereas most quantum error-mitigation methods target expectation values. We study sample-level recovery when measured probability mass is distributed around multiple latent bitstrings, called centers. Each component of the measured probability mass is called a source and we assume that each center is associated with one source. We identify dominance-at every coordinate, more than half of a retained region's probability mass comes from one source and agrees with its center-as a sufficient condition under which majority voting recovers that center with exponentially decreasing error probability. We show that nearest-center assignment, as used in clustering algorithms such as the k-modes algorithm, can fail to produce dominated regions even when the true centers are known. This failure motivates responsibility thresholding and a local dominance screen, whose combination we call dominance-aware (DA) refinement. Synthetic and simulated MaxCut-QAOA experiments show that DA refinement favors precision, while k-modes with DA refinement improves overall center recovery. All procedures are classical post-processing and require no additional quantum-circuit executions.
We consolidate a previously described IBM Quantum ibm_marrakesh compiled Shor-15 readout comparison (128 shots in a RAW configuration versus 8 shots in a preconfigured configuration) with three local, reproducible algorithmic analyses. First, an independent-binomial model quantifies the probability that a hypothetical 4-shot batch meets the original accepted-peak mass threshold of 0.60: at an assumed per-shot peak probability p=0.90 the pass probability is 0.947700, requiring p≈0.902389 for a 95% pass rate. Second, decision-preserving adaptive stopping of an eight-shot binary acceptance rule is proven pathwise by terminating at five accepted peaks or four failures. Under IID p=0.90 it requires 5.544908 shots on average, a 30.69% expected count reduction while preserving the fixed-eight-shot decision, conditional on per-shot feedback. Third, phase-denominator lifting tests a multiple of the measured phase denominator against modular order and factor constraints. For the period-informed compiled N=15, a=2 example this recovers factors from outcomes 0100, 1000 and 1100, versus two directly informative outcomes under the stricter denominator-only diagnostic. A five-shot intermediate candidate achieves a 0.988443 model probability for the joint peak-mass and lifted-evidence criterion at p=0.90, compared with 0.940581 for four and 0.994877 for eight. No new IBM QPU execution, hardware 32× speedup, independently measured throughput improvement or blind Shor period-finding result is claimed. We supply executable scripts, tests, archived local outputs, limitations, and a proposed matched-hardware validation protocol.
v0.3.0 of the multi-base post-processing analysis of Shor's order finding. The original five theorems (v0.2.1, DOI 10.5281/zenodo.20681847) are retained unchanged: (1) noise-invariant determinism, (2) logarithmic coverage time, (3) exact noise scaling 1/g_M(η), (4) conditional compatibility with Regev's 2023 multi-base framework, and (5) a hybrid (C)+Regev b-trick factoring algorithm with closed-form bound matching N=437 empirical mean within 4%. New in v0.3.0: §3.6 of v0.2.1 is *self-corrected*. The previously claimed 'boundary-flip + universal direction stochasticity + plateau/overload' framework is shown to be the finite-trial expression of a single closed form p(σ) = ρ + (p_0 - ρ)·exp(-σ²) derived from the standard phase-noise dephasing of the FFT. The closed form is verified across five algorithm classes — Grover (R²=0.88), Shor pure (0.95), QPE isolated (0.96), Simon (0.99), Hybrid (C)+b-trick (paper §3.6 setup, 0.91). Positioning: analytical complement to Yang-Markidis (arXiv:2605.16074, ICS Workshops '26), whose empirical recoverability model (1-ε)·P_s + ε·distractors has the same structural form; we provide the analytical foundation ε = 1 - exp(-σ²). Implication: SR-based factoring acceleration is precluded by a closed-form bound on |ΔK|. v0.3.0 retracts the 'boundary flip' lexicon as a distinct mechanism; all raw measurement data and theorems 1-5 are retained.
v0.3.0 of the multi-base post-processing analysis of Shor's order finding. The original five theorems (v0.2.1, DOI 10.5281/zenodo.20681847) are retained unchanged: (1) noise-invariant determinism, (2) logarithmic coverage time, (3) exact noise scaling 1/g_M(η), (4) conditional compatibility with Regev's 2023 multi-base framework, and (5) a hybrid (C)+Regev b-trick factoring algorithm with closed-form bound matching N=437 empirical mean within 4%. New in v0.3.0: §3.6 of v0.2.1 is *self-corrected*. The previously claimed 'boundary-flip + universal direction stochasticity + plateau/overload' framework is shown to be the finite-trial expression of a single closed form p(σ) = ρ + (p_0 - ρ)·exp(-σ²) derived from the standard phase-noise dephasing of the FFT. The closed form is verified across five algorithm classes — Grover (R²=0.88), Shor pure (0.95), QPE isolated (0.96), Simon (0.99), Hybrid (C)+b-trick (paper §3.6 setup, 0.91). Positioning: analytical complement to Yang-Markidis (arXiv:2605.16074, ICS Workshops '26), whose empirical recoverability model (1-ε)·P_s + ε·distractors has the same structural form; we provide the analytical foundation ε = 1 - exp(-σ²). Implication: SR-based factoring acceleration is precluded by a closed-form bound on |ΔK|. v0.3.0 retracts the 'boundary flip' lexicon as a distinct mechanism; all raw measurement data and theorems 1-5 are retained.