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.
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.
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.
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.
We investigate the sequential version of Shor's order-finding algorithm from the perspective of the imaginarity of quantum channels. By fixing an eigenbranch of the modular multiplication unitary and a target output path, the process is effectively decomposed into a real diagonal factor and a residual phase channel. We find that for the ideal residual phase channel, the three trace-norm induced imaginarity measures are all equal. On good output paths, a smaller residual imaginarity corresponds to a higher single-block success probability. By combining the branch-wise probabilities, we obtain the exact ideal success probability of the sequential order-finding protocol and derive lower and upper bounds in terms of residual phase-channel imaginarity. We further extend the analysis to noisy residual phase channels, and obtain the lower and upper bounds on the noisy success probability. These results clarify the role of imaginarity of channels in Shor's algorithm and provide a refined perspective on quantum-resource behavior in ideal and noisy sequential quantum algorithms.
This paper evaluates quantum recovery of minimal cut set (MCS) structure across eight IBM hardware runs spanning four runtime arms (A1–A4) and two backends (ibm_torino and ibm_marrakesh), using an independent raw-counts recomputation as the authoritative analysis layer. Each arm combines a resilience level (RL0, RL1, or RL2) with a dynamical decoupling (DD) setting (on or off), applied to CL-QUBO fault tree circuits encoding 8 reactor-scale pilot subtrees from a prior hardware study. Each run submitted 8 primitive unified blocs (pubs), one per subtree, at 8,192 shots each with bind parameters [0.2, 0.2]. The canonical analysis spans 64 pubs and 12,800 top-200 rows with zero unresolved issues. The principal finding is that the IBM hardware runs produced nonzero exact and nonzero superset MCS recovery. Across the study, mean top-200 exact hits were 16.6 per pub (range 10.4–22.6 across runs), mean exact MCS mass was 0.074, mean exact-or-superset mass was 0.820, and mean superset-nonexact mass was 0.746. Recovery is present but is not dominated by exact MCS outcomes: approximately 91% of the recovered exact-or-superset probability mass lies in superset-nonexact structure. ibm_torino showed descriptively stronger exact recovery (mean exact hits 20.8 versus 12.5 for ibm_marrakesh), while ibm_marrakesh showed descriptively stronger broad superset-heavy recovery (mean superset hits 146.4 versus 134.3 for ibm_torino). An earlier scorer-layer analysis yielded a zero-recovery interpretation; the independent raw-counts recomputation showed that this was an artifact of a contract mismatch and supersedes the earlier result. This paper does not claim quantum advantage.