Subquadratic total quantum gate complexity of RSA factoring

Problem

Can every balanced RSA semiprime be factored with polynomially subquadratic total quantum gate complexity?

Let \(N=pq\) be an \(n\)-bit integer whose distinct odd prime factors have bit length \(n/2+O(1)\). Does there exist a constant \(\delta>0\) and a uniform hybrid quantum–classical algorithm that factors every such \(N\) with probability at least \(2/3\) using

\begin{equation} G_{\mathrm{total}}(n)=O(n^{2-\delta}) \tag{1} \end{equation}

quantum gates and \(n^{O(1)}\) classical computation? The cost in Eq. (1) includes every quantum execution, restart, state preparation, measurement, reset, and gate-synthesis cost over a fixed finite universal gate set; modular exponentiation is not a unit-cost oracle.

Source

This precise formulation is editor wording based on the unresolved direction and limitations documented in the cited primary literature [Regev25][Pilatte26][KahanamokuMeyer25]; it is not presented as a verbatim conjecture of those authors.

Progress

Baseline. Shor established polynomial-time quantum factoring. With fast arithmetic, the relevant benchmark for total quantum work is nearly quadratic in \(n\). This is an upper-bound benchmark, not a proven lower bound. [Shor97], [Regev25]
Regev, 2023 preprint / 2025 journal publication. The improved circuit uses \(\widetilde O(n^{3/2})\) gates per execution, but the factoring procedure uses \(O(\sqrt n)\) executions. Thus its displayed resource accounting gives \(\widetilde O(n^2)\) total quantum gates, rather than settling the target above. Reducing the cost of a single coherent run remains valuable even without a total-exponent improvement. [Regev25]
Correctness update, February 9, 2026. Pilatte proves unconditional correctness for suitable versions of recent factoring and discrete-logarithm algorithms. Consequently, the blanket claim that these approaches still await a number-theoretic correctness conjecture is outdated. That progress does not, by itself, reduce the total quantum gate exponent. [Pilatte26]
Special-instance advance, latest revision July 2, 2026. The Jacobi factoring circuit achieves near-linear quantum gates for a substantial class including certain \(P^2Q\) inputs, but explicitly excludes RSA integers themselves. It therefore does not answer the balanced-semiprime question. [KahanamokuMeyer25]
Retained as open. Neither a per-run improvement nor an algorithm for a different factorization pattern establishes the specified total-cost bound for RSA semiprimes.

Comment

This problem is a precise resource target formulated here, not a named conjecture.

A useful way to expose the obstacle is to write total quantum work as

\begin{equation} G_{\mathrm{total}}=(\text{cost per sample})(\text{number of samples}), \tag{2} \end{equation}

with any coherent multi-sample processing included. An improvement must beat the product, not just one factor. Possible research directions include sharing arithmetic between samples, extracting more useful information per run, or replacing modular exponentiation with a different arithmetic observable. These are suggested directions, not known solutions.

This question concerns logical quantum work. A lower gate count need not imply lower physical spacetime under every architecture, and polynomial classical preprocessing could still dominate overall runtime. The companion quantum-memory question asks a genuinely different question: the maximum quantum memory simultaneously required.

The displayed definitions, constraints, and target bounds are recorded in Eqs. (2).

References

[Shor97]: Peter W. Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing 26, 1484–1509 (1997);arXiv
[Regev25]: Oded Regev. An Efficient Quantum Factoring Algorithm. Journal of the ACM 72(1) (2025); Inspect the abstract and execution-count accounting, not only the per-circuit gate bound.arXiv
[Pilatte26]: Cédric Pilatte. Unconditional correctness of recent quantum algorithms for factoring and computing discrete logarithms. Forum of Mathematics, Pi, published February 9, 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.arXiv

Subquadratic total quantum gate complexity of RSA factoring

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems