arXiv:2610.34446
Ancilla-free optimal quantum adder
Junhong Nie, Jialiang Tang, Xiaoming Sun, Wei Zi
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.
AI Summary
The paper asks whether exact in-place quantum addition can simultaneously achieve linear gate count, logarithmic depth, and zero ancillary qubits. It constructs an $n$-bit modular adder implementing $(a,b)\mapsto(a,a+b\bmod 2^n)$ with $O(n)$ gates and $O(\log n)$ depth using only $X$, CNOT, and Toffoli gates. The circuit is classically reversible and acts coherently on arbitrary superpositions. These bounds match bounded-arity gate-count and light-cone depth lower bounds. The construction reduces addition to two controlled ladders plus linear-size, logarithmic-depth CNOT circuits. It partitions each ladder into local block operations, an inter-block endpoint update, and interior corrections. Weighted Pascal matrices factor the inverse endpoint map into involutions, which can be implemented through repeated additions that restore borrowed workspace despite arbitrary initial states. Existing control wires provide workspace conditionally on propagation controls being satisfied. An initial recursive construction achieves $O(n\log\log n)$ gates and $O(\log n)$ depth. The final construction factors endpoint propagation into two weighted forests of logarithmic height. Shared encodings of dyadic-interval control products shorten the required workspace per block to $O(\log n)$, allowing logarithmic-size blocks and eliminating recursion. The resource bounds assume all-to-all connectivity and count gates in the stated reversible gate set. The paper establishes asymptotic bounds rather than concrete optimized gate counts or hardware performance; it does not analyze geometric-connectivity overhead. All borrowed input wires are restored, including when initially entangled with other registers.
We also used GPT-6.1 Sol (Codex) to assist with writing the manuscript and preparing LaTeX figures.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.