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 →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
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.
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
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- [§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.
- [§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.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.
- [§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, §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.'
- [Figure 11] The caption says 'type of test 3' but the legend appears to show all three test types; please correct the caption.
- [§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.
- [§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.
- [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
Outperformance over Shor is an artifact of per-N best-t selection, not a fixed implementation.
-
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
free parameters (2)
- t (Gaussian width parameter, repurposed as classical scaling) =
2, 5, 8, 11, or 14 depending on N; see Table 4
- 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
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.
- 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*.
- domain assumption Kiebert's lattice construction and LLL post-processing are valid for these small N with the rounded parameters.
- 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.
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.
Forward citations
Cited by 2 Pith papers
-
From Period Finding to Lattice Sampling: Experimental Insights into Shor's and Regev's Factoring Algorithms
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.
-
Qrisp Implementation and Resource Analysis of a T-Count-Optimised Non-Restoring Quantum Square-Root Circuit
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
-
[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)
work page 1978
-
[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)
work page 1994
-
[3]
Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Review41(2) (1999)
work page 1999
-
[6]
URL: https://arxiv.org/ abs/2308.06572v3 (2024)
Regev, O.: An Efficient Quantum Factoring Algorithm. URL: https://arxiv.org/ abs/2308.06572v3 (2024)
arXiv 2024
-
[7]
Regev, O.: An efficient quantum factoring algorithm. J. ACM72(1) (2025) https: //doi.org/10.1145/3708471
doi:10.1145/3708471 2025
-
[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)
work page 2023
-
[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)
work page 2006
-
[10]
Tan, X., Gao, P.: An efficient quantum circuit implementation of Shor’s algorithm for GPU accelerated simulation. AIP Advances14(2) (2024)
work page 2024
Show all 26 references
-
[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)
2000
-
[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)
2024
-
[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]
2021
-
[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)
2017 arXiv
-
[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)
2021
-
[16]
arXiv preprint arXiv:1904.07356 (2019)
Gidney, C.: Asymptotically efficient quantum Karatsuba multiplication. arXiv preprint arXiv:1904.07356 (2019)
2019 arXiv
-
[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)
2024 arXiv
-
[18]
arXiv preprint quant-ph/0205095 (2003)
Beauregard, S.: Circuit for Shor’s algorithm using2n + 3qubits. arXiv preprint quant-ph/0205095 (2003)
2003 arXiv
-
[19]
arXiv preprint quant- ph/0601097 (2006)
Zalka, C.: Shor’s algorithm with fewer (pure) qubits. arXiv preprint quant- ph/0601097 (2006)
2006
-
[20]
arXiv preprint arXiv:1706.07884 (2017)
Gidney, C.: Factoring withn+2 clean qubits andn−1dirty qubits. arXiv preprint arXiv:1706.07884 (2017)
2017 arXiv
-
[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)
2017
-
[22]
Mathematische Annalen261 (1982)
Lenstra, A., Lenstra, H., László, L.: Factoring polynomials with rational coeffi- cients. Mathematische Annalen261 (1982)
1982
-
[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)
2008
-
[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...
2020
- [25]
-
[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)
2023
-
[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)
2024
-
[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
2024
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.