Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2603.18110

Improved quantum circuits for division

Priyanka Mukhopadhyay, Alexandru Gheorghiu, Hari Krovi

quant-phSubmitted Mar 18, 2026• Announced Mar 19, 2026• 0 citations• Revised Sep 3, 2026 (v2)
v1 · Mar 18, 2026v2 · Sep 3, 2026
arXivHTMLPDF

Abstract

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.

Comments
Improvement in asymptotic gate count and depth, application of COMP-N-SUB to GCD

Related papers

Designs of the divider and special multiplier optimizing T and CNOT gates

Ping Fan, Hai-Sheng Li

Abstract Quantum circuits for multiplication and division are necessary for scientific computing on quantum computers. Clifford + T circuits are widely used in fault-tolerant realizations. T gates are more expensive than other gates in Clifford + T circuits. But neglecting the cost of CNOT gates may lead to a significant underestimation. Moreover, the small number of qubits available in existing quantum devices is another constraint on quantum circuits. As a result, reducing T-count, T-depth, CNOT-count, CNOT-depth, and circuit width has become the important optimization goal. We use 3-bit Hermitian gates to design basic arithmetic operations. Then, we present a special multiplier and a divider using basic arithmetic operations, where 'special' means that one of the two operands of multiplication is non-zero. Next, we use new rules to optimize the Clifford + T circuits of the special multiplier and divider in terms of T-count, T-depth, CNOT-count, CNOT-depth, and circuit width. Comparative analysis shows that the proposed multiplier and divider have lower T-count, T-depth, CNOT-count, and CNOT-depth than the current works. For instance, the proposed 32-bit divider achieves improvement ratios of 40.41 percent, 31.64 percent, 45.27 percent, and 65.93 percent in terms of T-count, T-depth, CNOT-count, and CNOT-depth compared to the best current work. Further, the circuit widths of the proposed $n$-bit multiplier and divider are $3n$. I.e., our multiplier and divider reach the minimum width of multipliers and dividers, keeping an operand unchanged.

EPJ Quantum Technology•Feb 23, 2024•3 citations

The integer multiplier with two unchanged operands reducing T and CNOT gates

Ping Fan, Hai-Sheng Li

Quantum circuits for multiplication are necessary for scientific computing on quantum computers. Clifford + T circuits are widely used in fault-tolerant implementations. The costs of implementing T and double-qubit gates are higher than those of other one-qubit gates in the Clifford + T group. In addition, the small number of qubits available in existing quantum devices is another constraint on quantum circuits. Therefore, we reduce T and CNOT gates and circuit width as the primary optimization goal in this paper. We propose an algorithm for multiplication with two unchanged operands. Preserving both operands of the multiplication is important for realizing some quantum algorithms, such as quantum bilinear interpolation. Using this algorithm, we design the circuit of the integer multiplier with two unchanged operands reducing CNOT gates. Next, we develop a Clifford + T circuit for the multiplier and introduce new optimization rules to reduce T gates. Comparative analysis shows that the proposed multiplier achieves the best width among existing multipliers. Compared to multipliers with two unchanged operands that use at most one ancillary qubit, our proposed multiplier has the best T-count, T-depth, and CNOT-count.

EPJ Quantum Technology•Apr 29, 2025•2 citations

Asymptotic 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.

quant-pharXiv:2511.20618•Nov 26, 2025•0 citations

Improving the number of T gates and their spread in integer multipliers on quantum computing

Francisco José Orts, Ernestas Filatovas, Gloria Ortega +2 more

Quantum circuits performing arithmetic operations are critical in quantum computing because of the need for such operations in proven quantum algorithms. Although quantum computers are becoming increasingly resourceful, the number of qubits currently available is still limited. Furthermore, these qubits are heavily affected by internal and external noise. It has been proven that quantum circuits built using Clifford $+T$ gates can be made fault tolerant. However, the use of the $T$ gates comes at a very high cost. If the number of $T$ gates used in a circuit is not optimized, the cost of the circuit will be increased excessively. As a consequence, it is essential to optimize the circuits so that they are as resource efficient as possible and also noise tolerant. This paper presents the design of a circuit to perform the multiplication of two integers. The circuit is built using only Clifford $+T$ gates for compatibility with error detection and correction codes. It outperforms the circuits in the state of the art in terms of $T$ count and $T$ depth.

Physical Review A•Apr 27, 2023•15 citations

Asymptotically Optimal Quantum Circuits for Comparators and Incrementers

Vivien Vandaele

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.

quant-pharXiv:2603.12917•Mar 16, 2026•0 citations

A New Quantum Efficient Fault Tolerant Parity Preserving Clifford + T ALU

Shekoofeh Moghimi, Mohammad Reza Reshadinezhad, Antonio Rubio

Reversible logic is characterized by its feature of being a prominent application in low-power conventional computers and the most compatible logic in quantum computers. Quantum circuits executes quantum algorithms and are important in a new generation of advanced computing. However, they are highly error-prone and also subject to the use of limited and sensitive physical resources like qubits and quantum gates. This paper introduces a comprehensive fault tolerant quantum-based reversible circuit which can calculate a high variety number of arithmetic and logic operations. It uses both: parity preserving method for detecting one or an odd number of bit errors, and Clifford + T implementation for protecting circuits against decoherence faults. First, we propose a new fault-tolerant (parity preserving and Clifford + T) adder/subtractor and derive a quantum reversible Arithmetic and Logic Unit (ALU). These modules reach the most optimized extent of circuit line, ancilla inputs, and garbage outputs according to the logical analysis done in this work. This article focuses on reducing T-cost metrics in conjunction with enhancing the number of operations and quantum costs in proposed circuits compared to other counterparts. We propose 4-bit fault tolerant ALU derived from our proposed single-bit module to show the proposed circuit can be extended to any larger size. The proposed circuit is implemented in the Qiskit simulation tool, and output results confirm the accuracy of our design functionality. The proposed full adder/ subtractor achieves an average of 64% and 43%, and the proposed ALU circuit achieves an average of 38% and 27% improvement in T-count and T-depth, respectively compared to their counterparts. The proposed reversible quantum-optimized fault tolerant adder/subtractor and ALU units can be applied as the basic part of DSP systems and quantum processor units in quantum computing devices.

IEEE Transactions on Emerging Topics in Computing•Apr 1, 2026•0 citations
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(n2)O(n^2)O(n2) to O(nm)O(nm)O(nm), and in the asymptotic T-depth from O(n2)O(n^2)O(n2) to O(nlog⁡m)O(n \log m)O(nlogm), where nnn and mmm 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.
Abstract Quantum circuits for multiplication and division are necessary for scientific computing on quantum computers. Clifford + T circuits are widely used in fault-tolerant realizations. T gates are more expensive than other gates in Clifford + T circuits. But neglecting the cost of CNOT gates may lead to a significant underestimation. Moreover, the small number of qubits available in existing quantum devices is another constraint on quantum circuits. As a result, reducing T-count, T-depth, CNOT-count, CNOT-depth, and circuit width has become the important optimization goal. We use 3-bit Hermitian gates to design basic arithmetic operations. Then, we present a special multiplier and a divider using basic arithmetic operations, where 'special' means that one of the two operands of multiplication is non-zero. Next, we use new rules to optimize the Clifford + T circuits of the special multiplier and divider in terms of T-count, T-depth, CNOT-count, CNOT-depth, and circuit width. Comparative analysis shows that the proposed multiplier and divider have lower T-count, T-depth, CNOT-count, and CNOT-depth than the current works. For instance, the proposed 32-bit divider achieves improvement ratios of 40.41 percent, 31.64 percent, 45.27 percent, and 65.93 percent in terms of T-count, T-depth, CNOT-count, and CNOT-depth compared to the best current work. Further, the circuit widths of the proposed nnn-bit multiplier and divider are 3n3n3n. I.e., our multiplier and divider reach the minimum width of multipliers and dividers, keeping an operand unchanged.
Quantum circuits for multiplication are necessary for scientific computing on quantum computers. Clifford + T circuits are widely used in fault-tolerant implementations. The costs of implementing T and double-qubit gates are higher than those of other one-qubit gates in the Clifford + T group. In addition, the small number of qubits available in existing quantum devices is another constraint on quantum circuits. Therefore, we reduce T and CNOT gates and circuit width as the primary optimization goal in this paper. We propose an algorithm for multiplication with two unchanged operands. Preserving both operands of the multiplication is important for realizing some quantum algorithms, such as quantum bilinear interpolation. Using this algorithm, we design the circuit of the integer multiplier with two unchanged operands reducing CNOT gates. Next, we develop a Clifford + T circuit for the multiplier and introduce new optimization rules to reduce T gates. Comparative analysis shows that the proposed multiplier achieves the best width among existing multipliers. Compared to multipliers with two unchanged operands that use at most one ancillary qubit, our proposed multiplier has the best T-count, T-depth, and CNOT-count.
Asymptotic yet practical optimization of quantum circuits implementing GF(2m2^m2m) multiplication and division operations
We present optimized quantum circuits for GF(2m)(2^m)(2m) 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(mlog⁡23)O(m^{\log_2{3}})O(mlog2​3), an improvement over the previous best bound of O(m2)O(m^2)O(m2). This was achieved by developing an efficient O(m)O(m)O(m) circuit for multiplication by the constant polynomial 1+x⌈m/2⌉1+x^{\lceil{m/2}\rceil}1+x⌈m/2⌉, 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 mmm of practical importance. For the GF division, we reduce gate count complexity from O(m2log⁡(m))O(m^2 \log(m))O(m2log(m)) to O(m2log⁡log⁡(m)/log⁡(m))O(m^2 \log \log(m)/\log(m))O(m2loglog(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 mmm, 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.
Quantum circuits performing arithmetic operations are critical in quantum computing because of the need for such operations in proven quantum algorithms. Although quantum computers are becoming increasingly resourceful, the number of qubits currently available is still limited. Furthermore, these qubits are heavily affected by internal and external noise. It has been proven that quantum circuits built using Clifford +T+T+T gates can be made fault tolerant. However, the use of the TTT gates comes at a very high cost. If the number of TTT gates used in a circuit is not optimized, the cost of the circuit will be increased excessively. As a consequence, it is essential to optimize the circuits so that they are as resource efficient as possible and also noise tolerant. This paper presents the design of a circuit to perform the multiplication of two integers. The circuit is built using only Clifford +T+T+T gates for compatibility with error detection and correction codes. It outperforms the circuits in the state of the art in terms of TTT count and TTT depth.
We present quantum circuits for comparison and increment operations that achieve an asymptotically optimal gate count of Θ(n)Θ(n)Θ(n) and depth of Θ(log⁡n)Θ(\log n)Θ(logn) 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 O(n3)\mathcal{O}(n^3)O(n3) to O(n2log⁡2n)\mathcal{O}(n^2 \log^2 n)O(n2log2n) 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.
Reversible logic is characterized by its feature of being a prominent application in low-power conventional computers and the most compatible logic in quantum computers. Quantum circuits executes quantum algorithms and are important in a new generation of advanced computing. However, they are highly error-prone and also subject to the use of limited and sensitive physical resources like qubits and quantum gates. This paper introduces a comprehensive fault tolerant quantum-based reversible circuit which can calculate a high variety number of arithmetic and logic operations. It uses both: parity preserving method for detecting one or an odd number of bit errors, and Clifford + T implementation for protecting circuits against decoherence faults. First, we propose a new fault-tolerant (parity preserving and Clifford + T) adder/subtractor and derive a quantum reversible Arithmetic and Logic Unit (ALU). These modules reach the most optimized extent of circuit line, ancilla inputs, and garbage outputs according to the logical analysis done in this work. This article focuses on reducing T-cost metrics in conjunction with enhancing the number of operations and quantum costs in proposed circuits compared to other counterparts. We propose 4-bit fault tolerant ALU derived from our proposed single-bit module to show the proposed circuit can be extended to any larger size. The proposed circuit is implemented in the Qiskit simulation tool, and output results confirm the accuracy of our design functionality. The proposed full adder/ subtractor achieves an average of 64% and 43%, and the proposed ALU circuit achieves an average of 38% and 27% improvement in T-count and T-depth, respectively compared to their counterparts. The proposed reversible quantum-optimized fault tolerant adder/subtractor and ALU units can be applied as the basic part of DSP systems and quantum processor units in quantum computing devices.