CoChat
Sign Up
Cited by 181Quantum Computing Algorithms and ArchitectureCryptography and Residue ArithmeticQuantum Information and Cryptography

Fast quantum modular exponentiation

Open access
Van Meter, Rodney, Itoh, Kohei M.·2005·Physical Review A
DOI 10.1103/physreva.71.052320
Open this paper in CoChat — free accountOpen PDF

Abstract

We present a detailed analysis of the impact on quantum modular exponentiation of architectural features and possible concurrent gate execution. Various arithmetic algorithms are evaluated for execution time, potential concurrency, and space trade-offs. We find that to exponentiate an $n\text{\ensuremath{-}}\text{bit}$ number, for storage space $100n$ (20 times the minimum $5n$), we can execute modular exponentiation 200--700 times faster than optimized versions of the basic algorithms, depending on architecture, for $n=128$. Addition on a neighbor-only architecture is limited to $O(n)$ time, whereas non-neighbor architectures can reach $O(\mathrm{log}\phantom{\rule{0.2em}{0ex}}n)$, demonstrating that physical characteristics of a computing device have an important impact on both real-world running time and asymptotic behavior. Our results will help guide experimental implementations of quantum algorithms and devices.

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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1103/physreva.71.052320

Cites

8 of 8 references verified0 citation errors · 0 not checkable

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.

A few free checks a day · papers already verified open instantly · results are public

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 [83]

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

Flagged first, then by citations

Research works printed but not linked: 14

  1. [19]P. W. Shor, in Proc. 37th Symposium on Foundations of Computer Science (IEEE Computer Society Press, Los Alamitos, CA, 1996), pp. 56-65.
  2. [20]A. M. Steane and B. Ibinson, Fault-tolerant logical gate networks for CSS codes , http://arXiv.org/quant-ph/0311014 (2003).
  3. [22]A. V. Aho and K. M. Svore, Compiling quantum circuits using the palindrome transform , http://arXiv.org/quant-ph/0311008 (2003).
  4. [27]L. M. K. Vandersypen, Ph.D. thesis, Stanford University (2001).
  5. [28]A. Yao, in Proceedings of the 34th Annual Symposium on Foundations of Computer Science (Institute of Electrical and Electronic Engineers Computer Society Press, Los Alamitos, CA, 1993), pp. 352-361.
  6. [29]R. Van Meter, in Proc. Int. Symp. on Mesoscopic Superconductivity and Spintronics (MS+S2004) (2004).
  7. [30]M. D. Ercegovac and T. Lang, Digital Arithmetic (Morgan Kaufmann, San Francisco, CA, 2004).
  8. [31]S. A. Cuccaro, T. G. Draper, S. A. Kutin, and D. P. Moulton, A new quantum ripple-carry addition circuit , http://arXiv.org/quant-ph/0410184 (2004).
  9. [32]T. G. Draper, S. A. Kutin, E. M. Rains, and K. M. Svore, A logarithmic-depth quantum carry-lookahead adder , http://arXiv.org/quant-ph/0406142 (2004).
  10. [34]T. G. Draper, Addition on a quantum computer , http://arXiv.org/quant-ph/0008033 (2000), first draft dated Sept. 1998.
  11. [36]S. J. Devitt, A. G. Fowler, and L. C. Hollenberg, Simulations of Shor's algorithm with implications to scaling and quantum error correction , http://arXiv.org/quant-ph/0408081 (2004).
  12. [38]G. K. Brennen, C. M. Caves, P. S. Jessen, and I. H. Deutsch, Physical Review Letters 82 , 1060 (1999).
  13. [39]M. Oskin, F. T. Chong, I. L. Chuang, and J. Kubiatowicz, in Computer Architecture News, Proc. 30th Annual International Symposium on Computer Architecture (ACM, 2003).
  14. [41]Proc. ERATO Conference on Quantum Information Science (EQIS2003) (2003).

Cited by

Sorted by citations

Authors
Van Meter, R., & Itoh, K. M.
Affiliations
Keio University (JP)
ORCID
Itoh, Kohei M.
Venue
Physical Review A
Publisher
American Physical Society (APS)
Published
2005-05-17
Volume
71
Issue
5
ISSN
  • 0556-2791 (ISSN-L)
  • 1050-2947
  • 1094-1622
DOI
10.1103/physreva.71.052320
OpenAlex
W2017278808
Cited by
181
References
8
Citations by year
2026: 7 · 2025: 7 · 2024: 8 · 2023: 7 · 2022: 7 · 2021: 10 · 2020: 6 · 2019: 2 · 2018: 11 · 2017: 9 · 2016: 5 · 2015: 9 · 2014: 9 · 2013: 14 · 2012: 10
FWCI
12.34
Type
journal article
Language
en
Open access
Licence
link.aps.org/licenses/aps-default-license (vor)
Locations
  • Physical Review A (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
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 arithmetic, addition algorithm, arithmetic algorithms, quantum computing hardware, algorithm performance evaluation

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