pith. sign in

arxiv: 2605.16074 · v1 · pith:CAIRYWKBnew · submitted 2026-05-15 · 🪐 quant-ph · cs.ET

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

Qingxin Yang , Stefano Markidis This is my paper

Pith reviewed 2026-05-20 18:45 UTC · model grok-4.3

classification 🪐 quant-ph cs.ET
keywords Shor's algorithmorder findingphase estimationquantum noiseNISQ devicescontinued fractionrecoverabilityIBM quantum hardware
0
0 comments X

The pith

Recoverability in noisy quantum order finding for Shor's algorithm tracks the dominant verified mass fraction in the output distribution.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper analyzes 680 measured distributions from IBM quantum hardware to determine when continued-fraction post-processing still extracts the true order from noisy phase estimation results. It shows that success correlates with residual comb-like structure and the concentration of verified probability mass on correct candidate denominators. The dominant verified mass fraction stands out as the strongest single predictor, with tree-based models confirming it as the primary decision threshold. Some visibly noisy outputs succeed when one verified denominator captures most mass, while structured ones can fail if post-processing selects the wrong candidate. This matters because it identifies which noisy runs on present hardware can still produce correct results without additional error mitigation.

Core claim

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.

What carries the argument

Dominant verified mass fraction extracted after continued-fraction expansion and modular verification of the measured probability distribution, which quantifies concentration on a single correct candidate and drives the classification of recoverability.

If this is right

  • Distributions that look heavily distorted can still yield the correct order when one verified denominator holds the majority of the post-processing mass.
  • Distributions with visible comb-like peaks can fail recovery if the classical step selects an incorrect verified denominator.
  • Single-feature AUROC scores rank dominant verified mass fraction highest, followed by autocorrelation and entropy measures.
  • An interpretable decision tree splits first on the dominant mass fraction and then on verified margin to label recoverable cases.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Real-time computation of the dominant mass fraction during execution could let hardware discard low-value shots before full post-processing.
  • The same feature analysis might apply to other quantum algorithms that rely on continued-fraction extraction from phase estimation.
  • Hardware-specific calibration of the mass-fraction threshold could improve yield without changing the quantum circuit itself.
  • Testing whether the feature ranking persists on superconducting versus trapped-ion platforms would clarify hardware dependence.

Load-bearing premise

The analysis assumes that continued-fraction expansion with modular verification is the only post-processing method considered and that the 680 collected distributions represent typical noisy order-finding instances from actual Shor's runs.

What would settle it

Generate new sets of noisy order-finding distributions on the same hardware with varying circuit depths and noise levels, then measure how accurately the dominant verified mass fraction threshold predicts actual recovery success rates.

Figures

Figures reproduced from arXiv: 2605.16074 by Qingxin Yang, Stefano Markidis.

Figure 1
Figure 1. Figure 1: Top: Recoverability despite weak global histogram structure. Although the measured distribution is diffuse and the [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Residual structure and recoverability. Each point [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Distribution of four features by recoverability. The [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Decision tree classifier for predicting recoverability. Internal nodes show split rules based on [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Permutation importance from a random-forest clas [PITH_FULL_IMAGE:figures/full_fig_p007_5.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript examines recoverability of the true order in noisy quantum order-finding for Shor's algorithm. Using 680 measured distributions from IBM quantum systems, the authors apply continued-fraction expansion with modular verification to label each distribution as recoverable or not. They extract four features from the distributions: autocorrelation peak strength, normalized entropy, dominant verified mass fraction, and verified margin fraction. Through univariate AUROC analysis and multivariate random forest classifiers with permutation importance, they identify the dominant verified mass fraction as the strongest indicator of recoverability. An interpretable decision tree is trained to provide threshold rules based on these features.

Significance. If the results hold, this study offers practical guidance on when noisy phase estimation outputs in order finding can still yield the correct order using standard post-processing. The empirical analysis on real hardware data and the focus on interpretable features contribute to understanding the interplay between quantum noise and classical recovery in Shor's algorithm on NISQ devices. The use of permutation importance and decision trees adds transparency to the feature contributions.

major comments (1)
  1. The recoverability definition and the two verification-derived features (dominant verified mass fraction, verified margin fraction) are computed from the same continued-fraction + modular verification pipeline. This makes the reported strong association and decision-tree thresholds specific to this classical post-processing choice; the mapping may change under alternative recovery procedures such as direct maximum-likelihood selection among candidate orders.
minor comments (2)
  1. The selection criteria and diversity of the 680 distributions (problem sizes, circuit depths, noise levels) should be stated more explicitly so readers can judge how representative they are of typical noisy Shor runs.
  2. Notation for the four features is introduced in the abstract and results but would benefit from a single consolidated table or subsection that lists their exact mathematical definitions and any normalization choices.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for the constructive comment. We address the point below and will incorporate a clarification through minor revision.

read point-by-point responses

  1. Referee: The recoverability definition and the two verification-derived features (dominant verified mass fraction, verified margin fraction) are computed from the same continued-fraction + modular verification pipeline. This makes the reported strong association and decision-tree thresholds specific to this classical post-processing choice; the mapping may change under alternative recovery procedures such as direct maximum-likelihood selection among candidate orders.

    Authors: We agree that recoverability is defined using the output of continued-fraction expansion with modular verification, and that the two verification-derived features are extracted from the same pipeline. This linkage is intentional: the study evaluates when the standard classical post-processing routine used in Shor's algorithm recovers the true order from noisy hardware data. Consequently, the reported associations and decision-tree thresholds are specific to this recovery procedure. Alternative methods, such as direct maximum-likelihood selection among candidate orders without modular verification, could produce different recoverability labels and alter feature importance. We will add an explicit statement in the revised manuscript clarifying this scope and noting that the results apply to the conventional post-processing pipeline. revision: yes

Circularity Check

0 steps flagged

No significant circularity; empirical associations derived from external labels

full rationale

The paper collects 680 hardware distributions for known problem instances, applies standard continued-fraction expansion plus modular verification to determine a recovered order, and labels recoverability by direct comparison to the known true order. Four features are extracted from each distribution (including dominant verified mass fraction and verified margin fraction computed over verified candidates), after which marginal comparisons, AUROC, random-forest importance, and decision-tree thresholds are used to quantify associations. No equation or claimed result reduces recoverability, a feature, or a classifier output to a quantity defined from the same fitted or verified values by construction; the true-order labels are external to the feature extraction and the post-processing pipeline is fixed and standard rather than derived within the paper. The analysis is therefore self-contained data-driven observation rather than tautological.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on the standard assumption that continued-fraction post-processing with modular verification correctly identifies the order when the recovered value matches the known ground truth; no new free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption Continued-fraction expansion of the measured phase followed by modular verification recovers the true order when the candidate denominator matches the ground-truth order.
    This is the definition of recoverability used throughout the study.

pith-pipeline@v0.9.0 · 5792 in / 1308 out tokens · 41127 ms · 2026-05-20T18:45:16.297940+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

41 extracted references · 41 canonical work pages · 7 internal anchors

  1. [1]

    Adriano Barenco, Artur Ekert, Kalle-Antti Suominen, and Päivi Törmä. 1996. Approximate Quantum Fourier Transform and Decoherence.Physical Review A 54, 1 (1996), 139–146. doi:10.1103/PhysRevA.54.139

    work page doi:10.1103/physreva.54.139 1996

  2. [2]

    Learning high-accuracy error decoding for quantum processors.Nature, 635:834–840, 2024

    Johannes Bausch, Andrew W. Senior, Francisco J. H. Heras, Thomas Edlich, Alex Davies, Michael Newman, Cody Jones, Kevin Satzinger, Murphy Yuezhen Niu, Sam Blackwell, George Holland, Dvir Kafri, Juan Atalaya, Craig Gidney, Demis Hassabis, Sergio Boixo, Hartmut Neven, and Pushmeet Kohli. 2024. Learning High-Accuracy Error Decoding for Quantum Processors.Nat...

    work page doi:10.1038/s41586-024-08148-8 2024

  3. [3]

    Bonet-Monroig, R

    X. Bonet-Monroig, R. Sagastizabal, M. Singh, and T. E. O’Brien. 2018. Low-Cost Error Mitigation by Symmetry Verification.Physical Review A98, 6 (2018), 062339. doi:10.1103/PhysRevA.98.062339

    work page doi:10.1103/physreva.98.062339 2018

  4. [4]

    Bravyi, S

    Sergey Bravyi, Sarah Sheldon, Abhinav Kandala, David C. McKay, and Jay M. Gambetta. 2021. Mitigating Measurement Errors in Multiqubit Experiments. Physical Review A103, 4 (2021), 042605. doi:10.1103/PhysRevA.103.042605

    work page doi:10.1103/physreva.103.042605 2021

  5. [5]

    Leo Breiman. 2001. Random forests.Machine learning45, 1 (2001), 5–32

    work page 2001

  6. [6]

    Friedman, Richard A

    Leo Breiman, Jerome H. Friedman, Richard A. Olshen, and Charles J. Stone. 1984. Classification and Regression Trees. Wadsworth International Group

    work page 1984

  7. [7]

    Electro nic transport in two-dimensional graphene

    Zhenyu Cai, Ryan Babbush, Simon C. Benjamin, Suguru Endo, William J. Huggins, Ying Li, Jarrod R. McClean, and Thomas E. O’Brien. 2023. Quantum Error Miti- gation.Reviews of Modern Physics95, 4 (2023), 045005. doi:10.1103/RevModPhys. 95.045005

    work page doi:10.1103/revmodphys 2023

  8. [8]

    Don Coppersmith. 2002. An Approximate Fourier Transform Useful in Quantum Factoring. arXiv:quant-ph/0201067 [quant-ph] IBM Research Report RC 19642, 1994

    work page internal anchor Pith review Pith/arXiv arXiv 2002

  9. [9]

    Coles, and Lukasz Cincio

    Piotr Czarnik, Andrew Arrasmith, Patrick J. Coles, and Lukasz Cincio. 2021. Error Mitigation with Clifford Quantum-Circuit Data.Quantum5 (2021), 592. doi:10.22331/q-2021-11-26-592

    work page doi:10.22331/q-2021-11-26-592 2021

  10. [10]

    Martin Ekerå. 2021. On completely factoring any integer efficiently in a single run of an order-finding algorithm.Quantum Information Processing20, 6 (2021),

    work page 2021

  11. [11]

    doi:10.1007/s11128-021-03069-1

    work page doi:10.1007/s11128-021-03069-1

  12. [12]

    Martin Ekerå. 2024. On the success probability of quantum order find- ing.ACM Transactions on Quantum Computing5, 2, Article 11 (2024). arXiv:2201.07791 [quant-ph] doi:10.1145/3655026

    work page doi:10.1145/3655026 2024

  13. [13]

    Benjamin, and Xiao Yuan

    Suguru Endo, Zhenyu Cai, Simon C. Benjamin, and Xiao Yuan. 2021. Hybrid Quantum-Classical Algorithms and Quantum Error Mitigation.Journal of the Physical Society of Japan90, 3 (2021), 032001. doi:10.7566/JPSJ.90.032001

    work page doi:10.7566/jpsj.90.032001 2021

  14. [14]

    Tom Fawcett. 2006. An Introduction to ROC Analysis.Pattern Recognition Letters 27, 8 (2006), 861–874. doi:10.1016/j.patrec.2005.10.010

    work page doi:10.1016/j.patrec.2005.10.010 2006

  15. [15]

    Fowler, Matteo Mariantoni, John M

    Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland

    work page

  16. [16]

    Fowler, Matteo Mariantoni, John M

    Surface Codes: Towards Practical Large-Scale Quantum Computation. Physical Review A86, 3 (2012), 032324. doi:10.1103/PhysRevA.86.032324

    work page doi:10.1103/physreva.86.032324 2012

  17. [17]

    Craig Gidney and Martin Ekerå. 2021. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits.Quantum5 (2021), 433. doi:10.22331/q-2021- 04-15-433

    work page doi:10.22331/q-2021- 2021

  18. [18]

    Griffiths and Chi-Sheng Niu

    Robert B. Griffiths and Chi-Sheng Niu. 1996. Semiclassical Fourier Transform for Quantum Computation.Physical Review Letters76, 17 (1996), 3228–3231. doi:10.1103/PhysRevLett.76.3228

    work page doi:10.1103/physrevlett.76.3228 1996

  19. [19]

    Dmitry Grinko, Julien Gacon, Christa Zoufal, and Stefan Woerner. 2021. Iterative quantum amplitude estimation.npj Quantum Information7, Article 52 (2021). arXiv:1912.05559 [quant-ph] doi:10.1038/s41534-021-00379-1

    work page doi:10.1038/s41534-021-00379-1 2021

  20. [20]

    Quantum computing with Qiskit

    Ali Javadi-Abhari, Matthew Treinish, Kevin Krsulich, Christopher J. Wood, Jake Lishman, Julien Gacon, Simon Martiel, Paul D. Nation, Lev S. Bishop, Andrew W. Cross, Blake R. Johnson, and Jay M. Gambetta. 2024. Quantum computing with Qiskit. arXiv:2405.08810 [quant-ph] doi:10.48550/arXiv.2405.08810

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2405.08810 2024

  21. [21]

    A. Yu. Kitaev. 1995. Quantum Measurements and the Abelian Stabilizer Problem. arXiv:quant-ph/9511026 [quant-ph]

    work page internal anchor Pith review Pith/arXiv arXiv 1995

  22. [22]

    Wang, Iskandar Sitdikov, Ciro Salcedo, Alireza Seif, and Zlatko K

    Haoran Liao, Derek S. Wang, Iskandar Sitdikov, Ciro Salcedo, Alireza Seif, and Zlatko K. Minev. 2024. Machine Learning for Practical Quantum Error Mitigation. Nature Machine Intelligence6, 12 (2024), 1478–1486. doi:10.1038/s42256-024- 00927-2

    work page doi:10.1038/s42256-024- 2024

  23. [23]

    S. M. Lim, C. E. Susa, and R. Cohen. 2024. Curve-Fitted QPE: Extending Quantum Phase Estimation Results for a Higher Precision using Classical Post-Processing. arXiv:2409.15752 [quant-ph] doi:10.48550/arXiv.2409.15752

    work page doi:10.48550/arxiv.2409.15752 2024

  24. [24]

    Easwar Magesan, J. M. Gambetta, and Joseph Emerson. 2011. Scalable and Robust Randomized Benchmarking of Quantum Processes.Physical Review Letters106, 18 (2011), 180504. doi:10.1103/PhysRevLett.106.180504

    work page doi:10.1103/physrevlett.106.180504 2011

  25. [25]

    Enrique Martín-López, Anthony Laing, Thomas Lawson, Roberto Alvarez, Xiao- Qi Zhou, and Jeremy L. O’Brien. 2012. Experimental Realization of Shor’s Quan- tum Factoring Algorithm Using Qubit Recycling.Nature Photonics6, 11 (2012), 773–776. doi:10.1038/nphoton.2012.259

    work page doi:10.1038/nphoton.2012.259 2012

  26. [26]

    Alexander May, Lars Schlieper, and Jonathan Schwinger. 2021. Noisy Simon Period Finding. InTopics in Cryptology – CT-RSA 2021 (Lecture Notes in Computer Science, Vol. 12704). Springer, 75–99. arXiv:1910.00802 [cs.CR] doi:10.1007/978-3- 030-75539-3_4

    work page doi:10.1007/978-3- 2021

  27. [27]

    Merkel, Jay M

    Seth T. Merkel, Jay M. Gambetta, John A. Smolin, S. Poletto, A. D. Córcoles, B. R. Johnson, Colm A. Ryan, and M. Steffen. 2013. Self-Consistent Quantum Process Tomography.Physical Review A87, 6 (2013), 062119. doi:10.1103/PhysRevA.87. 062119

    work page doi:10.1103/physreva.87 2013

  28. [28]

    Martinez, Matthias F

    Thomas Monz, Daniel Nigg, Esteban A. Martinez, Matthias F. Brandl, Philipp Schindler, Richard Rines, Shannon X. Wang, Isaac L. Chuang, and Rainer Blatt

    work page

  29. [29]

    Realization of a Scalable Shor Algorithm.Science351, 6277 (2016), 1068–

    work page 2016

  30. [30]

    doi:10.1126/science.aad9480

    work page doi:10.1126/science.aad9480

  31. [31]

    Erik Nielsen, John King Gamble, Kenneth Rudinger, Travis Scholten, Kevin Young, and Robin Blume-Kohout. 2021. Gate Set Tomography.Quantum5 (2021), 557. doi:10.22331/q-2021-10-05-557

    work page doi:10.22331/q-2021-10-05-557 2021

  32. [32]

    Nielsen and Isaac L

    Michael A. Nielsen and Isaac L. Chuang. 2010.Quantum Computation and Quantum Information(10th anniversary ed.). Cambridge University Press

    work page 2010

  33. [33]

    Quantum phase estimation of multiple eigenvalues for small-scale (noisy) experiments

    Thomas E. O’Brien, Brian Tarasinski, and Barbara M. Terhal. 2019. Quantum phase estimation of multiple eigenvalues for small-scale (noisy) experiments. New Journal of Physics21, 2 (2019), 023022. arXiv:1809.09697 [quant-ph] doi:10. 1088/1367-2630/aafb8e

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  34. [34]

    John Preskill. 2018. Quantum Computing in the NISQ Era and Beyond.Quantum 2 (2018), 79. doi:10.22331/q-2018-08-06-79

    work page internal anchor Pith review doi:10.22331/q-2018-08-06-79 2018

  35. [35]

    Peter W. Shor. 1997. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.SIAM J. Comput.26, 5 (1997), 1484–1509. doi:10.1137/S0097539795293172

    work page doi:10.1137/s0097539795293172 1997

  36. [36]

    Benjamin, and Ying Li

    Armands Strikis, Dayue Qin, Yanzhu Chen, Simon C. Benjamin, and Ying Li. 2021. Learning-Based Quantum Error Mitigation.PRX Quantum2, 4 (2021), 040330. doi:10.1103/PRXQuantum.2.040330

    work page doi:10.1103/prxquantum.2.040330 2021

  37. [37]

    Tomoki Tanaka, Yohichi Suzuki, Shumpei Uno, Rudy Raymond, Tamiya Onodera, and Naoki Yamamoto. 2021. Amplitude estimation via maximum likelihood on noisy quantum computer.Quantum Information Processing20, Article 293 (2021). arXiv:2006.16223 [quant-ph] doi:10.1007/s11128-021-03215-9

    work page doi:10.1007/s11128-021-03215-9 2021

  38. [38]

    Error mitigation for short-depth quantum circuits

    Kristan Temme, Sergey Bravyi, and Jay M. Gambetta. 2017. Error Mitigation for Short-Depth Quantum Circuits.Physical Review Letters119, 18 (2017), 180509. doi:10.1103/PhysRevLett.119.180509

    work page internal anchor Pith review doi:10.1103/physrevlett.119.180509 2017

  39. [39]

    Giacomo Torlai and Roger G. Melko. 2017. Neural Decoder for Topological Codes. Physical Review Letters119, 3 (2017), 030501. doi:10.1103/PhysRevLett.119.030501

    work page doi:10.1103/physrevlett.119.030501 2017

  40. [40]

    Savvas Varsamopoulos, Ben Criger, and Koen Bertels. 2018. Decoding Small Sur- face Codes with Feedforward Neural Networks.Quantum Science and Technology 3, 1 (2018), 015004. doi:10.1088/2058-9565/aa955a

    work page doi:10.1088/2058-9565/aa955a 2018

  41. [41]

    Nathan Wiebe and Christopher E. Granade. 2016. Efficient Bayesian Phase Estimation.Physical Review Letters117 (2016), 010503. arXiv:1508.00869 [quant- ph] doi:10.1103/PhysRevLett.117.010503

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/physrevlett.117.010503 2016