PreprintCC BY 4.0arXiv
Ancilla-free optimal quantum adder
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(nloglog 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.
Related
- Quantum Complexity of Ancilla-Free Unitary Embeddings for Nonlinear Dynamics via Generalized State-Dependent Double-Bracket Flows
- Exact Unitary Synthesis: Simultaneously Optimal in Size and Depth-Ancilla Tradeoff
- Ancilla-free randomized Toffoli gates and the T-count of Boolean oracles
- Evaluation of the quantum Fisher information for large systems via an ancilla
- Generation of arbitrary quantum states in cavity-atom systems with a three-level ancilla
BibTeX
@misc{nie2026ancillafree,
title = {{Ancilla-free optimal quantum adder}},
author = {Junhong Nie and Jialiang Tang and Xiaoming Sun and Wei Zi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.34446},
eprint = {2610.34446},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.34446},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Ancilla-free optimal quantum adder
AU - Junhong Nie
AU - Jialiang Tang
AU - Xiaoming Sun
AU - Wei Zi
PY - 2026
DA - 2026/10/25
PB - arXiv
DO - 10.48550/arxiv.2610.34446
UR - https://arxiv.org/abs/2610.34446
AB - 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(nloglog 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.
ER -