Pith. Sign in

REVIEW

Ancilla-free optimal quantum adder

PaperPDF from arXiv

data files

ReviewThe objections and verdict, as JSON Paper breakdownThe authors' claims, conditions and measurements, as JSON Signed receiptProof this review has not been altered
X Bluesky LinkedIn Reddit Hacker News
Junhong Nie, Jialiang Tang, Xiaoming Sun, Wei Zi

Quantum Physics · Submitted 25 Oct 2026 · 18 references

Pith's verdict: A technically deep paper that gives the first ancilla-free quantum adder with optimal asymptotic gate count and depth; the construction is intricate but the reasoning appears sound—the main practical caveat is the all-to-all connectivity assumption.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on October 27, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

  1. T0 AI review An AI read the paper and answered a fixed list of questions.
  2. T1 Audit Automatic checks that the references and files the paper relies on exist and match.
  3. T2 Compute The paper's code or calculations re-run with the same results.
  4. T3 Formal statement The claims written out in a formal math language a computer can read.
  5. T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 3 major objections · 7 minor · Ask about this paper · The compiled record · Read the full review →
Challenge this review Comment (0) Read on arXiv ↗
Cite ▾
arXiv ID2610.34446 (version 1)
Pith IDMSCIKVKA, Pith's permanent record of this paper and its review
CitationJialiang Tang, Junhong Nie, Wei Zi, Xiaoming Sun. "Ancilla-free optimal quantum adder." arXiv:2610.34446 (2026). https://pith.science/paper/MSCIKVKA
Cite this reviewBibTeX for Pith's review of this paper
Claim paper

Why Pith says this

Highlight any text to comment on it.

Referee report

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

An exact n-bit quantum adder achieves O(n) gates and O(log n) depth with no ancillary qubits, matching asymptotic lower bounds.

The reading

The paper constructs a quantum circuit that adds two n-bit numbers exactly using only X, CNOT, and Toffoli gates. It uses O(n) gates and O(log n) depth, and requires no extra qubits beyond the inputs. This is asymptotically optimal because any bounded-arity gate set must use at least Ω(n) gates and Ω(log n) depth. The construction works under all-to-all connectivity, meaning any two qubits can interact directly. If correct, it settles the resource trade-off for quantum addition: linear gate count, logarithmic depth, and zero ancillas can all be achieved simultaneously.

What carries the argument

The key machinery is a decomposition of the controlled ladder (the carry propagation) into a block framework and then into two forests whose paths have logarithmic length. Within each block, the algorithm uses existing control wires as conditional workspace via dirty-borrowing techniques (echoes based on Pascal matrices) to compute interval products. The forests decompose the inverse endpoint map into factors that square to the identity, allowing borrowed registers to be restored through four additions per factor. The shared dyadic encoding of interval products ensures that each walk uses O(log n) workspace per block.

Extended reading notes

Core claim

The paper proves that an exact n-bit quantum adder can be implemented without ancillary qubits using O(n) X, CNOT, and Toffoli gates and O(log n) depth, assuming all-to-all connectivity. This is achieved by accelerating the controlled ladder that underlies addition. The construction first partitions the data into blocks and uses a recursive scheme that yields O(n log log n) gates and O(log n) depth. It then refines the endpoint update by replacing the chain of consecutive endpoints with two weighted forest maps of logarithmic height, eliminating the recursion and cutting the gate count to O(n). Both the gate count and depth are asymptotically optimal.

Load-bearing premise

The construction assumes all-to-all connectivity, meaning any pair of qubits can interact directly with a single gate, which is not available in most near-term quantum processors with limited qubit connectivity.

Editorial extensions

If this is right

  • Quantum arithmetic circuits (addition, multiplication, modular exponentiation) can be built with asymptotically optimal resource counts, potentially reducing overhead in Shor's algorithm and quantum chemistry simulations.
  • The ancilla-free design frees qubits that would otherwise be used as temporary space, which is critical for near-term devices with limited qubit counts.
  • The construction provides a concrete reference point for quantum circuit compilers: any adder in a larger algorithm can be replaced by this one, and the resource analysis simplifies because ancillary qubits are not needed.
  • The techniques (conditional-space encoding, forest decomposition, Pascal-identity echoes) may generalize to other recursive or ladder-like computations, such as prefix sums or comparison circuits.

Reading between the lines

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

  • The all-to-all connectivity assumption is realistic for many proposed quantum error-corrected architectures but not for most current noisy intermediate-scale devices with nearest-neighbor restrictions; adapting the construction to limited connectivity would require additional routing gates, which may increase overhead.
  • The construction is classically reversible, meaning it could also be used as a reversible classical adder with the same resource bounds, potentially benefiting reversible computing or low-power design.
  • The paper leaves open whether the same asymptotic bounds can be achieved with a universal gate set (e.g., Clifford + T) under a standard error-correction fault-tolerant cost model, because the Toffoli gate is not native in most error-correction schemes and would need to be decomposed.
Original abstract

We construct an exact $n$-bit quantum adder with $O(n)$ gates and $O(\log n)$ depth that requires no ancillary qubits. The circuit uses only $X$, CNOT, and Toffoli gates under all-to-all connectivity and is classically reversible. Our construction accelerates the controlled ladder underlying addition. Grouping the data into blocks and use existing control qubits as conditional workspace gives a recursive construction with $O(n\log\log n)$ gates and $O(\log n)$ depth. We then coordinate inter-block propagation via two short-path forest operations to cut the per-block workspace requirement, yielding a nonrecursive implementation with $O(n)$ gates. Both the gate count and circuit depth are asymptotically optimal.

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.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-10-27: 1 request, 4,858 input tokens.

What the abstract itself states, as probabilities: claims first 0.06 · states limitation 0.37 · human participants 0.01 · controlled comparison 0.03 · randomized assignment 0.02 · states quantitative result 0.98 · compares with prior results 0.20 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; .

We construct an exact $n$-bit quantum adder with $O(n)$ gates and $O(\log n)$ depth that requires no ancillary qubits. The circuit uses only $X$, CNOT, and Toffoli gates under all-to-all connectivity and is classically reversible. Our construction accelerates the controlled ladder underlying addition. Grouping the data into blocks and use existing control qubits as conditional workspace gives a recursive construction with $O(n\log\log n)$ gates and $O(\log n)$ depth. We then coordinate inter-block propagation via two short-path forest operations to cut the per-block workspace requirement, yielding a nonrecursive implementation with $O(n)$ gates. Both the gate count and circuit depth are asymptotically optimal.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#sentencerolethe authors' own workstates the main conclusionstrength
s0 We construct an exact $n$-bit quantum adder with $O(n)$ gates and $O(\log n)$ depth that requires no ancillary qubits. contribution 0.92 0.95 0.86 asserted 1.00
s1 The circuit uses only $X$, CNOT, and Toffoli gates under all-to-all connectivity and is classically reversible. method 0.86 0.85 0.08 asserted 1.00
s2 Our construction accelerates the controlled ladder underlying addition. method 0.70 0.87 0.06 asserted 1.00
s3 Grouping the data into blocks and use existing control qubits as conditional workspace gives a recursive construction with $O(n\log\log n)$ gates and $O(\log n)$ depth. method 0.96 0.90 0.10 asserted 1.00
s4 We then coordinate inter-block propagation via two short-path forest operations to cut the per-block workspace requirement, yielding a nonrecursive implementation with $O(n)$ gates. method 0.90 0.93 0.16 asserted 1.00
s5 Both the gate count and circuit depth are asymptotically optimal. result 0.78 0.83 0.51 asserted 1.00

What kind of paper the classifier reports this is: method or tool 0.81 · evidence from proof or derivation 0.98.

What was examined, and what was not

sources read
  • arXiv listing abstract v1
not examined
  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers
levels run
  • P abstract
not run
  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures
Figure 1. The block framework with r = 3 and b = 4, so n = 16. Each column represents one block, with its endpoint at the bottom. Arrows show propagation dependencies. The circuit leaves both endpoints and all controls unchanged and needs no borrowed bits. Each block uses its incoming endpoint and leaves its outgoing endpoint to the next block, so all corrections run in parallel, giving total size O(n) and depth O(b). Lemma 5 (Block reduction). For the partition above, suppose the local ladders have ancilla-free implementations of size Sloc(b) and depth Dloc(b). Suppose the endpoint update…
Figure 2. Interior correction for b = 4 and j ≥ 1. Undo the two interior gates, add the incoming contribution, and replay the two gates. Both endpoints and all controls are preserved. Then Tn has an ancilla-free implementation satisfying S(n) ≤ (r + 1)Sloc(b) + Send + O(n), D(n) ≤ Dloc(b) + Dend + O(b). (12) The incrementer correction in Section 4.3 reduces the last depth term to O(log(b + 1)). 4 The recursive construction The block framework leaves us with the endpoint update in Step 2 of Section 3. We first reduce this update to additions between the endpoint register and a borrowed register
Figure 3. implements this encoding with one X and one multi-controlled X. The latter borrows and restores an interior bit wi . All blocks run in parallel, so E = Q i Ei has size O(rb) and depth O(log(b + 1)). It preserves Hi and is its own inverse. Hi mi = pi,b wi Hi fi = 1 + mi + χi wi
Figure 4. The chain construction with r = 4, b = 64. The orange wire pi,64 has original value mi and encoded value fi . The green word Hi contains positions 1, . . . , 63. The borrowed bit ci above each block is used for zero tests. Below the endpoints are borrowed interior data: Zi , the word ai of i bits, and wi . The highlighted walk for ζ3 visits 3, 2, 1, 0. The encoding leaves Hi unchanged. The same echo can therefore still test whether its original bits were all one, the case χi = 1
Figure 5. Computing all running products of four copied inputs. The upward tree computes each interval’s product. In the downward tree, a left child receives its parent’s preceding product and a right child also multiplies the left interval’s product. Multiplying at each leaf gives the four running products. All intermediate bits start at zero; the root preceding product is set to one by X. Each level takes a constant number of gate layers. p \ Hi Hi ci ai wi U +ciM(·, i) U −1 U +ciM(·, i) U −1
Figure 6. Computing M before encoding. The circuit for block i adds χiM(·, i) into the borrowed word ai . U computes the running products in Hi when it starts at zero. An uncontrolled ⊕ complements its word, and each open control tests the entire word for zero. The zero tests borrow and restore wi . All wires except ai return to their initial values. Cost of the endpoint update. Each of the r walks has at most r stops, giving O(r 2 ) gates for copies, products, and sums. CNOT fanout trees copy shared inputs to the walks with O(r 2 ) gates and O(log(r + 1)) depth. The additions controlled by
Figure 7. Computing with F after encoding. The circuit for block i adds χisi to ζi using the same dirty echo. The bracketed word Hi includes the position used for si . V computes (23) in that position when Hi starts at zero. The borrowed data ai and Z are preserved; all temporary calculations are reversed. p (c, w) a Z ζ M E F E −1 M E F E −1 p (c, w) a Z ζ + AZ
Figure 8. The complete circuit for (ζ, Z) 7→ (ζ + AZ, Z). Read from left to right. M is the parallel application of
Figure 9. The incrementer correction used for the larger recursive blocks. The two bundled wires each contain b − 1 bits, and the CNOTs act bitwise. The increment and its inverse act on the little-endian word (yj−1,b, pj,1, . . . , pj,b), each borrowing and restoring the first interior bit. two satisfying κ(r + 1)r ≤ n. Set b =  n r + 1 . For the finitely many smaller sizes, use the direct ladder. Then b ≥ κr, r = Θ(√ n), and b = Θ(√ n). Adjust B0 for the remainder as in Section 3. Its length n − rb lies between b − r and b, leaving enough interior data for its borrowed source bit. The…
Figure 10. The two forests on endpoints 0, . . . , 8, with h = 4. Green labels give the grade di of every vertex in the corresponding row. The orange paths show the edges visited by one block’s walk in each forest. Their edge weights multiply to the conjunction over the full path interval. Each path is a ladder on its ordered vertices, which may be nonconsecutive endpoints. All other entries below the diagonal are zero. Define Q1 in the same way with both grades decreased by one, setting its entries below the diagonal to zero when dj = 0. There is at most one directed path between any two…
Figure 11. The layout for r = 8, b = 64, and h = 4. Green bits form Hi . The four bottom positions are D(i, 1), . . . , D(i, 4), with physical coordinates (i, 61), . . . ,(i, 64). Blue positions are chosen at larger intervals; orange positions are chosen at Bi . The grey positions in B8 are left unchanged. The words ai , the bits ci , wi , and Z are existing interior data, all restored by the circuit. We now fix the positions. Use the four bottom controls in each block: D(i, 1) = (i, b − 3), D(i, 2) = (i, b − 2), D(i, 3) = (i, b − 1), D(i, 4) = (i, b). (32) Apply the following formula…
Figure 12. Two layers of the interval encoding for r = 8. The root pair is shown after its initial complements, on the branch where it enters at zero. Each box B(j, i) continues the recursion on (j, i], omitting positions chosen at larger intervals. Hats mark the values after encoding. For example,
Figure 13. The chosen positions for r = 8: inherited positions in blue, newly chosen positions in orange. Each D(i, t) is one physical bit index in Bi . The highlighted intervals supply the walk 7 → 6 → 4 → 0. child inherits exactly one pair. Induction therefore gives at most two inherited positions at every interval. Together with its own two chosen positions, these are precisely the at most four controls in m(j, i). If any of these original controls is zero, both Π(j, i) and m(j, i) are zero. Otherwise, the call’s own pair enters at zero and all the omitted controls from larger intervals…
Figure 14. Three inward walks contribute to ζ4. Each box runs the complete circuit with v2,2, v3,1, v4,1 as the bits to change, and restores its other bits. The first three CNOTs add their new parity; the last three add their original parity. All three borrowed bits are restored. Add these three bits to ζ4, run their circuits again to restore them, and add the three bits to ζ4 again. Their initial values cancel and the three desired terms remain, as

Figures reproduced from arXiv:2610.34446 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.