An approximate Fourier transform useful in quantum factoring
Open accessAbstract
We define an approximate version of the Fourier transform on $2^L$ elements, which is computationally attractive in a certain setting, and which may find application to the problem of factoring integers with a quantum computer as is currently under investigation by Peter Shor. (1994 IBM Internal Report)
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?
QFT is a basic component of many well-known quantum algorithms, including Shor's algorithm, quantum phase estimation, hidden subgroup problem, etc.
“QFT is a basic component of many well-known quantum algorithms, including Shor’s algorithm, quantum phase estimation, hidden subgroup problem, etc.”
From QASMBench: A Low-Level Quantum Benchmark Suite for NISQ Evaluation and Simulation (2023) · cites this paper as [26]
The Quantum computation section (p. 5) describes Shor’s algorithm performing a Fourier transform, supporting that example. The paper does not address quantum phase estimation or the hidden subgroup problem, so it does not support the full list of examples. (LLM, conf=0.88)
Experimental — accuracy not yet measured
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
No references could be resolved yet.
Research works printed but not linked: 2
- [KNU] Donald E. Knuth, volume 2. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. (Addison-Wesley, Reading, MA, 2nd ed., 1981)
- [SHO] Peter W. Shor, 'Algorithms for Quantum Computation: Discrete Log and Factoring,' manuscript, 1994. Proceedings of FOCS 1994.
Cited by
Sorted by citations
Algorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713 · see citing works
Elementary gates for quantum computation
Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D. P., Margolus, N., Shor, P., Sleator, T., Smolin, J. A., & Weinfurter, H. (1995) · Physical Review A · doi:10.1103/physreva.52.3457 · Cited by 4,311 · see citing works
Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
Vandersypen, L. M. K., Steffen, M., Breyta, G., Yannoni, C. S., Sherwood, M. H., & Chuang, I. L. (2001) · Nature · doi:10.1038/414883a · Cited by 1,738 · see citing works
Quantum computing with trapped ions
HAFFNER, H., ROOS, C., & BLATT, R. (2008) · Physics Reports · doi:10.1016/j.physrep.2008.09.003 · Cited by 1,154 · see citing works
Dynamics of Loschmidt echoes and fidelity decay
Gorin, T., Prosen, T., Seligman, T. H., & Žnidarič, M. (2006) · Physics Reports · doi:10.1016/j.physrep.2006.09.003 · Cited by 623 · see citing works
Polynomial-time quantum algorithm for the simulation of chemical dynamics
Kassal, I., Jordan, S. P., Love, P. J., Mohseni, M., & Aspuru-Guzik, A. (2008) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0808245105 · Cited by 385 · see citing works
Quantum algorithms for algebraic problems
Childs, A. M., & van Dam, W. (2010) · Reviews of Modern Physics · doi:10.1103/revmodphys.82.1 · Cited by 344 · see citing works
Circuit for Shor's algorithm using 2n+3 qubits
Beauregard, S. (2003) · Quantum Information and Computation · doi:10.26421/qic3.2-8 · Cited by 206 · see citing works
QASMBench: A Low-Level Quantum Benchmark Suite for NISQ Evaluation and Simulation
Li, A., Stein, S., Krishnamoorthy, S., & Ang, J. (2023) · ACM Transactions on Quantum Computing · doi:10.1145/3550488 · Cited by 183 · see citing works
Classification with Quantum Machine Learning: A Survey
Abohashima, Z., Elhosen, M., Houssein, E. H., & Mohamed, W. M. (2020) · arXiv · doi:10.48550/arxiv.2006.12270 · Cited by 68 · see citing works
Baldwin, C. H., Mayer, K., Brown, N. C., Ryan-Anderson, C., & Hayes, D. (2022) · Quantum · doi:10.22331/q-2022-05-09-707 · Cited by 54 · see citing works
Fast quantum modular exponentiation architecture for Shor's factoring alogrithm
Pavlidis, A., & Gizopoulos, D. (2014) · Quantum Information and Computation · doi:10.26421/qic14.7-8-8 · Cited by 38 · see citing works
How to factor 2048 bit RSA integers with less than a million noisy qubits
Gidney, C. (2025) · arXiv · Cited by 7 · see citing works
“In reality we must operate modulo 2 m , since we don’t know P , but it’s well known that the modulo-2 m behavior approximates the modulo-MP behavior [Cop02].”
- Authors
- Coppersmith, D.
- Affiliations
- Universidad de Málaga (ES)
- Corresponding author
- Coppersmith, D.
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2002
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- quant-ph/0201067
- OpenAlex
- W1608473410
- Cited by
- 343
- References
- 0
- Citations by year
- 2026: 4 · 2025: 27 · 2024: 30 · 2023: 47 · 2022: 23 · 2021: 24 · 2020: 20 · 2019: 4 · 2018: 4 · 2017: 7 · 2016: 2 · 2015: 9 · 2014: 7 · 2013: 6 · 2012: 3
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- U.S. Department of Energy (DESC0019040)
- Office of Science (DESC0019040)
- Advanced Scientific Computing Research (DE- sc0019040)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Logic, programming, and type systems
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Keywords
- quantum factoring, quantum programming, quantum program verification, hardware verification, quantum computing hardware
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
