arXiv:2603.12917

Asymptotically Optimal Quantum Circuits for Comparators and Incrementers

Vivien Vandaele

quant-phSubmitted Mar 13, 2026• Announced Mar 16, 2026• 0 citations

Abstract

We present quantum circuits for comparison and increment operations that achieve an asymptotically optimal gate count of $Θ(n)$ and depth of $Θ(\log n)$ over the Clifford+Toffoli gate set, while using a provably minimal number of qubits. We extend these results to classical-quantum comparators, yielding an improved classical-quantum adder with an optimal qubit count. Given the ubiquity of these operations as algorithmic building blocks, our constructions translate directly into reduced circuit complexity for many quantum algorithms. As a notable example, they can be used to improve a space-efficient circuit for Shor's factoring algorithm, reducing circuit depth from $\mathcal{O}(n^3)$ to $\mathcal{O}(n^2 \log^2 n)$ without increasing either the qubit count or the asymptotic gate complexity. Underpinning these results is a general theorem demonstrating how to trade ancilla qubits for control qubits with low overhead in both depth and gate count, providing a broadly applicable tool for quantum circuit design.

Related papers

Ancilla-free optimal quantum adder

Junhong Nie, Jialiang Tang, Xiaoming Sun +1 more

quant-pharXiv:2610.34446Oct 27, 20260 citations

Improved quantum circuits for division

Priyanka Mukhopadhyay, Alexandru Gheorghiu, Hari Krovi

quant-pharXiv:2603.18110Mar 19, 20260 citations

Fast quantum integer multiplication with zero ancillas

Gregory D. Kahanamoku–Meyer, Norman Y. Yao

arXiv:2403.18006Mar 26, 20242 citations

Asymptotic yet practical optimization of quantum circuits implementing GF($2^m$) multiplication and division operations

Noureldin Yosri, Dmytro Gavinsky, Dmitri Maslov

quant-pharXiv:2511.20618Nov 26, 20250 citations

Optimizing T and CNOT Gates in Quantum Ripple-Carry Adders and Comparators

Maxime Remaud

arXiv:2401.17921Jun 19, 20243 citations

Depth-optimized quantum circuit synthesis for diagonal unitary operators with asymptotically optimal gate count

Shihao Zhang, Kai Huang, Lvzhou Li

arXiv:2212.01002Physical Review AApr 1, 202412 citations

arXiv:2603.12917

Asymptotically Optimal Quantum Circuits for Comparators and Incrementers

Vivien Vandaele

quant-phSubmitted Mar 13, 2026• Announced Mar 16, 2026• 0 citations

arXiv HTML PDF

Abstract

We present quantum circuits for comparison and increment operations that achieve an asymptotically optimal gate count of

Θ(n)

and depth of

Θ(\log n)

over the Clifford+Toffoli gate set, while using a provably minimal number of qubits. We extend these results to classical-quantum comparators, yielding an improved classical-quantum adder with an optimal qubit count. Given the ubiquity of these operations as algorithmic building blocks, our constructions translate directly into reduced circuit complexity for many quantum algorithms. As a notable example, they can be used to improve a space-efficient circuit for Shor's factoring algorithm, reducing circuit depth from

\mathcal{O}(n^3)

\mathcal{O}(n^2 \log^2 n)

without increasing either the qubit count or the asymptotic gate complexity. Underpinning these results is a general theorem demonstrating how to trade ancilla qubits for control qubits with low overhead in both depth and gate count, providing a broadly applicable tool for quantum circuit design.

Related papers

Ancilla-free optimal quantum adder

Junhong Nie, Jialiang Tang, Xiaoming Sun +1 more

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

Improved quantum circuits for division

Priyanka Mukhopadhyay, Alexandru Gheorghiu, Hari Krovi

Arithmetic operations are an important component of many quantum algorithms. Optimizing quantum circuits for these operations therefore leads to more efficient implementations of the corresponding algorithms. In this paper, we develop new fault-tolerant quantum circuits for various integer division algorithms (both reversible and non-reversible). These circuits, when implemented in the Clifford+T gate set, achieve improvements in the asymptotic T-count and CNOT-count from $O(n^2)$ to $O(nm)$ , and in the asymptotic T-depth from $O(n^2)$ to $O(n \log m)$ , where $n$ and $m$ are the bit lengths of the dividend and divisor, respectively. The qubit counts are significantly lower than those in previous works. We achieve this through careful modifications of the division algorithms and by expressing them in terms of a primitive we call COMP-N-SUB that compares two integers and conditionally subtracts them. We show that this primitive can be implemented at a cost, in terms of both Clifford and non-Clifford gates, comparable to that of one addition. By contrast, performing comparison and conditional subtraction separately would cost roughly as much as a controlled addition plus a regular addition.Arithmetic operations are an important component of many quantum algorithms. Optimizing quantum circuits for these operations therefore leads to more efficient implementations of the corresponding algorithms. In this paper, we develop new fault-tolerant quantum circuits for various integer division algorithms (both reversible and non-reversible). These circuits, when implemented in the Clifford+T gate set, achieve improvements in the asymptotic T-count and CNOT-count from $O(n^2)$ to $O(nm)$, and in the asymptotic T-depth from $O(n^2)$ to $O(n \log m)$, where $n$ and $m$ are the bit lengths of the dividend and divisor, respectively. The qubit counts are significantly lower than those in previous works. We achieve this through careful modifications of the division algorithms and by expressing them in terms of a primitive we call COMP-N-SUB that compares two integers and conditionally subtracts them. We show that this primitive can be implemented at a cost, in terms of both Clifford and non-Clifford gates, comparable to that of one addition. By contrast, performing comparison and conditional subtraction separately would cost roughly as much as a controlled addition plus a regular addition.

quant-pharXiv:2603.18110Mar 19, 20260 citations

Fast quantum integer multiplication with zero ancillas

Gregory D. Kahanamoku–Meyer, Norman Y. Yao

The multiplication of superpositions of numbers is a core operation in many quantum algorithms. The standard method for multiplication (both classical and quantum) has a runtime quadratic in the size of the inputs. Quantum circuits with asymptotically fewer gates have been developed, but generally exhibit large overheads, especially in the number of ancilla qubits. In this work, we introduce a new paradigm for sub-quadratic-time quantum multiplication with zero ancilla qubits -- the only qubits involved are the input and output registers themselves. Our algorithm achieves an asymptotic gate count of $\mathcal{O}(n^{1+ε})$ for any $ε> 0$ ; with practical choices of parameters, we expect scalings as low as $\mathcal{O}(n^{1.3})$ . Used as a subroutine in Shor's algorithm, our technique immediately yields a factoring circuit with $\mathcal{O}(n^{2+ε})$ gates and only $2n + \mathcal{O}(\log n)$ qubits; to our knowledge, this is by far the best qubit count of any factoring circuit with a sub-cubic number of gates. Used in Regev's recent factoring algorithm, the gate count is $\mathcal{O}(n^{1.5+ε})$ . Finally, we demonstrate that our algorithm has the potential to outperform previous proposals at problem sizes relevant in practice, including yielding the smallest circuits we know of for classically-verifiable quantum advantage.The multiplication of superpositions of numbers is a core operation in many quantum algorithms. The standard method for multiplication (both classical and quantum) has a runtime quadratic in the size of the inputs. Quantum circuits with asymptotically fewer gates have been developed, but generally exhibit large overheads, especially in the number of ancilla qubits. In this work, we introduce a new paradigm for sub-quadratic-time quantum multiplication with zero ancilla qubits -- the only qubits involved are the input and output registers themselves. Our algorithm achieves an asymptotic gate count of $\mathcal{O}(n^{1+ε})$ for any $ε> 0$; with practical choices of parameters, we expect scalings as low as $\mathcal{O}(n^{1.3})$. Used as a subroutine in Shor's algorithm, our technique immediately yields a factoring circuit with $\mathcal{O}(n^{2+ε})$ gates and only $2n + \mathcal{O}(\log n)$ qubits; to our knowledge, this is by far the best qubit count of any factoring circuit with a sub-cubic number of gates. Used in Regev's recent factoring algorithm, the gate count is $\mathcal{O}(n^{1.5+ε})$. Finally, we demonstrate that our algorithm has the potential to outperform previous proposals at problem sizes relevant in practice, including yielding the smallest circuits we know of for classically-verifiable quantum advantage.

arXiv:2403.18006Mar 26, 20242 citations

Asymptotic yet practical optimization of quantum circuits implementing GF( $2^m$ ) multiplication and division operationsAsymptotic yet practical optimization of quantum circuits implementing GF($2^m$) multiplication and division operations

Noureldin Yosri, Dmytro Gavinsky, Dmitri Maslov

We present optimized quantum circuits for GF $(2^m)$ multiplication and division operations, which are essential computing primitives in various quantum algorithms. Our ancilla-free GF multiplication circuit has the gate count complexity of $O(m^{\log_2{3}})$ , an improvement over the previous best bound of $O(m^2)$ . This was achieved by developing an efficient $O(m)$ circuit for multiplication by the constant polynomial $1+x^{\lceil{m/2}\rceil}$ , a key component of Van Hoof's construction. This asymptotic reduction translates to a factor of 100+ improvement of the CNOT gate counts in the implementation of the multiplication by the constant for parameters $m$ of practical importance. For the GF division, we reduce gate count complexity from $O(m^2 \log(m))$ to $O(m^2 \log \log(m)/\log(m))$ by selecting irreducible polynomials that enable efficient implementation of both the constant polynomial multiplication and field squaring operations. We demonstrate practical advantages for cryptographically relevant values of $m$ , including reductions in both CNOT and Toffoli gate counts. Additionally, we explore the complexity of implementing square roots of linear reversible unitaries and demonstrate that a root, although itself still a linear reversible transformation, can require asymptotically deeper circuit implementations than the original unitary.We present optimized quantum circuits for GF$(2^m)$ multiplication and division operations, which are essential computing primitives in various quantum algorithms. Our ancilla-free GF multiplication circuit has the gate count complexity of $O(m^{\log_2{3}})$, an improvement over the previous best bound of $O(m^2)$. This was achieved by developing an efficient $O(m)$ circuit for multiplication by the constant polynomial $1+x^{\lceil{m/2}\rceil}$, a key component of Van Hoof's construction. This asymptotic reduction translates to a factor of 100+ improvement of the CNOT gate counts in the implementation of the multiplication by the constant for parameters $m$ of practical importance. For the GF division, we reduce gate count complexity from $O(m^2 \log(m))$ to $O(m^2 \log \log(m)/\log(m))$ by selecting irreducible polynomials that enable efficient implementation of both the constant polynomial multiplication and field squaring operations. We demonstrate practical advantages for cryptographically relevant values of $m$, including reductions in both CNOT and Toffoli gate counts. Additionally, we explore the complexity of implementing square roots of linear reversible unitaries and demonstrate that a root, although itself still a linear reversible transformation, can require asymptotically deeper circuit implementations than the original unitary.

quant-pharXiv:2511.20618Nov 26, 20250 citations

Optimizing T and CNOT Gates in Quantum Ripple-Carry Adders and Comparators

Maxime Remaud

The state of the art of quantum circuits using the ripple-carry strategy for the addition and comparison of two n-bit numbers is presented, as well as optimizations in the Clifford+ <?TeX $\mathsf {T}$ ?> Math 1 gate set, both in terms of <?TeX $\mathsf {CNOT}$ ?> Math 2 -depth and <?TeX $\mathsf {T}$ ?> Math 3 -depth, or <?TeX $\mathsf {CNOT}$ ?> Math 4 -count and <?TeX $\mathsf {T}$ ?> Math 5 -count. In particular, we consider the adders presented by Cuccaro et al. and Takahashi et al., and exhibit an adder with a <?TeX $\mathsf {T}$ ?> Math 6 -depth of 3n and a <?TeX $\mathsf {CNOT}$ ?> Math 7 -depth of 8n, while without optimization of the original circuits, a <?TeX $\mathsf {T}$ ?> Math 8 -depth of 6n is expected. Note that we have focused here on quantum ripple-carry adders using at most one ancilla, without any approximation of the 3-qubit gates involved (Toffoli, Peres and TR) or any strategy involving a measurement.The state of the art of quantum circuits using the ripple-carry strategy for the addition and comparison of two n-bit numbers is presented, as well as optimizations in the Clifford+ <?TeX $\mathsf {T}$?> Math 1 gate set, both in terms of <?TeX $\mathsf {CNOT}$?> Math 2 -depth and <?TeX $\mathsf {T}$?> Math 3 -depth, or <?TeX $\mathsf {CNOT}$?> Math 4 -count and <?TeX $\mathsf {T}$?> Math 5 -count. In particular, we consider the adders presented by Cuccaro et al. and Takahashi et al., and exhibit an adder with a <?TeX $\mathsf {T}$?> Math 6 -depth of 3n and a <?TeX $\mathsf {CNOT}$?> Math 7 -depth of 8n, while without optimization of the original circuits, a <?TeX $\mathsf {T}$?> Math 8 -depth of 6n is expected. Note that we have focused here on quantum ripple-carry adders using at most one ancilla, without any approximation of the 3-qubit gates involved (Toffoli, Peres and TR) or any strategy involving a measurement.

arXiv:2401.17921Jun 19, 20243 citations

Depth-optimized quantum circuit synthesis for diagonal unitary operators with asymptotically optimal gate count

Shihao Zhang, Kai Huang, Lvzhou Li

Diagonal unitary operators are well known to be key building blocks of many quantum algorithms and quantum computing procedures, and thus resource-efficient quantum circuit implementations are in demand. Here we propose a constructive algorithm that can generate a quantum circuit over the primitive gate set {cnot, ${R}_{Z}$ } for realizing any given diagonal unitary operator piece by piece. The theoretical analysis reveals that, for the general case, our generated circuit not only ensures the asymptotically optimal gate count, but also nearly halves the circuit depth compared with the previous Welch's method [New J. Phys. 16, 033040 (2014)]. Specifically, this substantial depth optimization originates from the use of a uniform circuit rewriting rule developed here. The performance of our circuit synthesis algorithm is further validated by numerical evaluations on two examples. First, we achieve a nearly 50% depth reduction over Welch's method for synthesizing random diagonal unitary operators with up to 16 qubits. Second, we achieve an average of 22.05% depth reduction for resynthesizing the diagonal part of the specific quantum approximate optimization algorithm (QAOA) circuits with up to 14 qubits.Diagonal unitary operators are well known to be key building blocks of many quantum algorithms and quantum computing procedures, and thus resource-efficient quantum circuit implementations are in demand. Here we propose a constructive algorithm that can generate a quantum circuit over the primitive gate set {cnot, ${R}_{Z}$} for realizing any given diagonal unitary operator piece by piece. The theoretical analysis reveals that, for the general case, our generated circuit not only ensures the asymptotically optimal gate count, but also nearly halves the circuit depth compared with the previous Welch's method [New J. Phys. 16, 033040 (2014)]. Specifically, this substantial depth optimization originates from the use of a uniform circuit rewriting rule developed here. The performance of our circuit synthesis algorithm is further validated by numerical evaluations on two examples. First, we achieve a nearly 50% depth reduction over Welch's method for synthesizing random diagonal unitary operators with up to 16 qubits. Second, we achieve an average of 22.05% depth reduction for resynthesizing the diagonal part of the specific quantum approximate optimization algorithm (QAOA) circuits with up to 14 qubits.

arXiv:2212.01002Physical Review AApr 1, 202412 citations

We present quantum circuits for comparison and increment operations that achieve an asymptotically optimal gate count of

Θ(n)

and depth of

Θ(\log n)

\mathcal{O}(n^3)

\mathcal{O}(n^2 \log^2 n)

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.

O(n^2)

O(nm)

, and in the asymptotic T-depth from

O(n^2)

O(n \log m)

, where

n

and

m

are the bit lengths of the dividend and divisor, respectively. The qubit counts are significantly lower than those in previous works. We achieve this through careful modifications of the division algorithms and by expressing them in terms of a primitive we call COMP-N-SUB that compares two integers and conditionally subtracts them. We show that this primitive can be implemented at a cost, in terms of both Clifford and non-Clifford gates, comparable to that of one addition. By contrast, performing comparison and conditional subtraction separately would cost roughly as much as a controlled addition plus a regular addition.

\mathcal{O}(n^{1+ε})

for any

ε> 0

; with practical choices of parameters, we expect scalings as low as

\mathcal{O}(n^{1.3})

. Used as a subroutine in Shor's algorithm, our technique immediately yields a factoring circuit with

\mathcal{O}(n^{2+ε})

gates and only

2n + \mathcal{O}(\log n)

qubits; to our knowledge, this is by far the best qubit count of any factoring circuit with a sub-cubic number of gates. Used in Regev's recent factoring algorithm, the gate count is

\mathcal{O}(n^{1.5+ε})

. Finally, we demonstrate that our algorithm has the potential to outperform previous proposals at problem sizes relevant in practice, including yielding the smallest circuits we know of for classically-verifiable quantum advantage.

Asymptotic yet practical optimization of quantum circuits implementing GF(

2^m

) multiplication and division operations

We present optimized quantum circuits for GF

(2^m)

multiplication and division operations, which are essential computing primitives in various quantum algorithms. Our ancilla-free GF multiplication circuit has the gate count complexity of

O(m^{\log_2{3}})

, an improvement over the previous best bound of

O(m^2)

. This was achieved by developing an efficient

O(m)

circuit for multiplication by the constant polynomial

1+x^{\lceil{m/2}\rceil}

, a key component of Van Hoof's construction. This asymptotic reduction translates to a factor of 100+ improvement of the CNOT gate counts in the implementation of the multiplication by the constant for parameters

m

of practical importance. For the GF division, we reduce gate count complexity from

O(m^2 \log(m))

O(m^2 \log \log(m)/\log(m))

by selecting irreducible polynomials that enable efficient implementation of both the constant polynomial multiplication and field squaring operations. We demonstrate practical advantages for cryptographically relevant values of

m

, including reductions in both CNOT and Toffoli gate counts. Additionally, we explore the complexity of implementing square roots of linear reversible unitaries and demonstrate that a root, although itself still a linear reversible transformation, can require asymptotically deeper circuit implementations than the original unitary.

The state of the art of quantum circuits using the ripple-carry strategy for the addition and comparison of two n-bit numbers is presented, as well as optimizations in the Clifford+ <?TeX

\mathsf {T}

?> Math 1 gate set, both in terms of <?TeX

\mathsf {CNOT}

?> Math 2 -depth and <?TeX

\mathsf {T}

?> Math 3 -depth, or <?TeX

\mathsf {CNOT}

?> Math 4 -count and <?TeX

\mathsf {T}

?> Math 5 -count. In particular, we consider the adders presented by Cuccaro et al. and Takahashi et al., and exhibit an adder with a <?TeX

\mathsf {T}

?> Math 6 -depth of 3n and a <?TeX

\mathsf {CNOT}

?> Math 7 -depth of 8n, while without optimization of the original circuits, a <?TeX

\mathsf {T}

?> Math 8 -depth of 6n is expected. Note that we have focused here on quantum ripple-carry adders using at most one ancilla, without any approximation of the 3-qubit gates involved (Toffoli, Peres and TR) or any strategy involving a measurement.

{R}_{Z}

} for realizing any given diagonal unitary operator piece by piece. The theoretical analysis reveals that, for the general case, our generated circuit not only ensures the asymptotically optimal gate count, but also nearly halves the circuit depth compared with the previous Welch's method [New J. Phys. 16, 033040 (2014)]. Specifically, this substantial depth optimization originates from the use of a uniform circuit rewriting rule developed here. The performance of our circuit synthesis algorithm is further validated by numerical evaluations on two examples. First, we achieve a nearly 50% depth reduction over Welch's method for synthesizing random diagonal unitary operators with up to 16 qubits. Second, we achieve an average of 22.05% depth reduction for resynthesizing the diagonal part of the specific quantum approximate optimization algorithm (QAOA) circuits with up to 14 qubits.