We present a detailed resource analysis of recursive quantum multiplication circuits based on the Toom-Cook family, emphasizing exact qubit and gate counts across multiple split parameters. By limiting recursive steps to Karatsuba and Toom-3 at each level, we show closed-form recurrences for both logical qubits and T-gate counts, and validate them up to 2048-bit instances. We further characterize the padding overhead from non-divisible limb sizes and discuss the impact of different recursion strategies on circuit depth. These results establish new benchmarks for quantum arithmetic and lay the groundwork for extensions to modular and fault-tolerant architectures.
We present a detailed resource analysis of recursive quantum multiplication circuits based on the Toom-Cook family, emphasizing exact qubit and gate counts across multiple split parameters. By limiting recursive steps to Karatsuba and Toom-3 at each level, we show closed-form recurrences for both logical qubits and T-gate counts, and validate them up to 2048-bit instances. We further characterize the padding overhead from non-divisible limb sizes and discuss the impact of different recursion strategies on circuit depth. These results establish new benchmarks for quantum arithmetic and lay the groundwork for extensions to modular and fault-tolerant architectures.
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.
In classical computation, Toom–Cook is one of the multiplication methods for large numbers which offers faster execution time compared to other algorithms such as schoolbook and Karatsuba multiplication. For the use in quantum computation, prior work considered the Toom-2.5 variant rather than the classically faster and more prominent Toom-3, primarily to avoid the nontrivial division operations inherent in the latter circuit. In this paper, we investigate the quantum circuit for Toom-3 multiplication, which is expected to give an asymptotically lower depth than the Toom-2.5 circuit. In particular, we designed the corresponding quantum circuit and adopted the sequence proposed by Bodrato to yield a lower number of operations, especially in terms of nontrivial division, which is reduced to only one exact division by 3 circuit per iteration. Moreover, to further minimize the cost of the remaining division, we utilize the unique property of the particular division circuit, replacing it with a constant multiplication by reciprocal circuit and the corresponding swap operations. Our numerical analysis shows that the resulting circuit indeed gives a lower asymptotic complexity in terms of Toffoli depth and qubit count compared to Toom-2.5 but with a large number of Toffoli gates that mainly come from realizing the division operation.
This paper examines the asymptotic performance of multiplication and the cost of quantum implementation for the Naive schoolbook, Karatsuba, and Toom-Cook methods in the classical and quantum cases and provides insights into multiplication roles in the post-quantum cryptography (PQC) era. Further, considering that the lattice-based PQC algorithm is based on polynomial multiplication algorithms, including the Toom-Cook 4-way multiplier as its fundamental building block, we propose a higher-degree multiplier, the Toom-Cook 8-way multiplier, which has the lowest asymptotic performance and implementation cost. Additionally, the designed multiplication will include additional sub-operations to complete the multiplication of large integers in order to prevent side-channel attacks. To design our Toom-Cook 8-way in detail, we employ detailed step computations such as splitting, evaluation, point-wise multiplication, interpolation, and recomposition, as well as several strategies to reduce space and time requirements. Existing asymptotic performance and quantum implementation cost multipliers are compared with our 2-way, 4-way, and 8-way Toom-Cook multiplier designs. Our Toom-Cook 8-way quantum multiplier has the lowest asymptotic performance analysis or qubit count in terms of space efficiency, withn( 15/8 )log 15 /(2 log 15–log 8) log8nor asymptoticallyO(n1.245). The design has the lowest logical Toffoli counts bound at 112nlog815– 128nand Toffoli depth ofn( 15/8 )1– log 15 /(2 log 15–log 8) log8n, asymptotically close toO(n1.0569), which corresponds to a space- and time-efficient multiplication.
Quantum computing has advanced rapidly in recent decades, driven by developments across the technology stack, including quantum error-correcting codes and efficient quantum algorithms. Among these, quantum arithmetic circuits serve as fundamental building blocks for various promising algorithms. Despite their crucial role, the design of quantum arithmetic circuits faces challenges arising from the no-cloning theorem, qubit limitations, and circuit depth constraints, which significantly impact the efficiency of large-scale quantum computing. We provide an overview of quantum arithmetic circuits in the context of public-key cryptanalysis, with particular emphasis on optimization strategies such as measurement-based uncomputation and conditionally clean ancilla. We review state-of-the-art designs for essential arithmetic operations in public-key cryptanalysis such as addition, multiplication, and modular exponentiation. We also present an overview of the techniques used for fault-tolerant runtime and resource estimation in quantum cryptanalysis. In brief, this chapter emphasizes strategies for designing resource-efficient quantum arithmetic circuits, providing a basis for realistic evaluations of quantum cryptanalytic capabilities.
This paper studies the asymptotic bounds of quantum resources required for high-degree multiplication based on the Toom–Cook algorithm. This work extends prior investigations on high- and half-degree quantum multiplication and proposes an optimized Toom–Cook 25.5-way quantum multiplication architecture to establish optimal asymptotic bounds on quantum resource consumption for Toom–Cook-based multiplication schemes. We provide asymptotic expressions for qubit complexity, Toffoli gate count, and Toffoli depth. The proposed Toom–Cook 25.5-way architecture achieves improved asymptotic performance, requiring a qubit count of n1.176, approximately 648nlog2651 − 666n Toffoli count, and n1.03025 Toffoli depth. Compared with existing classical and quantum Toom–Cook-based methods, the proposed 25.5-way Toom–Cook algorithm achieves lower asymptotic complexity and reduced quantum resource costs, yielding tighter bounds for optimal quantum multiplication.
This paper provides a thorough examination of strategies related to the design of the polynomial multiplication approach, which is essential to resolving large number operations, including multiplication in the post-quantum cryptography algorithm. Our research specifically centers on the implementation of Toom-Cook-based multiplication algorithms for high- and half-degree quantum multiplication, up to 20.5-way degrees, considering that existing Toom-Cook lower degrees are combined with a lattice-based approach like the Saber algorithm. In particular, we propose the quantum multiplication design, conduct computation step experiments, and implement the division-free method. In addition to examining the Toom-Cook 20.5-way algorithm, this study also provides an overview of the results obtained from the Toom-Cook 8.5-way and Toom-Cook 10.5-way algorithms. The Toom-Cook 20.5-way design exhibits significant performance improvement over its predecessor, as evidenced by its lower value of asymptotic complexity and lower cost of quantum implementation, with a qubit count ofn1.186, approximately 522nlog2141- 540nToffoli count, andn1.033Toffoli depth. Concerning the asymptotic performance analysis and quantum cost compared to alternative Toom-Cook-based multiplication, the results indicate the development of a more efficient multiplication polynomial that may be utilized in the evaluation of post-quantum security.