Shor's algorithm with fewer (pure) qubits
Open accessAbstract
In this note we consider optimised circuits for implementing Shor's quantum factoring algorithm. First I give a circuit for which none of the about 2n qubits need to be initialised (though we still have to make the usual 2n measurements later on). Then I show how the modular additions in the algorithm can be carried out with a superposition of an arithmetic sequence. This makes parallelisation of Shor's algorithm easier. Finally I show how one can factor with only about 1.5n qubits, and maybe even fewer.
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?
Zalka's coset representation allows cheaper non-modular arithmetic circuits to perform modular additions.
“We use Zalka's coset representation of modular integers [91], which allows the use of cheaper non-modular arithmetic circuits to perform modular additions.”
From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [91]
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
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
Parker, S., & Plenio, M. B. (2000) · Physical Review Letters · doi:10.1103/physrevlett.85.3049 · Cited by 130 · see citing works
Flagged first, then by citations
Research works printed but not linked: 3
- [1][1] C. Miquel, J.P. Paz and R. Perazzo, Factoring in a Dissipative Quantum Computer , Phys. Rev. A 54 , 2605 (1996), also quant-ph/9601021 - · arXiv
- [3][3] T.Draper, Addition on a quantum computer , quant-ph/0008033 - · arXiv
- [6][6] John Watrous, Quantum algorithms for solvable groups , Proceedings of the 33rd ACM Symposium on Theory of Computing, pages 60-67, 2001, also quant-ph/0011023 · 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
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 · 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
“5 n logical qubits [Zal06; Bea03; HRS16; Gid17].”
- Authors
- Zalka, C.
- Corresponding author
- Zalka, Christof
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2006
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- quant-ph/0601097
- OpenAlex
- W1545991018
- Cited by
- 20
- References
- 2
- Citations by year
- 2026: 1 · 2023: 1 · 2022: 3 · 2021: 1 · 2019: 4 · 2017: 2 · 2015: 1 · 2014: 1 · 2013: 2
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- CERN Document Server (European Organization for Nuclear Research) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Physical Sciences › Computer Science › Information Systems › Cryptography and Residue Arithmetic
- Keywords
- Shor's algorithm, quantum circuit optimization, modular addition, parallelization, 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
