We construct an exact $n$ -bit quantum adder with $O(n)$ gates and $O(\log n)$ depth that requires no ancillary qubits. The circuit uses only $X$ , CNOT, and Toffoli gates under all-to-all connectivity and is classically reversible. Our construction accelerates the controlled ladder underlying addition. Grouping the data into blocks and use existing control qubits as conditional workspace gives a recursive construction with $O(n\log\log n)$ gates and $O(\log n)$ depth. We then coordinate inter-block propagation via two short-path forest operations to cut the per-block workspace requirement, yielding a nonrecursive implementation with $O(n)$ gates. Both the gate count and circuit depth are asymptotically optimal.We construct an exact $n$-bit quantum adder with $O(n)$ gates and $O(\log n)$ depth that requires no ancillary qubits. The circuit uses only $X$, CNOT, and Toffoli gates under all-to-all connectivity and is classically reversible. Our construction accelerates the controlled ladder underlying addition. Grouping the data into blocks and use existing control qubits as conditional workspace gives a recursive construction with $O(n\log\log n)$ gates and $O(\log n)$ depth. We then coordinate inter-block propagation via two short-path forest operations to cut the per-block workspace requirement, yielding a nonrecursive implementation with $O(n)$ gates. Both the gate count and circuit depth are asymptotically optimal.

quant-pharXiv:2610.34446Oct 27, 20260 citations

Ancilla-Free Quantum Adder with Sublinear Depth

Maxime Remaud, Vivien Vandaele

arXiv:2501.16802Lecture notes in computer scienceJan 1, 20256 citations

A Logarithmic-Depth Quantum Multiplier

Fred Sun, Anton Borissov

We present a quantum algorithm for multiplying two $n$ -bit integers with overall circuit depth and $T$ -depth both bounded by $O(\log n)$ , while using $O(n^2)$ gates and ancillary qubits. Our construction generates partial products via indicator-controlled copying and adds them using a tree of reversible $3$ -to- $2$ adders followed by one quantum carry-lookahead adder. Building on the carry-save adders of Kim et al., we combine full input fanout, workspace reuse, and phase-corrected gate implementations to reduce $T$ -depth. We provide explicit circuit constructions, proofs of correctness, and concrete closed-form resource bounds.We present a quantum algorithm for multiplying two $n$-bit integers with overall circuit depth and $T$-depth both bounded by $O(\log n)$, while using $O(n^2)$ gates and ancillary qubits. Our construction generates partial products via indicator-controlled copying and adds them using a tree of reversible $3$-to-$2$ adders followed by one quantum carry-lookahead adder. Building on the carry-save adders of Kim et al., we combine full input fanout, workspace reuse, and phase-corrected gate implementations to reduce $T$-depth. We provide explicit circuit constructions, proofs of correctness, and concrete closed-form resource bounds.

quant-pharXiv:2604.09847Apr 14, 20260 citations

Quantum adder circuits

Hafiz Md. Hasan Babu

Institute of Physics eBooksMay 1, 20200 citations

The PPKN Gate: An Optimal 1-Toffoli Input-Preserving Full Adder for Quantum Arithmetic

G. Papakonstantinou

Efficient arithmetic operations are a prerequisite for practical quantum computing. Optimization efforts focus on two primary metrics: Quantum Cost (QC), determined by the number of non-linear gates, and Logical Depth, which defines the execution speed. Existing literature identifies the HNG gate as the standard for Input-Preserving Reversible Full Adders. HNG gate typically requires a QC of 12 and a logical depth of 5, in the area of classical reversible circuits. This paper proposes the PPKN Gate, a novel design that achieves the same inputpreserving functionality using only one Toffoli gate and five CNOT gates. With a Quantum Cost of 10 and a reduced logical depth of 4, the PPKN gate outperforms the standard HNG gate in both complexity and speed. Furthermore, we present a modular architecture for constructing an n-bit Ripple Carry Adder by cascading PPKN modules.Efficient arithmetic operations are a prerequisite for practical quantum computing. Optimization efforts focus on two primary metrics: Quantum Cost (QC), determined by the number of non-linear gates, and Logical Depth, which defines the execution speed. Existing literature identifies the HNG gate as the standard for Input-Preserving Reversible Full Adders. HNG gate typically requires a QC of 12 and a logical depth of 5, in the area of classical reversible circuits. This paper proposes the PPKN Gate, a novel design that achieves the same inputpreserving functionality using only one Toffoli gate and five CNOT gates. With a Quantum Cost of 10 and a reduced logical depth of 4, the PPKN gate outperforms the standard HNG gate in both complexity and speed. Furthermore, we present a modular architecture for constructing an n-bit Ripple Carry Adder by cascading PPKN modules.

quant-pharXiv:2512.12073Dec 16, 20250 citations

We construct an exact

n

-bit quantum adder with

O(n)

gates and

O(\log n)

depth that requires no ancillary qubits. The circuit uses only

X

, CNOT, and Toffoli gates under all-to-all connectivity and is classically reversible. Our construction accelerates the controlled ladder underlying addition. Grouping the data into blocks and use existing control qubits as conditional workspace gives a recursive construction with

O(n\log\log n)

gates and

O(\log n)

depth. We then coordinate inter-block propagation via two short-path forest operations to cut the per-block workspace requirement, yielding a nonrecursive implementation with

O(n)

gates. Both the gate count and circuit depth are asymptotically optimal.

We present a quantum algorithm for multiplying two

n

-bit integers with overall circuit depth and

T

-depth both bounded by

O(\log n)

, while using

O(n^2)

gates and ancillary qubits. Our construction generates partial products via indicator-controlled copying and adds them using a tree of reversible

3

-to-

2

adders followed by one quantum carry-lookahead adder. Building on the carry-save adders of Kim et al., we combine full input fanout, workspace reuse, and phase-corrected gate implementations to reduce

T

-depth. We provide explicit circuit constructions, proofs of correctness, and concrete closed-form resource bounds.