The DOI matches its DataCite record; 1 of the 1 references it cites were found in a registry or an index.
Factoring with n+2 clean qubits and n-1 dirty qubits
Open accessAbstract
We present reversible classical circuits for performing various arithmetic operations aided by dirty ancillae (i.e. extra qubits in an unknown state that must be restored before the circuit ends). We improve the number of clean qubits needed to factor an n-bit number with Shor's algorithm from 1.5n+O(1) to n+2, assisted by n-1 dirty qubits, without increasing the asymptotic size or depth of the circuit.
Overview
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
Verification
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?
The construction improves on estimates by Jones et al., Fowler et al., and Gheorghiu et al. by over 100x when accounting for slight remaining differences in the cost model.
“We improve on their estimates by over 100x (see Table 2) when accounting for slight remaining differences in the cost model.”
From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [30]
The Overview and Improvements section (p. 12) discusses Gidney’s own gate costs and says their constant factors are worse than previous work. It does not assess the citing authors’ construction against estimates by Jones, Fowler, or Gheorghiu, or report an improvement of over 100x after cost-model adjustments. Searches for those names, the 100x figure, and cost-model differences found no supporting passage. (LLM, conf=0.76)
Experimental — accuracy not yet measuredThe reaction time for Gheorghiu et al. (2019) [30] is 0.1 microseconds.
“So a 0.2 microsecond reaction time would not be sufficient, but a 0.1 microsecond reaction time would be, and so we state the reaction time as 0.1 microseconds.”
From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [30]
The Introduction (p. 1) says the paper ignores machine architecture, while §2.1 (p. 3) discusses measurement and classically controlled operations without specifying reaction times. Searches for “0.1 microseconds,” “Gheorghiu et al. 2019,” and measurement-feedback time found no passage supporting the claimed value or the 0.2-microsecond comparison. (LLM, conf=0.77)
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.
Citations
Cites
Efficient Factorization with a Single Pure Qubit andlogNMixed Qubits
Parker, S., & Plenio, M. B. (2000) · Physical Review Letters · doi:10.1103/physrevlett.85.3049 · Cited by 130
Flagged first, then by citations
Research works printed but not linked: 8
- [1][1] Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter. Elementary gates for quantum computation. Physical Review A , 52(5):3457-3467, nov 1995. -
- [3][3] David Beckman, Amalavoyal N. Chari, Srikrishna Devabhaktuni, and John Preskill. Efficient networks for quantum factoring. Physical Review A , 54(2):1034-1063, aug 1996. -
- [6][6] Martin F¨ urer. Faster integer multiplication. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing - STOC '07 . ACM Press, 2007. -
- [9][9] Michele Mosca and Artur Ekert. The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer. In Quantum Computing and Quantum Communications , pages 174-188. Springer Berlin Heidelberg, 1999. -
- [10][10] S. Parker and M. B. Plenio. Efficient Factorization with a Single Pure Qubit and log N Mixed Qubits. Physical Review Letters , 85(14):3049-3052, oct 2000. -
- [12][12] Peter W. Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Review , 41(2):303332, jan 1999. -
- [15][15] Yasuhiro Takahashi and Noboru Kunihiro. A quantum circuit for Shor's factoring algorithm using 2n+2 qubits. Quantum Information & Computation , 6(2):184-192, 2006. -
- [16][16] Vlatko Vedral, Adriano Barenco, and Artur Ekert. Quantum Networks for Elementary Arithmetic Operations. Physical Review A , 54(1):147-153, jul 1996. -
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
Self-citationAsymptotic improvements to quantum circuits via qutrits
Gokhale, P., Baker, J. M., Duckering, C., Brown, N. C., Brown, K. R., & Chong, F. T. (2019) · Proceedings of the 46th International Symposium on Computer Architecture · doi:10.1145/3307650.3322253 · Cited by 120
Anschuetz, E., Olson, J., Aspuru-Guzik, A., & Cao, Y. (2019) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-14082-3_7 · Cited by 104
Magic state cultivation: growing T states as cheap as CNOT gates
Gidney, C., Shutty, N., & Jones, C. (2024) · arXiv · doi:10.48550/arxiv.2409.17595 · Cited by 9
Self-citationHow to factor 2048 bit RSA integers with less than a million noisy qubits
Gidney, C. (2025) · arXiv · Cited by 7
Self-citation
Metadata
- Authors
- Gidney, C.
- Affiliations
- Google (United States) (US)
- Corresponding author
- Gidney, Craig
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2017
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1706.07884
- OpenAlex
- W2720385174
- Cited by
- 28
- References
- 1
- Citations by year
- 2026: 1 · 2025: 2 · 2024: 1 · 2023: 6 · 2022: 4 · 2021: 3 · 2020: 4 · 2019: 6 · 2018: 1
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Physical Sciences › Computer Science › Information Systems › Cryptography and Residue Arithmetic
- Keywords
- Shor's algorithm, integer factorization, quantum arithmetic, circuit depth
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
