Quantum Modular Adder over GF(2n − 1) without Saving the Final Carry

Abstract

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 frequencybased 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(n − 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.