A new quantum ripple-carry addition circuit

1 Introduction

• The new adder uses one ancilla, with 2n + O(1) Toffoli gates, 5n + O(1) CNOT gates, 2n + O(1) negations, and depth 2n + O(1).The VBE adder uses n − O(1) ancillae, 4n + O(1) CNOT gates, and 4n + O(1) Toffoli gates with little parallelism.Source: §1 · p. 1
• The construction's key ingredient is an in-place circuit that computes the majority of three bits.The paper presents a simple adder and then an optimized version built around this ingredient.Source: §1 · p. 1
• The design includes variants for addition modulo 2n, incoming carry, and computing only the high sum bit, with the last variant adaptable to comparison.Their complexities are summarized in Table 1.Source: §1 · p. 1

2 The basic idea

• Carries are defined recursively by c0 = 0 and ci+1 = MAJ(ai, bi, ci), while si = ai ⊕ bi ⊕ ci and sn = cn.Reversibility requires computing carries upward and then erasing them while working downward.Source: §2 · p. 2
• The in-place majority gate applies two CNOTs followed by one Toffoli to compute the majority of three bits.It is the first component of the adder.Source: §2 · p. 2, Figure 1
• The UMA gate restores ai and ci while writing si to Bi after the carry has been used.Two UMA implementations compute the same function, but the second permits greater parallelism.Source: §2 · p. 2, Figure 2
• The MAJ and UMA gates can be chained into a ripple-carry adder using one ancilla X initialized to 0 and an output Z that accumulates the high sum bit.The simple construction is illustrated for n = 6.Source: §2 · p. 2, Figure 3 · p. 3, Figure 4 · p. 3

3 Improving the circuit

• The optimized circuit parallelizes initial and final CNOT layers and reorders neighboring Toffoli and CNOT gates to reduce depth.These transformations apply symmetrically to the MAJ and UMA halves of the ripple circuit.Source: §3 · p. 3
• Because c0 = 0, the circuit computes c1 directly with one Toffoli, later reverses it, and writes B0 to s0 with one CNOT.This removes the need for a MAJ gate at the low-order boundary.Source: §3 · p. 3
• Figures 5 and 6 present the optimized ripple-carry circuit as pseudocode for n ≥4 and as a sample circuit for n = 6.Each pseudocode line in Figure 5 represents one time-slice.Source: Figure 5 · p. 4, Figure 6 · p. 4, §3 · p. 5
• The final construction replaces an intermediate carry-copy-and-erase sequence with one Toffoli and two CNOTs, including one parallelizable CNOT.The pseudocode is valid for n ≥4, while the construction itself applies for any n.Source: §3 · p. 5
• 2n + 4 depth with 2n −1 Toffoli gates, 5n −3 CNOTs, and 2n −4 negations for n ≥2.The depth comprises 2n −1 Toffoli time-slices and 5 CNOT time-slices.Source: §3 · p. 5

4 Extensions

• The extensions are simple modifications of the Section 3 circuit, with Table 1 reporting inputs, outputs, ancillae, gate counts, and overall depth while excluding negations from size and depth.The high-bit-only circuit can be adapted into a comparator by computing the high bit of a −b, which equals 1 exactly when a < b.Source: §4 · p. 5, Table 1 · p. 6, §4.3 · p. 7

4.1 Addition Modulo 2n

• For n ≥3, addition modulo 2n omits the high bit and uses 2n −3 Toffolis, 5n −7 CNOTs, 2n −6 negations, and depth 2n + 2.The low-order n −1 bits are added first, and the final output-bit operation can run in parallel with the last time-slice of that step.Source: §4.1 · p. 5

4.2 Addition with Incoming Carry

• For n ≥2, the ripple-carry adder with incoming carry uses 2n −1 Toffolis, 5n+1 CNOTs, 2n−2 negations, and depth 2n+6.The fourth improvement cannot be used because the incoming bit is not assumed zero, while the other improvements still apply.Source: §4.2 · p. 6

4.3 High Bit Only

• For n ≥2, the high-bit-only circuit uses 2n −1 Toffoli gates, 4n −3 CNOTs, and depth 2n + 3.Combining it with incoming carry gives 2n −1 Toffolis, 4n + 1 CNOTs, and depth 2n + 5.Source: §4.3 · pp. 6–7

• The paper leaves open whether one-ancilla reversible addition must have linear depth and whether constant-ancilla logarithmic-depth addition is possible.A logarithmic-depth adder is known using 2n ancillae, and depth O(k + log n) is available with n/k ancillae.Source: §5 · p. 7
• A no-ancilla ripple-carry variant exists when the output bit starts at zero, but removing that initialization restriction remains unresolved.Source: §5 · p. 7
• Compared with the transform adder, both designs have linear depth, but practical implementation depends on the relative costs of Toffoli gates and controlled rotations.Source: §5 · p. 7
• 6n −2 controlled-unary depth results from overlapping Toffoli decompositions, rather than the expected 10n + O(1) depth.The comparison is based on implementing each Toffoli with five controlled rotations.Source: §5 · p. 7
• For classical-to-quantum addition, the ripple-carry adder still requires n quantum bits for the classical addend, while the transform adder seems superior.Source: §5 · p. 7