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• 1 citation
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•5 citations

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

Windowed quantum arithmetic

Craig Gidney

We demonstrate a technique for optimizing quantum circuits that is analogous to classical windowing. Specifically, we show that small table lookups can allow control qubits to be iterated in groups instead of individually. We present various windowed quantum arithmetic circuits, including a windowed modular exponentiation with nested windowed modular multiplications, which have lower Toffoli counts than previous work at register sizes ranging from tens of qubits to thousands of qubits.

arXiv:1905.07682•May 19, 2019•68 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

Benchmarking the quantum cryptanalysis of symmetric, public-key and hash-based cryptographic schemes

Vlad Gheorghiu, Michele Mosca

Quantum algorithms can break factoring and discrete logarithm based cryptography and weaken symmetric cryptography and hash functions. In order to estimate the real-world impact of these attacks, apart from tracking the development of fault-tolerant quantum computers it is important to have an estimate of the resources needed to implement these quantum attacks. For attacking symmetric cryptography and hash functions, generic quantum attacks are substantially less powerful than they are for today's public-key cryptography. So security will degrade gradually as quantum computing resources increase. At present, there is a substantial resource overhead due to the cost of fault-tolerant quantum error correction. We provide estimates of this overhead using state-of-the-art methods in quantum fault-tolerance. We use state-of-the-art optimized circuits, though further improvements in their implementation would also reduce the resources needed to implement these attacks. To bound the potential impact of further circuit optimizations we provide cost estimates assuming trivial-cost implementations of these functions. These figures indicate the effective bit-strength of the various symmetric schemes and hash functions based on what we know today (and with various assumptions on the quantum hardware), and frame the various potential improvements that should continue to be tracked. As an example, we also look at the implications for Bitcoin's proof-of-work system. For many of the currently used asymmetric (public-key) cryptographic schemes based on RSA and elliptic curve discrete logarithms, we again provide cost estimates based on the latest advances in cryptanalysis, circuit compilation and quantum fault-tolerance theory. These allow, for example, a direct comparison of the quantum vulnerability of RSA and elliptic curve cryptography for a fixed classical bit strength.

arXiv:1902.02332•Feb 6, 2019•71 citations

Quantum cryptanalysis of symmetric, public-key and hash-based cryptographic schemes

Vlad Gheorghiu, Michele Mosca

Quantum algorithms can break factoring and discrete logarithm based cryptography and weaken symmetric cryptography and hash functions. In order to estimate the real-world impact of these attacks, apart from tracking the development of fault-tolerant quantum computers it is important to have an estimate of the resources needed to implement these quantum attacks. For attacking symmetric cryptography and hash functions, generic quantum attacks are substantially less powerful than they are for today's public-key cryptography. So security will degrade gradually as quantum computing resources increase. At present, there is a substantial resource overhead due to the cost of fault-tolerant quantum error correction. We provide estimates of this overhead using state-of-the-art methods in quantum fault-tolerance. We use state-of-the-art optimized circuits, though further improvements in their implementation would also reduce the resources needed to implement these attacks. To bound the potential impact of further circuit optimizations we provide cost estimates assuming trivial-cost implementations of these functions. These figures indicate the effective bit-strength of the various symmetric schemes and hash functions based on what we know today (and with various assumptions on the quantum hardware), and frame the various potential improvements that should continue to be tracked. As an example, we also look at the implications for Bitcoin's proof-of-work system. For many of the currently used asymmetric (public-key) cryptographic schemes based on RSA and elliptic curve discrete logarithms, we again provide cost estimates based on the latest advances in cryptanalysis, circuit compilation and quantum fault-tolerance theory. These allow, for example, a direct comparison of the quantum vulnerability of RSA and elliptic curve cryptography for a fixed classical bit strength.

•Feb 6, 2019•2 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.
Quantum algorithms can break factoring and discrete logarithm based cryptography and weaken symmetric cryptography and hash functions. In order to estimate the real-world impact of these attacks, apart from tracking the development of fault-tolerant quantum computers it is important to have an estimate of the resources needed to implement these quantum attacks. For attacking symmetric cryptography and hash functions, generic quantum attacks are substantially less powerful than they are for today's public-key cryptography. So security will degrade gradually as quantum computing resources increase. At present, there is a substantial resource overhead due to the cost of fault-tolerant quantum error correction. We provide estimates of this overhead using state-of-the-art methods in quantum fault-tolerance. We use state-of-the-art optimized circuits, though further improvements in their implementation would also reduce the resources needed to implement these attacks. To bound the potential impact of further circuit optimizations we provide cost estimates assuming trivial-cost implementations of these functions. These figures indicate the effective bit-strength of the various symmetric schemes and hash functions based on what we know today (and with various assumptions on the quantum hardware), and frame the various potential improvements that should continue to be tracked. As an example, we also look at the implications for Bitcoin's proof-of-work system. For many of the currently used asymmetric (public-key) cryptographic schemes based on RSA and elliptic curve discrete logarithms, we again provide cost estimates based on the latest advances in cryptanalysis, circuit compilation and quantum fault-tolerance theory. These allow, for example, a direct comparison of the quantum vulnerability of RSA and elliptic curve cryptography for a fixed classical bit strength.
Quantum algorithms can break factoring and discrete logarithm based cryptography and weaken symmetric cryptography and hash functions. In order to estimate the real-world impact of these attacks, apart from tracking the development of fault-tolerant quantum computers it is important to have an estimate of the resources needed to implement these quantum attacks. For attacking symmetric cryptography and hash functions, generic quantum attacks are substantially less powerful than they are for today's public-key cryptography. So security will degrade gradually as quantum computing resources increase. At present, there is a substantial resource overhead due to the cost of fault-tolerant quantum error correction. We provide estimates of this overhead using state-of-the-art methods in quantum fault-tolerance. We use state-of-the-art optimized circuits, though further improvements in their implementation would also reduce the resources needed to implement these attacks. To bound the potential impact of further circuit optimizations we provide cost estimates assuming trivial-cost implementations of these functions. These figures indicate the effective bit-strength of the various symmetric schemes and hash functions based on what we know today (and with various assumptions on the quantum hardware), and frame the various potential improvements that should continue to be tracked. As an example, we also look at the implications for Bitcoin's proof-of-work system. For many of the currently used asymmetric (public-key) cryptographic schemes based on RSA and elliptic curve discrete logarithms, we again provide cost estimates based on the latest advances in cryptanalysis, circuit compilation and quantum fault-tolerance theory. These allow, for example, a direct comparison of the quantum vulnerability of RSA and elliptic curve cryptography for a fixed classical bit strength.