We present an efficient addition circuit, borrowing techniques from classical carry-lookahead arithmetic. Our quantum carry-lookahead (\QCLA) adder accepts two n-bit numbers and adds them in O(\log n) depth using O(n) ancillary qubits. We present both in-place and out-of-place versions, as well as versions that add modulo 2^n and modulo 2^n - 1. Previously, the linear-depth ripple-carry addition circuit has been the method of choice. Our work reduces the cost of addition dramatically with only a slight increase in the number of required qubits. The \QCLA\ adder can be used within current modular multiplication circuits to reduce substantially the run-time of Shor's algorithm.
We present an efficient addition circuit, borrowing techniques from the classical carry-lookahead arithmetic circuit. Our quantum carry-lookahead (QCLA) adder accepts two n-bit numbers and adds them in O(log n) depth using O(n) ancillary qubits. We present both in-place and out-of-place versions, as well as versions that add modulo 2^n and modulo 2^n - 1. Previously, the linear-depth ripple-carry addition circuit has been the method of choice. Our work reduces the cost of addition dramatically with only a slight increase in the number of required qubits. The QCLA adder can be used within current modular multiplication circuits to reduce substantially the run-time of Shor's algorithm.
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.
The state of the art of quantum circuits using the ripple-carry strategy for the addition and comparison of two n-bit numbers is presented, as well as optimizations in the Clifford+ <?TeX
T?> Math 1 gate set, both in terms of <?TeX
CNOT?> Math 2 -depth and <?TeX
T?> Math 3 -depth, or <?TeX
CNOT?> Math 4 -count and <?TeX
T?> Math 5 -count. In particular, we consider the adders presented by Cuccaro et al. and Takahashi et al., and exhibit an adder with a <?TeX
T?> Math 6 -depth of 3n and a <?TeX
CNOT?> Math 7 -depth of 8n, while without optimization of the original circuits, a <?TeX
T?> Math 8 -depth of 6n is expected. Note that we have focused here on quantum ripple-carry adders using at most one ancilla, without any approximation of the 3-qubit gates involved (Toffoli, Peres and TR) or any strategy involving a measurement.
Addition is the most basic operation of computing based on a bit system. There are various addition algorithms considering multiple number systems and hardware, and studies for a more efficient addition are still ongoing. Quantum computing based on qubits as the information unit asks for the design of a new addition because it is, physically, wholly different from the existing frequency-based computing in which the minimum information unit is a bit. In this paper, we propose an efficient quantum circuit of modular addition, which reduces the number of gates and the depth. The proposed modular addition is for the Galois Field GF(2n−1), which is important as a finite field basis in various domains, such as cryptography. Its design principle was from the ripple carry addition (RCA) algorithm, which is the most widely used in existing computers. However, unlike conventional RCA, the storage of the final carry is not needed due to modifying existing diminished-1 modulo 2n−1 adders. Our proposed adder can produce modulo sum within the range 0,2n−2 by fewer qubits and less depth. For comparison, we analyzed the proposed quantum addition circuit over GF(2n−1) and the previous quantum modular addition circuit for the performance of the number of qubits, the number of gates, and the depth, and simulated it with IBM’s simulator ProjectQ.