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• 35 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

T-count Optimized Design of Quantum Integer Multiplication

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 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. Recently, the design of a quantum multiplier is presented by Babu [1] which improves the existing works in terms of number of quantum gates, number of qubits, and delay. However, the recent design is not based on fault-tolerant Clifford + T gates. Also, it has large number of qubits and garbage outputs. Therefore, this work presents a T-count optimized quantum circuit for integer multiplication with only $4 \cdot n + 1$ qubits and no garbage outputs. The proposed quantum multiplier design saves the T-count by using a novel quantum conditional adder circuit. Also, where one operand to the controlled adder is zero, the conditional adder is replaced with a Toffoli gate array to further save the T gates. To have fair comparison with the recent design by Babu and get an actual estimate of the T-count, it is made garbageless by using Bennett's garbage removal scheme. The proposed design achieves an average T-count savings of $47.55\%$ compared to the recent work by Babu. Further, comparison is also performed with other recent works by Lin et. al. [2], and Jayashree et. al.[3]. Average T-count savings of $62.71\%$ and $26.30\%$ are achieved compared to the recent works by Lin et. al., and Jayashree et. al., respectively.

arXiv:1706.05113•Jun 15, 2017•10 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 International Symposium on Nanoelectronic and Information Systems (iNIS)•Dec 1, 2017•82 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.

IEEE Transactions on Computers•Nov 22, 2018•89 citations

T-count and Qubit Optimized Quantum Circuit Designs of Carry Lookahead Adder

Himanshu Thapliyal, Edgard Muñoz‐Coreas, Vladislav Khalus

Quantum circuits of arithmetic operations such as addition are needed to implement quantum algorithms in hardware. Quantum circuits based on Clifford+T gates are used as they can be made tolerant to noise. The tradeoff of gaining fault tolerance from using Clifford+T gates and error correcting codes is the high implementation overhead of the T gate. As a result, the T-count performance measure has become important in quantum circuit design. Due to noise, the risk for errors in a quantum circuit computation increases as the number of gate layers (or depth) in the circuit increases. As a result, low depth circuits such as quantum carry lookahead adders (QCLA)s have caught the attention of researchers. This work presents two QCLA designs each optimized with emphasis on T-count or qubit cost respectively. In-place and out-of-place versions of each design are shown. The proposed QCLAs are compared against the existing works in terms of T-count. The proposed QCLAs for out-of-place addition achieve average T gate savings of $54.34 \%$ and $37.21 \%$, respectively. The proposed QCLAs for in-place addition achieve average T gate savings of $72.11 \%$ and $35.87 \%$

arXiv:2004.01826•Apr 4, 2020•6 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
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 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 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. Recently, the design of a quantum multiplier is presented by Babu [1] which improves the existing works in terms of number of quantum gates, number of qubits, and delay. However, the recent design is not based on fault-tolerant Clifford + T gates. Also, it has large number of qubits and garbage outputs. Therefore, this work presents a T-count optimized quantum circuit for integer multiplication with only 4⋅n+14 \cdot n + 14⋅n+1 qubits and no garbage outputs. The proposed quantum multiplier design saves the T-count by using a novel quantum conditional adder circuit. Also, where one operand to the controlled adder is zero, the conditional adder is replaced with a Toffoli gate array to further save the T gates. To have fair comparison with the recent design by Babu and get an actual estimate of the T-count, it is made garbageless by using Bennett's garbage removal scheme. The proposed design achieves an average T-count savings of 47.55%47.55\%47.55% compared to the recent work by Babu. Further, comparison is also performed with other recent works by Lin et. al. [2], and Jayashree et. al.[3]. Average T-count savings of 62.71%62.71\%62.71% and 26.30%26.30\%26.30% are achieved compared to the recent works by Lin et. al., and Jayashree et. al., respectively.
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.
Quantum circuits of arithmetic operations such as addition are needed to implement quantum algorithms in hardware. Quantum circuits based on Clifford+T gates are used as they can be made tolerant to noise. The tradeoff of gaining fault tolerance from using Clifford+T gates and error correcting codes is the high implementation overhead of the T gate. As a result, the T-count performance measure has become important in quantum circuit design. Due to noise, the risk for errors in a quantum circuit computation increases as the number of gate layers (or depth) in the circuit increases. As a result, low depth circuits such as quantum carry lookahead adders (QCLA)s have caught the attention of researchers. This work presents two QCLA designs each optimized with emphasis on T-count or qubit cost respectively. In-place and out-of-place versions of each design are shown. The proposed QCLAs are compared against the existing works in terms of T-count. The proposed QCLAs for out-of-place addition achieve average T gate savings of 54.34%54.34 \%54.34% and 37.21%37.21 \%37.21%, respectively. The proposed QCLAs for in-place addition achieve average T gate savings of 72.11%72.11 \%72.11% and 35.87%35.87 \%35.87%
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.