Reversible quantum networks for asymptotically fast multiplication in Shor's factoring algorithm: construction, scratch space, and crossover

Shor's quantum factoring algorithm is dominated by modular exponentiation, whose cost in the known reversible networks is set by the integer-multiplication circuits inside it. In 1996, Beckman, Chari, Devabhaktuni and Preskill constructed explicit quantum networks that factor a $K$-bit number using $5K+1$ qubits and of order $K^3$ elementary gates, and noted that classical fast-multiplication algorithms such as Schonhage-Strassen (which multiplies $K$-bit numbers in $O(K\log K\log\log K)$ operations) should in principle lower the modular-exponentiation time to order $LK\log K\log\log K$, while explicitly leaving the corresponding reversible networks, their precise scratch-space requirements, and the regime in which such fast arithmetic actually pays off unworked out. The problem is to construct reversible quantum networks implementing asymptotically fast classical integer multiplication inside modular exponentiation, determine their precise ancilla (scratch-space) and gate costs, and establish the crossover point, including overheads, beyond which they beat the quadratic-time networks. Later literature has built sub-quadratic reversible multipliers (Zalka's two-level FFT-based networks of 1998; Toom-Cook networks of 2018; space-optimal Karatsuba of 2019) and complete fault-tolerant resource estimates now exist for 2048-bit RSA factoring with windowed quadratic arithmetic, but no quasi-linear-time reversible multiplier composed with the modern windowed, coset-representation and error-correction machinery has been constructed, and a rigorous crossover analysis under full fault-tolerance overheads is still missing; a 2021 reference resource estimate explicitly lists this as future work.

Background

Shor's factoring algorithm (1994) finds a nontrivial factor of an $n$-bit composite integer by coherently evaluating the modular exponential $a\mapsto x^a \bmod N$ on a quantum superposition and then applying a quantum Fourier transform (a unitary that Fourier-transforms the amplitudes of a register, used to extract the period of the function). The bottleneck is the modular exponentiation: it must be executed as a reversible quantum circuit, because quantum computation is unitary and cannot overwrite or discard information mid-computation.

Reversible arithmetic has a characteristic cost structure. Every elementary step is built from reversible logic gates such as the Toffoli gate (a three-bit controlled-controlled-NOT that flips its target only when both controls are set, and from which all classical Boolean logic can be built reversibly). Intermediate results ('garbage') must be uncomputed, typically by running the computation backwards (Bennett's compute-uncompute trick), which roughly doubles the work and, if done at nested levels of recursion, can worsen the asymptotic gate count. Extra ancilla qubits ('scratch space') hold intermediates; minimizing both qubits and gates, and trading one against the other, is the central design problem of quantum arithmetic.

In this setting, Beckman, Chari, Devabhaktuni and Preskill (1996) analyzed the memory-versus-time tradeoff for Shor's algorithm in detail. Their networks, designed with the Cirac-Zoller linear ion-trap proposal in mind (an architecture whose two-qubit gates are driven by shared vibrational modes and which is intrinsically slow, with clock speeds plausibly well below $10^4$ operations per second), factor a $K$-bit number in time of order $K^3$ using $5K+1$ qubits, with about $72K^3$ elementary gates for the modular exponential. They also gave a $K^5$-time variant with even fewer qubits. The multiplications inside these networks are schoolbook (quadratic-time) ones: multiplying two $K$-bit numbers costs of order $K^2$ elementary reversible operations.

Classical algorithmics, however, provides faster multiplication: Karatsuba's divide-and-conquer method runs in $O(K^{\log_2 3})\approx O(K^{1.585})$, Toom-Cook generalizations interpolate to $O(K^{1+\varepsilon})$ for fixed $\varepsilon$, and the Schonhage-Strassen algorithm multiplies $K$-bit integers in $O(K\log K\log\log K)$ time by embedding them in a finite ring and applying the fast Fourier transform over that ring (a number-theoretic transform with exact modular arithmetic, not to be confused with the quantum Fourier transform acting on amplitudes). The 1996 paper observed that invoking such algorithms should reduce modular exponentiation on a quantum computer to time of order $LK\log K\log\log K$ (where $L\approx 2K$ is the bit length of the exponent), but stated: 'We have not worked out the corresponding networks in detail, or determined the precise scratch space requirements for such an algorithm.' It also warned that fast multiplication requires additional storage and carries a high overhead, so that the speed advantage is realized only when the numbers being multiplied are enormous. Making fast classical multiplication reversible is not a routine translation: recursive divide-and-conquer algorithms allocate large intermediate arrays, and reversible implementations must uncompute them, so the translation changes both the asymptotic gate count and the space requirements in ways that must be worked out explicitly.

This arithmetic question sits inside a broader program the same paper framed: the incorporation of quantum error correction into the operation of large reversible networks (so that a factoring network can run reliably despite decoherence, the decoherence of a pure superposition into a statistical mixture through entanglement with the environment), and the scaling of physical hardware, which the authors judged to be far beyond the ion-trap clock speeds of the time. The error-correction and resource-estimate parts of that program have since been substantially carried out (fault-tolerant quantum computation and complete surface-code resource estimates for 2048-bit RSA factoring), which sharpens the arithmetic question: fast multipliers must now also compose with error-corrected, architecture-aware cost models, where every additional ancilla qubit competes with other uses of the hardware such as factories that distill special resource states (magic states) needed for reversible logic gates.

Problem Statement

Construct reversible quantum networks that implement asymptotically fast classical integer multiplication (exemplified by the Schonhage-Strassen FFT-based algorithm, which multiplies $K$-bit numbers in $O(K\log K\log\log K)$ elementary operations) as the inner loop of the modular exponentiation in Shor's factoring algorithm, so that the modular exponential $a\mapsto x^a \bmod N$ is evaluated on a $K$-bit number $N$ in time of order $LK\log K\log\log K$ (with $L$ the bit length of the exponent). For such networks, determine (i) the precise scratch-space (ancilla qubit) requirements, including the cost of uncomputing the intermediate arrays that fast multiplication generates, and (ii) the total gate/time cost with explicit constant and overhead factors. Then determine the crossover regime: for which input sizes, and under which assumptions about parallelism, qubit availability and error-correction overheads, these asymptotically fast networks actually outperform the quadratic-time (schoolbook or windowed) multiplication networks used in the known Shor constructions. The construction should be stated so that its costs can be compared within a fault-tolerant resource-estimate framework, since any large-scale factoring network must run under quantum error correction, where extra workspace competes with other uses of the hardware. The quantities to be determined are the ancilla count as an explicit function of $K$ in qubits, the gate and time costs as explicit functions of the input size with their constant factors, and the crossover under a cost metric such as Toffoli count or wall-clock time, as a function of the assumptions adopted about parallelism, qubit availability and error-correction overheads.

References

1. D. Beckman, A. N. Chari, S. Devabhaktuni, J. Preskill, 'Efficient networks for quantum factoring', Phys. Rev. A 54, 1034 (1996). DOI: 10.1103/PhysRevA.54.1034, https://doi.org/10.1103/PhysRevA.54.1034 (preprint: arXiv:quant-ph/9602016, https://arxiv.org/abs/quant-ph/9602016)
2. C. Zalka, 'Fast versions of Shor's quantum factoring algorithm', arXiv:quant-ph/9806084 (1998, unpublished preprint). arXiv: quant-ph/9806084, https://arxiv.org/abs/quant-ph/9806084
3. P. W. Shor, 'Fault-tolerant quantum computation', in 37th Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society Press, 1996, pp. 56-65. arXiv: quant-ph/9605011, https://arxiv.org/abs/quant-ph/9605011
4. T. Monz, D. Nigg, E. A. Martinez, M. F. Brandl, P. Schindler, R. Rines, S. X. Wang, I. L. Chuang, R. Blatt, 'Realization of a scalable Shor algorithm', Science 351 (6277), 1068-1070 (2016). DOI: 10.1126/science.aad9480, https://doi.org/10.1126/science.aad9480
5. S. Dutta, D. Bhattacharjee, A. Chattopadhyay, 'Quantum circuits for Toom-Cook multiplication', Phys. Rev. A 98, 012311 (2018). DOI: 10.1103/PhysRevA.98.012311, https://doi.org/10.1103/PhysRevA.98.012311 (preprint: arXiv:1805.02342, https://arxiv.org/abs/1805.02342)
6. C. Gidney, 'Asymptotically efficient quantum Karatsuba multiplication', arXiv:1904.07356 (2019). arXiv: 1904.07356, https://arxiv.org/abs/1904.07356
7. C. Gidney, M. 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 (preprint: arXiv:1905.09749, https://arxiv.org/abs/1905.09749)
8. E. R. Hansen, S. Joshi, H. Rarick, 'Resource estimation of quantum multiplication algorithms', in 2023 IEEE International Conference on Quantum Computing and Engineering (QCE), 2023, pp. 199-202. DOI: 10.1109/QCE57702.2023.10211, https://doi.org/10.1109/QCE57702.2023.10211 (preprint: arXiv:2402.01891, https://arxiv.org/abs/2402.01891)
9. O. Regev, 'An efficient quantum factoring algorithm', Journal of the ACM 72(1), 1-13 (2025). DOI: 10.1145/3708471, https://doi.org/10.1145/3708471
10. S. Ragavan, V. Vaikuntanathan, 'Space-efficient and noise-robust quantum factoring', in Advances in Cryptology - CRYPTO 2024, Springer, 2024. DOI: 10.1007/978-3-031-68391-6_4, https://doi.org/10.1007/978-3-031-68391-6_4 (preprint: arXiv:2310.00899, https://arxiv.org/abs/2310.00899)
11. G. D. Kahanamoku-Meyer, S. Ragavan, V. Vaikuntanathan, K. Van Kirk, 'The Jacobi factoring circuit: quantum factoring with near-linear gates and sublinear space and depth', in Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC 2025), 2025. DOI: 10.1145/3717823.3718273, https://doi.org/10.1145/3717823.3718273 (preprint: arXiv:2412.12558, https://arxiv.org/abs/2412.12558)
12. A. M. Patoary, A. Vikram, V. Galitski, 'A discrete Fourier transform based quantum circuit for modular multiplication in Shor's algorithm', arXiv:2503.10008 (2025). arXiv: 2503.10008, https://arxiv.org/abs/2503.10008
13. D. Fedoriaka, B. Goldsmith, Y. Chen, 'Quantum arithmetic algorithms: implementation, resource estimation, and comparison', in 2025 IEEE International Conference on Quantum Computing and Engineering (QCE), 2025, pp. 349-355. DOI: 10.1109/QCE65121.2025.00047, https://doi.org/10.1109/QCE65121.2025.00047 (preprint: arXiv:2509.07015, https://arxiv.org/abs/2509.07015)
14. Y. Cao, M. Rivas, S. Guo, A. Küçükçolak, A. Ma, 'Detailed implementation of quantum Toom-Cook multiplication circuits and resource estimation', in 2025 IEEE International Conference on Quantum Computing and Engineering (QCE), 2025, pp. 424-425. DOI: 10.1109/QCE65121.2025.10377, https://doi.org/10.1109/QCE65121.2025.10377
15. V. Vandaele, 'Asymptotically optimal quantum circuits for comparators and incrementers', arXiv:2603.12917 (2026). arXiv: 2603.12917, https://arxiv.org/abs/2603.12917
16. T. Xue, J. P. Covey, 'Factoring 2048 bit RSA integers with a half-million-qubit modular atomic processor', arXiv:2605.03951 (2026). arXiv: 2605.03951, https://arxiv.org/abs/2605.03951