T-count Optimized Design of Quantum Integer Multiplication

Abstract

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.

References in corpus (7)

• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• Methodology for quantum logic gate constructions
• Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
• Reducing the overhead for quantum computation when noise is biased
• Efficient Quantum Algorithms for Estimating Gauss Sums
• Quantum implementation of elementary arithmetic operations
• Classical and Quantum Algorithms for Exponential Congruences

Cited by in corpus (7)

• Halving the cost of quantum addition
• QFold: Quantum Walks and Deep Learning to Solve Protein Folding
• Quantum circuits design for evaluating transcendental functions based on a function-value binary expansion method
• TFermion: A non-Clifford gate cost assessment library of quantum phase estimation algorithms for quantum chemistry
• Grover's oracle for the Shortest Vector Problem and its application in hybrid classical-quantum solvers
• T-count Optimized Quantum Circuits for Bilinear Interpolation
• Approximative lookup-tables and arbitrary function rotations for facilitating NISQ-implementations of the HHL and beyond