{"id":"64767a77-76dd-4624-b8fb-fe44535e6bf4","arxiv_id":"2501.16802","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new construction shows exact in-place addition of two n-bit quantum registers can be done in O(log^2 n) depth with O(n log n) classical reversible gates and zero ancilla qubits.","lead":"Researchers built a quantum circuit that adds two n-bit numbers in polylogarithmic depth without using any extra 'scratch' qubits. If correct, it gives a depth-efficient, ancilla-free alternative to QFT-based adders that avoids expensive rotation gates.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4's dirty-ancilla allocation is the load-bearing gap: without a proof that every parallel-MCX layer has two idle qubits per gate, Theorem 2's depth bound does not follow.","rationale":"The reader's conditional verdict is well-founded: the algebra in Lemmas 2 and 3 checks out, but Lemma 4 is the bottleneck. The dirty-ancilla requirement is not a minor technicality; it is exactly what converts the O(log n)-depth MCX circuit into an ancilla-free {Toffoli, X} circuit. The paper's own proof of Lemma 4 is a one-paragraph assertion without a matching argument. Independent verification of small instances by the reader does not settle the asymptotic allocation. Corollary 2's ancilla-count inconsistency is real but does not affect Theorem 2. Novelty and prior work are secondary; the main claim stands or falls on Lemma 4. Hence no change to the reader's conditional verdict is needed, though the requested check should be performed before acceptance.","tokens_in":18678,"tokens_out":9678,"duration_ms":81692,"concrete_test":"Write a script that instantiates Algorithm 2 for L(n)_2 for n=8,16,32,64, enumerates every layer of MCX gates, and for each layer computes the set of qubits touched by no gate in that layer. Check whether one can assign to each MCX gate two distinct untouched qubits, disjoint across gates, e.g., via bipartite matching. If any layer fails for n<=64, Lemma 4 is false and the adder's depth bound falls. If all pass, report the matching and confirm the allocation is constructive, thereby upgrading the proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central result (Theorem 2) inherits its O(log^2 n) depth from Lemma 4, which claims an ancilla-free {Toffoli, X} implementation of L(n)_2. The proof asserts that in every layer of the Algorithm 2 circuit, parallel MCX gates are 'separated by at least two qubits on which no gates are acting,' so two dirty ancillae can be assigned per gate via Theorem 1. But separation of intervals by idle qubits does not by itself guarantee a disjoint assignment of two idle qubits per gate: a gate at the boundary of a layer might have only one adjacent idle qubit, or the two idle qubits on either side might be claimed by neighboring gates. For the top-level CL layer of Ladder2 with alpha=(2,4,...,2n), intervals [2,4], [6,8], ... are separated by single qubits 5,9,..., so each interior gate has exactly one idle qubit on each side; with care this may suffice, but Lemma 4 gives no counting or matching argument, and for deeper recursion levels the qubit subsets X' become irregular. If any layer has fewer than two idle qubits per MCX gate, Theorem 1 cannot be applied in parallel and that layer's depth becomes O(n) rather than O(log n), destroying the O(log^2 n) claim for L2 and hence for the adder. This is a genuine gap, not a style issue: the asymptotic claim rests entirely on this allocation.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":18960,"tokens_out":27888,"duration_ms":206896,"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":[{"comment":"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.","section":"Section 4, proof of Lemma 4"},{"comment":"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.","section":"Section 4, proof of Lemma 4"},{"comment":"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.","section":"Section 7.2, Eq. (23)"}],"minor_comments":[{"comment":"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.","section":"Section 6, Lemma 5"},{"comment":"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.","section":"Appendix A, proof of Lemma 3"},{"comment":"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'.","section":"Figure 3 caption"},{"comment":"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.","section":"Section 6, Theorem 3 proof"}],"recommendation":"major_revision","confidential_remarks":"The key issue is the unproven dirty-ancilla allocation in Lemma 4. The authors should either supply a rigorous induction showing that each parallel-MCX layer has enough disjoint idle qubits, or modify the construction (for example, by splitting layers with insufficient idle qubits at only constant overhead). If the allocation cannot be proven, the main theorem fails. The constant-adder recurrence (Eq. 23) is also a clear mathematical inconsistency that needs correction. The paper is otherwise well organized and the ladder-correctness proofs are a strength."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know up front. First, the main claim is worth taking seriously: an exact in-place adder over {Toffoli, CNOT, X} in O(log^2 n) depth with no ancilla would break the previous trade-off, where sublinear depth required renting ancillas. Nothing in the paper makes me think the claim is false. Second, the proof is not airtight. Lemma 4 is where the depth bound is earned, and it is the weakest paragraph in the paper.\n\nWhat is actually new: replacing a Toffoli ladder by a divide-and-conquer circuit of MCX gates, then compiling each MCX gate with two dirty ancillas using the Khattar–Gidney construction, is a good combination. The Ladder1 construction is a prefix-XOR network, which is standard, so the paper overstates that novelty; but the Ladder2 result and the adder assembled from it are new. The correctness proofs for Algorithms 1 and 2 are coherent and the recurrences are consistent. The controlled adder in Section 6 is a nice use of the U, V, U† cancellation trick.\n\nSoft spots, in order of importance. Lemma 4 asserts that in every layer of the Algorithm 2 circuit, each parallel MCX gate can be assigned two idle qubits, with gates separated by at least two non-acting qubits. Separation of supports by idle qubits is not by itself a matching argument. At the top level of Ladder2 you can probably make it work with care, but the recursion produces irregular qubit subsets and no counting argument is given. If any layer has fewer than two idle qubits per gate, that layer compiles in O(n) depth and Theorem 2's O(log^2 n) bound falls. This is a genuine gap, not a style issue. Corollary 2 is also internally inconsistent: the statement says no ancilla, the proof uses a dirty ancilla, and Table 3 lists one dirty. The constant-adder recursion in Corollary 2 is sketched rather than proven, and the recurrence deserves scrutiny. The novelty claim on Ladder1 should be tempered.\n\nWho gets value: circuit designers and resource-estimation people, anyone building quantum arithmetic on limited qubits. The paper deserves a serious referee. I would send it out and ask for a rigorous proof of Lemma 4, a corrected Corollary 2, and a calmer description of Ladder1.","headline":"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.","tokens_in":19499,"tokens_out":4085,"would_cite":true,"duration_ms":38099,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","81P68"],"pacs":["03.67.Lx"],"model":"deepseek-v4-flash","headline":"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.","keywords":["quantum adder","ripple-carry addition","ancilla-free","reversible logic","Toffoli gate","CNOT ladder","conditionally clean ancillae","logarithmic depth"],"falsifier":"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.","tokens_in":18472,"feed_emoji":"➕","tokens_out":12944,"duration_ms":94837,"temperature":0.7,"pith_summary":"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.","feed_headline":"Ancilla-free quantum adder runs in O(log²n) depth","feed_subtitle":"The first exact reversible adder to beat linear depth, needing zero extra qubits.","key_machinery":"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)$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the logarithmic-depth, two-dirty-ancilla implementation of multi-controlled-X gates that Lemma 4 uses to compile each layer of the Toffoli ladder.","marker":"[2]"},{"why":"Provides the ancilla-free ripple-carry adder that Algorithm 3 tweaks; its four ladders are the linear-depth bottlenecks replaced by the new circuits.","marker":"[14]"},{"why":"Introduced the conditionally clean ancillae technique that the paper's Toffoli-ladder construction builds on.","marker":"[1]"},{"why":"Supply the folklore logarithmic-depth fan-out operator (Lemma 1) used in the controlled adder and in the incrementer and constant-adder corollaries.","marker":"[16, 17]"},{"why":"Supplies the one-dirty-ancilla constant-adder recursion and CARRY operator that Corollary 2 plugs into with the new ladder circuits.","marker":"[11]"},{"why":"Supplies the dirty-ancilla incrementer splitting construction that lets Corollary 1 reduce the ancilla requirement from n dirty qubits to one.","marker":"[20]"}],"fun_headline_variants":["Quantum adder hits O(log²n) depth with zero ancillas","First exact reversible adder in sublinear depth, no ancillas","Ancilla-free adder achieves O(log²n) depth","Sublinear-depth adder needs no ancilla qubits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Quantum adder hits O(log²n) depth with zero ancillas","First exact reversible adder in sublinear depth, no ancillas","Ancilla-free adder achieves O(log²n) depth","Sublinear-depth adder needs no ancilla qubits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000486,"raw_usage":{"total_tokens":2463,"prompt_tokens":1081,"completion_tokens":1382,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":697,"completion_tokens_details":{"reasoning_tokens":1312}},"tokens_in":697,"tokens_out":1382,"duration_ms":9966,"temperature":1.0,"reasoning_tokens":1312,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T10:40:08.447622+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Quantum addition circuits and unbounded fan-out","cited_arxiv_id":null,"evidence_quote":"Provides the ancilla-free ripple-carry adder that Algorithm 3 tweaks; its four ladders are the linear-depth bottlenecks replaced by the new circuits."},{"cited_title":"Factoring using 2n + 2 qubits with toffoli based modular multiplication","cited_arxiv_id":null,"evidence_quote":"Supplies the one-dirty-ancilla constant-adder recursion and CARRY operator that Corollary 2 plugs into with the new ladder circuits."},{"cited_title":"Constructing large increment gates","cited_arxiv_id":null,"evidence_quote":"Supplies the dirty-ancilla incrementer splitting construction that lets Corollary 1 reduce the ancilla requirement from n dirty qubits to one."}],"review_version":1}