Toward Optimal Quantum Multipliers: Space–Time Efficiency and Asymptotic Bounds for Advanced Toom–Cook Methods - Rini Wisnu Wardhani; Dedy Septono Catur Putranto (Mathematics Department, Maulana Malik Ibrahim State Islamic University of Malang, 2026)
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.