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:1706.03419 · Leibniz international proceedings in informatics

Improved reversible and quantum circuits for Karatsuba-based integer multiplication

Alex Parent, Martin Roetteler, Michele Mosca

Published Jun 11, 2017• 24 citations
arXivHTMLPDF

Abstract

Integer arithmetic is the underpinning of many quantum algorithms, with applications ranging from Shor's algorithm over HHL for matrix inversion to Hamiltonian simulation algorithms. A basic objective is to keep the required resources to implement arithmetic as low as possible. This applies in particular to the number of qubits required in the implementation as for the foreseeable future this number is expected to be small. We present a reversible circuit for integer multiplication that is inspired by Karatsuba's recursive method. The main improvement over circuits that have been previously reported in the literature is an asymptotic reduction of the amount of space required from $O(n^{1.585})$ to $O(n^{1.427})$. This improvement is obtained in exchange for a small constant increase in the number of operations by a factor less than $2$ and a small asymptotic increase in depth for the parallel version. The asymptotic improvement are obtained from analyzing pebble games on complete ternary trees.

DOI
10.4230/lipics.tqc.2017.7

Related papers

Quantum circuits for Toom-Cook multiplication

Srijit Dutta, Debjyoti Bhattacharjee, Anupam Chattopadhyay

In this paper, we report efficient quantum circuits for integer multiplication using the Toom-Cook algorithm. By analyzing the recursive tree structure of the algorithm, we obtained a bound on the count of Toffoli gates and qubits. These bounds are further improved by employing reversible pebble games through uncomputing the intermediate results. The asymptotic bounds for different performance metrics of the proposed quantum circuit are superior to the prior implementations of multiplier circuits using schoolbook and Karatsuba algorithms.

arXiv:1805.02342•Physical Review A•Jul 12, 2018•29 citations

Reversible Karatsuba's Algorithm

Luis Antônio Brasil Kowada, Renato Portugal, Celina M.H. de Figueiredo

Abstract: Karatsuba discovered the first algorithm that accomplishes multiprecision integer multiplication with complexity below that of the grade-school method. This algorithm is implemented nowadays in computer algebra systems using irreversible logic. In this paper we describe reversible circuits for the Karatsuba’s algorithm and analyze their computational complexity. We discuss garbage disposal methods and compare with the well known Bennett’s schemes. These circuits can be used in reversible computers which have the advantage of being very efficient in terms of energy consumption. The algorithm can also be used in quantum computers and is an improvement of previous circuits for the same purpose described in the literature.

JUCS - Journal of Universal Computer Science•Jan 1, 2006•18 citations

Quantum Circuit Design for Integer Multiplication Based on Schönhage–Strassen Algorithm

Junhong Nie, Qinlin Zhu, Meng Li +1 more

Quantum arithmetic circuits have attracted extensive attention recently since it plays fundamental roles in many applications of quantum computing. Specifically, quantum circuits for integer multiplication are of great significance to various quantum algorithms, including Shor’s integer factorization and discrete logarithm algorithm. In this article, we design a family of quantum circuits for integer multiplication based on the famous classical integer multiplication algorithm, Schönhage–Strassen algorithm. We have made slight modifications to the algorithm to simplify its quantum circuit implementation. As a result, the quantum circuit we designed has gate depth$O(\log ^{2} n)$. To the best of our knowledge, this is the first poly-logarithmic depth quantum circuit for integer multiplication which keeps the circuit size and the number of ancillary qubits subquadratic. Our design has size$O(n\log n\log \log n)$counted by elementary quantum gates which is the same as the time complexity of the Schönhage–Strassen algorithm, and it consumes$O(n\log n\log \log n)$clean ancillary qubits. In addition, we also utilize a weaker version of Schönhage–Strassen algorithm to give a family of circuits which has depth at the same order$O(\log ^{2} n)$but with significantly smaller constants, while still keeping the size and number of ancillary qubits subquadratic.

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•May 30, 2023•16 citations

Improved quantum circuits for division

Priyanka Mukhopadhyay, Alexandru Gheorghiu, Hari Krovi

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.

quant-pharXiv:2603.18110•Mar 19, 2026•0 citations

Quantum Binary Field Multiplication with Optimized Toffoli Depth and Extension to Quantum Inversion

Kyungbae Jang, Wonwoong Kim, Sejin Lim +3 more

The Shor's algorithm can find solutions to the discrete logarithm problem on binary elliptic curves in polynomial time. A major challenge in implementing Shor's algorithm is the overhead of representing and performing arithmetic on binary elliptic curves using quantum circuits. Multiplication of binary fields is one of the critical operations in the context of elliptic curve arithmetic, and it is especially costly in the quantum setting. Our goal in this paper is to optimize quantum multiplication in the binary field. In the past, efforts to optimize quantum multiplication have centred on reducing the Toffoli gate count or qubits required. However, despite the fact that circuit depth is an important metric for indicating the performance of a quantum circuit, previous studies have lacked sufficient consideration for reducing circuit depth. Our approach to optimizing quantum multiplication differs from previous work in that we aim at reducing the Toffoli depth and full depth. To optimize quantum multiplication, we adopt the Karatsuba multiplication method which is based on the divide-and-conquer approach. In summary, we present an optimized quantum multiplication that has a Toffoli depth of one. Additionally, the full depth of the quantum circuit is also reduced thanks to our Toffoli depth optimization strategy. To demonstrate the effectiveness of our proposed method, we evaluate its performance using various metrics such as the qubit count, quantum gates, and circuit depth, as well as the qubits-depth product. These metrics provide insight into the resource requirements and complexity of the method. Our work achieves the lowest Toffoli depth, full depth, and the best trade-off performance for quantum multiplication. Further, our multiplication is more effective when not used in stand-alone cases. We show this effectiveness by using our multiplication to the Itoh-Tsujii algorithm-based inversion of F(x8+x4+x3+x+1).

Sensors•Mar 15, 2023•7 citations

Constant-optimized quantum circuits for modular multiplication and exponentiation

Igor L. Markov, Mehdi Saeedi

Reversible circuits for modular multiplication $Cx\%M$ with $x<M$ arise as components of modular exponentiation in Shor's quantum number-factoring algorithm. However, existing generic constructions focus on asymptotic gate count and circuit depth rather than actual values, producing fairly large circuits not optimized for specific $C$ and $M$ values. In this work, we develop such optimizations in a bottom-up fashion, starting with most convenient $C$ values. When zero-initialized ancilla registers are available, we reduce the search for compact circuits to a shortest-path problem. Some of our modular-multiplication circuits are asymptotically smaller than previous constructions, but worst-case bounds and average sizes remain $\Theta(n^2)$. In the context of modular exponentiation, we offer several constant-factor improvements, as well as an improvement by a constant additive term that is significant for few-qubit circuits arising in ongoing laboratory experiments with Shor's algorithm.

Quantum Information and Computation•May 1, 2012•83 citations
Integer arithmetic is the underpinning of many quantum algorithms, with applications ranging from Shor's algorithm over HHL for matrix inversion to Hamiltonian simulation algorithms. A basic objective is to keep the required resources to implement arithmetic as low as possible. This applies in particular to the number of qubits required in the implementation as for the foreseeable future this number is expected to be small. We present a reversible circuit for integer multiplication that is inspired by Karatsuba's recursive method. The main improvement over circuits that have been previously reported in the literature is an asymptotic reduction of the amount of space required from O(n1.585)O(n^{1.585})O(n1.585) to O(n1.427)O(n^{1.427})O(n1.427). This improvement is obtained in exchange for a small constant increase in the number of operations by a factor less than 222 and a small asymptotic increase in depth for the parallel version. The asymptotic improvement are obtained from analyzing pebble games on complete ternary trees.
In this paper, we report efficient quantum circuits for integer multiplication using the Toom-Cook algorithm. By analyzing the recursive tree structure of the algorithm, we obtained a bound on the count of Toffoli gates and qubits. These bounds are further improved by employing reversible pebble games through uncomputing the intermediate results. The asymptotic bounds for different performance metrics of the proposed quantum circuit are superior to the prior implementations of multiplier circuits using schoolbook and Karatsuba algorithms.
Abstract: Karatsuba discovered the first algorithm that accomplishes multiprecision integer multiplication with complexity below that of the grade-school method. This algorithm is implemented nowadays in computer algebra systems using irreversible logic. In this paper we describe reversible circuits for the Karatsuba’s algorithm and analyze their computational complexity. We discuss garbage disposal methods and compare with the well known Bennett’s schemes. These circuits can be used in reversible computers which have the advantage of being very efficient in terms of energy consumption. The algorithm can also be used in quantum computers and is an improvement of previous circuits for the same purpose described in the literature.
Quantum arithmetic circuits have attracted extensive attention recently since it plays fundamental roles in many applications of quantum computing. Specifically, quantum circuits for integer multiplication are of great significance to various quantum algorithms, including Shor’s integer factorization and discrete logarithm algorithm. In this article, we design a family of quantum circuits for integer multiplication based on the famous classical integer multiplication algorithm, Schönhage–Strassen algorithm. We have made slight modifications to the algorithm to simplify its quantum circuit implementation. As a result, the quantum circuit we designed has gate depthO(log⁡2n)O(\log ^{2} n)O(log2n). To the best of our knowledge, this is the first poly-logarithmic depth quantum circuit for integer multiplication which keeps the circuit size and the number of ancillary qubits subquadratic. Our design has sizeO(nlog⁡nlog⁡log⁡n)O(n\log n\log \log n)O(nlognloglogn)counted by elementary quantum gates which is the same as the time complexity of the Schönhage–Strassen algorithm, and it consumesO(nlog⁡nlog⁡log⁡n)O(n\log n\log \log n)O(nlognloglogn)clean ancillary qubits. In addition, we also utilize a weaker version of Schönhage–Strassen algorithm to give a family of circuits which has depth at the same orderO(log⁡2n)O(\log ^{2} n)O(log2n)but with significantly smaller constants, while still keeping the size and number of ancillary qubits subquadratic.
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.
The Shor's algorithm can find solutions to the discrete logarithm problem on binary elliptic curves in polynomial time. A major challenge in implementing Shor's algorithm is the overhead of representing and performing arithmetic on binary elliptic curves using quantum circuits. Multiplication of binary fields is one of the critical operations in the context of elliptic curve arithmetic, and it is especially costly in the quantum setting. Our goal in this paper is to optimize quantum multiplication in the binary field. In the past, efforts to optimize quantum multiplication have centred on reducing the Toffoli gate count or qubits required. However, despite the fact that circuit depth is an important metric for indicating the performance of a quantum circuit, previous studies have lacked sufficient consideration for reducing circuit depth. Our approach to optimizing quantum multiplication differs from previous work in that we aim at reducing the Toffoli depth and full depth. To optimize quantum multiplication, we adopt the Karatsuba multiplication method which is based on the divide-and-conquer approach. In summary, we present an optimized quantum multiplication that has a Toffoli depth of one. Additionally, the full depth of the quantum circuit is also reduced thanks to our Toffoli depth optimization strategy. To demonstrate the effectiveness of our proposed method, we evaluate its performance using various metrics such as the qubit count, quantum gates, and circuit depth, as well as the qubits-depth product. These metrics provide insight into the resource requirements and complexity of the method. Our work achieves the lowest Toffoli depth, full depth, and the best trade-off performance for quantum multiplication. Further, our multiplication is more effective when not used in stand-alone cases. We show this effectiveness by using our multiplication to the Itoh-Tsujii algorithm-based inversion of F(x8+x4+x3+x+1).
Reversible circuits for modular multiplication Cx%MCx\%MCx%M with x<Mx<Mx<M arise as components of modular exponentiation in Shor's quantum number-factoring algorithm. However, existing generic constructions focus on asymptotic gate count and circuit depth rather than actual values, producing fairly large circuits not optimized for specific CCC and MMM values. In this work, we develop such optimizations in a bottom-up fashion, starting with most convenient CCC values. When zero-initialized ancilla registers are available, we reduce the search for compact circuits to a shortest-path problem. Some of our modular-multiplication circuits are asymptotically smaller than previous constructions, but worst-case bounds and average sizes remain Θ(n2)\Theta(n^2)Θ(n2). In the context of modular exponentiation, we offer several constant-factor improvements, as well as an improvement by a constant additive term that is significant for few-qubit circuits arising in ongoing laboratory experiments with Shor's algorithm.