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:1712.08254 · ACM Journal on Emerging Technologies in Computing Systems

T-count and Qubit Optimized Quantum Circuit Design of the Non-Restoring Square Root Algorithm

Edgard Muñoz‐Coreas, Himanshu Thapliyal

Published Jul 31, 2018• 43 citations
arXivHTMLPDF

Abstract

Quantum circuits for basic mathematical functions such as the square root are required to implement scientific computing algorithms on quantum computers. Quantum circuits that are based on Clifford+T gates can easily be made fault tolerant, but the T gate is very costly to implement. As a result, reducing T-count has become an important optimization goal. Further, quantum circuits with many qubits are difficult to realize, making designs that save qubits and produce no garbage outputs desirable. In this work, we present a T-count optimized quantum square root circuit with only 2 ṡ n + 1 qubits and no garbage output. To make a fair comparison against existing work, the Bennett’s garbage removal scheme is used to remove garbage output from existing works. We determined that our proposed design achieves an average T-count savings of 43.44%, 98.95%, 41.06%, and 20.28% as well as qubit savings of 85.46%, 95.16%, 90.59%, and 86.77% compared to existing works.

DOI
10.1145/3264816

Related papers

Qubit and T-count Optimized Quantum Circuit Design for Fixed Precision Square Root

Afrin Sultana, Edgard Muñoz‐Coreas

Quantum square root operation is a useful building block in implementing important quantum algorithms such as the Harrow–Hassidim–Lloyd (HHL) algorithm, algorithms in physics and quantum chemistry, and also used in computing roots of quadratic equation, evaluating quadratic congruence, solving Hamiltonian and Poisson equations, trigonometric functions, computing logarithm and fractional exponent, and in quantum chemistry [1]–[5]. Quantum circuits could be made fault-tolerant by using error correcting codes and fault-tolerant quantum gates (such as the Clifford + T-gates). However, The T-gates are expensive to implement than other fault-tolerant gates (such as Clifford+T gates) [6] [7]. Therefore, quantum circuits with low T-count and qubit cost is preferred. In this paper, we present a novel quantum square root architecture optimized for T-count and Qubit cost that produces no garbage outputs. The proposed square root circuit accepts integer and fractional inputs. We use the Babylonian method to calculate the square root. To reduce the number of iteration, the initial guess required in the Babylonian method is calculated from the integer square root circuit in [8] which reduces the cost measures. To further save the cost, we use the resource efficient non-restoring division circuit shown in [9] and quantum adder shown in [6]. The proposed quantum square root circuit sees an asymptotic reduction of 95.84% in T-count and 88.89% in Qubit cost with respect to Bhaskar et al. [1]. With respect to Dutta et al. [10] the design sees an asymptotic reduction of 96% in T-count, and 88.89% in Qubit cost.

IEEE Computer Society Annual Symposium on VLSI•Jul 1, 2024•0 citations

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

Quantum Circuit Design of a T-count Optimized Integer Multiplier

Edgard Muñoz‐Coreas, Himanshu Thapliyal

Quantum circuits of many qubits are extremely difficult to realize; thus, the number of qubits is an important metric in a quantum circuit design. Further, scalable and reliable quantum circuits are based on fault tolerant implementations of quantum gates such as Clifford+T gates. An efficient quantum circuit saves quantum hardware resources by reducing the number of T gates without substantially increasing the number of qubits. This work presents a T-count optimized quantum circuit for integer multiplication with only 4 · n + 1 qubits and no garbage outputs. The proposed quantum multiplier design reduces the T-count by using a novel quantum conditional adder circuit. Also, where one operand to the conditional adder is zero, the conditional adder is replaced with a Toffoli gate array to further save T gates. Average T-count savings of 46:12, 47:55, 62:71 and 26.30 percent are achieved compared to the recent works by Kotiyal et al., Babu, Lin et al., and Jayashree et al., respectively.

arXiv:1706.05113•IEEE Transactions on Computers•Nov 22, 2018•112 citations

Qrisp Implementation and Resource Analysis of a T-Count-Optimized Non-Restoring Quantum Square-Root Circuit

Heorhi Kupryianau, Marcin Niemiec

Abstract \noindent Efficient quantum arithmetic operations are essential building blocks for complex quantum algorithms, yet few theoretical designs have been implemented in practical quantum programming frameworks. This paper presents the first complete implementation of the T-count optimized non-restoring quantum square root algorithm using the Qrisp quantum programming framework. The algorithm offers better resource efficiency compared to alternative methods, achieving reduced T-count and qubit requirements while avoiding garbage output. Our implementation validates the theoretical resource estimates, confirming a T-count of $14n-14$ and a T-depth of $5n+3$ for $n$-bit inputs. The modular design approach enabled by Qrisp allows the construction of reusable components, including reversible adders, subtractors, and conditional logic blocks built from fundamental quantum gates. The three-stage algorithm, comprising initial subtraction, iterative conditional addition/subtraction, and remainder restoration, is successfully translated from algorithmic description to executable quantum code. Experimental validation across multiple test cases confirms the correctness, with the circuit producing accurate integer square roots and remainders. This work demonstrates the practical realizability of resource-optimized quantum arithmetic algorithms and establishes a foundation for implementing different arithmetic operations in modern quantum programming frameworks.

•Dec 8, 2025•0 citations

T-count Optimized Quantum Circuits for Bilinear Interpolation

Edgard Muñoz‐Coreas, Himanshu Thapliyal

Quantum circuits for basic image processing functions such as bilinear interpolation are required to implement image processing algorithms on quantum computers. In this work, we propose quantum circuits for the bilinear interpolation of NEQR encoded images based on Clifford+T gates. Quantum circuits for the scale up operation and scale down operation are illustrated. The proposed quantum circuits are based on quantum Clifford+T gates and are optimized for T-count. Quantum circuits based on Clifford+T gates can be made fault tolerant but the T gate is very costly to implement. As a result, reducing T-count is an important optimization goal. The proposed quantum bilinear interpolation circuits are based on (i) a quantum adder, (ii) a proposed quantum subtractor, and (iii) a quantum multiplication circuit. Further, both designs are compared and shown to be superior to existing work in terms of T-count. The proposed quantum bilinear interpolation circuits for the scale down operation and for the scale up operation each have a 92.52% improvement in terms of T-count compared to the existing work.

arXiv:1809.09249•International Green and Sustainable Computing Conference•Oct 1, 2018•10 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
Quantum circuits for basic mathematical functions such as the square root are required to implement scientific computing algorithms on quantum computers. Quantum circuits that are based on Clifford+T gates can easily be made fault tolerant, but the T gate is very costly to implement. As a result, reducing T-count has become an important optimization goal. Further, quantum circuits with many qubits are difficult to realize, making designs that save qubits and produce no garbage outputs desirable. In this work, we present a T-count optimized quantum square root circuit with only 2 ṡ n + 1 qubits and no garbage output. To make a fair comparison against existing work, the Bennett’s garbage removal scheme is used to remove garbage output from existing works. We determined that our proposed design achieves an average T-count savings of 43.44%, 98.95%, 41.06%, and 20.28% as well as qubit savings of 85.46%, 95.16%, 90.59%, and 86.77% compared to existing works.
Quantum square root operation is a useful building block in implementing important quantum algorithms such as the Harrow–Hassidim–Lloyd (HHL) algorithm, algorithms in physics and quantum chemistry, and also used in computing roots of quadratic equation, evaluating quadratic congruence, solving Hamiltonian and Poisson equations, trigonometric functions, computing logarithm and fractional exponent, and in quantum chemistry [1]–[5]. Quantum circuits could be made fault-tolerant by using error correcting codes and fault-tolerant quantum gates (such as the Clifford + T-gates). However, The T-gates are expensive to implement than other fault-tolerant gates (such as Clifford+T gates) [6] [7]. Therefore, quantum circuits with low T-count and qubit cost is preferred. In this paper, we present a novel quantum square root architecture optimized for T-count and Qubit cost that produces no garbage outputs. The proposed square root circuit accepts integer and fractional inputs. We use the Babylonian method to calculate the square root. To reduce the number of iteration, the initial guess required in the Babylonian method is calculated from the integer square root circuit in [8] which reduces the cost measures. To further save the cost, we use the resource efficient non-restoring division circuit shown in [9] and quantum adder shown in [6]. The proposed quantum square root circuit sees an asymptotic reduction of 95.84% in T-count and 88.89% in Qubit cost with respect to Bhaskar et al. [1]. With respect to Dutta et al. [10] the design sees an asymptotic reduction of 96% in T-count, and 88.89% in Qubit cost.
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.
Quantum circuits of many qubits are extremely difficult to realize; thus, the number of qubits is an important metric in a quantum circuit design. Further, scalable and reliable quantum circuits are based on fault tolerant implementations of quantum gates such as Clifford+T gates. An efficient quantum circuit saves quantum hardware resources by reducing the number of T gates without substantially increasing the number of qubits. This work presents a T-count optimized quantum circuit for integer multiplication with only 4 · n + 1 qubits and no garbage outputs. The proposed quantum multiplier design reduces the T-count by using a novel quantum conditional adder circuit. Also, where one operand to the conditional adder is zero, the conditional adder is replaced with a Toffoli gate array to further save T gates. Average T-count savings of 46:12, 47:55, 62:71 and 26.30 percent are achieved compared to the recent works by Kotiyal et al., Babu, Lin et al., and Jayashree et al., respectively.
Abstract \noindent Efficient quantum arithmetic operations are essential building blocks for complex quantum algorithms, yet few theoretical designs have been implemented in practical quantum programming frameworks. This paper presents the first complete implementation of the T-count optimized non-restoring quantum square root algorithm using the Qrisp quantum programming framework. The algorithm offers better resource efficiency compared to alternative methods, achieving reduced T-count and qubit requirements while avoiding garbage output. Our implementation validates the theoretical resource estimates, confirming a T-count of 14n−1414n-1414n−14 and a T-depth of 5n+35n+35n+3 for nnn-bit inputs. The modular design approach enabled by Qrisp allows the construction of reusable components, including reversible adders, subtractors, and conditional logic blocks built from fundamental quantum gates. The three-stage algorithm, comprising initial subtraction, iterative conditional addition/subtraction, and remainder restoration, is successfully translated from algorithmic description to executable quantum code. Experimental validation across multiple test cases confirms the correctness, with the circuit producing accurate integer square roots and remainders. This work demonstrates the practical realizability of resource-optimized quantum arithmetic algorithms and establishes a foundation for implementing different arithmetic operations in modern quantum programming frameworks.
Quantum circuits for basic image processing functions such as bilinear interpolation are required to implement image processing algorithms on quantum computers. In this work, we propose quantum circuits for the bilinear interpolation of NEQR encoded images based on Clifford+T gates. Quantum circuits for the scale up operation and scale down operation are illustrated. The proposed quantum circuits are based on quantum Clifford+T gates and are optimized for T-count. Quantum circuits based on Clifford+T gates can be made fault tolerant but the T gate is very costly to implement. As a result, reducing T-count is an important optimization goal. The proposed quantum bilinear interpolation circuits are based on (i) a quantum adder, (ii) a proposed quantum subtractor, and (iii) a quantum multiplication circuit. Further, both designs are compared and shown to be superior to existing work in terms of T-count. The proposed quantum bilinear interpolation circuits for the scale down operation and for the scale up operation each have a 92.52% improvement in terms of T-count compared to the existing work.
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.