Sublinear logical quantum space for RSA factoring
- Field
- Topics
Problem
Can every balanced RSA semiprime be factored in polynomial time using sublinear logical quantum space?
Let \(N=pq\) be an \(n\)-bit integer whose distinct odd prime factors have bit length \(n/2+O(1)\). Does a uniform hybrid algorithm exist that factors every such \(N\) with probability at least \(2/3\) while satisfying
Here \(q(n)\) in Eq. (1) counts all simultaneously live logical qubits, including control, data, workspace, quantum memory, and resource states. Polynomial classical storage, intermediate measurements, and resets are allowed, and total runtime includes repetitions and classical processing.
Source
This precise formulation is editor wording based on the unresolved direction and limitations documented in the cited primary literature [Chevignard25][Ragavan26][KahanamokuMeyer25]; it is not presented as a verbatim conjecture of those authors.
Progress
CRYPTO 2025, full version revised December 31, 2025. Chevignard, Fouque, and Schrottenloher factor \(n\)-bit RSA moduli with \(n/2+o(n)\) logical qubits. Their modular-exponentiation technique uses sublinear work space, but the full algorithm still has linear total quantum width. These are different claims. [Chevignard25]
February 4, 2026. Ragavan and Vaikuntanathan give a space-efficient Regev implementation with \(O(n\log n)\) qubits and \(O(n^{3/2}\log n)\) gates per circuit. This improves the space–work balance of that approach but remains superlinear in the qubit parameter relevant here. [Ragavan26]
July 2, 2026 revision. For \(P^2Q\) with \(\log Q=\Theta(n^a)\) and \(2/3<a<1\), the Jacobi construction has \(\widetilde O(\log Q)=o(n)\) quantum space and depth. This is genuine progress for a classically difficult factoring family, but not for balanced RSA semiprimes. [KahanamokuMeyer25]
Earlier “sublinear-resource” claims require care. A primary critique by Khattar and Yosri found failures in the proposed Schnorr/QAOA factoring approach even when idealizing its optimizer. Such heuristic proposals do not supply the uniform polynomial-time guarantee in this question. [Khattar23]
Retained as open for RSA. A broader claim that no classically difficult factoring family admits proven sublinear quantum space would already be false.
Comment
This problem is a precise resource target formulated here from the quantum-space frontier.
The important distinction is between reducing workspace around an existing coherent register and reducing total coherent information storage. Replacing a large work register by recomputation does not resolve the problem when another register remains of size \(\Theta(n)\).
There is no inference here that \(\Omega(n)\) logical qubits are necessary for all polynomial-time hybrid factoring algorithms. Establishing such a universal lower bound would be a different, substantially stronger undertaking. The permitted classical memory also means that an information-counting argument based only on the \(n\)-bit input length is insufficient: the input need not reside in quantum memory.
References
- [Chevignard25]
- Clémence Chevignard, Pierre-Alain Fouque, and André Schrottenloher. Reducing the Number of Qubits in Quantum Factoring. CRYPTO 2025; ePrint 2024/222, full version last revised December 31, 2025.link
- [Ragavan26]
- Seyoon Ragavan and Vinod Vaikuntanathan. Space-Efficient and Noise-Robust Quantum Factoring. Journal of Cryptology 39, article 14 (2026), published February 4, 2026.link
- [KahanamokuMeyer25]
- Gregory D. Kahanamoku-Meyer, Seyoon Ragavan, Vinod Vaikuntanathan, and Katherine Van Kirk. The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth. STOC 2025; July 2, 2026. Especially the input-family restriction and the sublinear-space result.arXiv
- [Khattar23]
- Tanuj Khattar and Noureldin Yosri. A comment on “Factoring integers with sublinear resources on a superconducting quantum processor”.(2023), preprint.arXiv