Resource scaling and viability of Schnorr-type lattice factoring with variational quantum local search

Integer factoring underlies RSA security. Beyond Shor's algorithm (which needs error-corrected, million-qubit hardware), a family of heuristic hybrid algorithms attempts factoring by combining Schnorr's lattice-based method with a shallow variational quantum circuit — a Quantum Approximate Optimization Algorithm (QAOA) or a Variational Quantum Eigensolver (VQE) — that refines the classical Babai nearest-plane step. The 2024 VQE instantiation (Sánchez Cano et al.) factored only $N=1961=37\times53$, with 7 of 8 experimental configurations failing, and left the pipeline's cost profile entirely open: how classical preprocessing (LLL reduction, Babai), the number of quantum executions, and per-run success probability jointly scale with $N$ and the hyperparameters; how sensitive the outcome is to the lattice-preprocessing implementation; how many variational restarts are statistically required; and whether any of this supports the published claim that such sublinear-qubit methods could challenge RSA-2048 with 372 physical qubits. Independent 2023 analyses give strong negative evidence (even a perfect quantum optimizer only reaches about 70 bits; smooth-number density decays exponentially), yet the original authors' 2025 review still claims polynomial resource constraints, and 2025–2026 follow-ups (trapped-ion QAOA, tensor networks, probabilistic bits) all leave the end-to-end scaling question explicitly open. The open problem is an end-to-end resource characterization of this hybrid pipeline, sufficient to settle its asymptotic and practical viability.

Background

Integer factorization is the hard inverse of multiplication on which the RSA cryptosystem's security rests: the best classical algorithms, such as the General Number Field Sieve, run in subexponential time, and no polynomial-time classical method is known. Shor's quantum algorithm factors in polynomial time but requires fault-tolerant quantum computers with millions of physical qubits, far beyond today's NISQ (Noisy Intermediate-Scale Quantum) devices — small, noisy processors without error correction.

A heuristic alternative goes back to Schnorr (1991). A lattice is the set of all integer linear combinations of a basis of $\mathbb{R}^d$; the closest vector problem (CVP) asks for the lattice point nearest a given target. Schnorr's method builds, from the integer $N$ and a smoothness bound (only primes up to a fixed bound are used), a lattice in which points close to a target encode pairs of integers whose prime factors are all small ("smooth"). A valid pair of such smooth relations — an "sr-pair" — yields a congruence of squares modulo $N$, from which a nontrivial factor of $N$ follows by taking greatest common divisors, exactly as in classical sieving factoring. In practice the lattice basis is first reduced with the LLL algorithm (Lenstra–Lenstra–Lovász), which computes a nearly orthogonal basis in polynomial time, and the CVP is then approximated by Babai's nearest-plane algorithm, a cheap deterministic procedure. The quality of this purely classical pipeline degrades badly as the lattice dimension grows with $N$, because useful smooth relations become sparse.

Yan et al. (2022) proposed repairing the weak Babai step with a local quantum search: after Babai produces a candidate lattice point, a small neighborhood is searched by QAOA (Quantum Approximate Optimization Algorithm), a shallow parameterized quantum circuit whose parameters are tuned classically to lower the expected value of a cost Hamiltonian that encodes the neighborhood search as a binary optimization problem. They reported factoring integers up to 48 bits using 10 superconducting qubits, claimed the required qubit count scales as $O(\log N/\log\log N)$ — sublinear in the bit length of $N$, versus the linear scaling of Shor's algorithm — and estimated that 372 physical qubits would suffice to "challenge RSA-2048". Independent re-analyses in 2023 pushed back hard: an open-source re-implementation (Khattar and Yosri) showed that even replacing QAOA by a perfect optimizer, the claimed sublinear lattice dimension only factors integers up to about 70 bits and fails to find enough relations for random 80-bit integers; Grebnev et al. documented that the proposal never analyzed the complexity of its classical part; and Aboumrad, Widdows, and Kaushik argued that the exponential decay of smooth-number density makes commercial-scale factoring by these lattice methods unfounded, with the quantum enhancement not altering that conclusion.

Sánchez Cano et al. (2024) replicated the pipeline replacing QAOA by VQE (Variational Quantum Eigensolver) — a parameterized quantum circuit optimized classically to minimize the expectation value of a cost Hamiltonian. Their variant factored only $N=1961=37\times53$ with 3 qubits; 7 of their 8 experimental configurations failed; the larger instance $N=48567227$ failed entirely; and success depended on which implementation reduced the lattice — a textbook LLL implementation and the floating-point L2 implementation in the fpylll library produce different reduced bases and different Babai points from the same input, changing downstream outcomes. They left the method's overall resource profile unresolved, and it is this cluster of unresolved issues that constitutes the present problem.

Problem Statement

Determine the end-to-end resource scaling of the Schnorr-type hybrid factoring pipeline with heuristic local quantum search — the pipeline instantiated by Yan et al. with QAOA and by Sánchez Cano et al. with VQE — as a function of the bit length of $N$ and of the hyperparameters: the lattice-dimension multiplier $l$ (the Schnorr lattice is built with dimension $n=\lfloor l\log_2 N/\log_2\log_2 N\rfloor$, with $l\in\{1,2\}$ in the source experiments), the positive basis-scaling constant $c$ that weights the entries of the lattice basis, the smoothness bound (only primes up to this bound are used in relations), the choice of LLL backend, and the random permutation of the diagonal entries of the lattice basis matrix. The objective is to characterize jointly:

(i) the cost of the classical preprocessing (LLL reduction and Babai nearest-plane) and the growth of the required lattice dimension with $N$;

(ii) the number of quantum local searches needed per useful smooth-relation pair, given the per-run success probability — and, for variational versions, the additional statistical overhead of independent VQE restarts, ansatz depth, and optimizer effort;

(iii) the sensitivity of (i) and (ii) to the lattice-preprocessing implementation (LLL variant and backend, diagonal permutation, seeds), since different reduced bases of the same lattice demonstrably change downstream success;

(iv) the total success probability and total (classical plus quantum) resource count on instances of increasing size, from the toy scale up to the largest size at which the pipeline remains runnable, for the worst case or the average case under explicitly stated assumptions, together with the resulting scaling, under stated assumptions, up to RSA-scale $N$.

From these quantities, determine whether the total resources of any variant of the approach are asymptotically or practically superior to the best known classical factoring algorithms, taken as the General Number Field Sieve, with the comparison measured by total operation count (and qubit count for the quantum part) at a stated size — in particular, whether any parameter regime supports sublinear-resource claims such as challenging RSA-2048 with 372 physical qubits. All four components serve this single objective: a resource accounting sufficient to decide the pipeline's viability, since a verdict on the RSA-2048 claim is only as strong as the weakest link in the chain.

References

1. Luis Sánchez Cano, Ginés Carrascal de las Heras, Guillermo Botella Juan, Alberto del Barrio García, 'Factoring integers via Schnorr's algorithm assisted with VQE', arXiv:2411.16632 (2024), https://arxiv.org/abs/2411.16632
2. Bao Yan, Ziqi Tan, Shijie Wei, Haocong Jiang, Weilong Wang, Hong Wang, Lan Luo, Qianheng Duan, Yiting Liu, Wenhao Shi, Yangyang Fei, Xiangdong Meng, Yu Han, Zheng Shan, Jiachen Chen, Xuhao Zhu, Chuanyu Zhang, Feitong Jin, Hekang Li, Chao Song, Zhen Wang, Zhi Ma, H. Wang, Gui-Lu Long, 'Factoring integers with sublinear resources on a superconducting quantum processor', arXiv:2212.12372 (2022), https://arxiv.org/abs/2212.12372
3. Tanuj Khattar, Noureldin Yosri, 'A comment on "Factoring integers with sublinear resources on a superconducting quantum processor"', arXiv:2307.09651 (2023), https://arxiv.org/abs/2307.09651
4. Sergey V. Grebnev, Maxim A. Gavreev, Evgeniy O. Kiktenko, Anton P. Guglya, Albert R. Efimov, Aleksey K. Fedorov, 'Pitfalls of the Sublinear QAOA-Based Factorization Algorithm', IEEE Access 11, 134760-134768 (2023), DOI 10.1109/ACCESS.2023.3336989, arXiv:2303.04656, https://arxiv.org/abs/2303.04656
5. Willie Aboumrad, Dominic Widdows, Ananth Kaushik, 'Quantum and Classical Combinatorial Optimizations Applied to Lattice-Based Factorization', arXiv:2308.07804 (2023), https://arxiv.org/abs/2308.07804
6. Ilia V. Zalivako, Andrey Yu. Chernyavskiy, Anastasiia S. Nikolaeva, Alexander S. Borisenko, Nikita V. Semenin, Kristina P. Galstyan, Andrey E. Korolkov, Sergey V. Grebnev, Evgeniy O. Kiktenko, Ksenia Yu. Khabarova, Aleksey K. Fedorov, Ilya A. Semerikov, Nikolay N. Kolachevsky, 'Experimental Factoring Integers Using Fixed-Point-QAOA with a Trapped-Ion Quantum Processor', Quantum Information & Computation 25, 369-384 (2025), DOI 10.2478/qic-2025-0021, arXiv:2503.10588, https://arxiv.org/abs/2503.10588
7. Marco Tesoro, Ilaria Siloi, Daniel Jaschke, Giuseppe Magnifico, Simone Montangero, 'Integer factorization via tensor-network Schnorr's sieving', Physical Review A 113, 032418 (2026), DOI 10.1103/d9dl-ctt4, arXiv:2410.16355, https://arxiv.org/abs/2410.16355
8. Max O. Al-Hasso, Marko von der Leyen, 'A Probabilistic Computing Approach to the Closest Vector Problem for Lattice-Based Factoring', arXiv:2510.19390 (2025), https://arxiv.org/abs/2510.19390
9. Bao Yan, Shijie Wei, Guilu Long, 'The status and prospect of quantum-classical combination integer factorization algorithm', Scientia Sinica Informationis 55, 2084-2095 (2025), DOI 10.1360/ssi-2025-0105, https://doi.org/10.1360/ssi-2025-0105
10. Sarang Vehale, Deeksha Kushwah, Rahul Kumar Neiwal, Amit Saxena, 'Survey of Integer Factorization Using Lattice-Based Algorithms', SN Computer Science 7, 655 (2026), DOI 10.1007/s42979-026-05231-x, https://link.springer.com/article/10.1007/s42979-026-05231-x
11. C. P. Schnorr, 'Factoring Integers and Computing Discrete Logarithms via Diophantine Approximation', Advances in Cryptology - EUROCRYPT '91, Lecture Notes in Computer Science 547, 281-293 (1991), DOI 10.1007/3-540-46416-6_24, https://doi.org/10.1007/3-540-46416-6_24
12. A. K. Lenstra, H. W. Lenstra, L. Lovász, 'Factoring polynomials with rational coefficients', Mathematische Annalen 261, 515-534 (1982), DOI 10.1007/BF01457454, https://doi.org/10.1007/BF01457454
13. L. Babai, 'On Lovász' lattice reduction and the nearest lattice point problem', Combinatorica 6, 1-13 (1986), DOI 10.1007/BF02579403, https://doi.org/10.1007/BF02579403
14. Mona Sobhani, Yahui Chai, Tobias Hartung, Karl Jansen, 'Variational quantum eigensolver approach to prime factorization on IBM's noisy intermediate scale quantum computer', Physical Review A 111, 042413 (2025), DOI 10.1103/PhysRevA.111.042413, arXiv:2410.01935, https://arxiv.org/abs/2410.01935