A linear-size quantum circuit for addition with no ancillary qubits

Abstract

We construct a quantum circuit for addition of two $n$-bit binary numbers that uses no ancillary qubits. The circuit is based on the ripple-carry approach. The depth and size of the circuit are $O(n)$. This is an affirmative answer to the question of Kutin \cite{Kutin} as to whether a linear-depth quantum circuit for addition can be constructed without ancillary qubits using the ripple-carry approach. We also construct quantum circuits for addition modulo $2^n$, subtraction, and comparison that use no ancillary qubits by modifying the circuit for addition.