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:2410.00899

Quantum schoolbook multiplication with fewer Toffoli gates

Daniel Litinski

Published Oct 1, 2024• 10 citations
arXivHTMLPDF

Abstract

This paper presents a method for constructing quantum circuits for schoolbook multiplication using controlled add-subtract circuits, asymptotically halving the Toffoli count compared to traditional controlled-adder-based constructions. Controlled n-qubit add-subtract circuits, which perform an addition when the control qubit is one and a subtraction when it is zero, require only n-1 Toffoli gates, instead of the 2n-1 needed for controlled adders. Despite the existence of multiplication circuits with better asymptotic scaling, schoolbook multiplication yields the lowest Toffoli counts for small register sizes, making it advantageous in practical applications. For example, the presented approach reduces the Toffoli count by up to around 30% in circuits for breaking 256-bit elliptic curve keys compared to circuits with standard schoolbook multipliers.

DOI
10.48550/arxiv.2410.00899

Related papers

A Classical-Quantum Adder with Constant Workspace and Linear Gates

Craig Gidney

In 2004, Cuccaro et al found a quantum-quantum adder with $O(n)$ gate cost and $O(1)$ ancilla qubits. Since then, it's been an open question whether classical-quantum adders can achieve the same asymptotic complexity. These costs are particularly relevant to modular arithmetic circuits, which often offset by the classically known modulus. In this paper, I construct an adder that uses 3 clean ancillae and $4n \pm O(1)$ Toffoli gates to add a classical offset into a quantum register. I also present an adder with a Toffoli cost of $3n \pm O(1)$ that uses 2 clean ancillae and $n-2$ dirty ancillae. I further show that applying the presented adders conditioned on a control qubit requires no additional workspace or Toffolis.

arXiv:2507.23079•Jul 30, 2025•15 citations

Ancilla-free optimal quantum adder

Junhong Nie, Jialiang Tang, Xiaoming Sun +1 more

We construct an exact $n$-bit quantum adder with $O(n)$ gates and $O(\log n)$ depth that requires no ancillary qubits. The circuit uses only $X$, CNOT, and Toffoli gates under all-to-all connectivity and is classically reversible. Our construction accelerates the controlled ladder underlying addition. Grouping the data into blocks and use existing control qubits as conditional workspace gives a recursive construction with $O(n\log\log n)$ gates and $O(\log n)$ depth. We then coordinate inter-block propagation via two short-path forest operations to cut the per-block workspace requirement, yielding a nonrecursive implementation with $O(n)$ gates. Both the gate count and circuit depth are asymptotically optimal.

quant-pharXiv:2610.34446•Oct 27, 2026•0 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

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•33 citations

Asymptotically Optimal Quantum Circuits for Comparators and Incrementers

Vivien Vandaele

We present quantum circuits for comparison and increment operations that achieve an asymptotically optimal gate count of $Θ(n)$ and depth of $Θ(\log n)$ over the Clifford+Toffoli gate set, while using a provably minimal number of qubits. We extend these results to classical-quantum comparators, yielding an improved classical-quantum adder with an optimal qubit count. Given the ubiquity of these operations as algorithmic building blocks, our constructions translate directly into reduced circuit complexity for many quantum algorithms. As a notable example, they can be used to improve a space-efficient circuit for Shor's factoring algorithm, reducing circuit depth from $\mathcal{O}(n^3)$ to $\mathcal{O}(n^2 \log^2 n)$ without increasing either the qubit count or the asymptotic gate complexity. Underpinning these results is a general theorem demonstrating how to trade ancilla qubits for control qubits with low overhead in both depth and gate count, providing a broadly applicable tool for quantum circuit design.

quant-pharXiv:2603.12917•Mar 16, 2026•9 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
This paper presents a method for constructing quantum circuits for schoolbook multiplication using controlled add-subtract circuits, asymptotically halving the Toffoli count compared to traditional controlled-adder-based constructions. Controlled n-qubit add-subtract circuits, which perform an addition when the control qubit is one and a subtraction when it is zero, require only n-1 Toffoli gates, instead of the 2n-1 needed for controlled adders. Despite the existence of multiplication circuits with better asymptotic scaling, schoolbook multiplication yields the lowest Toffoli counts for small register sizes, making it advantageous in practical applications. For example, the presented approach reduces the Toffoli count by up to around 30% in circuits for breaking 256-bit elliptic curve keys compared to circuits with standard schoolbook multipliers.
In 2004, Cuccaro et al found a quantum-quantum adder with O(n)O(n)O(n) gate cost and O(1)O(1)O(1) ancilla qubits. Since then, it's been an open question whether classical-quantum adders can achieve the same asymptotic complexity. These costs are particularly relevant to modular arithmetic circuits, which often offset by the classically known modulus. In this paper, I construct an adder that uses 3 clean ancillae and 4n±O(1)4n \pm O(1)4n±O(1) Toffoli gates to add a classical offset into a quantum register. I also present an adder with a Toffoli cost of 3n±O(1)3n \pm O(1)3n±O(1) that uses 2 clean ancillae and n−2n-2n−2 dirty ancillae. I further show that applying the presented adders conditioned on a control qubit requires no additional workspace or Toffolis.
We construct an exact nnn-bit quantum adder with O(n)O(n)O(n) gates and O(log⁡n)O(\log n)O(logn) depth that requires no ancillary qubits. The circuit uses only XXX, CNOT, and Toffoli gates under all-to-all connectivity and is classically reversible. Our construction accelerates the controlled ladder underlying addition. Grouping the data into blocks and use existing control qubits as conditional workspace gives a recursive construction with O(nlog⁡log⁡n)O(n\log\log n)O(nloglogn) gates and O(log⁡n)O(\log n)O(logn) depth. We then coordinate inter-block propagation via two short-path forest operations to cut the per-block workspace requirement, yielding a nonrecursive implementation with O(n)O(n)O(n) gates. Both the gate count and circuit depth are asymptotically optimal.
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.
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.
We present quantum circuits for comparison and increment operations that achieve an asymptotically optimal gate count of Θ(n)Θ(n)Θ(n) and depth of Θ(log⁡n)Θ(\log n)Θ(logn) over the Clifford+Toffoli gate set, while using a provably minimal number of qubits. We extend these results to classical-quantum comparators, yielding an improved classical-quantum adder with an optimal qubit count. Given the ubiquity of these operations as algorithmic building blocks, our constructions translate directly into reduced circuit complexity for many quantum algorithms. As a notable example, they can be used to improve a space-efficient circuit for Shor's factoring algorithm, reducing circuit depth from O(n3)\mathcal{O}(n^3)O(n3) to O(n2log⁡2n)\mathcal{O}(n^2 \log^2 n)O(n2log2n) without increasing either the qubit count or the asymptotic gate complexity. Underpinning these results is a general theorem demonstrating how to trade ancilla qubits for control qubits with low overhead in both depth and gate count, providing a broadly applicable tool for quantum circuit design.
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).