## A Logarithmic Depth Quantum Carry-Lookahead Modulo (2 n - 1) Adder

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.01002v1-figure-95b58db5-c444-4692-816a-cd2ed1a88e87.jpg)

Edgard Muñoz-Coreas University of North Texas Denton, TX, USA

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.01002v1-figure-81207c03-ca0b-4504-9435-e0b0832cbc07.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.01002v1-figure-f8e79cb3-ee0d-4696-bd19-48ff04a2d73a.jpg)

Edgard.Munoz-coreas@unt.edu

Bhaskar Gaur University of Tennessee Knoxville, TN, USA bgaur@vols.utk.edu

Himanshu Thapliyal University of Tennessee Knoxville, TN, USA hthapliyal@utk.edu

## ABSTRACT

Quantum Computing is making significant advancements toward creating machines capable of implementing quantum algorithms in various fields, such as quantum cryptography, quantum image processing, and optimization. The development of quantum arithmetic circuits for modulo addition is vital for implementing these quantum algorithms. While it is ideal to use quantum circuits based on fault-tolerant gates to overcome noise and decoherence errors, the current Noisy Intermediate Scale Quantum (NISQ) era quantum computers cannot handle the additional computational cost associated with fault-tolerant designs. Our research aims to minimize circuit depth, which can reduce noise and facilitate the implementation of quantum modulo addition circuits on NISQ machines. This work presents quantum carry-lookahead modulo (2 n - 1) adder (QCLMA), which is designed to receive two n-bit numbers and perform their addition with an O(log n) depth. Compared to existing work of O(n) depth, our proposed QCLMA reduces the depth and helps increase the noise fidelity. In order to increase error resilience, we also focus on creating a tree structure based Carry path, unlike the chain based Carry path of the current work. We run experiments on Quantum Computer IBM Cairo to evaluate the performance of the proposed QCLMA against the existing work and define Quantum State Fidelity Ratio (QSFR) to quantify the closeness of the correct output to the top output. When compared against existing work, the proposed QCLMA achieves a 47.21% increase in QSFR for 4-qubit modulo addition showcasing its superior noise fidelity.

## KEYWORDS

quantum adders, modulo addition, noise, carry-lookahead, quantum circuit, quantum computing, NISQ, FTQ

## ACKNOWLEDGEMENT

This research used resources of the Oak Ridge Leadership Computing Facility, which is a DOE Office of Science User Facility supported under Contract DE-AC05-00OR22725.

## 1 INTRODUCTION

Quantum computing is an upcoming field with many potential applications, including cryptography, optimization, machine learning, communication, and simulating scientific experiments. Quantum arithmetic circuits enable efficient implementations of quantum computing algorithms such as variational quantum algorithms, quantumapproximate optimization algorithms, singular value thresholding, HHL algorithm, elliptic curve cryptography (ECC), Shor's algorithm, and quantum convolution neural networks (QCNN) [3, 5, 10, 14].

Quantum modulo arithmetic circuits are a subset of the quantum arithmetic circuits that perform arithmetic operations by returning the remainder of the division of the result by a given modulus. The result of a modulo operation is always within a finite range (0, modulus - 1), which ensures closure under addition, subtraction, and multiplication. Among various quantum modulo operations, quantum modulo adder is the most basic and versatile quantum circuit, which can help create quantum modulo arithmetic circuits for subtraction, multiplication and exponentiation [16, 17, 19]. In addition, quantum modulo adders fulfill specialized purposes in quantum image processing (QIP), quantum cryptography, and quantum convolution neural networks by reducing the cost of computations and operating in a finite set of numbers [3, 5, 8, 12, 14, 19].

Vedral et al. designed one of the earliest known general modulo N adders [18]. This adder generates a modulo sum by adding the two inputs and subtracting N using a simple mechanism. The final output depends on whether the Sum is larger or smaller than N. However, this design includes five stages that increase the quantum gate count and depth, making it impractical for the NISQ era.

Therefore, upcoming research endeavors focus on designing resource-efficient modulo adders that can be applied to crucial moduli with practical significance in designated fields. For example, the quantum modulo 2 n adder is utilized in quantum image scrambling and quantum image encryption [8]. Most quantum modulo 2 n adders are effortlessly derived from existing quantum full adder designs by carryout truncation [1, 15]. The quantum modulo (2 n - 1) adder, on the other hand, reduces computational cost in convolution neural networks and assumes a crucial role in public cryptographic systems that operate on moduli expressible in Galois Field GF(2 n - 1) [3, 5, 12]. Nevertheless, unlike quantum modulo 2 n adder designs, designing a quantum modulo (2 n - 1) adder is not a straightforward undertaking, with the design proposed by Kim et al. currently representing the most efficient option [9].

Unlike Vedral et al., the design proposed by Kim et al. employs only two stages. Nevertheless, it still employs quantum ripple-carry addition (QRCA) for generating those two stages and consequently inherits the shortcomings of QRCA [1, 9, 18]. The QRCA logic entails a lengthy Carry path, which increases the carryout's depth and noise susceptibility. Additionally, the output's least significant bits (LSB) are generated last, despite being inputted first, leading to increased idle time and a higher probability of being impacted by amplitude damping and depolarizing noise sources [7].

In order to address these issues, we propose the use of a quantum carry-lookahead modulo (2 n - 1) adder (QCLMA), which has an O(log n) depth in contrast to Kim et al.'s quantum modulo (2 n -1) adder, which has an O(n) depth. QCLMA's lower depth, when compared to Kim et al.'s version, leads to a reduction in idle time

available to the qubits, potentially increasing the noise fidelity of the circuit. Furthermore, QCLMA relies on a tree structure for generating carryout, which is more resilient to error accumulation than the single longer Carry path of Kim et al.'s quantum modulo (2 n - 1) adder that passes through all the qubits. As a result, the improved noise fidelity of the proposed QCLMA makes it a more suitable choice for NISQ era quantum computers that suffer from higher noise and erroneous results. In the fault-tolerant quantum (FTQ) era quantum computers featuring error correction, the proposed QCLMA would still be relevant as it would execute faster due to its lower depth.

To illustrate the superior noise fidelity of the proposed quantum modulo (2 n - 1) adder over Kim et al.'s version [9], we run our experiments on a 27-qubit quantum computer called IBM Cairo using IBM Qiskit [6]. Due to excessive noise in the current NISQ era quantum computers, we compare the proposed QCLMA with Kim et al.'s QRCA based modulo (2 n - 1) adder using Quantum State Fidelity Ratio (QSFR), a figure of merit which measures the ratio of the frequency of correct output to the frequency of top occurring output. We calculate the QSFR for both our proposed QCLMA and Kim et al.'s QRCA based modulo (2 n - 1) adder for all possible input combinations. Our results demonstrate that our proposed design has a 47.21% higher QSFR than Kim et al.'s design, indicating that our design produces correct output closer to the top output than Kim et al.'s design. To summarize, our main contributions are:

- · We propose a quantum carry-lookahead modulo (2 n - 1) adder (QCLMA) with an O(log n) depth compared to the O(n) depth of existing works. The proposed QCLMA offers superior noise fidelity and scalability via its improved carry path and reduced depth.
- · We demonstrate the higher noise resilience of the proposed QCLMAover Kim et al.'s existing design by running experiments on a 27-qubit IBM Quantum Computer IBM Cairo.
- · Wedefine the quantum state fidelity ratio (QSFR), a figure of merit for noise resilience to measure the closeness of the correct output to the top output. Our proposed QCLMA has a 47.21% higher QSFR in a 4-qubit configuration, establishing the effectiveness of our design.

This paper is organized with section 2 providing background on quantum gates and modulo addition. Section 3 discusses the existing works related to this research. Section 4 presents the proposed design. Section 5 compares the performance of the proposed quantum modulo (2 n - 1) adder with Kim et al.'s version[9]. Section 6 discusses the results and reasons behind the superior performance of the proposed quantum modulo (2 n - 1) adder. Finally, section 7 concludes this work.

## 2 BACKGROUND

## 2.1 Quantum Gates

To provide a comprehensive understanding, a detailed explanation of the quantum gates utilized in this paper is presented below.

- · CNOT Gate: CNOT gate, also known as the Feynman gate is shown in Figure 1(a). It maps |A,B ⟩ to |A, 𝐴 ⊕ ⟩ B helping realize XOR and XNOR operations.
- · Toffoli Gate: Toffoli gate, also referred to as CCNOT (double controlled NOT) gate, achieves AND and NAND logical operations depending upon value of the third input |C . It is the most ⟩ resource intensive gate used in this work. Figure 1(b) shows how the Toffoli gate maps three input |A,B,C ⟩ to three outputs |A,B,A B · ⊕ C . ⟩

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.01002v1-figure-61f2e2c5-220c-42c9-b5c7-615182449875.jpg)

## 2.2 Modulo (2 n - 1) addition

The modulo addition operation accepts two inputs, a and b, fulfilling 0 ≤ a,b &lt; N, and provides (a + b) mod N as the output, where N is the modulus. The modulo operation performs division on the Sum and discards the quotient to return only the remainder. As represented by Equation 1, the modulo (2 n - 1) addition is a special case of modulo addition where the modulus N = (2 n - 1). The modulo 2 n and (2 n - 1) are efficient in their binary representation, as they can represent the maximum numbers possible in n-bits. Modulo (2 n - 1) has the additional advantage of representing prime numbers depending on the value of n. Due to this unique property of modulo (2 n - 1) adders, optimizing them can help optimize various cryptography systems such as RSA that use large prime numbers [3, 12]. Modulus (2 n - 1) can also reduce computation when used alongside other moduli like 2 n and (2 n + 1) within a residue number system (RNS) [2]. Finally, the modulo (2 n - 1) adder can help enable other operations of the modulo and RNS algebra, such as subtraction and multiplication [11].

$$S u m = \begin{cases} a + b, & \text{if $0\leq (a+b)<2^{n}-1$} \\ 0, & \text{if $(a+b)=2^{n}-1$} \\ ( a + b ) m o d ( 2 ^ { n } - 1 ) & \text{if $(a+b)>2^{n}-1$} \end{cases}$$



$$\text{where } 0 \leq a, b, S u m < 2 ^ { n } - 1$$

However, a common problem faced by the modulo adders is the double representation of zero when zero is represented by all bits set to zero and all bits set to one. In finite field number systems used in cryptography and RNS, a double representation of zero can cause ambiguity in mathematical operations. We avoid this issue by ensuring that both the inputs and output remain within the range (0, 2 n -2).

## 3 RELATED WORKS

The research on quantum modulo adder began with Vedral et al.'s proposal of a general quantum modulo adder that calculates the output as (a+b) mod N, with a and b being input satisfying the condition: 0 ≤ a,b ≤ N [18]. Their method involves using the output of a quantum full adder and subtracting N depending on whether a+b is greater or smaller than N. Unfortunately, although their design is versatile, allowing for any integer value of modulus N, it requires five stages, making it impractical for NISQ.

Figure 2: Quantum ripple-carry adder (QRCA) based quantum modulo (2 n - 1) adder by Kim et al. in 4-qubit configuration [9]. The inputs are (a 0 :a 3 ) and (b 0 :b 3 ) while (S 0 :S 3 ) represent Sum qubits and (c 0 :c 3 ) represent the Carry qubits. The QRCA mechanism causes higher depth and longer paths in both Carry and the Sum generation, increasing the noise susceptibility. The LSB qubits are more noise prone as they spend significantly longer time idling than the MSB qubits [7].

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.01002v1-figure-49ad35cd-b0de-48bb-ba61-f303d49a1084.jpg)

Further interesting research focused on optimizing quantum modulo adders for specific applications. For instance, Roetteler et al. optimize a variant of quantum modulo adder for use in reversible elliptic curve operations in quantum cryptography, which uses a constant integer modulus [13]. However, their design also suffers from high depth as it uses four stages. On the other hand, Markov and Saeedi do not design a modulo adder but instead propose a reversible circuit for conditional modular addition with a constant as they focus on optimizing modular multiplication for Shor's quantum number-factoring algorithm [11].

## where 0 ≤ 𝑎, 𝑏, 𝑆𝑢𝑚 &lt; 2 n - 1

Additional research on quantum modulo adders accompanied the development of quantum full adders. For quantum modulo 2 n adders, Cuccaro et al. and Takahashi et al. extend their designs for the quantum full adders to quantum modulo 2 n adders using simple truncation of the carryout [1, 15]. This technique works as an n-bit output is expected from n-bit input addition, with the truncated carryout being the most significant bit (MSB) representing the 2 n position.

Draper et al. propose a new architecture for quantum carrylookahead adders with O(log n) depth and extend their design to both modulo 2 n and modulo (2 n - 1) adders [4]. However, their research lacks sufficient information on the conversion process and its limitations. Additionally, their design uses one's complement arithmetic, which represents zero with both all zeros and all ones, creating the problem of double representation of zero that is not addressed in their research.

Kim et al. design a quantum modulo adder for the Galois Field GF(2 n - 1) useful in ECC and multivariate quadratic-based postquantum cryptography (MQPQC). Their design outputs (a+b) mod (2 n - 1) with the inputs satisfying condition: 0 ≤ a,b &lt;(2 n - 1) [3, 9, 12].

$$S u m = \begin{cases} \begin{array} { c c } 0, & \text{if $(a+b)=2^{n}-1$} & (2a) & \text{the $1$} \\ ( a + b + c _ { n } ) m o d ( 2 ^ { n } - 1 ) & \text{else} & (2b) & \text{in $F$} \end{array} \end{cases} \end{cases}$$

Their approach works in two stages. First, they implement Equation 2b using Carry generation logic to calculate carryout c n and feed it as input Carry to Carry truncated full adder performing addition of a and b. As shown in Figure 2, their optimized circuit utilizes two ripple carry addition units, first for generating Carry and second for Carry truncated addition. However, if the Sum is equal to the modulus, the set zero logic acts to return zero. Figure 2 shows the set zero logic enabled using two CNOT and two NOT gates outside the boxes denoting the addition units. The set zero logic also solves the problem of double representation of zero. Our upcoming section will detail our proposed design, which leverages our comprehension of the approach adopted by the aforementioned research.

## 4 PROPOSED DESIGN

In the previous section, we discussed how Kim et al. designed the quantum modulo (2 n - 1) adder. However, as both stages in Kim et al. 's quantum modulo (2 n - 1) adder uses quantum ripple carry addition (QRCA) logic, it suffers from issues persistent in Vedral et al. For example, the depth grows linearly with input qubit size, causing the Carry propagation chain to become longer, thereby reducing the noise fidelity. We address these issues in the proposed quantum carry-lookahead modulo (2 n - 1) adder (QCLMA) using by introducing logarithmic depth of O(log n) complexity. We also utilize tree based Carry propagation which is more resilient to noise than the chain based Carry propagation of QRCA.

To construct the proposed quantum carry-lookahead modulo (2 n - 1) adder (QCLMA), we selectively choose between two types of logic: out-of-place and in-place. The out-of-place logic passes both the inputs unchanged and generates Sum on ancillae. As depicted in Figure 3, we use it as the first stage of our quantum modulo (2 n

Figure 3: Proposed quantum carry-lookahead modulo adder (QCLMA) in 4-qubit configuration. First, the Carry generation logic takes the inputs (a 0 :a 3 ) and (b 0 :b 3 ) to generate Carry qubits (c 0 :c 4 ). The out-of-place carry-lookahead generation logic makes sure that the inputs are passed intact for next stage. The in-place carry-lookahead truncated full adder generates the Sum (S0 :S 3 ) in place of input b. Both the Carry and Sum are generated using a tree-based structure which has a shorter O(log n) depth. Lesser variation in idling time among the qubits makes the proposed QCLMA noise resilient.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.01002v1-figure-cb9ca210-d0bb-4587-bb5a-67fd9fb88898.jpg)

Table 1: /Q\_u.scantum Resources for Proposed QCLMA and Kim et al.'s QRCA based Modulo (2 n - 1) Adders ( log 2 denoted as log and w(n) is number of 1's in binary representation of n.)

| Adder          | Sub-Modules     | Depth   | Depth                                 | Gate Count   | Gate Count                 | Gate Count   | Qubits              |
|----------------|-----------------|---------|---------------------------------------|--------------|----------------------------|--------------|---------------------|
| Adder          | Sub-Modules     | CNOT    | Toffoli                               | CNOT         | Toffoli                    | NOT          | Qubits              |
|                | Carry Generator | 1       | 2n                                    | n            | 3n - 1                     | 0            |                     |
|                | Truncated Adder | 3n - 2  | 3n - 3                                | 3n - 2       | 3n - 3                     | 0            |                     |
|                | Set Zero Logic  | 2       | 0                                     | 2            | 0                          | 2            |                     |
|                | Total           | 3n + 1  | 5n - 3                                | 4n           | 3n -4                      | 2            | 3n+1                |
| Proposed QCLMA | Carry Generator | 2       | ⌊ 𝑙𝑜𝑔 ( 𝑛 )⌋ +3                       | 2n           | 4n-3w(n)-2 ⌊ 𝑙𝑜𝑔 ( 𝑛 )⌋ +1 | 0            |                     |
| Proposed QCLMA | Truncated Adder | 4       | ⌊ 𝑙𝑜𝑔 ( 𝑛 )⌋ +2 ⌊ 𝑙𝑜𝑔 ( 𝑛 - 1 )⌋ +2   | 4n           | 4n-4                       | 2n           |                     |
| Proposed QCLMA | Set Zero Logic  | 2       | 0                                     | 2            | 0                          | 1            |                     |
| Proposed QCLMA | Total           | 8       | 3 ⌊ 𝑙𝑜𝑔 ( 𝑛 )⌋ +2 ⌊ 𝑙𝑜𝑔 ( 𝑛 - 1 )⌋ +5 | 6n+2         | 8n-3w(n)-2 ⌊ 𝑙𝑜𝑔 ( 𝑛 )⌋ -3 | 2n+1         | 3n+2+2 ⌊ 𝑙𝑜𝑔 ( 𝑛 )⌋ |

- 1) adder as it can pass the inputs to be used by the second stage. We optimize the out-of-place logic to generate only Carry while passing the inputs to second stage. Furthermore, we initialize the first ancilla with |1 ⟩ to eliminate the redundant NOT gate.

and depth for the two adders. We see an increase in qubits used in the proposed QCLMA as it uses extra qubits as ancillae. The depth, on the other hand, is O(log n) compared O(n) of Kim et al.'s quantum modulo (2 n - 1) adder.

The first stage generates carryout c n for the second stage, which uses it as input Carry for carryout truncated full adder, like in Equation 2b. Here, we use an in-place quantum carry-lookahead adder which generates Sum in place of input B saving ancillae, as evident from Figure 3. The set zero logic mechanism works in the same manner as before. Table 1 shows the quantum resource usage

For a 4-qubit configuration, the proposed QCLMA has 38% lower CNOT depth compared to Kim et al.'s modulo (2 n - 1) adder. Here CNOT depth is defined as a measure of CNOT gate layers that can be executed in parallel in the quantum circuit. Figures 2 and 3 illustrates that the CNOT depth in the proposed QCLMA and Kim et al. 's version are eight and thirteen, respectively. Similarly, the

proposed QCLMA has 23% lower Toffoli depth compared to Kim et al. 's modulo (2 n - 1) adder, as the Toffoli depth in proposed QCLMA and Kim et al.'s version are thirteen and seventeen, respectively. We define Toffoli depth as a measure of Toffoli gate layers that can be executed in parallel in the quantum circuit. In the section 5, we present a detailed analysis of the implications of depth reduction on noise resilience.

## 5 NOISE-RESILIENCE OF PROPOSED DESIGN

To compare the noise resilience of the proposed quantum modulo (2 n - 1) adder with Kim et al.'s quantum modulo (2 n - 1) adder, we run experiments on a 27-qubit IBM quantum computer (IBM Cairo) using the following methodology. We first create 4-qubit versions of both circuits as shown in Figure 2 and Figure 3. For four bits, the modulus is (2 4 - 1) = 15, and the range of input and output values is 0 ≤ 𝑎, 𝑏, 𝑆𝑢𝑚 &lt; 15.

For the proposed quantum adder, we fix the value of input A as constant but iterate over the value of B from (0, 14) to create fifteen circuits appended to a single job before being sent to IBM Cairo. We batch fifteen such jobs for each value of A in (0, 14) to run the proposed quantum adder for all 255 input combinations. We use the same methodology also to generate and batch the jobs for Kim et al. 's quantum adder. All jobs are dispatched with 1024 shots. The output from IBM Cairo is received in the form of shot frequency in the sixteen different possible outputs, from 0000 to 1111.

Since the output of NISQ era machines such as IBM Cairo is noisy, the correct output may not stand among the top three outputs and strongly depends on the input combinations. For example, for the input combination causing the least delay: A = B = 0, the correct output is the output with the highest shot count for both quantum modulo (2 n - 1) adders. Whereas for the input combination causing the maximum delay: A = B = 14, the correct output is at a fourteenth place for Kim et al.'s modulo adder and sixth place for the proposed modulo adder. Since the rank of correct output among all the possible outputs does not measure it's degree of divergence from the top output, we need another criterion to facilitate a meaningful comparison of the adders.

Hence we design a figure of merit called Quantum State Fidelity Ratio (QSFR) to measure the closeness of the correct output to the top output. As shown in Equation 3, QSFR is the ratio of the frequency of the correct output to the frequency of the top output. QSFR helps us to quantify the fidelity and degree of improvement needed to advance the correct answer to the top position.

$$Q S F R = \frac { Frequency of Correct Output } { Frequency of Top Output } \quad \ \ ( 3 ) \quad \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$$

We calculate the average QSFR for every value of input A added with B in range (0, 14) and plot them in Figure 4. Each tick on the x-axis represents the QSFR averaged for a job with constant input A and input B iterating in range (0, 14). The mean of all the average QSFR helps quantify the improvement needed by the design considering all 255 input combinations, which computes to 0.6891 for the proposed QCLMA compared to 0.4681 for the Kim et al.'s QRCA based modulo (2 n - 1) adder. The substantial 47.21% rise in average QSFR confirms the superior noise fidelity and enhanced potential for improvement in the proposed QCLMA.

Figure 4: Comparison of Average QSFR of Proposed QCLMA and Kim et al.'s QRCA based modulo (2 n - 1) adder, obtained keeping constant A and varying B. Proposed adder has 47.21% higher average QSFR establishing superior noise fidelity.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.01002v1-figure-c49f23a9-1010-4177-962c-4e7875773a3b.jpg)

In the forthcoming section, we analyze various factors contributing to this improvement.

## 6 DISCUSSION

To gain further insight into the superior performance of the proposed quantum carry-lookahead modulo adder (QCLMA), we examine an input combination of A = 10 and B = 2. In this scenario, both modulo (2 n - 1) adders yield the output S = 12 at the eleventh position among sixteen possible outputs. Figure 5 highlights the variation in QSFR between the two cases, despite the frequency of the correct output being nearly identical. For instance, Figure 5(b) shows the proposed QCLMA has the correct output with a frequency of 55 and QSFR of 0.55, compared to the frequency of 49 and QSFR of 0.343 for Kim et al.'s QRCA based modulo (2 n - 1) adder shown in Figure 5(a).

Figure 5(a) displays the output frequency profile of Kim et al.'s QRCA based modulo (2 n - 1) adder, revealing a nearly exponential decline from the top output. It means that the correct output unless it is the top occurring one, will have an exponentially increasing gap with the top output. The source of this exponential drop is the QRCA architecture that introduces a considerable variation in the depth and qubit idling time. In comparison, Figure 5(b) shows that the proposed QCLMA follows a linear decrease in frequency under the same experimental conditions, demonstrating a higher resilience to disruptions caused by noise. QCLMA's tree structure essentially creates a self-normalization effect, reducing inter-output variation and introducing noise robustness.

## 7 CONCLUSION

In this work, we have proposed quantum carry-lookahead modulo (2 n - 1) adder (QCLMA) that primarily introduces O(log n) depth compared to O(n) depth of existing work. We demonstrate the impact of O(log n) depth in improving noise resilience by running experiments on a 27-qubit quantum computer called IBM Cairo. As a result, the proposed QCLMA improves by 47.21% in terms of

(a) Kim et al.'s QRCA based Modulo (2 n - 1) adder

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.01002v1-figure-1a53faca-7bc5-4aae-869a-262a35dc00e9.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.01002v1-figure-afb1b0f7-0c52-4075-b77a-b171a8c6e1a0.jpg)

(b) Proposed quantum carry-lookahead modulo adder (QCLMA)

Figure 5: The above graphs illustrate the output of the modulo adders generated from IBM Cairo, arranged in descending order of frequency. Identical input A = 10 and B = 2 is supplied, with both adders yielding S = 12 or 1100 as the output at the same 11 th position among 16 possible outputs. The output profile of our proposed QLCMA adder exhibits a slower descent rate than the version proposed by Kim et al., reducing the relative gap with the top output and improving its chances of improvement.

noise fidelity using quantum state fidelity ratio (QSFR), a figure of merit that measures the closeness of the correct output to the top output. We also trace the origin of this performance by comparing the output frequency profile of the proposed quantum modulo (2 n - 1) adder with existing work obtained under identical input and output scenarios.

Our results illustrate that the shorter depth and distributed Carry path increase the noise fidelity and make the QCLMA suitable for NISQ era quantum computers. The proposed QCLMA can be instrumental in creating quantum modulo subtraction and multiplication circuits, and for applications such as quantum cryptography and quantum image processing. We conclude that QCLMA has the potential to benefit quantum modulo arithmetic circuits by increasing their noise resilience.

## REFERENCES

- [1] Steven A Cuccaro, Thomas G Draper, Samuel A Kutin, and David Petrie Moulton. 2004. A new quantum ripple-carry addition circuit. arXiv preprint quantph/0410184 (2004).
- [2] Laurent-Stéphane Didier and Luc Jaulmes. 2013. Fast modulo 2 n- 1 and 2 n; 1 adder using carry-chain on FPGA. In 2013 Asilomar Conference on Signals, Systems and Computers . IEEE, 1155-1159.
- [3] Jintai Ding and Dieter Schmidt. 2005. Rainbow, a new multivariable polynomial signature scheme. In ACNS , Vol. 5. Springer, 164-175.
- [4] Thomas G Draper, Samuel A Kutin, Eric M Rains, and Krysta M Svore. 2004. A logarithmic-depth quantum carry-lookahead adder. arXiv preprint quantph/0406142 (2004).
- [5] Tak Hur et al. 2022. Quantum convolutional neural network for classical data classification. Quantum Machine Intelligence 4, 1 (2022), 3.
- [6] IBM Quantum. 2022. version 0.39.0 . https://quantum-computing.ibm.com/ computer software.
- [7] Akshaya Jayashankar, My Duy Hoang Long, Hui Khoon Ng, and Prabha Mandayam. 2022. Achieving fault tolerance against amplitude-damping noise. Physical Review Research 4, 2 (2022), 023034.
- [8] Nan Jiang, Wen-Ya Wu, and Luo Wang. 2014. The quantum realization of Arnold and Fibonacci image scrambling. Quantum information processing 13, 5 (2014), 1223-1236.
- [9] Aeyoung Kim, Seong-Min Cho, Chang-Bae Seo, Sokjoon Lee, and Seung-Hyun Seo. 2021. Quantum Modular Adder over GF (2 n- 1) without Saving the Final Carry. Applied Sciences 11, 7 (2021), 2949.
- [10] Yonghae Lee, Jaewoo Joo, and Soojoon Lee. 2019. Hybrid quantum linear equation algorithm and its experimental test on IBM Quantum Experience. Scientific reports 9, 1 (2019), 4778.
- [11] Igor L Markov and Mehdi Saeedi. 2012. Constant-optimized quantum circuits for modular multiplication and exponentiation. arXiv preprint arXiv:1202.6614 (2012).
- [12] Albrecht Petzoldt. 2020. Efficient key generation for rainbow. In Post-Quantum Cryptography: 11th International Conference, PQCrypto 2020, Paris, France, April 15-17, 2020, Proceedings 11 . Springer, 92-107.
- [13] Martin Roetteler, Michael Naehrig, Krysta M Svore, and Kristin Lauter. 2017. Quantum resource estimates for computing elliptic curve discrete logarithms. In Advances in Cryptology-ASIACRYPT 2017 . Springer, 241-270.
- [14] Peter W Shor. 1994. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science . Ieee, 124-134.
- [15] Yasuhiro Takahashi and Noboru Kunihiro. 2005. A linear-size quantum circuit for addition with no ancillary qubits. Quantum Information &amp; Computation 5, 6 (2005), 440-448.
- [16] Himanshu Thapliyal. 2016. Mapping of subtractor and adder-subtractor circuits on reversible quantum gates. In Transactions on Computational Science XXVII . Springer, 10-34.
- [17] Rodney Van Meter and Kohei M. Itoh. 2005. Fast quantum modular exponentiation. Phys. Rev. A 71 (May 2005), 052320. Issue 5. https://doi.org/10.1103/ PhysRevA.71.052320
- [18] Vlatko Vedral, Adriano Barenco, and Artur Ekert. 1996. Quantum networks for elementary arithmetic operations. Physical Review A 54, 1 (1996), 147.
- [19] Bo Wu et al. 2020. A novel modular multiplier for isogeny-based post-quantum cryptography. In 2020 IEEE Computer Society Annual Symposium on VLSI (ISVLSI) . IEEE, 334-339.
Bhaskar Gaur Edgard Muñoz-Coreas Himanshu Thapliyal
A Logarithmic Depth Quantum Carry-Lookahead Modulo $(2^n-1)$ Adder
Quantum Computing is making significant advancements toward creating machines
capable of implementing quantum algorithms in various fields, such as quantum
cryptography, quantum image processing, and optimization. The development of
quantum arithmetic circuits for modulo addition is vital for implementing these
quantum algorithms. While it is ideal to use quantum circuits based on
fault-tolerant gates to overcome noise and decoherence errors, the current
Noisy Intermediate Scale Quantum (NISQ) era quantum computers cannot handle the
additional computational cost associated with fault-tolerant designs. Our
research aims to minimize circuit depth, which can reduce noise and facilitate
the implementation of quantum modulo addition circuits on NISQ machines. This
work presents quantum carry-lookahead modulo $(2^n - 1)$ adder (QCLMA), which
is designed to receive two n-bit numbers and perform their addition with an
O(log n) depth. Compared to existing work of O(n) depth, our proposed QCLMA
reduces the depth and helps increase the noise fidelity. In order to increase
error resilience, we also focus on creating a tree structure based Carry path,
unlike the chain based Carry path of the current work. We run experiments on
Quantum Computer IBM Cairo to evaluate the performance of the proposed QCLMA
against the existing work and define Quantum State Fidelity Ratio (QSFR) to
quantify the closeness of the correct output to the top output. When compared
against existing work, the proposed QCLMA achieves a 47.21% increase in QSFR
for 4-qubit modulo addition showcasing its superior noise fidelity.