Pith. sign in

REVIEW 4 major objections 5 minor 2 cited by

Implementation and Analysis of Regev's Quantum Factorization Algorithm

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Pith's one-line read The paper reports the first working implementation of Regev's quantum factoring algorithm and claims it beats Shor's factor-finding effectiveness on N in {21, 33, 39, 51} after per-input tuning of a classical parameter, while remaining…

desk verdict A real first implementation of Regev's algorithm with honest reporting, but the 'outperforms Shor' claim needs a random-vector control before it can be believed. read the letter →

arxiv 2502.09772 v2 pith:S55SVAUK submitted 2025-02-13 quant-ph cs.CR

classification quant-phcs.CR MSC 81P68 PACS 03.67.Lx
keywords Regev'salgorithmShor'squantumfactorizationsemiprimefactoringlatticereductionLLLparametertuninguniformsuperposition
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper reports the first publicly available implementation of Regev's quantum factoring algorithm and evaluates it by simulation on small products of two primes (semiprimes). Its central empirical claim is that, after choosing a value of the classical parameter t for each input, the implementation finds non-trivial factors more often than Shor's algorithm for N equal to 21, 33, 39, and 51, with 100 percent success for N = 39 and N = 51 in finding non-trivial square roots of unity modulo N. The paper also finds that Regev's implementation runs considerably longer than Shor's in both the quantum and classical parts at these sizes, so the asymptotic advantage is not yet visible. The upshot is that a concrete Regev circuit can be competitive with Shor's on factor-finding effectiveness for selected small inputs, which makes further benchmarking at larger N and on real hardware the natural next step.

What carries the argument

The engine of the paper is a $d$-dimensional period-finding circuit followed by a lattice-based classical post-process. The quantum part superposes $d$ registers, applies modular exponentiation for the first $d$ squared primes ($a_i = b_i^2$), performs a quantum Fourier transform, and measures; the measured vectors are meant to approximate vectors of the dual lattice $L^*$. The classical part assembles $d+4$ such vectors into a matrix $B$, scales them using the parameter $t$, runs the LLL lattice-reduction algorithm, and checks whether the resulting vectors lie in the lattices $L$ and $L \setminus L_0$; vectors in $L \setminus L_0$ yield non-trivial square roots of unity modulo $N$, and a gcd then gives $p$ and $q$. Two parameter choices carry much of the analysis: the dimension $d$ and the register width $q_d$ are each rounded up or down, producing four configurations (ceil_ceil, ceil_floor, floor_ceil, floor_floor). A further design choice replaces Regev's Gaussian state with a uniform superposition and moves $t$ entirely into the classical scaling, giving the paper its tuning knob. For this implementation the authors estimate gate complexity $\widetilde{O}(n^{5/2} \log n)$ and circuit width $O(n)$, against the $\widetilde{O}(n^{3/2})$ gate complexity of Regev's original proposal.

What would settle it

Run the same circuit for the same small N twice, once with the uniform superposition used here and once with a true Gaussian initial distribution as Regev specifies, and compare the rates of finding non-trivial square roots of unity modulo N. If the uniform version's advantage over Shor disappears or its optimal t changes once the Gaussian is used, the reported effectiveness is a property of the uniform-state surrogate. A second decisive check is to fix t before seeing any results (for example, t = 8) and test all N; if per-N tuning was the source of the gains, the fixed-t rates should fall back toward Shor's.

Watch

Extended reading notes

Core claim

The core claim is that Regev's multidimensional factoring algorithm, implemented for the first time as a concrete quantum circuit, can match or beat Shor's algorithm in factor-finding effectiveness on certain small composite numbers once the classical scaling parameter t is tuned. In the reported experiments, the best per-N choice of t produces non-trivial square roots of unity modulo N at rates above Shor's for N equal to 21, 33, 39, and 51, including 100 percent effectiveness for N = 39 and N = 51, while other tested numbers lag (for instance, 32 percent for N = 55). The same experiments show Regev's runtime is substantially longer than Shor's at these sizes in both the quantum and classical components, which the authors read as consistent with the asymptotic crossover lying beyond the simulated range. The implemented circuit follows Regev's structure: d quantum input registers hold exponents of the first d squared primes, modular exponentiation gates and a quantum Fourier transform produce output vectors, and a classical lattice-reduction step using the LLL algorithm recovers the factors. The paper is explicit that Regev's Gaussian initial distribution was replaced by a uniform superposition, with t used only in classical post-processing, and that this substitution was an assumption rather than a validated equivalence.

Load-bearing premise

The load-bearing premise is that a uniform superposition over the d input registers, with the parameter t applied only in classical post-processing, produces measurement vectors that serve the dual-lattice recovery just as well as Regev's Gaussian distribution would; the paper states that the Gaussian was not implemented and offers no experimental check that the substitution is equivalent.

Editorial extensions

If this is right

  • If the implementation is sound, it gives other groups a concrete circuit and reproducible test data for Regev's algorithm instead of only theoretical resource estimates.
  • Because Shor remains faster at every N simulated here, the practical payoff of Regev's asymptotic gate savings would have to appear at larger N than the simulator could reach.
  • The effectiveness of the implemented algorithm depends strongly on the classical parameter t, but no systematic rule for choosing t is found, so the best value must currently be selected per input.
  • Until the uniform-superposition substitution is validated, the reported success rates are evidence about this particular circuit, not necessarily about Regev's algorithm as originally specified with a Gaussian state.
  • The classical lattice-reduction step is slower than Shor's classical post-processing but remains negligible next to the simulated quantum runtime.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because t was tuned per N to find the best result, the gains over Shor may partly reflect selection over many candidate t values; a fair comparison would fix t in advance and test all N.
  • A direct test of the central shortcut would be to prepare the circuit with Regev's Gaussian distribution and compare success rates and optimal t values against the uniform-superposition version; if uniform sampling already approximates the dual lattice after scaling, the shortcut is harmless, and if not, the comparison against Shor applies only to the surrogate.
  • The absence of a visible t-effectiveness correlation suggests t is acting as an arbitrary scaling of the lattice vectors rather than as the Gaussian width parameter it was designed to be; checking whether t can be absorbed into the normalization of B would clarify what the tuning actually changes.
  • If the runtime crossover between Regev and Shor does exist at practically relevant sizes, it should appear only with the full Gaussian state and a more scalable classical post-process; the present uniform-state implementation is not evidence against that crossover, only a lower bound on what must be fixed to reach it.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The manuscript describes an implementation of Regev's quantum factoring algorithm using Qiskit, a statevector simulator, and an LLL-based classical post-processing stage. For small semiprimes, the authors compare the runtime and effectiveness of their Regev implementation with Shor's algorithm, reporting that after tuning a classical parameter t, Regev's algorithm outperforms Shor's algorithm for N in {21, 33, 39, 51} while remaining slower in runtime. The paper also claims to present the first publicly available implementation of Regev's algorithm.

Significance. If fully supported, an open-source Regev implementation would be a useful community resource, and the detailed circuit decompositions and runtime measurements for small N would be of practical interest. The observation that classical post-processing parameters strongly affect success rates is a useful warning for future implementers. However, the central comparative claims are not currently established by the experiments as presented: the reported outperformance is selected post hoc, the quantum state preparation deviates from Regev's algorithm, and there is no control against random vectors under the same tuned parameters. The paper's value lies mainly in the implementation details and data, not in the stated conclusions.

major comments (4)
  1. [§4.2, Table 4, §4.3] The headline claim that Regev's algorithm outperforms Shor's algorithm for N in {21, 33, 39, 51} is based on per-N selection of t after scanning the range [2, 20]. Table 4 reports the t that gives the highest effectiveness for each N, not the performance of a fixed implementation or a pre-registered parameter choice. Since §4.3 states that with Kiebert's parameters the quantum output gave results 'similar to those obtained by using a random vector' (test 3), the reported success rates may be produced by the classical LLL post-processing alone once t is tuned. The paper does not report a control in which random vectors are processed with the same per-N t values from Table 4, and it does not report effectiveness for a fixed t across all N. This control is needed before the advantage can be attributed to the quantum circuit.
  2. [§3.1.2, §4.3] Regev's algorithm requires preparing a Gaussian superposition over the input registers; the implementation instead uses a uniform superposition and moves t entirely into classical post-processing. The paper explicitly states in §4.3 that the authors 'did not implemented the Gaussian distribution which is correlated with parameter t' and instead 'assumed that changing the value of t might increase the effectiveness.' No theoretical, numerical, or experimental evidence is provided that a uniform superposition followed by classical scaling produces vectors that approximate vectors in the dual lattice L*. Without such validation, the experiment is not demonstrably an implementation of Regev's algorithm, and the comparison with Shor's algorithm is not meaningful as presented.
  3. [§3.2, Table 3] The approximate value T = exp(n/(2d)) used to set the lattice parameter R was obtained by calculating exact values of T for a few cases and determining the best-fitting curve. The exact values are computed for N = 15, 21, 35, 51, 57, which are the same small N used later in the effectiveness tests. This in-sample calibration can make the success rates look better than an out-of-sample or a priori parameter choice would. The paper should report effectiveness with T fixed by Regev's asymptotic heuristic or by a leave-one-out calibration, and it should quantify the sensitivity of the results to T.
  4. [§3.1, §4.1] The quantum part is simulated once with 128 shots, and the d+4 independent executions required by Regev's algorithm are replaced by draws from that single measurement record. The statement in §3.1 that this approach 'does not have an impact on the accuracy of the results' is not justified: finite-sample fluctuations in the 128-shot histogram affect the empirical distribution used by test 1, and runtimes are measured only once. The paper should provide multiple independent simulation runs or bootstrap confidence intervals for both effectiveness and runtime, especially for the N values in Table 4.
minor comments (5)
  1. [§1.1, §5] The claim of being 'the first publicly available implementation of Regev's algorithm' is asserted without supporting evidence; please provide a reference, a dated search statement, or soften the claim to 'to the best of our knowledge.'
  2. [Figure 11] The caption says 'type of test 3' but the legend appears to show all three test types; please correct the caption.
  3. [§4.3] There are typos such as 'did not implemented' and inconsistent spelling of 'Kiebert' vs. 'Kierbert' (reference [28] is 'Kiebert'); please proofread for grammar and terminology.
  4. [§3.1.2] The sentence 'the output register is ignored (measured), as its value is not relevant to our objectives' is confusing because measuring the output register is not needed; please clarify whether it is simply not used or whether its measurement is required for the simulation.
  5. [Appendix A] The symbol q is used both for one of the prime factors of N and as part of the qd parameter; please use distinct notation to avoid ambiguity.

Circularity Check

1 steps flagged · score 6.0 of 10

Outperformance over Shor is an artifact of per-N best-t selection, not a fixed implementation.

  1. fitted input called prediction [Section 4.2 (Efficiency Analysis), Table 4; Section 4.3 (Performance Summary)]
    "Table 4 presents, for each N, the parameter t that yielded the highest effectiveness, together with the corresponding percentage value. ... The better effectiveness of factoring N than Shor's algorithm was obtained for N ∈ {21, 33, 39, 51}. ... The results we obtained were of similar to those obtained by using a random vector."

    The headline claim that Regev's algorithm outperforms Shor for N in {21,33,39,51} is based on Table 4, which is constructed by scanning t over [2,20] and, for each N, recording only the t that maximizes effectiveness. Shor's comparison is a single fixed success rate, so the comparison is per-N optima against a fixed baseline; the advantage is therefore an artifact of the selection procedure rather than a property of one implemented algorithm. The paper also concedes that with Kiebert's parameters the quantum results were 'similar to those obtained by using a random vector', and no control is reported applying the same per-N t values from Table 4 to random vectors.

full rationale

The central circularity is localized to the efficiency comparison. The abstract and Section 4.2 claim Regev's algorithm 'indeed outperforms Shor's algorithm' for N ∈ {21,33,39,51}, but Table 4 is explicitly a per-N maximum over a t scan, and Section 4.3 records that with Kiebert's parameters the quantum output was 'similar to those obtained by using a random vector'. Without a random-vector control using the same tuned per-N t values, the reported advantage cannot be attributed to the quantum circuit. I did not count the uniform-superposition substitution as circular: it is an openly stated modeling limitation, though it further weakens the link to Regev's algorithm. Likewise, the T ≈ exp(n/(2d)) approximation is a disclosed in-sample fit that shapes LLL behavior, but the paper presents it as a heuristic rather than as a derived prediction, so it does not by itself establish a circular derivation. No load-bearing self-citation chain exists: references [12], [13], and [28] are external works, and the 'first publicly available implementation' claim is a novelty assertion rather than a derivation. Because the headline effectiveness claim is partially constructed by per-N parameter selection, the score is 6.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The implementation rests on Regev's heuristic, on an unverified replacement of Gaussian by uniform superposition, on Kiebert's lattice post-processing, and on treating one 128-shot run as a source of many independent executions. The two fitted parameters t and T are selected using the very data they then explain.

free parameters (2)
  • t (Gaussian width parameter, repurposed as classical scaling) = 2, 5, 8, 11, or 14 depending on N; see Table 4
    The parameter t is scanned over [2,20] and the value giving highest effectiveness is selected per factorized N. Because the quantum circuit uses uniform superposition instead of Regev's Gaussian, t has no quantum role and becomes a free classical knob. The 'better than Shor' cases in Table 4 are the optimized outcomes of this scan.
  • T (bound on norm of target vector), approximated as exp(n/(2d)) = exp(n/(2d)), rounded; exact values for N = 15, 21, 35, 51, 57 used to fit the curve
    Section 3.2 states that the approximation was obtained by calculating accurate T values for a few cases and determining the best-fitting curve. This fitted T controls R and the determinant of the lattice matrix B, so it directly shapes LLL outputs and reported effectiveness.
assumptions (4)
  • domain assumption At least half of the period vectors for the function (z1,...,zd) -> a1^z1 ... ad^zd mod N yield non-trivial square roots of 1 mod N.
    Adopted from Regev [6] in Section 2.1. The paper does not test it independently, and it underlies the guarantee that factoring succeeds after period recovery.
  • ad hoc to paper A uniform superposition over the input registers can replace Regev's Gaussian distribution and still yield vectors that, after classical scaling by t, approximate vectors in the dual lattice L*.
    Section 3.1.2 initializes with Hadamards, and Section 4.3 admits the Gaussian was not implemented and t was repurposed. The theoretical link between Regev's proof and this implementation depends on this unvalidated equivalence.
  • domain assumption Kiebert's lattice construction and LLL post-processing are valid for these small N with the rounded parameters.
    Section 3.2 builds matrix B and chooses R using Kiebert [28] and Regev's heuristic T = exp(O(n/d)). Small-N validity is assumed rather than proven.
  • ad hoc to paper Drawing d+4 vectors from the frequency distribution of one 128-shot statevector run is equivalent to running the quantum circuit d+4 independent times.
    Section 3.1 says the simulator runs once and collects 128 measurements, then Section 3.2 samples d+4 vectors from those outputs to simulate repeated executions. Finite-sample and correlation effects are not analyzed.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Implementation and Analysis of Regev's Quantum Factorization Algorithm." pith.science (2026). https://pith.science/paper/S55SVAUK

@misc{pith2026250209772,
  author       = {Pith},
  title        = {Pith review of: Implementation and Analysis of Regev's Quantum Factorization Algorithm},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/S55SVAUK}},
  note         = {Machine review of arXiv:2502.09772}
}
read the original abstract

Quantum computing represents a significant advancement in computational capabilities. Of particular concern is its impact on asymmetric cryptography through, notably, Shor's algorithm and the more recently developed Regev's algorithm for factoring composite numbers. We present our implementation of the latter. Our analysis encompasses both quantum simulation results and classical component examples, with particular emphasis on comparative cases between Regev's and Shor's algorithms. Our experimental results reveal that Regev's algorithm indeed outperforms Shor's algorithm for certain composite numbers in practice. However, we observed significant performance variations across different input values. Despite Regev's algorithm's theoretical asymptotic efficiency advantage, our implementation exhibited execution times longer than Shor's algorithm for small integer factorization in both quantum and classical components. These findings offer insights into the practical challenges and performance characteristics of implementing Regev's algorithm in realistic quantum computing scenarios.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

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

    quant-ph 2026-06 unverdicted novelty 5.0 of 10

    Experimental comparison of Shor's and Regev's factoring algorithms on QMIO and IBM quantum computers for N=15, showing differences in noise robustness via one- vs higher-dimensional Fourier sampling.

  2. Qrisp Implementation and Resource Analysis of a T-Count-Optimised Non-Restoring Quantum Square-Root Circuit

    quant-ph 2025-07 reject novelty 3.0 of 10

    A Qrisp implementation of the non-restoring square root circuit is demonstrated, but its headline resource claim (T-count 14n-14) is contradicted by the paper's own table, which matches the quadratic 7/2 n^2 + 21n - 28.

Reference graph

Works this paper leans on

26 extracted references · 19 canonical work pages · cited by 2 Pith papers

  1. [1]

    Communications of the ACM21(2) (1978)

    Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM21(2) (1978)

  2. [2]

    In: Proceedings 35th Annual Symposium on Foundations of Computer Science (1994)

    Shor, P.W.: Algorithms for quantum computation: discrete logarithms and fac- toring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science (1994)

  3. [3]

    SIAM Review41(2) (1999)

    Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Review41(2) (1999)

  4. [6]

    URL: https://arxiv.org/ abs/2308.06572v3 (2024)

    Regev, O.: An Efficient Quantum Factoring Algorithm. URL: https://arxiv.org/ abs/2308.06572v3 (2024)

  5. [7]

    Regev, O.: An efficient quantum factoring algorithm. J. ACM72(1) (2025) https: //doi.org/10.1145/3708471

  6. [8]

    Physical Review A107(2) (2023)

    Mutter, P.M., Burkard, G.: Theory of qubit noise characterization using the long- time cavity transmission. Physical Review A107(2) (2023)

  7. [9]

    Quantum Information & Computation6(2) (2006)

    Takahashi, Y., Kunihiro, N.: A quantum circuit for Shor’s factoring algorithm using 2n + 2qubits. Quantum Information & Computation6(2) (2006)

  8. [10]

    AIP Advances14(2) (2024)

    Tan, X., Gao, P.: An efficient quantum circuit implementation of Shor’s algorithm for GPU accelerated simulation. AIP Advances14(2) (2024)

Show all 26 references
  1. [11]

    In: Proc

    Cleve, R., Watrous, J.: Fast parallel circuits for the quantum Fourier transform. In: Proc. 41st Annual Symposium on Foundations of Computer Science (2000)

  2. [12]

    In: Reyzin, L., Stebila, D

    Ragavan, S., Vaikuntanathan, V.: Space-efficient and noise-robust quantum fac- toring. In: Reyzin, L., Stebila, D. (eds.) Advances in Cryptology – CRYPTO 2024, pp. 107–140. Springer, Cham (2024)

  3. [13]

    Master’s thesis, AGH University of Science and Technology, Krakow (2021)

    Stępień, B.: Algorytm Shora dla IBM Qiskit. Master’s thesis, AGH University of Science and Technology, Krakow (2021). [in Polish]

  4. [14]

    URL: https://arxiv.org/abs/1611.07995 (2017)

    Häner, T., Roetteler, M., Svore, K.M.: Factoring using2n + 2qubits with Toffoli based modular multiplication. URL: https://arxiv.org/abs/1611.07995 (2017)

  5. [15]

    Annals of Mathematics 193(2) (2021)

    Harvey, D., Van Der Hoeven, J.: Integer multiplication in timeO(n log n). Annals of Mathematics 193(2) (2021)

  6. [16]

    arXiv preprint arXiv:1904.07356 (2019)

    Gidney, C.: Asymptotically efficient quantum Karatsuba multiplication. arXiv preprint arXiv:1904.07356 (2019)

  7. [17]

    arXiv preprint arXiv:2403.18006 (2024)

    Kahanamoku-Meyer, G.D., Yao, N.Y.: Fast quantum integer multiplication with zero ancillas. arXiv preprint arXiv:2403.18006 (2024)

  8. [18]

    arXiv preprint quant-ph/0205095 (2003)

    Beauregard, S.: Circuit for Shor’s algorithm using2n + 3qubits. arXiv preprint quant-ph/0205095 (2003)

  9. [19]

    arXiv preprint quant- ph/0601097 (2006)

    Zalka, C.: Shor’s algorithm with fewer (pure) qubits. arXiv preprint quant- ph/0601097 (2006)

  10. [20]

    arXiv preprint arXiv:1706.07884 (2017)

    Gidney, C.: Factoring withn+2 clean qubits andn−1dirty qubits. arXiv preprint arXiv:1706.07884 (2017)

  11. [21]

    In: Advances in Cryptology– ASIACRYPT 2017: 23rd International Conference on the Theory and Applica- tions of Cryptology and Information Security (2017)

    Roetteler, M., Naehrig, M., Svore, K.M., Lauter, K.: Quantum resource estimates 27 for computing elliptic curve discrete logarithms. In: Advances in Cryptology– ASIACRYPT 2017: 23rd International Conference on the Theory and Applica- tions of Cryptology and Information Security (2017)

  12. [22]

    Mathematische Annalen261 (1982)

    Lenstra, A., Lenstra, H., László, L.: Factoring polynomials with rational coeffi- cients. Mathematische Annalen261 (1982)

  13. [23]

    PhD thesis, The University of Electro-Communications, Tokyo (2008)

    Takahashi, Y.: Efficient quantum circuits for arithmetic operations and their applications. PhD thesis, The University of Electro-Communications, Tokyo (2008)

  14. [24]

    Nature585(7825) (2020)

    Harris, C.R., Millman, K.J., Walt, S.J., Gommers, R., Virtanen, P., Cournapeau, D., Wieser, E., Taylor, J., Berg, S., Smith, N.J., Kern, R., Picus, M., Hoyer, S., Kerkwijk, M.H., Brett, M., Haldane, A., R’ıo, J.F., Wiebe, M., Peterson, P., G’erard-Marchant, P., Sheppard, K., R...

  15. [25]

    arXiv 10.48550/arXiv.2405.08810 (2024)

    Javadi-Abhari, A., Treinish, M., Krsulich, K., Wood, C.J., Lishman, J., Gacon, J., Martiel, S., Nation, P.D., Bishop, L.S., Cross, A.W., Johnson, B.R., Gambetta, J.M.: Quantum computing with Qiskit. arXiv 10.48550/arXiv.2405.08810 (2024)

  16. [26]

    Reviews of Modern Physics95(4) (2023)

    Cai, Z., Babbush, R., Benjamin, S.C., Endo, S., Huggins, W.J., Li, Y., McClean, J.R., O’Brien, T.E.: Quantum error mitigation. Reviews of Modern Physics95(4) (2023)

  17. [27]

    URL: https://docs

    IBM: Error mitigation and suppression techniques. URL: https://docs. quantum.ibm.com/guides/error-mitigation-and-suppression-techniques# error-mitigation-and-suppression-techniques. Accessed on 9 July 2025 (2024)

  18. [28]

    Mathematics and Computer Science at Informatics Institute, Korteweg-de Vries Institute for Mathematics, Faculty of Sciences, University of Amsterdam (2024) 28

    Kiebert, M.: Oded Regev’s Quantum Factoring Algorithm. Mathematics and Computer Science at Informatics Institute, Korteweg-de Vries Institute for Mathematics, Faculty of Sciences, University of Amsterdam (2024) 28

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.