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
2n, subtraction, and comparison that use no ancillary qubits by modifying the circuit for addition.
We show how to construct a fast quantum circuit for computing the sum of two
n-bit binary numbers with few qubits. The constructed circuit uses
O(n/logn) ancillary qubits and its depth and size are
O(logn) and
O(n), respectively. The number of ancillary qubits is asymptotically less than that in Draper et al.'s quantum carry-lookahead adder, and the depth and size are asymptotically the same as those of Draper et al.'s. Moreover, we show that the circuit is useful for constructing an efficient quantum circuit for Shor's factoring algorithm.
We first show how to construct an
O(n)-depth
O(n)-size quantum circuit for addition of two
n-bit binary numbers with no ancillary qubits. The exact size is
7n−6, which is smaller than that of any other quantum circuit ever constructed for addition with no ancillary qubits. Using the circuit, we then propose a method for constructing an
O(d(n))-depth
O(n)-size quantum circuit for addition with
O(n/d(n)) ancillary qubits for any
d(n)=Ω(logn). If we are allowed to use unbounded fan-out gates with length
O(nε) for an arbitrary small positive constant
ε, we can modify the method and construct an
O(e(n))-depth
O(n)-size circuit with
o(n) ancillary qubits for any
e(n)=Ω(log∗n). In particular, these methods yield efficient circuits with depth
O(logn) and with depth
O(log∗n), respectively. We apply our circuits to constructing efficient quantum circuits for Shor's discrete logarithm algorithm.