Rigorous complexity analysis of QAOA-assisted Schnorr lattice factoring with sublinear quantum resources

The December 2022 preprint 'Factoring integers with sublinear resources on a superconducting quantum processor' (Yan et al., arXiv:2212.12372) proposed the SQIF algorithm: combine Schnorr's lattice-based factoring method with the quantum approximate optimization algorithm (QAOA) applied to the closest-vector-problem (CVP) rounding step, use a sublinear lattice dimension $n=2c\log N/\log\log N$, and thereby challenge RSA-2048 with an estimated 372 physical qubits — while conceding that 'the quantum speedup of the algorithm is unclear due to the ambiguous convergence of QAOA'. Technical comments (Grebnev et al. 2023; Khattar and Yosri 2023; Aboumrad et al. 2023) found reproduction problems, unanalyzed classical costs, barren plateaus, and — most decisively — that even an ideal (brute-force) optimizer leaves the sublinear-dimension variant failing beyond roughly 70-80 bits; later work (tensor-network Schnorr sieving; trapped-ion fixed-point QAOA; fixed-angle QAOA for approximate CVP) keeps the route alive only at toy scale, and the original authors still defend it in a 2025 review. What no later work provides is the rigorous analysis whose absence the source itself conceded. The surviving open core is analytic and precise: prove or disprove (i) that QAOA-type variational optimization of the CVP rounding on Schnorr's prime lattices yields any asymptotic or provable advantage over classical lattice-reduction rounding, (ii) the validity of the relative-density assumption (Assumption 1) underlying the sublinear dimension choice at cryptographic sizes, and (iii) a quantified end-to-end runtime and success-probability bound for the hybrid algorithm — which together decide whether quantum-assisted lattice factoring is a genuine cryptanalytic threat and what it implies for lattice-based post-quantum cryptography.

Background

Integer factoring underpins the security of the RSA public-key cryptosystem: multiplying two large primes is easy, while no polynomial-time classical factoring algorithm is known. Shor's quantum algorithm (Peter W. Shor, SIAM Journal on Computing, 1997) factors integers in polynomial time on a fault-tolerant quantum computer, but the error-correction overhead is enormous — Gidney and Ekerå estimate about 20 million noisy physical qubits to factor a 2048-bit RSA integer in 8 hours. This gap motivated searches for factoring heuristics that could run on near-term noisy intermediate-scale quantum (NISQ) devices, which have hundreds to thousands of uncorrected qubits.

The quantum approximate optimization algorithm (QAOA) is a leading NISQ heuristic (Farhi, Goldstone, and Gutmann, 2014): a parameterized quantum state is prepared by alternately applying layers generated from a cost Hamiltonian — for combinatorial problems typically an Ising Hamiltonian, a diagonal operator on qubits whose ground state encodes the optimal bit assignment — and a mixing Hamiltonian, with the layer angles tuned by a classical optimizer. Despite hundreds of studies, no problem is known for which QAOA has a proven asymptotic speedup over the best classical algorithm.

Schnorr's lattice-based factoring method (C. P. Schnorr, 'Fast Factoring Integers by SVP Algorithms, corrected', IACR ePrint 2021/933) reduces factoring an integer $N$ to a sequence of approximate closest vector problems (CVP): given a lattice — a discrete additive subgroup of $\mathbb{R}^n$ — and a target point, find the lattice point nearest to the target. One seeks smooth relation pairs (sr-pairs): pairs of integers $u\equiv v \pmod N$ whose prime factors all lie below a smoothness bound $B_2$; enough independent sr-pairs yield linear equations over $\mathbb{F}_2$ whose solution discloses the factors of $N$. The search maps to approximate CVP on a 'prime lattice' whose basis encodes logarithms of small primes, and the probability that a CVP solution yields an sr-pair grows as the solution vector gets closer to the target. Classically the CVP step is handled by Babai's rounding procedure ('size reduction') applied to a reduced basis produced by LLL (the Lenstra–Lenstra–Lovász basis-reduction algorithm) or the stronger BKZ (block Korkine–Zolotarev) reduction.

Yan et al. (arXiv:2212.12372, December 2022) proposed the 'sublinear-resource quantum integer factorization' (SQIF) algorithm: encode Babai's rounding choices as an Ising Hamiltonian and use QAOA to search for closer lattice points than classical rounding finds, thereby raising the sr-pair yield. They factored 1961, 48567227, and the 48-bit integer 261980999226229 with 3, 5, and 10 superconducting qubits, chose lattice dimension $n=2c\log N/\log\log N$ (sublinear in the bit length of $N$), and estimated that a circuit of 372 physical qubits and depth of thousands could challenge RSA-2048. Their own conclusion concedes the pivotal caveat: 'the quantum speedup of the algorithm is unclear due to the ambiguous convergence of QAOA'.

The sublinear dimension choice rests on an unproven premise — Assumption 1 of the paper, a relative-density bound for the random prime lattices (a bound on how short the lattice's shortest vector $\lambda_1$ is relative to the Hermite-constant upper bound $\sqrt{\gamma_n}(\det\Lambda)^{1/n}$ for lattices of the same dimension and volume, i.e. on the relative density $rd(\Lambda)=\lambda_1/(\sqrt{\gamma_n}(\det\Lambda)^{1/n})$). This descends from the assumption attached to Schnorr's 2021 claim, which Leo Ducas's SchnorrGate reimplementation found empirically wanting: zero factoring relations in a thousand trials at 400-bit inputs with the claimed lattice dimension. The Yan et al. claims were publicly challenged within weeks (Scott Aaronson's 'Cargo Cult Quantum Factoring' post; Nature news coverage by Castelvecchi), and subsequent technical comments found reproduction issues, unanalyzed classical costs, barren plateaus (flat, vanishing-gradient cost landscapes that frustrate variational optimization), and a failure of the sublinear-dimension scheme beyond roughly 70-80 bits even with an ideal optimizer. Meanwhile a continuing 2024-2026 line of work — classical tensor-network Schnorr sieving (Tesoro et al.), trapped-ion experiments with fixed-point QAOA, i.e. QAOA whose layer angles are pre-set universal constants rather than optimized per instance (Zalivako et al.), fixed-angle QAOA of the same pre-set-angle kind for approximate CVP (Priestley and Wallden), and probabilistic-computing CVP refinement (Al-Hasso and von der Leyen) — probes the same quantum-optimization-for-lattice-problems idea, and the original authors defend the route in a 2025 review. What has never been produced, by either side, is the rigorous complexity analysis whose absence the source paper itself conceded.

Problem Statement

The unresolved problem is the rigorous, end-to-end complexity analysis of quantum-assisted Schnorr-type lattice factoring — the SQIF algorithm of Yan et al. and its natural variants — with one overarching objective: determine whether quantum variational optimization confers any real factoring advantage over classical lattice reduction. Three jointly linked questions constitute that objective, each feeding the next: all three are mandatory, each is independently resolvable on its own terms — a solution to any one settles that sub-question while the others, and hence the overarching objective, remain open — and the objective is resolved only when all three have been answered.

1. QAOA convergence and cost on the CVP-derived Hamiltonians. Prove or disprove that QAOA — at any specified depth and parameter regime, including fixed-angle and fixed-point variants, whose layer angles are pre-set universal constants rather than optimized per instance — applied to the Ising Hamiltonians encoding Babai's size-reduction step on Schnorr prime lattices yields an asymptotic runtime or solution-quality improvement over classical Babai/LLL/BKZ rounding for these instances. This includes how the required circuit depth, number of repetitions, and classical optimization effort scale with the lattice dimension $n$, and whether the observed barren plateaus can be provably avoided.

2. Validity of the lattice-density assumption. Prove or refute Assumption 1 of Yan et al. — the relative-density bound (a bound on the shortest vector of the random prime lattices relative to the Hermite-constant upper bound $\sqrt{\gamma_n}(\det\Lambda)^{1/n}$ for their dimension and volume) used in Schnorr's method — for RSA-like instances at cryptographic sizes, and determine the lattice dimension actually required as a function of $N$; in particular, whether the sublinear choice $n=2c\log N/\log\log N$ can suffice in any provable sense.

3. End-to-end resource scaling. Derive a quantified bound (worst-case, or averaged over the probabilistic sr-pair yield) for the total runtime, success probability, and quantum resources of the full hybrid algorithm — the number of QAOA-optimized CVP solves needed to collect enough independent sr-pairs, the classical lattice-reduction and linear-algebra costs, and the noise and depth tolerance required — as a function of $N$. Whereas item 2 concerns the lattice-dimension premise, this item requires the end-to-end consequence: establish whether factoring RSA-class integers with $O(\log N/\log\log N)$ qubits by this route is achievable at all, or prove that it is not.

Settling the overarching question also fixes what, if anything, quantum-assisted lattice subroutines imply for the security of lattice-based post-quantum cryptosystems, whose hardness assumptions concern general rather than prime-structured lattices.

References

1. 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, and Gui-Lu Long, 'Factoring integers with sublinear resources on a superconducting quantum processor', arXiv:2212.12372 (2022), https://arxiv.org/abs/2212.12372
2. C. P. Schnorr, 'Fast Factoring Integers by SVP Algorithms, corrected', IACR Cryptology ePrint Archive 2021/933 (2021), https://eprint.iacr.org/2021/933
3. Edward Farhi, Jeffrey Goldstone, and Sam Gutmann, 'A Quantum Approximate Optimization Algorithm', arXiv:1411.4028 (2014), https://arxiv.org/abs/1411.4028
4. Peter W. Shor, 'Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer', SIAM Journal on Computing (1997), DOI 10.1137/S0097539795293172, https://doi.org/10.1137/S0097539795293172
5. Craig Gidney and Martin Ekerå, 'How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits', Quantum 5, 433 (2021), DOI 10.22331/q-2021-04-15-433, https://doi.org/10.22331/q-2021-04-15-433
6. L. Babai, 'On Lovász' lattice reduction and the nearest lattice point problem', Combinatorica 6 (1986), DOI 10.1007/BF02579403, https://doi.org/10.1007/BF02579403
7. A. K. Lenstra, H. W. Lenstra, and L. Lovász, 'Factoring polynomials with rational coefficients', Mathematische Annalen (1982), DOI 10.1007/BF01457454, https://doi.org/10.1007/BF01457454
8. Sergey V. Grebnev, Maxim A. Gavreev, Evgeniy O. Kiktenko, Anton P. Guglya, Albert R. Efimov, and Aleksey K. Fedorov, 'Pitfalls of the Sublinear QAOA-Based Factorization Algorithm', IEEE Access 11, 134760-134768 (2023), DOI 10.1109/ACCESS.2023.3336989; preprint arXiv:2303.04656, https://arxiv.org/abs/2303.04656
9. Tanuj Khattar and 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
10. Willie Aboumrad, Dominic Widdows, and Ananth Kaushik, 'Quantum and Classical Combinatorial Optimizations Applied to Lattice-Based Factorization', arXiv:2308.07804 (2023), https://arxiv.org/abs/2308.07804
11. Marco Tesoro, Ilaria Siloi, Daniel Jaschke, Giuseppe Magnifico, and Simone Montangero, 'Integer factorization via tensor-network Schnorr's sieving', Physical Review A (2026), DOI 10.1103/d9dl-ctt4; preprint arXiv:2410.16355, https://arxiv.org/abs/2410.16355
12. 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, and Nikolay N. Kolachevsky, 'Experimental factoring integers using fixed-point-QAOA with a trapped-ion quantum processor', Quantum Information & Computation (2025), DOI 10.2478/qic-2025-0021; preprint arXiv:2503.10588, https://arxiv.org/abs/2503.10588
13. Ben Priestley and Petros Wallden, 'A Practically Scalable Approach to the Closest Vector Problem for Sieving via QAOA with Fixed Angles', arXiv:2503.08403 (2025), https://arxiv.org/abs/2503.08403
14. Max O. Al-Hasso and 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
15. Bao Yan, Shijie Wei, and Gui-Lu Long, 'The Status and Prospect of Quantum-Classical Combination Integer Factorization Algorithm', Scientia Sinica Informationis (2025), DOI 10.1360/ssi-2025-0105, https://doi.org/10.1360/ssi-2025-0105
16. Sarang Vehale, Deeksha Kushwah, Rahul Kumar Neiwal, and Amit Saxena, 'Survey of Integer Factorization Using Lattice-Based Algorithms', SN Computer Science (2026), DOI 10.1007/s42979-026-05231-x, https://doi.org/10.1007/s42979-026-05231-x
17. Scott Aaronson, 'Cargo Cult Quantum Factoring', Shtetl-Optimized blog, January 4, 2023, https://scottaaronson.blog/?p=6957
18. Davide Castelvecchi, 'Are quantum computers about to break online privacy?', Nature 613, 221 (2023), DOI 10.1038/d41586-023-00017-0, https://doi.org/10.1038/d41586-023-00017-0
19. Leo Ducas, 'SchnorrGate: Testing Schnorr's factorization claim in Sage', software and experimental notes (2021), https://github.com/lducas/SchnorrGate