Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM/IEEE Design Automation Conference (DAC)

Optimizing windowed arithmetic for quantum attacks against RSA-2048

Alessandro Luongo, Varun Narasimhachar, Adithya Sireesh

Published Jun 22, 2025• 0 citations
Publisher

Abstract

Windowed arithmetic is a technique for reducing the cost of quantum arithmetic circuits with space-time trade-offs using memory queries to precomputed tables. It can reduce the asymptotic cost of modular exponentiation from $\mathcal{O}\left(n^{2}\right)$ to $\mathcal{O}\left(n^{2} / \log ^{2} n\right)$ operations, resulting in the current state-of-the-art compilations of quantum attacks against modern cryptography. We introduce several optimizations to windowed arithmetic. Notably, we effect an approximate $50 \%$ reduction in the costs of uncomputing memory lookups in quantum factoring applications. We validate our optimizations by improving the gate count of quantum attacks against public-key cryptography by $1.5 \%$ to $3.4 \%$, depending on the key size. We also enable a $16 \%$ runtime reduction at the cost of a $12 \%$ increase in qubit count. Our techniques can be used to reduce the complexity of not only factoring algorithms but also a wide range of quantum algorithms that rely on windowed arithmetic.

DOI
10.1109/dac63849.2025.11132436

Related papers

Optimized circuits for windowed modular arithmetic with applications to quantum attacks against RSA

Alessandro Luongo, Varun Narasimhachar, Adithya Sireesh

Windowed arithmetic [Gidney, 2019] is a technique for reducing the cost of quantum arithmetic circuits with space--time tradeoffs using memory queries to precomputed tables. It can reduce the asymptotic cost of modular exponentiation from $O\left(n^3\right)$ to $O\left(n^3/\log^2 n\right)$ operations, resulting in the current state-of-the-art compilations of quantum attacks against modern cryptography. In this work we introduce four optimizations to windowed modular exponentiation. We (1) show how the cost of unlookups can be reduced by $66\%$ asymptotically in the number of bits, (2) illustrate how certain addresses can be bypassed, reducing both circuit depth and the overall lookup cost, (3) demonstrate that multiple lookup--addition operations can be merged into a single, larger lookup at the start of the modular exponentiation circuit, and (4) reduce the depth of the unary conversion for unlookups. On a logical level, this leads to a $3\%$ improvement in Toffoli count and Toffoli depth for modular exponentiation circuits relevant to cryptographic applications. This translates to some improvements on [Gidney and Ekerå, 2021]'s factoring algorithm: for a given number of physical qubits, our improvements show a reduction in the expected runtime from $2\%$ to $6\%$ for factoring $\mathsf{RSA}$-$2048$ integers.

arXiv:2502.17325•Feb 24, 2025•1 citation

Quantum Arithmetic Circuits in Public-Key Cryptography

Siyi Wang, Kyungbae Jang, Hyunji Kim +4 more

Quantum computing has advanced rapidly in recent decades, driven by developments across the technology stack, including quantum error-correcting codes and efficient quantum algorithms. Among these, quantum arithmetic circuits serve as fundamental building blocks for various promising algorithms. Despite their crucial role, the design of quantum arithmetic circuits faces challenges arising from the no-cloning theorem, qubit limitations, and circuit depth constraints, which significantly impact the efficiency of large-scale quantum computing. We provide an overview of quantum arithmetic circuits in the context of public-key cryptanalysis, with particular emphasis on optimization strategies such as measurement-based uncomputation and conditionally clean ancilla. We review state-of-the-art designs for essential arithmetic operations in public-key cryptanalysis such as addition, multiplication, and modular exponentiation. We also present an overview of the techniques used for fault-tolerant runtime and resource estimation in quantum cryptanalysis. In brief, this chapter emphasizes strategies for designing resource-efficient quantum arithmetic circuits, providing a basis for realistic evaluations of quantum cryptanalytic capabilities.

quant-pharXiv:2607.11713•Jul 14, 2026•0 citations

Quantum Arithmetic Algorithms: Implementation, Resource Estimation, and Comparison

Dmytro Fedoriaka, Brian Goldsmith, Yingrong Chen

As quantum computing technology advances, the need for optimized arithmetic circuits continues to grow. This paper presents the implementation and resource estimation of a library of quantum arithmetic algorithms, including addition, multiplication, division, and modular exponentiation. Using the Azure Quantum Resource Estimator, we evaluate runtime, qubit usage, and space-time trade-offs and identify the best-performing algorithm for each arithmetic operation. We explore the design space for division, optimize windowed modular exponentiation, and identify the tipping point between multipliers, demonstrating effective applications of resource estimation in quantum research. Additionally, we highlight the impact of parallelization, reset operations, and uncomputation techniques on implementation and resource estimation. Our findings provide both a practical library and a valuable knowledge base for selecting and optimizing quantum arithmetic algorithms in real-world applications.

arXiv:2509.07015•IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 citations

Space-Efficient and Noise-Robust Quantum Factoring

Seyoon Ragavan, Vinod Vaikuntanathan

We provide two improvements to Regev's recent quantum factoring algorithm (Journal of the ACM 2025), addressing its space efficiency and its noise-tolerance. Our first contribution is to improve the quantum space efficiency of Regev's algorithm while keeping the circuit size the same. Our main result constructs a quantum factoring circuit using $O(n \log n)$ qubits and $O(n^{3/2} \log n)$ gates. We achieve the best of Shor and Regev (upto a logarithmic factor in the space complexity): on the one hand, Regev's circuit requires $O(n^{3/2})$ qubits and $O(n^{3/2} \log n)$ gates, while Shor's circuit requires $O(n^2 \log n)$ gates but only $O(n \log n)$ qubits. As with Regev, to factor an $n$-bit integer $N$, we run our circuit independently $O(\sqrt{n})$ times and apply Regev's classical postprocessing procedure. Our optimization is achieved by implementing efficient and reversible exponentiation with Fibonacci numbers in the exponent, rather than the usual powers of 2, adapting work by Kaliski (arXiv:1711.02491) from the classical reversible setting to the quantum setting. This technique also allows us to perform quantum modular exponentiation that is efficient in both space and size without requiring significant precomputation, a result that may be useful for other quantum algorithms. A key ingredient of our exponentiation implementation is an efficient circuit for a function resembling in-place quantum-quantum modular multiplication. Our second contribution is to show that Regev's classical postprocessing procedure can be modified to tolerate a constant fraction of the quantum circuit runs being corrupted by errors. In contrast, Regev's analysis of his classical postprocessing procedure requires all $\approx \sqrt{n}$ runs to be successful. In a nutshell, we achieve this using lattice reduction techniques to detect and filter out corrupt samples.

arXiv:2310.00899•Oct 2, 2023•2 citations

How to factor 2048 bit RSA integers with less than a million noisy qubits

Craig Gidney

Planning the transition to quantum-safe cryptosystems requires understanding the cost of quantum attacks on vulnerable cryptosystems. In Gidney+Ekerå 2019, I co-published an estimate stating that 2048 bit RSA integers could be factored in eight hours by a quantum computer with 20 million noisy qubits. In this paper, I substantially reduce the number of qubits required. I estimate that a 2048 bit RSA integer could be factored in less than a week by a quantum computer with less than a million noisy qubits. I make the same assumptions as in 2019: a square grid of qubits with nearest neighbor connections, a uniform gate error rate of $0.1\%$, a surface code cycle time of 1 microsecond, and a control system reaction time of $10$ microseconds. The qubit count reduction comes mainly from using approximate residue arithmetic (Chevignard+Fouque+Schrottenloher 2024), from storing idle logical qubits with yoked surface codes (Gidney+Newman+Brooks+Jones 2023), and from allocating less space to magic state distillation by using magic state cultivation (Gidney+Shutty+Jones 2024). The longer runtime is mainly due to performing more Toffoli gates and using fewer magic state factories compared to Gidney+Ekerå 2019. That said, I reduce the Toffoli count by over 100x compared to Chevignard+Fouque+Schrottenloher 2024.

arXiv:2505.15917•May 21, 2025•7 citations

QUANTUM ANNEALING APPROACHES TO BREAKING RSA ENCRYPTION

Yaroslav Aleksandrovich Kholodov, Hadi Salloum, Natalia A. Agapova

Objective: to study the transformational potential of quantum annealing in solving the problem of simple factorization. Research method(s): the approach includes a comprehensive review of recent experimental breakthroughs and theoretical innovations. In particular, we analyze techniques such as surface code memory, HUBO and QUBO formulations, range-dependent Hamiltonian algorithms, modular locally structured embedding methods, and a modified multiplication table method random number. Research Output(s): the study evaluates the application of quantum annealing to factorization of primes, showing that advanced problem mapping techniques, such as the HUBO and QUBO formulations, significantly improve the efficiency of representing complex factorization problems on quantum hardware. Notably, the inclusion of surface code memory increases the stability of qubit states during annealing, reducing errors and improving computational accuracy It also demonstrates that Hamiltonian's range-dependent algorithms and modular, locally structured embedding methods help optimize qubit interaction, enabling a more accurate factorization process. A modified multiplication table method is presented, providing an optimized computational strategy, especially effective for large composite numbers. Preliminary experiments with random numbers confirm the theoretical conclusions, indicating that these integrated methods allow for better performance than traditional approaches. Taken together, the results highlight the potential of quantum annealing as a solid foundation for solving complex cryptographic problems and lay the foundation for future research into scalable quantum algorithms and hardware implementations. Scientific novelty: the work combines several advanced quantum annealing techniques for factorization of prime numbers, combining experimental innovations with theoretical developments to propose a new framework that improves the efficiency of cryptographic computing.

Voprosy kiberbezopasnosti•Jan 1, 2025•0 citations
Windowed arithmetic is a technique for reducing the cost of quantum arithmetic circuits with space-time trade-offs using memory queries to precomputed tables. It can reduce the asymptotic cost of modular exponentiation from O(n2)\mathcal{O}\left(n^{2}\right)O(n2) to O(n2/log⁡2n)\mathcal{O}\left(n^{2} / \log ^{2} n\right)O(n2/log2n) operations, resulting in the current state-of-the-art compilations of quantum attacks against modern cryptography. We introduce several optimizations to windowed arithmetic. Notably, we effect an approximate 50%50 \%50% reduction in the costs of uncomputing memory lookups in quantum factoring applications. We validate our optimizations by improving the gate count of quantum attacks against public-key cryptography by 1.5%1.5 \%1.5% to 3.4%3.4 \%3.4%, depending on the key size. We also enable a 16%16 \%16% runtime reduction at the cost of a 12%12 \%12% increase in qubit count. Our techniques can be used to reduce the complexity of not only factoring algorithms but also a wide range of quantum algorithms that rely on windowed arithmetic.
Windowed arithmetic [Gidney, 2019] is a technique for reducing the cost of quantum arithmetic circuits with space--time tradeoffs using memory queries to precomputed tables. It can reduce the asymptotic cost of modular exponentiation from O(n3)O\left(n^3\right)O(n3) to O(n3/log⁡2n)O\left(n^3/\log^2 n\right)O(n3/log2n) operations, resulting in the current state-of-the-art compilations of quantum attacks against modern cryptography. In this work we introduce four optimizations to windowed modular exponentiation. We (1) show how the cost of unlookups can be reduced by 66%66\%66% asymptotically in the number of bits, (2) illustrate how certain addresses can be bypassed, reducing both circuit depth and the overall lookup cost, (3) demonstrate that multiple lookup--addition operations can be merged into a single, larger lookup at the start of the modular exponentiation circuit, and (4) reduce the depth of the unary conversion for unlookups. On a logical level, this leads to a 3%3\%3% improvement in Toffoli count and Toffoli depth for modular exponentiation circuits relevant to cryptographic applications. This translates to some improvements on [Gidney and Ekerå, 2021]'s factoring algorithm: for a given number of physical qubits, our improvements show a reduction in the expected runtime from 2%2\%2% to 6%6\%6% for factoring RSA\mathsf{RSA}RSA-204820482048 integers.
Quantum computing has advanced rapidly in recent decades, driven by developments across the technology stack, including quantum error-correcting codes and efficient quantum algorithms. Among these, quantum arithmetic circuits serve as fundamental building blocks for various promising algorithms. Despite their crucial role, the design of quantum arithmetic circuits faces challenges arising from the no-cloning theorem, qubit limitations, and circuit depth constraints, which significantly impact the efficiency of large-scale quantum computing. We provide an overview of quantum arithmetic circuits in the context of public-key cryptanalysis, with particular emphasis on optimization strategies such as measurement-based uncomputation and conditionally clean ancilla. We review state-of-the-art designs for essential arithmetic operations in public-key cryptanalysis such as addition, multiplication, and modular exponentiation. We also present an overview of the techniques used for fault-tolerant runtime and resource estimation in quantum cryptanalysis. In brief, this chapter emphasizes strategies for designing resource-efficient quantum arithmetic circuits, providing a basis for realistic evaluations of quantum cryptanalytic capabilities.
As quantum computing technology advances, the need for optimized arithmetic circuits continues to grow. This paper presents the implementation and resource estimation of a library of quantum arithmetic algorithms, including addition, multiplication, division, and modular exponentiation. Using the Azure Quantum Resource Estimator, we evaluate runtime, qubit usage, and space-time trade-offs and identify the best-performing algorithm for each arithmetic operation. We explore the design space for division, optimize windowed modular exponentiation, and identify the tipping point between multipliers, demonstrating effective applications of resource estimation in quantum research. Additionally, we highlight the impact of parallelization, reset operations, and uncomputation techniques on implementation and resource estimation. Our findings provide both a practical library and a valuable knowledge base for selecting and optimizing quantum arithmetic algorithms in real-world applications.
We provide two improvements to Regev's recent quantum factoring algorithm (Journal of the ACM 2025), addressing its space efficiency and its noise-tolerance. Our first contribution is to improve the quantum space efficiency of Regev's algorithm while keeping the circuit size the same. Our main result constructs a quantum factoring circuit using O(nlog⁡n)O(n \log n)O(nlogn) qubits and O(n3/2log⁡n)O(n^{3/2} \log n)O(n3/2logn) gates. We achieve the best of Shor and Regev (upto a logarithmic factor in the space complexity): on the one hand, Regev's circuit requires O(n3/2)O(n^{3/2})O(n3/2) qubits and O(n3/2log⁡n)O(n^{3/2} \log n)O(n3/2logn) gates, while Shor's circuit requires O(n2log⁡n)O(n^2 \log n)O(n2logn) gates but only O(nlog⁡n)O(n \log n)O(nlogn) qubits. As with Regev, to factor an nnn-bit integer NNN, we run our circuit independently O(n)O(\sqrt{n})O(n​) times and apply Regev's classical postprocessing procedure. Our optimization is achieved by implementing efficient and reversible exponentiation with Fibonacci numbers in the exponent, rather than the usual powers of 2, adapting work by Kaliski (arXiv:1711.02491) from the classical reversible setting to the quantum setting. This technique also allows us to perform quantum modular exponentiation that is efficient in both space and size without requiring significant precomputation, a result that may be useful for other quantum algorithms. A key ingredient of our exponentiation implementation is an efficient circuit for a function resembling in-place quantum-quantum modular multiplication. Our second contribution is to show that Regev's classical postprocessing procedure can be modified to tolerate a constant fraction of the quantum circuit runs being corrupted by errors. In contrast, Regev's analysis of his classical postprocessing procedure requires all ≈n\approx \sqrt{n}≈n​ runs to be successful. In a nutshell, we achieve this using lattice reduction techniques to detect and filter out corrupt samples.
Planning the transition to quantum-safe cryptosystems requires understanding the cost of quantum attacks on vulnerable cryptosystems. In Gidney+Ekerå 2019, I co-published an estimate stating that 2048 bit RSA integers could be factored in eight hours by a quantum computer with 20 million noisy qubits. In this paper, I substantially reduce the number of qubits required. I estimate that a 2048 bit RSA integer could be factored in less than a week by a quantum computer with less than a million noisy qubits. I make the same assumptions as in 2019: a square grid of qubits with nearest neighbor connections, a uniform gate error rate of 0.1%0.1\%0.1%, a surface code cycle time of 1 microsecond, and a control system reaction time of 101010 microseconds. The qubit count reduction comes mainly from using approximate residue arithmetic (Chevignard+Fouque+Schrottenloher 2024), from storing idle logical qubits with yoked surface codes (Gidney+Newman+Brooks+Jones 2023), and from allocating less space to magic state distillation by using magic state cultivation (Gidney+Shutty+Jones 2024). The longer runtime is mainly due to performing more Toffoli gates and using fewer magic state factories compared to Gidney+Ekerå 2019. That said, I reduce the Toffoli count by over 100x compared to Chevignard+Fouque+Schrottenloher 2024.
Objective: to study the transformational potential of quantum annealing in solving the problem of simple factorization. Research method(s): the approach includes a comprehensive review of recent experimental breakthroughs and theoretical innovations. In particular, we analyze techniques such as surface code memory, HUBO and QUBO formulations, range-dependent Hamiltonian algorithms, modular locally structured embedding methods, and a modified multiplication table method random number. Research Output(s): the study evaluates the application of quantum annealing to factorization of primes, showing that advanced problem mapping techniques, such as the HUBO and QUBO formulations, significantly improve the efficiency of representing complex factorization problems on quantum hardware. Notably, the inclusion of surface code memory increases the stability of qubit states during annealing, reducing errors and improving computational accuracy It also demonstrates that Hamiltonian's range-dependent algorithms and modular, locally structured embedding methods help optimize qubit interaction, enabling a more accurate factorization process. A modified multiplication table method is presented, providing an optimized computational strategy, especially effective for large composite numbers. Preliminary experiments with random numbers confirm the theoretical conclusions, indicating that these integrated methods allow for better performance than traditional approaches. Taken together, the results highlight the potential of quantum annealing as a solid foundation for solving complex cryptographic problems and lay the foundation for future research into scalable quantum algorithms and hardware implementations. Scientific novelty: the work combines several advanced quantum annealing techniques for factorization of prime numbers, combining experimental innovations with theoretical developments to propose a new framework that improves the efficiency of cryptographic computing.