REVIEW
Shared Lookups and Lazy Residues: Fewer Toffoli Gates for Factoring RSA-2048
Quantum Physics · Submitted 6 Nov 2026 · 15 references
Pith's verdict: A well-executed, technically sound paper that delivers genuine Toffoli reductions for RSA-2048 factoring circuits, with careful benchmarking and transparent limitations.
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
Shared lookups and lazy residues reduce Toffoli gates for RSA-2048 factoring by up to 46% at 1,806 logical qubits compared to the best prior circuit at the same qubit budget.
The reading
What carries the argument
Shared table lookups across k primes, which exploit the fact that each prime's loop-1 table is addressed by the same exponent window; checkpoints that preserve intermediate residues r_{j-1} instead of deleting them; and lazy residues that replace modular reductions in loop 3 with plain integer addition followed by a single modular reduction. Shared lookups reduce the per-window Toffoli cost by a factor of k, while checkpoints and lazy residues cut the cleanup cost by avoiding recomputation and by removing borrow measurements and deferred comparisons.
Extended reading notes
Core claim
The reference circuit for RSA-2048 factoring spends 55% of its Toffoli gates on per-prime discrete-log lookups (loop 1) and 30% on residue uncomputation (loop-3 cleanup). The paper discovers that these two cost centers can be reduced simultaneously: (1) because every prime uses the same exponent-window address, one lookup can return the entries for k primes at once at no additional Toffoli cost; (2) by retaining intermediate residues rather than deleting them, the recomputation in cleanup is avoided; (3) with those residues kept, the intermediate sums no longer need to be canonical residues, so all modular reductions in loop 3 can be replaced with plain integer additions and a single final reduction. The result is a circuit family that, for a given logical-qubit budget, achieves fewer Toffoli gates than the strongest comparable reference setting.
Load-bearing premise
The sampled-prime projection assumes that the per-prime Toffoli cost is affine in the number of complete groups, and the paper validates this to within 1% error on a 330-bit instance, but systematic errors at full RSA-2048 scale or for untested parameter combinations are not ruled out.
Editorial extensions
If this is right
- If these Toffoli reductions hold in practice, future quantum factoring resource estimates can be lowered without changing the underlying fault-tolerant architecture.
- The open benchmark provides a platform for others to verify and further optimize these circuits, closing several cost-accounting loopholes in the reference simulator.
- The techniques may be applicable to other quantum algorithms that use per-item lookups with shared addresses, such as certain verification routines or signal processing.
- The architecture-dependent runtime analysis shows that the best circuit varies with hardware: wide shared lookups help on the surface code but slow down space-efficient neutral-atom processors, guiding hardware-specific optimizations.
Reading between the lines
- The paper's focus on logical gate counts means that architectural optimizations that exploit parallelism or reduced measurement overhead may compound the savings, potentially bringing physical resource estimates lower than the paper's projections.
- The trimmed discrete-log register (L=29 instead of 32) is a direct consequence of bounding the sum of discrete logs; similar trimming may be possible in other windowed arithmetic routines where the accumulated sum has an upper bound.
- The paper does not explore varying the Ekerå–Håstad parameter s in combination with their circuits; a systematic search might yield further gate reductions at the cost of more exponent qubits.
Original abstract
Gidney's 2025 construction for factoring RSA-2048 with few logical qubits spends most of its Toffoli gates on discrete-log table lookups and residue uncomputation. We reduce both costs. Shared lookups return entries for several primes of a residue number system at once because they have the same address. Retained intermediate residues remove recomputation during cleanup and enable lazy arithmetic with a single final modular reduction. We prove output preservation and estimate resources with an open benchmark built on the reference simulator. Against the best reference setting within the same logical-qubit budget, using the published model for the reference and benchmark counts for our circuits, we obtain $15\%$ fewer Toffolis at $1{,}461$ qubits ($5.08 \times 10^{9}$ per factoring) and $46\%$ fewer at $1{,}806$ qubits ($2.55 \times 10^{9}$). A matched ablation finds $28.8\%$ fewer Toffolis from three-prime sharing at fixed window and checkpoint settings. Architecture-specific timing determines how much becomes a runtime saving.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
Gidney's 2025 construction for factoring RSA-2048 with few logical qubits spends most of its Toffoli gates on discrete-log table lookups and residue uncomputation. We reduce both costs. Shared lookups return entries for several primes of a residue number system at once because they have the same address. Retained intermediate residues remove recomputation during cleanup and enable lazy arithmetic with a single final modular reduction. We prove output preservation and estimate resources with an open benchmark built on the reference simulator. Against the best reference setting within the same logical-qubit budget, using the published model for the reference and benchmark counts for our circuits, we obtain $15\%$ fewer Toffolis at $1{,}461$ qubits ($5.08 \times 10^{9}$ per factoring) and $46\%$ fewer at $1{,}806$ qubits ($2.55 \times 10^{9}$). A matched ablation finds $28.8\%$ fewer Toffolis from three-prime sharing at fixed window and checkpoint settings. Architecture-specific timing determines how much becomes a runtime saving.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Gidney's 2025 construction for factoring RSA-2048 with few logical qubits spends most of its Toffoli gates on discrete-log table lookups and residue uncomputation. We reduce both costs. | contribution 0.51 | 0.48 | 0.50 | asserted 1.00 |
| s1 | Shared lookups return entries for several primes of a residue number system at once because they have the same address. | method 0.93 | 0.70 | 0.05 | asserted 1.00 |
| s2 | Retained intermediate residues remove recomputation during cleanup and enable lazy arithmetic with a single final modular reduction. | method 0.88 | 0.80 | 0.10 | asserted 1.00 |
| s3 | We prove output preservation and estimate resources with an open benchmark built on the reference simulator. | method 0.77 | 0.93 | 0.04 | asserted 0.99 |
| s4 | Against the best reference setting within the same logical-qubit budget, using the published model for the reference and benchmark counts for our circuits, we obtain $15\%$ fewer Toffolis at $1{,}461$ qubits ($5.08 \times 10^{9}$ per factoring) and $46\%$ fewer at $1{,}806$ qubits ($2.55 \times 10^{9}$). | result 1.00 | 0.94 | 0.64 | asserted 1.00 |
| s5 | A matched ablation finds $28.8\%$ fewer Toffolis from three-prime sharing at fixed window and checkpoint settings. | result 1.00 | 0.95 | 0.10 | asserted 1.00 |
| s6 | Architecture-specific timing determines how much becomes a runtime saving. | limitation 0.63 | 0.43 | 0.04 | asserted 0.98 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
Figures
Figures reproduced from arXiv:2611.08907 by the authors.
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.