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• 1 citation• 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

Quantum Circuit Designs of Integer Division Optimizing T-Count and T-Depth

Himanshu Thapliyal, T. S. S. Varun, Edgard Muñoz‐Coreas +2 more

Quantum circuits for mathematical functions such as division are necessary to use quantum computers for scientific computing. Quantum circuits based on Clifford+T gates can easily be made fault-tolerant but the T gate is very costly to implement. The small number of qubits available in existing quantum computers adds another constraint on quantum circuits. As a result, reducing T-count and qubit cost have become important optimization goals. The design of quantum circuits for integer division has caught the attention of researchers and designs have been proposed in the literature. However, these designs suffer from excessive T gate and qubit costs. Many of these designs also produce significant garbage output resulting in additional qubit and T gate costs to eliminate these outputs. In this work, we propose two quantum integer division circuits. The first proposed quantum integer division circuit is based on the restoring division algorithm and the second proposed design implements the non-restoring division algorithm. Both proposed designs are optimized in terms of T-count, T-depth and qubits. Both proposed quantum circuit designs are based on (i) a quantum subtractor, (ii) a quantum adder-subtractor circuit, and (iii) a novel quantum conditional addition circuit. Our proposed restoring division circuit achieves average T-count savings from 79.03 to 91.69 percent compared to the existing works. Our proposed non-restoring division circuit achieves average T-count savings from 49.22 to 90.03 percent compared to the existing works. Further, both our proposed designs have linear T-depth. We also illustrate the application of the proposed quantum division circuits in quantum image processing with a case study of quantum bilinear interpolation.

arXiv:1809.09732•IEEE Transactions on Emerging Topics in Computing•Dec 1, 2017•87 citations

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 3 n . I.e., our multiplier and divider reach the minimum width of multipliers and dividers, keeping an operand unchanged.

EPJ Quantum Technology•Feb 23, 2024•5 citations

Quantum Circuit Design of Integer Division Optimizing Ancillary Qubits and T-Count

Himanshu Thapliyal, Varun, T. S. S., Edgard Muñoz‐Coreas

In this paper, we present Clifford+T gates based quantum circuit design of integer division having $n$ ancillary qubits. The proposed quantum circuit is based on restoring division algorithm. The proposed quantum circuit of integer division consists of (i) quantum circuitry of conditional addition operation, (ii) quantum circuitry of integer subtraction. To design ancillary and T-count optimized design of quantum integer division, the optimized quantum circuit design of integer conditional addition operation and integer subtraction are presented. The proposed quantum integer division circuitry has 50\% improvement in terms of ancillary qubits, and 90\% improvement in terms of T-count compared to the existing design of integer quantum division based on quantum fourier transform.

arXiv:1609.01241•Sep 5, 2016•9 citations

Resource-Efficient Modular Quantum Arithmetic Logic Unit with Clifford+T Optimization for Quantum Nanoelectronic Systems

P. Sowmithri, N. Roshitha, K. Santhi Priya, M. Manoj Kumar, K. Harika and M. Prakash

ABSTRACT Quantum arithmetic is a basic computational layer for reversible processing in quantum processors, yet its implementation cost grows rapidly with operand width and multi-qubit gate requirements. This paper presents a modular quantum arithmetic and logic unit (QALU) designed with resource-aware reversible primitives and Clifford+T decomposition. The architecture separates addition, subtraction, multiplication, and division into reusable submodules and evaluates their circuit cost in terms of T-count, T-depth, CNOT-count, CNOT-depth, qubit width, and total gate count. Hermitian LI gates and approximate Toffoli decompositions are incorporated to reduce redundant non-Clifford operations and circuit depth. The circuits are constructed and validated in Qiskit for small operand sizes, followed by symbolic resource analysis for scalable forms. For the demonstrated instances, the optimized adder is reduced from 10 to 7 total gates, the subtractor from 9 to 5, the multiplier from 12 to 8, and the divider from 11 to 6, while preserving the intended arithmetic mappings. The resulting modular framework provides a compact circuit-level approach for quantum arithmetic and is relevant to emerging quantum technology and quantum nanoelectronic systems where qubit count and fault-tolerant gate overhead are critical design constraints. Key words: quantum arithmetic, quantum ALU, reversible logic, Clifford+T, Hermitian LI gate, approximate Toffoli, Qiskit, quantum nanoelectronics.

International Journal of Emerging Trends in Engineering and Development•Nov 6, 2026•0 citations

RESOURCE EFFICIENT DESIGN OF QUANTUM CIRCUITS FOR CRYPTANALYSIS AND SCIENTIFIC COMPUTING APPLICATIONS

Edgard Muñoz‐Coreas

Quantum computers offer the potential to extend our abilities to tackle computational problems in fields such as number theory, encryption, search and scientific computation. Up to a superpolynomial speedup has been reported for quantum algorithms in these areas. Motivated by the promise of faster computations, the development of quantum machines has caught the attention of both academics and industry researchers. Quantum machines are now at sizes where implementations of quantum algorithms or their components are now becoming possible. In order to implement quantum algorithms on quantum machines, resource efficient circuits and functional blocks must be designed. In this work, we propose quantum circuits for Galois and integer arithmetic. These quantum circuits are necessary building blocks to realize quantum algorithms. The design of resource efficient quantum circuits requires the designer takes into account the gate cost, quantum bit (qubit) cost, depth and garbage outputs of a quantum circuit. Existing quantum machines do not have many qubits meaning that circuits with high qubit cost cannot be implemented. In addition, quantum circuits are more prone to errors and garbage output removal adds to overall cost. As more gates are used, a quantum circuit sees an increased rate of failure. Failures and error rates can be countered by using quantum error correcting codes and fault tolerant implementations of universal gate sets (such as Clifford+T gates). However, Clifford+T gates are costly to implement with the T gate being significantly more costly than the Clifford gates. As a result, designers working with Clifford+T gates seek to minimize the number of T gates (T-count) and the depth of T gates (T-depth). In this work, we propose quantum circuits for Galois and integer arithmetic with lower T-count, T-depth and qubit cost than existing work. This work presents novel quantum circuits for squaring and exponentiation over binary extension fields (Galois fields of form GF(2 m )). The proposed circuits are shown to have lower depth, qubit and gate cost to existing work. We also present quantum circuits for the core operations of multiplication and division which enjoy lower T-count, T-depth and qubit costs compared to existing work. This work also illustrates the design of a T-count and qubit cost efficient design for the square root. This work concludes with an illustration of how the arithmetic circuits can be combined into a functional block to implement quantum image processing algorithms.

•Aug 26, 2020•1 citation

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•17 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.
Quantum circuits for mathematical functions such as division are necessary to use quantum computers for scientific computing. Quantum circuits based on Clifford+T gates can easily be made fault-tolerant but the T gate is very costly to implement. The small number of qubits available in existing quantum computers adds another constraint on quantum circuits. As a result, reducing T-count and qubit cost have become important optimization goals. The design of quantum circuits for integer division has caught the attention of researchers and designs have been proposed in the literature. However, these designs suffer from excessive T gate and qubit costs. Many of these designs also produce significant garbage output resulting in additional qubit and T gate costs to eliminate these outputs. In this work, we propose two quantum integer division circuits. The first proposed quantum integer division circuit is based on the restoring division algorithm and the second proposed design implements the non-restoring division algorithm. Both proposed designs are optimized in terms of T-count, T-depth and qubits. Both proposed quantum circuit designs are based on (i) a quantum subtractor, (ii) a quantum adder-subtractor circuit, and (iii) a novel quantum conditional addition circuit. Our proposed restoring division circuit achieves average T-count savings from 79.03 to 91.69 percent compared to the existing works. Our proposed non-restoring division circuit achieves average T-count savings from 49.22 to 90.03 percent compared to the existing works. Further, both our proposed designs have linear T-depth. We also illustrate the application of the proposed quantum division circuits in quantum image processing with a case study of quantum bilinear interpolation.
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 3 n . I.e., our multiplier and divider reach the minimum width of multipliers and dividers, keeping an operand unchanged.
In this paper, we present Clifford+T gates based quantum circuit design of integer division having nnn ancillary qubits. The proposed quantum circuit is based on restoring division algorithm. The proposed quantum circuit of integer division consists of (i) quantum circuitry of conditional addition operation, (ii) quantum circuitry of integer subtraction. To design ancillary and T-count optimized design of quantum integer division, the optimized quantum circuit design of integer conditional addition operation and integer subtraction are presented. The proposed quantum integer division circuitry has 50\% improvement in terms of ancillary qubits, and 90\% improvement in terms of T-count compared to the existing design of integer quantum division based on quantum fourier transform.
ABSTRACT Quantum arithmetic is a basic computational layer for reversible processing in quantum processors, yet its implementation cost grows rapidly with operand width and multi-qubit gate requirements. This paper presents a modular quantum arithmetic and logic unit (QALU) designed with resource-aware reversible primitives and Clifford+T decomposition. The architecture separates addition, subtraction, multiplication, and division into reusable submodules and evaluates their circuit cost in terms of T-count, T-depth, CNOT-count, CNOT-depth, qubit width, and total gate count. Hermitian LI gates and approximate Toffoli decompositions are incorporated to reduce redundant non-Clifford operations and circuit depth. The circuits are constructed and validated in Qiskit for small operand sizes, followed by symbolic resource analysis for scalable forms. For the demonstrated instances, the optimized adder is reduced from 10 to 7 total gates, the subtractor from 9 to 5, the multiplier from 12 to 8, and the divider from 11 to 6, while preserving the intended arithmetic mappings. The resulting modular framework provides a compact circuit-level approach for quantum arithmetic and is relevant to emerging quantum technology and quantum nanoelectronic systems where qubit count and fault-tolerant gate overhead are critical design constraints. Key words: quantum arithmetic, quantum ALU, reversible logic, Clifford+T, Hermitian LI gate, approximate Toffoli, Qiskit, quantum nanoelectronics.
Quantum computers offer the potential to extend our abilities to tackle computational problems in fields such as number theory, encryption, search and scientific computation. Up to a superpolynomial speedup has been reported for quantum algorithms in these areas. Motivated by the promise of faster computations, the development of quantum machines has caught the attention of both academics and industry researchers. Quantum machines are now at sizes where implementations of quantum algorithms or their components are now becoming possible. In order to implement quantum algorithms on quantum machines, resource efficient circuits and functional blocks must be designed. In this work, we propose quantum circuits for Galois and integer arithmetic. These quantum circuits are necessary building blocks to realize quantum algorithms. The design of resource efficient quantum circuits requires the designer takes into account the gate cost, quantum bit (qubit) cost, depth and garbage outputs of a quantum circuit. Existing quantum machines do not have many qubits meaning that circuits with high qubit cost cannot be implemented. In addition, quantum circuits are more prone to errors and garbage output removal adds to overall cost. As more gates are used, a quantum circuit sees an increased rate of failure. Failures and error rates can be countered by using quantum error correcting codes and fault tolerant implementations of universal gate sets (such as Clifford+T gates). However, Clifford+T gates are costly to implement with the T gate being significantly more costly than the Clifford gates. As a result, designers working with Clifford+T gates seek to minimize the number of T gates (T-count) and the depth of T gates (T-depth). In this work, we propose quantum circuits for Galois and integer arithmetic with lower T-count, T-depth and qubit cost than existing work. This work presents novel quantum circuits for squaring and exponentiation over binary extension fields (Galois fields of form GF(2 m )). The proposed circuits are shown to have lower depth, qubit and gate cost to existing work. We also present quantum circuits for the core operations of multiplication and division which enjoy lower T-count, T-depth and qubit costs compared to existing work. This work also illustrates the design of a T-count and qubit cost efficient design for the square root. This work concludes with an illustration of how the arithmetic circuits can be combined into a functional block to implement quantum image processing algorithms.
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.