Windowed quantum arithmetic
Open accessAbstract
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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Windowed arithmetic reduces the number of modular multiplications by using small table lookups to fuse several multiplications together.
“The number of multiplications is reduced by using windowed arithmetic [35, 51, 83], which uses small table lookups to fuse several multiplications together.”
From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [35]
Windowed arithmetic can fuse multiple additions into individual lookup additions.
“We use windowed arithmetic (again) to fuse multiple additions into individual lookup additions [35].”
From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [35]
The paper follows the modular exponentiation construction from [35] and uses windowing at two levels.
“Specifically, we follow the modular exponentiation construction from [35] and use windowing at two levels.”
From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [35]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
Babbush, R., Gidney, C., Berry, D. W., Wiebe, N., McClean, J., Paler, A., Fowler, A., & Neven, H. (2018) · Physical Review X · doi:10.1103/physrevx.8.041015 · Cited by 383 · see citing works
Self-citationHalving the cost of quantum addition
Gidney, C. (2018) · Quantum · doi:10.22331/q-2018-06-18-74 · Cited by 279 · see citing works
Self-citationFactoring using $2n+2$ qubits with Toffoli based modular multiplication
Haner, T., Roetteler, M., & Svore, K. M. (2017) · Quantum Information and Computation · doi:10.26421/qic17.7-8-7 · Cited by 90 · cited 2× · see citing works
“Modular exponentiation is typically implemented using a series of controlled modular multiplications [14, 15, 9, 6].”
MethodFast versions of Shor's quantum factoring algorithm
Zalka, C. (1998) · arXiv · doi:10.48550/arxiv.quant-ph/9806084 · Cited by 73 · see citing works
Flagged first, then by citations
Research works printed but not linked: 12
- [2][2] R. Barends, J. Kelly, A. Megrant, A. Veitia, D. Sank, E. Jeffrey, T. C. White, J. Mutus, A. G. Fowler, B. Campbell, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, C. Neill, P. O'Malley, P. Roushan, A. Vainsencher, J. Wenner, A. N. Korotkov, A. N. Cleland, and John M. Martinis. Superconducting quantum circuits at the surface code threshold for fault tolerance. Nature , 508:500-503, 2014. arXiv:1402.4848. - · arXiv
- [3][3] Dominic W Berry, Craig Gidney, Mario Motta, Jarrod R McClean, and Ryan Babbush. Qubitization of arbitrary basis quantum chemistry by low rank factorization. arXiv preprint arXiv:1902.02134 , 2019. - · arXiv
- [4][4] Earl Campbell, Ankur Khurana, and Ashley Montanaro. Applying quantum algorithms to constraint satisfaction problems. arXiv preprint arXiv:1810.05582 , 2018. - · arXiv
- [5][5] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland. Surface codes: Towards practical large-scale quantum computation. Phys. Rev. A , 86:032324, 2012. URL https://doi.org/10. 1103/PhysRevA.86.032324 . arXiv:1208.0928. - · arXiv
- [6][6] Craig Gidney. Factoring with n+ 2 clean qubits and n-1 dirty qubits. arXiv preprint arXiv:1706.07884 , 2017. - · arXiv
- [8][8] Craig Gidney. Asymptotically efficient quantum karatsuba multiplication. arXiv preprint arXiv:1904.07356 , 2019. - · arXiv
- [10][10] Y. Kim, R. Daly, J. Kim, C. Fallin, J. H. Lee, D. Lee, C. Wilkerson, K. Lai, and O. Mutlu. Flipping bits in memory without accessing them: An experimental study of dram disturbance errors. In 2014 ACM/IEEE 41st International Symposium on Computer Architecture (ISCA) , pages 361-372, June 2014. DOI: 10.1109/ISCA.2014.6853210. - · DOI · Paper page
- [11][11] Guang Hao Low, Vadym Kliuchnikov, and Luke Schaeffer. Trading t-gates for dirty qubits in state preparation and unitary synthesis. arXiv preprint arXiv:1812.00954 , 2018. - · arXiv
- [12][12] Aram Perez. Byte-wise crc calculations. IEEE Micro , 3(3):40-50, 1983. DOI: 10.1109/MM.1983.291120. - · DOI
- [13][13] Bianca Schroeder, Eduardo Pinheiro, and Wolf-Dietrich Weber. Dram errors in the wild: a large-scale field study. In ACM SIGMETRICS Performance Evaluation Review , volume 37, pages 193-204. ACM, 2009. -
- [14][14] Vlatko Vedral, Adriano Barenco, and Artur Ekert. Quantum networks for elementary arithmetic operations. Physical Review A , 54(1):147, 1996. -
- [16][16] Christof Zalka. Shor's algorithm with fewer (pure) qubits. arXiv preprint quant-ph/0601097 , 2006. · arXiv
Cited by
Sorted by citations
How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
Gidney, C., & Ekerå, M. (2021) · Quantum · doi:10.22331/q-2021-04-15-433 · Cited by 830 · see citing works
Self-citationImplementing Grover Oracles for Quantum Key Search on AES and LowMC
Jaques, S., Naehrig, M., Roetteler, M., & Virdia, F. (2020) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-45724-2_10 · Cited by 234 · see citing works
“Yet, on a quantum computer, this is not efficient (see [5,32] and [20]).”
BackgroundImproved Quantum Circuits for Elliptic Curve Discrete Logarithms
Häner, T., Jaques, S., Naehrig, M., Roetteler, M., & Soeken, M. (2020) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-44223-1_23 · Cited by 76 · see citing works
Flexible layout of surface code computations using AutoCCZ states
Gidney, C., & Fowler, A. G. (2019) · arXiv · doi:10.48550/arxiv.1905.08916 · Cited by 12 · see citing works
Self-citationHow to factor 2048 bit RSA integers with less than a million noisy qubits
Gidney, C. (2025) · arXiv · Cited by 7 · see citing works
“The second optimization that I apply is windowing [Kut06; VI05; Gid19b].”
Self-citation
- Authors
- Gidney, C.
- Affiliations
- Google (United States) (US)
- Corresponding author
- Gidney, Craig
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2019
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1905.07682
- OpenAlex
- W2945626982
- Cited by
- 11
- References
- 4
- Citations by year
- 2026: 1 · 2025: 1 · 2023: 3 · 2022: 2 · 2020: 2 · 2019: 2
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University) (cc-by)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Information Systems › Cryptography and Residue Arithmetic
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Keywords
- quantum circuit optimization, look-up table, modular exponentiation, modular multiplication, quantum arithmetic circuits
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
