Pith. sign in

REVIEW 3 major objections 4 minor 2 cited by

Ancilla-free Quantum Adder with Sublinear Depth

T0 review · 3 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read The paper proves that in-place addition of two n-bit numbers can be performed in $O(\log^2 n)$ depth using only Toffoli, CNOT, and X gates, with no ancilla qubits.

desk verdict If Lemma 4's dirty-ancilla allocation can be made rigorous, the no-ancilla O(log^2 n) adder is a real result; as written the proof has a load-bearing gap. read the letter →

arxiv 2501.16802 v2 pith:VQOKBMKX submitted 2025-01-28 quant-ph cs.DM

Maxime Remaud , Vivien Vandaele This is my paper · ORCID
classification quant-phcs.DM MSC 68Q1281P68 PACS 03.67.Lx
keywords quantumadderripple-carryadditionancilla-freereversiblelogicToffoligateCNOTladderconditionallycleanancillaelogarithmicdepth
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 aims to break the trade-off in quantum arithmetic between speed and workspace: the fastest classical-reversible adders were either linear-depth with no ancillas (ripple-carry) or logarithmic-depth with many ancillas (carry-lookahead). It proves a construction that achieves both goals at once—an in-place adder for two n-bit numbers using only Toffoli, CNOT, and X gates, with depth $O(\log^2 n)$, gate count $O(n \log n)$, and zero ancilla qubits. The route is to isolate the two ladders of gates inside the ripple-carry adder that force linear depth, and to replace each ladder with a shallower divide-and-conquer circuit. If the construction is right, it is the first exact ancilla-free adder with sublinear depth, and the same ladder techniques immediately improve controlled adders, incrementers, and constant adders.

What carries the argument

The load-bearing object is the ladder-synthesis recursion. Algorithm 1 halves a CNOT ladder by surrounding a recursive call on every other qubit with two depth-1 layers of parallel CNOT gates, giving exact depth $\lfloor \log n \rfloor + \lfloor \log(2n/3) \rfloor$. Algorithm 2 lifts the same pattern to an arbitrary ladder $L_\alpha$ of multi-controlled-X gates, producing $2\lfloor \log k \rfloor$ layers of parallel MCX gates, where $k$ is the number of MCX gates in the ladder. The second load-bearing piece is the MCX compilation theorem (Theorem 1, from [2]): an $\text{MCX}_m$ gate can be implemented over $\{\text{Toffoli}, X\}$ with depth $O(\log m)$, size $O(m)$, and two dirty ancilla qubits. Lemma 4 combines the two: because every layer of the decomposed Toffoli ladder leaves each parallel MCX gate separated from its neighbors by at least two idle qubits, each gate can borrow two disjoint dirty ancillas, giving each layer depth $O(\log n)$ and the whole ladder depth $O(\log^2 n)$.

What would settle it

Run the recursive synthesis for a Toffoli ladder on a concrete size, say 1024 qubits, and layer by layer check whether the parallel multi-controlled gates are separated by at least two idle qubits so that each can borrow two disjoint dirty ancillas. If any layer contains two gates whose control and target spans overlap so tightly that no pair of disjoint idle qubits can be assigned to both, then Lemma 4's separation claim is false for that size and the $O(\log^2 n)$ depth bound for the ladder—and hence for the adder—would not follow from the argument presented.

Watch

Extended reading notes

Core claim

The central claim, stated as Theorem 2, is that there exists a circuit over the gate set $\{\text{Toffoli}, \text{CNOT}, X\}$ implementing the in-place map $|a\rangle|b\rangle|z\rangle \mapsto |a\rangle|a+b \bmod 2^n\rangle|z \oplus (a+b)_n\rangle$ in depth $O(\log^2 n)$ and size $O(n \log n)$, using no ancilla qubits. The proof decomposes the standard ancilla-free ripple-carry adder into slices and shows that the only pieces with linear depth are the CNOT ladder $L_1$ and the Toffoli ladder $L_2$. Lemma 2 gives a divide-and-conquer replacement for any ladder of $n$ CNOT gates: it runs in depth $2\lfloor \log n \rfloor$ and uses $2n - O(\log n)$ gates (Algorithm 1). Lemma 4 gives a replacement for any ladder of $n$ Toffoli gates: first Algorithm 2 rewrites the ladder as $O(\log n)$ layers of parallel multi-controlled-X (MCX) gates, and then each MCX gate is implemented in $O(\log m)$ depth and $O(m)$ size using two dirty ancillas, via the conditionally clean ancillae result stated as Theorem 1 from [2]. The adder (Algorithm 3) is the ripple-carry circuit of [14] with those four ladders substituted by the new shallow circuits.

Load-bearing premise

The proof of the logarithmic-depth Toffoli ladder assumes, without giving a counting argument, that in every layer of the recursive circuit each parallel multi-controlled-X gate can be assigned two qubits that are idle in that layer and disjoint from the qubits assigned to every other gate in the same layer.

Editorial extensions

If this is right

  • The controlled version of the adder—the operator used in modular exponentiation for factoring algorithms—retains the same $O(\log^2 n)$ depth and $O(n \log n)$ gate count with zero ancillas (Theorem 3).
  • A quantum incrementer ($|v\rangle \mapsto |v+1 \bmod 2^n\rangle$) can be built in $O(\log^2 n)$ depth and $O(n \log n)$ gates using only one dirty ancilla qubit, whereas previous polylogarithmic incrementers needed a clean ancilla (Corollary 1).
  • Adding a classical constant to a quantum register requires $O(\log^3 n)$ depth and $O(n \log^2 n)$ gates with no ancilla, by recursive decomposition into smaller constant additions (Corollary 2).
  • Because the CNOT ladder appears in other arithmetic circuits—for example, binary field multiplication of certain polynomials—the logarithmic-depth CNOT-ladder construction yields logarithmic-depth multipliers for those cases, as noted in the paper's discussion.

Reading between the lines

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

  • The depth bound of Lemma 4 rests on a separation claim that is asserted rather than proved in detail: in every layer of the divide-and-conquer Toffoli-ladder circuit, each parallel MCX gate must be able to borrow two qubits that are idle in that layer, with disjoint sets of borrowers. A formal counting and assignment argument would close this gap; without it, the $O(\log^2 n)$ bound for the ladder
  • If the separation property holds asymptotically but fails at small recursion depths (where gates are dense), the practical depth for small n could exceed the asymptotic bound; a concrete ancilla-assignment algorithm would settle the constant and likely refine the depth estimate.
  • The gap between the CNOT ladder ($O(\log n)$) and the Toffoli ladder ($O(\log^2 n)$) comes entirely from the per-MCX compilation cost. If future work implements MCX gates with fewer dirty ancillas or at lower depth, the adder's depth would drop toward $O(\log n)$ while preserving the zero-ancilla property.
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

3 major / 4 minor

Summary. The paper proposes an ancilla-free reversible classical adder for two n-bit numbers with O(log^2 n) depth and O(n log n) gates, based on new low-depth implementations of CNOT and Toffoli ladders. Algorithm 1 gives a logarithmic-depth CNOT ladder, and Algorithm 2 gives a polylogarithmic-depth Toffoli ladder by decomposing the ladder into layers of parallel multi-controlled X (MCX) gates, each compiled using the dirty-ancilla technique of Khattar and Gidney. The authors apply these ladders to a modified Takahashi ripple-carry adder, and also give a controlled adder, a quantum incrementer, and a constant adder. The core correctness proofs for the ladder algebras are explicit, with recurrences for depth and gate counts, and the main adder theorem is intended to follow from these lemmas.

Significance. If valid, the main result would be the first exactly reversible (Toffoli/CNOT/X) adder with no ancillas and sublinear depth, an important step for fault-tolerant quantum arithmetic. The paper is well structured, provides pseudocode, and gives exact counts for the CNOT-ladder construction. Its reliance on the recently developed conditionally-clean-ancilla technique is timely. However, the central asymptotic claim rests on a lemma whose proof contains an unproven resource-allocation assertion; this must be fixed before the main theorem can be accepted. The constant-adder corollary also contains a recurrence whose solution is inconsistent with the stated depth.

major comments (3)
  1. [Section 4, proof of Lemma 4] The proof asserts that 'for all the other layers of the circuit, the parallel MCX gates are all separated by at least two qubits on which no gates are acting' and concludes that two dirty ancillas can be assigned to every gate in the layer. This is not established by any counting or matching argument. For the top-level CL layer of L2 (α=(2,4,...,2n)) the adjacent intervals are separated by a single qubit (e.g., qubit 5 between [2,4] and [6,8]), so the literal separation statement is false for that layer; the gates there are Toffolis and need no ancillas, but the proof does not say this. For the deeper recursive layers, no induction is given showing that every parallel-MCX layer has at least 2m idle qubits for its m gates. Without a rigorous allocation argument, Theorem 1 cannot be applied uniformly, and the O(log^2 n) depth bound for L2, and hence Theorem 2, does not follow.
  2. [Section 4, proof of Lemma 4] The proof also states that for each MCX layer, Σ_i m_i ≤ n, where m_i is the number of controls of the i-th MCX gate in that layer. This is needed for the O(n log n) gate count, but no justification is provided. It should be proven from the structure of Algorithm 2, or replaced by a correct bound on the total number of controls in each layer.
  3. [Section 7.2, Eq. (23)] The recurrence for the constant adder's depth is inconsistent with its stated solution. Taking D(n) = 2D(n/2) + Θ(log^2 n) for the first level and D(m) = D(m/2) + Θ(log^2 m) for m = n/2^j, j>1, yields D(n) = Θ(n) (or Θ(n log^2 n) with more careful bookkeeping), not Θ(log^3 n). The claimed O(log^3 n) depth for Corollary 2 is therefore not established; please correct the recurrence or the analysis.
minor comments (4)
  1. [Section 6, Lemma 5] The proof of Lemma 5 is only a sketch: the split of F(n)_2 into F(⌈n/2⌉)_2 and F(⌊n/2⌋)_2, the availability of the other half as dirty ancillas, and the depth and gate-count recurrences should be formalized, including a proof of the circuit equality (16) for general n.
  2. [Appendix A, proof of Lemma 3] The sentence 'This equation is equivalent to Equation 9, which was demonstrated in the proof of Theorem 2' should refer to the proof of Lemma 2, not Theorem 2.
  3. [Figure 3 caption] The caption says 'On the right, an equivalent logarithmic-depth CNOT circuit produced by Algorithm 2,' but the circuit consists of Toffoli/MCX gates; the caption should say 'MCX circuit' or 'Toffoli circuit'.
  4. [Section 6, Theorem 3 proof] The final sentence states the circuit can be implemented over the {Toffoli, CNOT, X} gate set, while the theorem statement and the algorithm use {Toffoli, CNOT}; this discrepancy should be resolved.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the sublinear-depth adder is obtained by composing externally sourced MCX and ripple-carry results, and the only self-citation is a non-load-bearing remark.

full rationale

The derivation chain is self-contained in the relevant sense: the two load-bearing imported results—Theorem 1 (MCX_n with two dirty ancillae, from Khattar and Gidney [2]) and the Takahashi et al. ripple-carry base [14]—come from outside the present paper and are not fitted to the adder's claimed complexity. Ladder1 and Ladderα are defined independently of the adder, and Lemmas 2 and 3 prove correctness by explicit unitary calculations; Lemma 4 then composes Theorem 1 layer by layer rather than assuming the conclusion. The only self-citation, reference [18] by one of the present authors, appears in the Discussion as a downstream-use example and does not support Theorem 2, Theorem 3, Corollary 1, or Corollary 2. The flagged caveat in the proof of Lemma 4 is a correctness gap, not circularity: the assertion that 'the parallel MCX gates are all separated by at least two qubits on which no gates are acting' is used to conclude that two disjoint dirty ancillas can be assigned per gate without a counting or matching proof. If that allocation fails, the O(log^2 n) depth bound would not follow, but the failure would be an unproven obligation, not a reduction of the theorem to its own input.

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

The construction is mathematical with no fitted constants. It imports two external results: the dirty-ancilla MCX implementation of Khattar and Gidney and the Takahashi ripple-carry adder. The central new content is the divide-and-conquer synthesis of the ladders.

assumptions (4)
  • domain assumption Theorem 1 of [2]: MCX_n can be implemented over {Toffoli, X} with O(log n) depth, O(n) size, using two dirty ancilla qubits.
    Used in Lemma 4 to convert the MCX circuit produced by Algorithm 2 into a Toffoli/X circuit. The result is cited, not proved in this paper.
  • domain assumption Algorithm 3, inherited from Takahashi et al. [14], implements in-place addition correctly.
    Theorem 2's correctness relies on the ripple-carry adder structure; the paper only cites [14] and applies a circuit equality, without giving a full independent correctness proof.
  • domain assumption Dirty ancilla qubits can be arbitrary, including entangled with control qubits, and the MCX implementation from [2] restores them.
    The L2 circuit uses data qubits as dirty ancilla; the argument relies on the standard dirty-ancilla technique.
  • standard math Standard GF(2) algebra and recurrence solving.
    Used in the proofs of Lemmas 2 and 3 to verify circuit actions and solve depth and count recurrences.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Ancilla-free Quantum Adder with Sublinear Depth." pith.science (2026). https://pith.science/paper/VQOKBMKX

@misc{pith2026250116802,
  author       = {Pith},
  title        = {Pith review of: Ancilla-free Quantum Adder with Sublinear Depth},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VQOKBMKX}},
  note         = {Machine review of arXiv:2501.16802}
}
abstract

We present the first exact quantum adder with sublinear depth and no ancilla qubits. Our construction is based on classical reversible logic only and employs low-depth implementations for the CNOT ladder operator and the Toffoli ladder operator, two key components to perform ripple-carry addition. Namely, we demonstrate that any ladder of $n$ CNOT gates can be replaced by a CNOT-circuit with $O(\log n)$ depth, while maintaining a linear number of gates. We then generalize this construction to Toffoli gates and demonstrate that any ladder of $n$ Toffoli gates can be substituted with a circuit with $O(\log^2 n)$ depth while utilizing a linearithmic number of gates. This builds on the recent works of Nie et al. and Khattar and Gidney on the technique of conditionally clean ancillae. By combining these two key elements, we present a novel approach to design quantum adders that can perform the addition of two $n$-bit numbers in depth $O(\log^2 n)$ without the use of any ancilla and using classical reversible logic only (Toffoli, CNOT and X gates). We also present new constructions for incrementing and adding a constant to a quantum register.

Figures

Figures reproduced from arXiv: 2501.16802 by the authors.

Figure 1
Figure 1. Ancilla-free adder represented as a circuit for [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. On the left, a linear-depth circuit implementing the [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. On the left, a linear-depth Toffoli circuit implementing the [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

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

  1. Logarithmic Depth Decomposition of Approximate Multi-Controlled Single-Qubit Gates Without Ancilla Qubits

    quant-ph 2025-07 conditional novelty 6.0 of 10

    The authors construct relative-phase n-qubit Toffoli gates without ancillas and O(log n)-depth multi-controlled SU(2)/U(2) decompositions, improving on earlier methods.

  2. On Exact Space-Depth Trade-Offs in Multi-Controlled Toffoli Decomposition

    quant-ph 2025-02 reject novelty 4.0 of 10

    The paper gives exact Toffoli-depth versus ancilla-count formulas for multi-controlled Toffoli decomposition and claims a ceil(log2 n) lower bound, but the main formula is inconsistent with its own example.

Reference graph

Works this paper leans on

20 extracted references · 14 canonical work pages · cited by 2 Pith papers

  1. [1]

    Quantum circuit for multi-qubit toffoli gate with optimal resource

    Junhong Nie, Wei Zi, and Xiaoming Sun. “Quantum circuit for multi-qubit toffoli gate with optimal resource” (2024). arXiv:2402.05053

    arXiv 2024

  2. [2]

    Rise of conditionally clean ancillae for optimizing quantum circuits

    Tanuj Khattar and Craig Gidney. “Rise of conditionally clean ancillae for optimizing quantum circuits” (2024). arXiv:2407.17966. 18

    arXiv 2024

  3. [3]

    Polynomial-time algorithms for prime factorization and discrete loga- rithms on a quantum computer

    Peter W. Shor. “Polynomial-time algorithms for prime factorization and discrete loga- rithms on a quantum computer”. SIAM Journal on Computing26, 1484–1509 (1997)

    work page 1997

  4. [4]

    Quantum networks for elementary arithmetic operations

    Vlatko Vedral, Adriano Barenco, and Artur Ekert. “Quantum networks for elementary arithmetic operations”. Phys. Rev. A54, 147–153 (1996)

    1996

  5. [5]

    A quantum circuit for Shor’s factoring algorithm using 2n+2 qubits

    Yasuhiro Takahashi and Noboru Kunihiro. “A quantum circuit for Shor’s factoring algorithm using 2n+2 qubits”. Quant. Inf. Comput.6, 184–192 (2006)

    work page 2006

  6. [6]

    Factoring with n+2 clean qubits and n-1 dirty qubits

    Craig Gidney. “Factoring with n+2 clean qubits and n-1 dirty qubits” (2018). arXiv:1706.07884

    arXiv 2018

  7. [7]

    A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space

    Oded Regev. “A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space” (2004). arXiv:quant-ph/0406151

    work page Pith review arXiv 2004

  8. [8]

    Faster quantum chemistry simulation on fault-tolerant quantum computers

    N Cody Jones, James D Whitfield, Peter L McMahon, Man-Hong Yung, Rod- ney Van Meter, Alán Aspuru-Guzik, and Yoshihisa Yamamoto. “Faster quantum chemistry simulation on fault-tolerant quantum computers”. New Journal of Physics 14, 115023 (2012)

    work page 2012

Show all 20 references
  1. [9]

    A quantum deep convolutionalneuralnetworkforimagerecognition

    YaoChong Li, Ri-Gui Zhou, RuQing Xu, Jia Luo, and WenWen Hu. “A quantum deep convolutionalneuralnetworkforimagerecognition”. QuantumScienceandTechnology 5, 044003 (2020)

    2020

  2. [10]

    Addition on a quantum computer

    Thomas G. Draper. “Addition on a quantum computer” (2000). arXiv:quant- ph/0008033

    2000

  3. [11]

    Factoring using 2n + 2 qubits with toffoli based modular multiplication

    Thomas Häner, Martin Roetteler, and Krysta M. Svore. “Factoring using 2n + 2 qubits with toffoli based modular multiplication”. Quantum Info. Comput. 17, 673–684 (2017)

    2017

  4. [12]

    A logarithmic-depth quantum carry-lookahead adder

    Thomas G. Draper, Samuel A. Kutin, Eric M. Rains, and Krysta M. Svore. “A logarithmic-depth quantum carry-lookahead adder”. Quantum Info. Comput. 6, 351–369 (2006)

    2006

  5. [13]

    A fast quantum circuit for addition with few qubits

    Yasuhiro Takahashi and Noboru Kunihiro. “A fast quantum circuit for addition with few qubits”. Quantum Info. Comput.8, 636–649 (2008)

    2008

  6. [14]

    Quantum addition circuits and unbounded fan-out

    Yasuhiro Takahashi, Seiichiro Tani, and Noboru Kunihiro. “Quantum addition circuits and unbounded fan-out”. Quantum Info. Comput.10, 872–890 (2010)

    2010

  7. [15]

    A new quantum ripple-carry addition circuit

    Steven A. Cuccaro, Thomas G. Draper, Samuel A. Kutin, and David Petrie Moulton. “A new quantum ripple-carry addition circuit” (2004). arXiv:quant-ph/0410184

    2004 arXiv

  8. [16]

    Quantum lower bounds for fanout

    M. Fang, S. Fenner, F. Green, S. Homer, and Y. Zhang. “Quantum lower bounds for fanout”. Quantum Info. Comput.6, 46–57 (2006)

    2006

  9. [17]

    Parallelizing quantum circuits

    Anne Broadbent and Elham Kashefi. “Parallelizing quantum circuits”. Theoretical Computer Science410, 2489–2510 (2009)

    2009

  10. [18]

    Quantum binary field multiplication with subquadratic Toffoli gate count and low space-time cost

    Vivien Vandaele. “Quantum binary field multiplication with subquadratic Toffoli gate count and low space-time cost” (2025). arXiv:quant-ph/2501.16136

    2025 arXiv

  11. [19]

    Constructing large controlled nots

    Craig Gidney. “Constructing large controlled nots” (2015)

    2015

  12. [20]

    Constructing large increment gates

    Craig Gidney. “Constructing large increment gates” (2015). A Proof of Lemma 3 Let us recall Lemma 3: Lemma 3. Let α be a vector ofk− 1 integers, where k ≥ 2, associated with the Lα operator. The circuit produced by Algorithm 2 implementsLα with a MCX-depth of ⌊log (k)⌋ + ⌊ log...

    2015

Pith tools

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