pith. sign in

arxiv: 2606.17647 · v1 · pith:OT2DRAO2new · submitted 2026-06-16 · 🪐 quant-ph

From Period Finding to Lattice Sampling: Experimental Insights into Shor's and Regev's Factoring Algorithms

Daniela Falc\'o , Arturo Rodr\'iguez , Guillermo Rivas , Ricardo S. Alonso This is my paper

Pith reviewed 2026-06-27 00:37 UTC · model grok-4.3

classification 🪐 quant-ph
keywords quantum factoringShor's algorithmRegev's algorithmNISQ hardwareexperimental benchmarkingFourier samplinghardware noise
0
0 comments X

The pith

Experiments on N=15 show Shor's and Regev's factoring algorithms respond differently to NISQ noise but neither gains a practical edge.

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

The paper runs both Shor's algorithm and Regev's algorithm on real quantum hardware for the integer N=15, using the QMIO machine and an IBM device, and compares those runs to ideal simulations. It examines how the two algorithms turn arithmetic structure into quantum states, with Shor using one-dimensional Fourier sampling and Regev using higher-dimensional sampling, and records how those choices interact with hardware noise, circuit depth limits, and sampling statistics. The study finds observable differences in robustness and failure modes yet concludes that neither algorithm delivers a practical advantage at this small scale. The work therefore supplies concrete data on how algorithmic design choices play out under current device constraints.

Core claim

Parallel execution of the quantum circuits for Shor's and Regev's factoring algorithms on the same NISQ hardware for N=15 reveals distinct patterns of interaction with noise that trace back to their respective one- and higher-dimensional Fourier sampling strategies, without either algorithm showing a clear practical advantage in the small-N regime.

What carries the argument

The side-by-side hardware execution and noise-response comparison of the two factoring circuits, each encoding arithmetic via Fourier sampling in a different number of dimensions.

If this is right

  • Differences in dimensional structure of Fourier sampling produce measurable differences in how each algorithm degrades under NISQ noise.
  • Neither algorithm yet shows a practical factoring advantage on current devices for N=15.
  • Experimental benchmarking of alternative factoring algorithms can expose which design choices affect real-device behavior.
  • Failure-mode data from these runs can inform choices between algorithms or motivate hybrid approaches on NISQ hardware.

Where Pith is reading between the lines

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

  • Regev's higher-dimensional sampling may exhibit different scaling of noise tolerance once hardware error rates drop below current levels.
  • Similar head-to-head hardware tests could be applied to other quantum algorithms whose theoretical resource trade-offs differ.
  • The absence of advantage at small N implies that any eventual superiority will appear only after hardware reaches a threshold size or coherence time.
  • Error-mitigation techniques could be tested selectively on the more noise-sensitive steps of each algorithm to see whether the robustness gap narrows.

Load-bearing premise

The implementations of both algorithms were compiled and run on the hardware without hidden compilation, calibration, or sampling errors that would distort the noise comparison.

What would settle it

A follow-up run on the same or comparable hardware in which one algorithm consistently produces higher success probability or lower effective error rate than the other across multiple N values while matching ideal simulation more closely.

Figures

Figures reproduced from arXiv: 2606.17647 by Arturo Rodr\'iguez, Daniela Falc\'o, Guillermo Rivas, Ricardo S. Alonso.

Figure 1
Figure 1. Figure 1: Measurement distributions for Shor’s algorithm ( [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Measurement distributions for Regev’s factoring algorithm ( [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
read the original abstract

Quantum algorithms for integer factorization represent one of the most prominent applications of quantum computation, with far-reaching implications for modern cryptography. While Shor's algorithm provides a polynomial-time solution in the ideal quantum model, its practical implementation is severely constrained by the limitations of current noisy intermediate-scale quantum (NISQ) hardware. These constraints have motivated the exploration of alternative factoring algorithms with different structural and resource trade-offs. In this work, we present an experimental study of Regev's quantum factoring algorithm, implemented on real quantum hardware, and compare its behavior with that of Shor's algorithm under analogous conditions. Focusing on the case N = 15, we execute both algorithms on the QMIO quantum computer at the Centro de Supercomputacion de Galicia (CESGA) and contrast the results with one of IBM's open-access quantum computers and ideal simulations. This parallel execution enables a low-level comparison of the two algorithms, highlighting how their respective quantum implementations interact with hardware noise, limited circuit depth, and finite sampling. Our analysis emphasizes the different ways in which Shor's and Regev's algorithms encode arithmetic structure into quantum states through Fourier sampling in one and higher dimensions, respectively, and how these differences manifest in experimental outcomes. Although neither algorithm demonstrates a practical advantage in the small N regime, the results provide insight into their relative robustness and failure modes on contemporary quantum devices. This study illustrates the value of experimental benchmarking of alternative quantum factoring algorithms as a means of understanding the practical implications of algorithmic design choices in the NISQ era.

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

2 major / 1 minor

Summary. The manuscript presents an experimental study comparing Shor's and Regev's quantum factoring algorithms for the case N=15. Both are executed on the QMIO quantum computer and an IBM device, with results contrasted against ideal simulations to analyze how their respective Fourier sampling methods (one-dimensional vs. higher-dimensional) interact with hardware noise and limited circuit depth.

Significance. If the reported executions accurately reflect the theoretical algorithms without unaccounted implementation discrepancies, the study provides useful empirical data on the relative robustness of these algorithms on contemporary NISQ hardware, informing algorithmic design choices beyond theoretical resource counts.

major comments (2)
  1. [Abstract] Abstract: the central claim that the experiments yield insight into relative robustness and failure modes requires that observed differences arise from the algorithmic distinction (1D Fourier sampling vs higher-dimensional lattice sampling) rather than from differences in circuit compilation, qubit mapping, gate decomposition, or sampling strategy; no such implementation details are provided, rendering the attribution unverifiable.
  2. [Results/Methods (implied by abstract claims)] Experimental execution description: no error bars, raw data, shot counts, or circuit resource metrics (depth, gate count) are reported for the QMIO or IBM runs, which is load-bearing for any claim of comparative robustness on real hardware.
minor comments (1)
  1. [Abstract] Abstract: the term 'analogous conditions' is imprecise and should be replaced by explicit statements of the circuit depths, qubit counts, and sampling parameters used for each algorithm.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback highlighting the need for implementation transparency and quantitative metrics. We address each major comment below and will revise the manuscript to incorporate the requested details, strengthening the verifiability of our claims regarding algorithmic robustness.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that the experiments yield insight into relative robustness and failure modes requires that observed differences arise from the algorithmic distinction (1D Fourier sampling vs higher-dimensional lattice sampling) rather than from differences in circuit compilation, qubit mapping, gate decomposition, or sampling strategy; no such implementation details are provided, rendering the attribution unverifiable.

    Authors: We agree that explicit implementation details are required to attribute observed differences to the 1D versus higher-dimensional Fourier sampling rather than to compilation or mapping choices. In the revised manuscript, we will add a new subsection (likely under Methods or a dedicated Implementation Details section) that specifies the qubit mapping strategies, gate decompositions, compilation passes, and sampling procedures applied to both algorithms on the QMIO and IBM hardware. This will allow independent verification that the reported robustness differences originate from the algorithmic structure. revision: yes

  2. Referee: [Results/Methods (implied by abstract claims)] Experimental execution description: no error bars, raw data, shot counts, or circuit resource metrics (depth, gate count) are reported for the QMIO or IBM runs, which is load-bearing for any claim of comparative robustness on real hardware.

    Authors: We concur that the absence of these quantitative elements limits the strength of hardware-robustness claims. The revised manuscript will include: (i) shot counts for all QMIO and IBM executions, (ii) error bars on all reported success probabilities and sampled distributions, (iii) tables listing circuit depth and two-qubit gate counts for the compiled circuits of both algorithms, and (iv) a statement on data availability (raw counts or a repository link where feasible). These additions will be placed in the Results section and supplementary material. revision: yes

Circularity Check

0 steps flagged

No circularity: experimental benchmarking with no derivation chain

full rationale

The manuscript is an experimental study executing Shor's and Regev's circuits for N=15 on QMIO and IBM hardware, comparing noise responses and failure modes. No theoretical derivation, first-principles prediction, or parameter fit is claimed; the central statements concern observed hardware outcomes and their attribution to algorithmic structure (1D vs. higher-dimensional Fourier sampling). Because the work contains no equations or claims that reduce by construction to fitted inputs, self-citations, or ansatzes, the derivation chain is empty and the result is self-contained against external hardware benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only the abstract is available, so the ledger is minimal. The study relies on standard domain assumptions of quantum hardware rather than new free parameters or invented entities.

axioms (1)
  • domain assumption Quantum hardware can faithfully execute the compiled circuits for both algorithms under the stated noise and depth constraints
    Implicit in any claim of experimental execution on real devices

pith-pipeline@v0.9.1-grok · 5817 in / 1217 out tokens · 50200 ms · 2026-06-27T00:37:26.435010+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

14 extracted references · 2 linked inside Pith

  1. [1]

    Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484–1509, October 1997

    1997

  2. [2]

    Modifying shor’s algorithm to compute short discrete logarithms

    Martin Ekerå. Modifying shor’s algorithm to compute short discrete logarithms. Cryptology ePrint Archive, Paper 2016/1128, 2016

    2016

  3. [3]

    Cybersecurityinanerawithquantumcomputers: Willwebeready?IEEESecurity&Privacy,16:38–41, 09 2018

    MicheleMosca. Cybersecurityinanerawithquantumcomputers: Willwebeready?IEEESecurity&Privacy,16:38–41, 09 2018

    2018

  4. [4]

    The future of cybersecurity in the age of quantum computers.Future Internet, 14(11):335, 2022

    Fazal Raheman. The future of cybersecurity in the age of quantum computers.Future Internet, 14(11):335, 2022

    2022

  5. [5]

    How to factor 2048 bit rsa integers in 8 hours using 20 million noisy qubits.Quantum, 5:433, 2021

    Craig Gidney and Martin Ekerå. How to factor 2048 bit rsa integers in 8 hours using 20 million noisy qubits.Quantum, 5:433, 2021

    2048

  6. [6]

    Space-efficient and noise-robust quantum factoring.arXiv preprint arXiv:2304.00662, 2023

    Craig Gidney. Space-efficient and noise-robust quantum factoring.arXiv preprint arXiv:2304.00662, 2023

    arXiv 2023

  7. [7]

    Circuit for shor’s algorithm using 2n+3 qubits, 2003

    Stephane Beauregard. Circuit for shor’s algorithm using 2n+3 qubits, 2003

    2003

  8. [8]

    Stephen Parker and Martin B. Plenio. Efficient factorization with a single pure qubit and lognmixed qubits.Physical Review Letters, 85(14):3049–3052, 2000. arXiv:quant-ph/0001066

    Pith/arXiv arXiv 2000

  9. [9]

    Quantum computing in the nisq era and beyond.Quantum, 2:79, August 2018

    John Preskill. Quantum computing in the nisq era and beyond.Quantum, 2:79, August 2018

    2018

  10. [10]

    An efficient quantum factoring algorithm.arXiv preprint arXiv:2308.06572, 2023

    Oded Regev. An efficient quantum factoring algorithm.arXiv preprint arXiv:2308.06572, 2023

    arXiv 2023

  11. [11]

    A comprehensive analysis of regev’s quantum algorithm

    Razvan Barbulescu, Mugurel Barcau, and Vicentiu Pasol. A comprehensive analysis of regev’s quantum algorithm. Cryptology ePrint Archive, Paper 2024/1758, 2024

    2024

  12. [12]

    Cryptology ePrint Archive, Paper 2024/629, 2024

    CédricPilatte.Unconditionalcorrectnessofrecentquantumalgorithmsforfactoringandcomputingdiscretelogarithms. Cryptology ePrint Archive, Paper 2024/629, 2024

    2024

  13. [13]

    Implementation and analysis of regev’s quantum factorization algorithm, 2025

    Przemysław Pawlitko, Natalia Moćko, Marcin Niemiec, and Piotr Chołda. Implementation and analysis of regev’s quantum factorization algorithm, 2025

    2025

  14. [14]

    Implementation and analysis of regev’s quantum factorization algorithm.arXiv preprint arXiv:2502.09772, 2025

    Przemysław Pawlitko, Natalia Moćko, Marcin Niemiec, and Piotr Chołda. Implementation and analysis of regev’s quantum factorization algorithm.arXiv preprint arXiv:2502.09772, 2025. 10

    Pith/arXiv arXiv 2025