Toward Optimal Quantum Multipliers: Space–Time Efficiency and Asymptotic Bounds for Advanced Toom–Cook Methods

Rini Wisnu Wardhani, Dedy Septono Catur Putranto

Abstract


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.

Keywords


Asymptotic performance analysis; Multiplier; Quantum Arithmetic; Toom–Cook 25.5-way

Full Text:

PDF

References


[1] Jose Maria Bermudo Mera, Angshuman Karmakar, and Ingrid Verbauwhede. “Time-memory trade-off in Toom-Cook multiplication: an application to module-lattice based cryptography”. IACR Transactions on Cryptographic Hardware and Embedded Systems 2020.2 (2020), pp. 222–244. DOI: https://doi.org/10.13154/tches.v2020.i2.222-244.

[2] Siyi Wang, Xiufan Li, Wei Jie Bryan Lee, Suman Deb, Eugene Lim, and Anupam Chattopadhyay. “A comprehensive study of quantum arithmetic circuits”. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 383.2288 (2025). DOI: https://doi.org/10.1098/rsta.2023.0392.

[3] Srijit Dutta, Debjyoti Bhattacharjee, and Anupam Chattopadhyay. “Quantum circuits for Toom-Cook multiplication”. Physical Review A 98.1 (2018), p. 012311. DOI: https://doi.org/10.1103/PhysRevA.98.012311.

[4] Andrei L. Toom. “The complexity of a scheme of functional elements realizing the multiplication of integers”. Soviet Mathematics Doklady. Vol. 3. No. 4. 1963, pp. 714–716. URL: https://www.mathnet.ru/links/23f1aee5b47892b05da233b500953802/dan27978.pdf.

[5] Stephen A. Cook and Stål O. Aanderaa. “On the minimum computation time of functions”. Transactions of the American Mathematical Society 142 (1969), pp. 291–314. DOI: https://doi.org/10.2307/1995359.

[6] Alberto Zanoni. “Toom-cook 8-way for long integers multiplication”. 2009 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing. IEEE. 2009, pp. 54–57. DOI: https://doi.org/10.1109/SYNASC.2009.23.

[7] Marco Bodrato. “High degree Toom’n’half for balanced and unbalanced multiplication”. 2011 IEEE 20th Symposium on Computer Arithmetic. IEEE. 2011, pp. 15–22. DOI: https://doi.org/10.1109/ARITH.2011.12.

[8] Harashta Tatimma Larasati, Asep Muhamad Awaludin, Janghyun Ji, and Howon Kim. “Quantum circuit design of toom 3-way multiplication”. Applied Sciences 11.9 (2021), p. 3752. DOI: https://doi.org/10.3390/app11093752.

[9] Dedy Septono Catur Putranto, Rini Wisnu Wardhani, Harashta Tatimma Larasati, and Howon Kim. “Space and Time-Efficient Quantum Multiplier in Post Quantum Cryptography Era”. IEEE Access 11 (2023), pp. 21848–21862. DOI: https://doi.org/10.1109/ACCESS.2023.3252504.

[10] Rini Wisnu Wardhani, Dedy Septono Catur Putranto, and Howon Kim. “Quantum circuits for high-degree and half-multiplication for post-quantum analysis”. International Conference on Information Security and Cryptology. Springer. 2023, pp. 140–160. DOI: https://doi.org/10.1007/978-981-97-1235-9_8.

[11] Rini Wisnu Wardhani, Dedy Septono Catur Putranto, and Howon Kim. “High-and half-degree quantum multiplication for post-quantum security evaluation”. IEEE Access 12 (2024), pp. 8806–8821. DOI: https://doi.org/10.1109/ACCESS.2024.3352157.

[12] Marco Bodrato and Alberto Zanoni. “Integer and polynomial multiplication: Towards optimal Toom-Cook matrices”. Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation. 2007, pp. 17–24. DOI: https://doi.org/10.1145/1277548.1277552.

[13] Zhen Gu and Shuguo Li. “A Division-Free Toom–Cook Multiplication-Based Montgomery Modular Multiplication”. IEEE Transactions on Circuits and Systems II: Express Briefs 66.8 (2018), pp. 1401–1405. DOI: https://doi.org/10.1109/TCSII.2018.2886962.

[14] Marco Bodrato. “Towards optimal Toom-Cook multiplication for univariate and multivariate polynomials in characteristic 2 and 0”. International Workshop on the Arithmetic of Finite Fields. Springer. 2007, pp. 116–133. DOI: https://doi.org/10.1007/978-3-540-73074-3_10.

[15] Steven A. Cuccaro, Thomas G. Draper, Samuel A. Kutin, and David Petrie Moulton. “A new quantum ripple-carry addition circuit”. arXiv preprint quant-ph/0410184 (2004). DOI: https://doi.org/10.48550/arXiv.quant-ph/0410184.

[16] Charles H. Bennett. “Time/space trade-offs for reversible computation”. SIAM Journal on Computing 18.4 (1989), pp. 766–776. DOI: https://doi.org/10.1137/0218053.

[17] Richard Král’ovič. “Time and space complexity of reversible pebbling”. International Conference on Current Trends in Theory and Practice of Computer Science. Springer. 2001, pp. 292–303. DOI: https://doi.org/10.1007/3-540-45627-9_26.

[18] Alex Parent, Martin Roetteler, and Michele Mosca. “Improved reversible and quantum circuits for Karatsuba-based integer multiplication”. 12th Conference on the Theory of Quantum Computation, Communication, and Cryptography (TQC 2017). Springer. 2017, 7:1–7:15. DOI: https://doi.org/10.48550/arXiv.1706.03419.

[19] Matthew Amy. “Algorithms for the optimization of quantum circuits”. MA thesis. University of Waterloo, 2013. URL: http://hdl.handle.net/10012/7818.

[20] Thomas G. Draper, Samuel A. Kutin, Eric M. Rains, and Krysta M. Svore. “A logarithmic-depth quantum carry-lookahead adder”. Quantum Information and Computation 6.4 (2006). DOI: https://doi.org/10.26421/QIC6.4-5-4.

[21] Archimedes Pavlidis and Dimitris Gizopoulos. “Fast quantum modular exponentiation architecture for Shor’s factorization algorithm”. Quantum Information and Computation 14.7 & 8 (2012). DOI: https://doi.org/10.48550/arXiv.1207.0511.

[22] Shane Kepley and Rainer Steinwandt. “Quantum circuits for F2n-multiplication with subquadratic gate count”. Quantum Information Processing 14.7 (2015), pp. 2373–2386. DOI: https://doi.org/10.1007/s11128-015-0993-1.

[23] Iggy van Hoof. “Space-efficient quantum multiplication polynomials for binary finite fields with sub-quadratic Toffoli gate count”. Quantum Information and Computation 20.9&10 (2020), pp. 721–735. DOI: https://doi.org/10.26421/QIC20.9-10-1.

[24] Dedy Septono Catur Putranto, Rini Wisnu Wardhani, Harashta Tatimma Larasati, Janghyun Ji, and Howon Kim. “Depth-optimization of Quantum Cryptanalysis on Binary Elliptic Curves”. IEEE Access (2023). DOI: https://doi.org/10.1109/ACCESS.2023.3273601.




DOI: https://doi.org/10.18860/cauchy.v11i1.41908

Refbacks

  • There are currently no refbacks.


Copyright (c) 2026 Rini Wisnu Wardhani, Dedy Septono Catur Putranto

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Editorial Office
Mathematics Department,
Universitas Islam Negeri Maulana Malik Ibrahim Malang
Gajayana Street 50 Malang, East Java, Indonesia 65144
Faximile (+62) 341 558933
e-mail: cauchy@uin-malang.ac.id

Creative Commons License
CAUCHY: Jurnal Matematika Murni dan Aplikasi is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.