Pith. sign in

REVIEW 2 major objections 3 minor 3 cited by

A Classical-Quantum Adder with Constant Workspace and Linear Gates

T0 review · 2 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A family of circuits now adds a classical integer into a quantum register with linear Toffoli gate count and only three clean ancilla qubits, matching the older quantum-quantum result and closing an open problem from 2004.

desk verdict Gidney actually closes the 20-year gap for classical-quantum addition, and the venting-based construction is sound enough to referee. read the letter →

arxiv 2507.23079 v1 pith:NZ442GEE submitted 2025-07-30 quant-ph

Craig Gidney This is my paper · ORCID
classification quant-ph MSC 68Q1281P68
keywords classical-quantumadderconstantworkspacelinearToffolicountventingcarriescarry-xordirtyancillaequantumarithmeticripple-carryaddition
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper closes a twenty-year gap in quantum arithmetic: it constructs the first classical-quantum adder that uses O(n) gates while keeping the workspace to a constant number of qubits. The offset is a classical integer, the target is a quantum register, and the circuit realizes the map target → (target + d) mod 2^n. Two versions are given, trading clean ancillae for dirty ancillae and Toffoli count. A reader should care because modular arithmetic on quantum registers, a common step in Shor's algorithm and related tasks, is typically dominated by exactly this kind of addition, and the usual workarounds either cost quadratic time or a large amount of extra storage.

What carries the argument

Three mechanisms carry the argument. (1) 'Venting': after a carry qubit is no longer needed, measuring it in the X basis converts the garbage qubit into a conditional phase flip on the remaining state; because carries are Z-redundant (a carry value is recoverable from the final sum), this measurement is reversible in the sense that the phase flip can be accounted for later. (2) The 'carry-xor' construction borrowed from Häner et al., which xors the carries of a planned addition into a secondary register; interleaving Z gates with carry-xors has the effect of applying Z to each carry. (3) 'Borrowing back and forth': splitting the n-bit addition into two halves and using each half as the dirty workspace needed by the other, which eliminates the need for a large clean register.

What would settle it

Simulate the paper's n=6, d=43 example circuit on all $2^{6}$ classical input states, apply the described phase-correction steps, and check that every output equals (x+d) mod 64 with relative phase +1 and that all ancillae return to their initial states; any input whose amplitude or phase differs from the ideal addition would falsify the central claim.

Watch

Extended reading notes

Core claim

The central claim is that the asymptotic barrier thought to separate quantum-quantum adders from classical-quantum adders does not exist. The paper gives an explicit family of circuits using 3 clean ancillae and 4n ± O(1) Toffoli gates, and another using 2 clean plus n−2 dirty ancillae and 3n ± O(1) Toffolis. Both perform the intended addition exactly, with no residual garbage left in the workspace after a complete phase-correction step. The known quantum-quantum adder of Cuccaro et al. already achieves O(n) gates and O(1) ancillae, and the paper shows the classical-offset case can be brought to the same asymptotic resource counts.

Load-bearing premise

The construction rests on the assumption that measuring a Z-redundant carry qubit in the X basis leaves behind only a single, later-correctable phase flip and no other error, a behavior attributed to the referenced work on irreversible uncomputation.

Editorial extensions

If this is right

  • The open problem from Cuccaro et al. (2004) is resolved: classical-quantum addition is no longer asymptotically harder than quantum-quantum addition.
  • Modular addition circuits that offset by a classically known modulus can be built with linear Toffoli count and constant extra qubits, potentially reducing the resource estimates for Shor's algorithm and other quantum arithmetic pipelines.
  • Because the adders can be controlled at no extra Toffoli cost, they can serve as directly controlled additions (for example in modular exponentiation) without an added constant-factor overhead.
  • The version using 2 clean and n−2 dirty ancillae at 3n ± O(1) Toffolis gives a concrete trade-off: more dirty workspace buys fewer Toffoli gates, which is useful when dirty ancillae are freely available inside a larger computation.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The venting mechanism may generalize to other reversible computations where intermediate garbage values are functions of the output: any Z-redundant temporary qubit could in principle be measured out and corrected later, suggesting a broader 'garbage-phasing' design pattern for constant-space circuits.
  • A true quantum carry-save adder with O(1) marginal depth, which the paper leaves explicitly open, is a natural next target; venting could plausibly be an ingredient for accumulating offsets at constant depth if an analogous streaming phase correction can be devised.
  • The paper's linear-depth circuits imply a depth-workspace trade-off when parallelizing arithmetic under constant workspace, a constraint that itself limits routing and magic-state production; finding low-depth variants would be a direct, nontrivial extension.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

Summary. The paper constructs a classical-quantum adder that adds a constant d to an n-qubit register using O(n) Toffoli gates and O(1) clean ancillae, closing a gap left open since Cuccaro et al. (2004). The circuit is based on three ideas: (i) 'venting' carry qubits by measuring them in the X basis, converting them from Z-basis garbage into correctable phase-flip tasks; (ii) cancelling those phase-flip tasks by interleaving classically controlled Z gates with Häner et al.'s carry-xor circuit; and (iii) splitting the addition into two halves so that each half can borrow the other as dirty workspace. Two variants are given: one using 2 clean ancillae plus n-2 dirty ancillae with 3n ± O(1) Toffolis, and one using 3 clean ancillae with 4n ± O(1) Toffolis. The paper also claims that a controlled version of the adder can be made with no extra workspace or Toffoli gates. The manuscript is short (8 pages) and relies heavily on circuit figures, Quirk links, and a Zenodo code repository for verification.

Significance. If correct, this is a significant result: it resolves a 20-year open problem on the asymptotic resource cost of classical-quantum addition, a central primitive in modular arithmetic and other quantum algorithms. The construction is parameter-free: there is no fitting, hidden post-selection, or adjustable constants in the gate counts, and the correctness of the key identities (Equation 8 and the interleaving phase-flip relation) is shown analytically. The paper also provides reproducible assets (Python code and interactive Quirk circuits), which strengthens its credibility. The main result appears mathematically sound, though the absence of a full formal proof of the circuit identities and the unusual citation of a blog post for the venting lemma lower my confidence slightly.

major comments (2)
  1. [Section 2.4 and Abstract] The claim that applying the presented adders conditioned on a control qubit requires no additional Toffoli gates is not adequately justified. The sentence 'Because d_k is only ever used to invert controls and to control bit flips, this replacement introduces no new Toffoli gates' is insufficient: in a constant-specialized circuit, a control set to 1 often turns a Toffoli into a CNOT, and replacing that constant control with a qubit would reintroduce a Toffoli, increasing the count. Please provide a rigorous proof of the gate-count invariance, or clearly state the precise comparison being made (e.g., to a generic unspecialized circuit). If the claim is meant only asymptotically, that should be stated explicitly.
  2. [Section 2.4, steps 1-5] The two-half borrowing procedure is described at a high level, and the phase-correction steps (steps 3 and 5) are stated without a detailed circuit-level proof. Because the correctness of the whole construction depends on these phase relations holding for arbitrary dirty-register states, including states correlated with the target register, I would like to see either a formal correctness argument (e.g., a unitary decomposition of the overall circuit) or an explicit machine-checkable verification of the generated circuits (e.g., a script that tests the unitary for random inputs). The Zenodo code is a start, but the paper should guide the reader toward such a verification.
minor comments (3)
  1. [Section 2.2] The venting property is cited to a non-peer-reviewed blog post [Gid19b]. Since this property is load-bearing, the paper should provide a full proof in the text (the sketch in Section 2.2 is close) or cite a peer-reviewed source.
  2. [Section 2.3] The sentence 'The first carry-xor can be achieved cheaply by using the carry qubits that were already being computed during the addition' is a bit vague; a pointer to the specific gates in Figure 4 would improve clarity.
  3. [General] A summary table of the resource counts (clean ancillae, dirty ancillae, Toffolis, and whether the carry input can be a bit) for the two variants and their controlled versions would help readers quickly compare the constructions.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the adder construction stands on an explicit algebraic identity and an independent carry-xor subroutine, with no fitted parameter or self-referential definition.

full rationale

The paper's central claims are circuit constructions with explicit Toffoli counts, not empirical predictions. The load-bearing mathematical step is Equation 8, which proves by direct algebra that the carries of x+d+c0 recur as the carries of ~(x+d+c0)+d+c0; this makes carry qubits Z-redundant after the addition. The 'venting' lemma (measuring a Z-redundant qubit in the X basis converts deletion into a correctable phase flip) is cited to [Gid19b], a prior work by the same author, but it is a parameter-free identity of X-basis measurement and does not assume or fit the paper's adder; it is stated explicitly in Section 2.2 and is independently checkable. The carry-xor subroutine is imported from [HRS17], an independent reference, and the paper only interleaves phase flips with it using the standard Z-CNOT-Z-CNOT identity. The 'borrowing back and forth' step is an accounting argument over two halves; each half borrows the other as dirty workspace and the phase corrections are implemented by cancelling pairs of carry-xors. No fitted parameter is renamed as a prediction, no asymptotics are imported from the author's own prior work, and the controlled variant is obtained by substituting control qubits for classical bits, which introduces no new Toffoli cost by construction. The only caveats are that the venting lemma is sourced to a non-peer-reviewed blog post and the generated circuits are not independently machine-checked here, but these are confidence issues, not circularity.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central claim rests on the venting measurement property (from a non-peer-reviewed blog post) and on the carry-xor construction from prior work. No free parameters or invented physical entities are introduced.

assumptions (3)
  • domain assumption The venting property: measuring a Z-redundant qubit in the X basis produces a classical random bit and, on the |-> outcome, an equivalent phase flip Z_q that can be corrected later.
    Invoked in Section 2.2 'Streaming Addition by Venting Carries' to justify deleting carry qubits via measurement; cited from [Gid19b].
  • domain assumption The carry-xor construction from [HRS17] correctly computes g -> g XOR carry(x, d, c0) using O(n) gates and no clean ancillas.
    Used in Section 2.3 and 2.4; taken as a building block from prior work.
  • standard math Standard quantum circuit model with Toffoli gates and unitary operations.
    Background for all circuit constructions.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Classical-Quantum Adder with Constant Workspace and Linear Gates." pith.science (2026). https://pith.science/paper/NZ442GEE

@misc{pith2026250723079,
  author       = {Pith},
  title        = {Pith review of: A Classical-Quantum Adder with Constant Workspace and Linear Gates},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NZ442GEE}},
  note         = {Machine review of arXiv:2507.23079}
}
abstract

In 2004, Cuccaro et al found a quantum-quantum adder with $O(n)$ gate cost and $O(1)$ ancilla qubits. Since then, it's been an open question whether classical-quantum adders can achieve the same asymptotic complexity. These costs are particularly relevant to modular arithmetic circuits, which often offset by the classically known modulus. In this paper, I construct an adder that uses 3 clean ancillae and $4n \pm O(1)$ Toffoli gates to add a classical offset into a quantum register. I also present an adder with a Toffoli cost of $3n \pm O(1)$ that uses 2 clean ancillae and $n-2$ dirty ancillae. I further show that applying the presented adders conditioned on a control qubit requires no additional workspace or Toffolis.

Figures

Figures reproduced from arXiv: 2507.23079 by the authors.

Figure 1
Figure 1. Non-standard circuit notation in this paper. Left: Bit-inverted controls. A black box containing the [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. An n = 6 example of an adder that vents carries in order to only use 2 clean ancilla and n ± O(1) Toffolis. Performs target → (target + d + carryin) mod 2n , except that completing the addition requires performing phase flips based on the vented values m0, . . . , mn−3. If mk is true, then a phase flip by carry(∼ target′ , d, carryin)k+1 is needed, where target′ is the value of the target register after the addition… view at source ↗
Figure 3
Figure 3. An n = 6 variant of the carry-xor construction from [HRS17]. Performs _dirty → _dirty ⊕ ⌊carry(target, d, carryin)/2⌋. Skips over the least significant carry because that’s equal to the carry input and so is trivial to access. Click here to open this circuit, specialized to d = 43, in Quirk. 4 [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: An n = 6 example of an adder that uses 2 clean ancillae, n − 2 dirty ancillae, and 3n ± O(1) Toffolis. Top: decomposed into other subroutines defined by the paper. Bottom: further decomposed into constant sized gates. Performs target → (target + d + carryin) mod 2n . T…
Figure 5
Figure 5. Figure 5: An n = 9 example of an adder circuit that uses 3 clean ancillae and 4n ± O(1) Toffolis. Top: decomposed into other subroutines defined by the paper. Bottom: further decomposed into constant sized gates. Performs target → (target + d + carryin) mod 2n [PITH_FULL_IMAGE…
Figure 6
Figure 6. Figure 6: A controlled variant of [PITH_FULL_IMAGE:figures/full_fig_p006_6.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Parallel Spooky Pebbling Makes Regev Factoring More Practical

    quant-ph 2025-10 conditional novelty 8.0 of 10

    Parallel spooky pebbling reduces Regev factoring multiplication depth to 193 for 4096-bit N, beating prior Regev variants while remaining space-heavier than Shor.

  2. Quantum Algorithm for Elliptic Curve Discrete Logarithms with Space-Efficient Point Addition

    quant-ph 2026-07 conditional novelty 7.0 of 10

    A space-efficient reversible modular-inversion circuit lowers Shor's ECDLP resource estimate for secp256k1 to 835 logical qubits and about 2^30.63 Toffoli gates.

  3. Quantum Arithmetic Circuits in Public-Key Cryptography

    quant-ph 2026-07 accept novelty 2.5 of 10

    A structured survey of optimized quantum adders, multipliers, modular exponentiation and point-addition circuits for public-key cryptanalysis, plus fault-tolerant resource estimation techniques.

Reference graph

Works this paper leans on

2 extracted references · 1 linked inside Pith · cited by 3 Pith papers

  1. [7]

    Data for

    2015 (Cited on pages 1, 7). [Gid19a] Craig Gidney. Approximate encoded permutations and piecewise quantum adders. 2019. doi: 10.48550/ARXIV.1905.08488.url: https://arxiv.org/abs/1905.08488 (Cited on page 7). [Gid19b] Craig Gidney. Spooky Pebble Games and Irreversible Uncomputation . https://algas sert.com/post/1905. Accessed: 2025-07-07. 2019 (Cited on pa...

    arXiv doi:10.48550/arxiv.1905.08488 2015

  2. [1622]

    url: http://dx.doi.org/10.1103/PhysRevA

    doi: 10.1103/physreva.54.147. url: http://dx.doi.org/10.1103/PhysRevA. 54.147 (Cited on page 1). 8

    doi:10.1103/physreva.54.147

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.