# Quantum Modular Adder over \(GF(2^{n}-1)\) without Saving the Final Carry
## 2 Related Works  
### Quantum Modular Adder Circuit  
[PERSON] et al. proposed several elementary quantum circuits for two \(n\)-qubit binary numbers \(a\) and \(b\), such as the quantum full adder \(|a,b>\rightarrow|a,a+b>\) and the quantum modulo \(N\) adder. The quantum modulo \(N\) adder called Adder-Mod, as shown in Figure 1, computes \(|a,b>\rightarrow|a,a+b\ mod\ N>\), where \(0\leq a,b<N\). The third resister for \(|b>\) as the input is one qubit larger than the second register for \(|a>\) as the input to prevent overflow. The last qubit in the third register is for the last carry of \(|a+b>\), and the third register finally provides the results from calculating \(|a+b\ mod\ N>\), denoted \(|S>\). [PERSON]'s Adder-Mod gate consists of five full adder \(FA\) gates, including two inverse full adder \(FA^{\dagger}\), as shown in Figure 2. \(FA\) is the addition of \(a\) given number to \(b\), and \(FA^{\dagger}\) is the inverse of \(FA\) to subtract a given number from \(b\). The parameters in Figure 2 are \(N\) for modulo, \(a\) and \(b\) for two numbers to add, \(c\) for carries, and \(t\) for checking whether \(a+b\) is smaller than \(N\) or not. [PERSON]'s approach for calculating the modulo operation is taking the output of \(a+b\) and subtracting \(N\). The subtraction of \(N\) depends on whether the value \(a+b\) is bigger than \(N\) or not. Looking at the Adder-Mod in Figure 2 step by step, the first \(FA\) in steps 1 and 2 performs a simple addition on the state \(|a,b>\), returning \(|a,a+b>\); the second \(FA\) in steps 3 and 4 adds \(-N\), obtaining the state \(|N,a+b-N>\) as the inverse \(FA\) after swapping \(a\) and \(N\) in steps 2 and 3. After the second \(FA\), denoted \(FA^{\dagger}\), the most significant qubit of \(|b>\) takes a value for whether an overflow occurred or not. \(|t>\) saves this information in steps 4 to 7 through the NOT gate and the CNOT (CONTROL-NOT) gate, as shown in Figure 6. If there is no overflow (\(a+b-N\) is smaller than \(N\)), the value of the \((n+1)\)-th qubit \(|b_{n}>\) is 0, 1, 1, and 0 in steps 4, 5, 6, and 7, respectively. At this stage, the value of \(|t>\) conditionally becomes 1 in steps 5 to 6 and resets the first resister \(|a>\) with \(N\) to zero in steps 7 and 8. On the contrary (\(a+b-N\) is larger than \(N\)), \(|b_{n}>\) is 1, 0, 0, and 1 in steps 4, 5, 6, and 7, respectively. \(|t>\) is 0 in steps 5 and 6 and the qubits \(|a>\) keep \(N\) as their value. After the third \(FA(+N)\) in steps 8 and 9, the value of \(|a>\) swaps back from \(N\) to \(a\) in steps 10 and 11, subtracting \(a\) in the total state \(|a,((a+b)\ mod\ N)-a>\) in steps 11 and 12, and adding \(a\) in the final state \(|a,(a+b)\ mod\ N>\) in steps 13 and 14. This operation is for leaving \(|a>\) and \(|b>\) in state \(|a,(a+b)\ mod\ N>\). Moreover, \(|c>\) and \(|t>\) are reset to their original value in state \(|0>\) through a second CONTROL-NOT gate in steps 12 and 13. Finally, the last \(FA\) returns original \(N,a,c,t\), and the result of sum \(|S>\), which is \((a+b)\ mod\ N\). Figure 1: [PERSON]’s quantum modulo \(N\) adder, called Adder-Mod. They also defined the quantum circuit of \(FA\)\(|a,b>\rightarrow|a,a+b>\) based on RCA, as shown in Figure 3, and used it for modular addition such as Figure 2. The \(FA\) shown in Figure 4 composites \(n\) carry gates called \(CR\), \(n-1\) inverse carry gates called \(CR^{\dagger}\), and \(n\) sum gates called \(SM\), where the \(CR\) and \(SM\) gates are shown in Figure 5. Unlike a half adder, \(FA\) computes the most significant bit of the result \(a+b\). This computation requires computing all carries \(c_{i}\), through the relation \(c_{i}\gets a_{i}\) and \(b_{i}\) and \(c_{i-1}\), where \(a_{i}\), \(b_{i}  
the target qubit, where the state of the control qubit is \(|1>\). If \(|x_{1}>\) is \(|1>\), the CNOT changes \(|x_{2}>\) in the state \(|0>\) into \(|1>\), where \(|x_{2}>\) is \(|0>\).