Quantum Circuit Design of Toom 3-Way Multiplication
Source abstract
Abstract
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.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Quantum Computing Algorithms and Architecture · Low-power high-performance VLSI design · Coding theory and cryptography
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
School of Computer Science and Engineering, Pusan National University, Busan 609735, Korea
School of Electrical Engineering and Informatics, Institut Teknologi Bandung, Bandung 40116, Indonesia
Funding
Ministry of Science and ICT, South Korea
References (45)
Show source-provided references
1. Quantum arithmetic circuits: A survey10.1587/transfun.E92.A.1276 ↗
2. Quantum networks for elementary arithmetic operations10.1103/PhysRevA.54.147 ↗
3. Shor, P.W. (1994, January 20–22). Algorithms for quantum computation: Discrete logarithms and factoring. Proceedings of the 35th annual symposium on foundations of computer science, Santa Fe, NM, USA.
4. Rines, R., and Chuang, I. (2018). High performance quantum modular multipliers. arXiv.
5. Markov, I.L., and Saeedi, M. (2012). Constant-optimized quantum circuits for modular multiplication and exponentiation. arXiv.10.26421/QIC12.5-6-1 ↗
6. Efficient networks for quantum factoring10.1103/PhysRevA.54.1034 ↗
7. Beauregard, S. (2002). Circuit for Shor’s algorithm using 2n + 3 qubits. arXiv.10.26421/QIC3.2-8 ↗
8. Parent, A., Roetteler, M., and Mosca, M. (2017). Improved reversible and quantum circuits for Karatsuba-based integer multiplication. arXiv.
9. Childs, A.M., Schulman, L.J., and Vazirani, U.V. (2007, January 21–23). Quantum algorithms for hidden nonlinear structures. Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), Providence, RI, USA.10.1109/FOCS.2007.18 ↗
10. Cleve, R., and Watrous, J. (2000, January 12–14). Fast parallel circuits for the quantum Fourier transform. Proceedings of the 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, CA, USA.
11. Quantum circuits for Toom-Cook multiplication10.1103/PhysRevA.98.012311 ↗
12. Amy, M. (2013). Algorithms for the optimization of quantum circuits. [Master’s Thesis, University of Waterloo].
13. Reversible Karatsuba’s Algorithm
14. Multiplication of many-digital numbers by automatic computers
15. The complexity of a scheme of functional elements realizing the multiplication of integers
16. On the minimum computation time of functions10.1090/S0002-9947-1969-0249212-8 ↗
17. Time/space trade-offs for reversible computation10.1137/0218053 ↗
18. A Division-Free Toom–Cook Multiplication-Based Montgomery Modular Multiplication
19. Granlund, T. (2014). The GMP Development Team. The GNU Multiple Precision Arithmetic Library Manual, The GMP Development Team.
20. Khosropour, A., Aghababa, H., and Forouzandeh, B. (2011, January 11–13). Quantum division circuit based on restoring division algorithm. Proceedings of the 2011 Eighth International Conference on Information Technology: New Generations, Las Vegas, NV, USA.10.1109/ITNG.2011.177 ↗
21. Dibbo, S.V., Babu, H.M.H., and Jamal, L. (2016, January 22–25). An efficient design technique of a quantum divider circuit. Proceedings of the 2016 IEEE International Symposium on Circuits and Systems (ISCAS), Montreal, QC, Canada.10.1109/ISCAS.2016.7538994 ↗
22. Thapliyal, H., Munoz-Coreas, E., Varun, T., and Humble, T. (2019). Quantum circuit designs of integer division optimizing T-count and T-depth. IEEE Trans. Emerg. Top. Comput.
23. Jamal, L., and Babu, H.M.H. (2013, January 19–23). Efficient approaches to design a reversible floating point divider. Proceedings of the 2013 IEEE International Symposium on Circuits and Systems (ISCAS), Beijing, China.10.1109/ISCAS.2013.6572511 ↗
24. Fast Quantum Modular Exponentiation Architecture for Shor’s Factoring Algorithm10.26421/QIC14.7-8-8 ↗
25. Bodrato, M. (2007). Towards optimal Toom-Cook multiplication for univariate and multivariate polynomials in characteristic 2 and 0. International Workshop on the Arithmetic of Finite Fields, Springer.10.1007/978-3-540-73074-3_10 ↗
26. Proos, J., and Zalka, C. (2003). Shor’s discrete logarithm quantum algorithm for elliptic curves. arXiv Prepr.10.26421/QIC3.4-3 ↗
27. Roetteler, M., Naehrig, M., Svore, K.M., and Lauter, K. (2017). Quantum resource estimates for computing elliptic curve discrete logarithms. International Conference on the Theory and Application of Cryptology and Information Security, Springer.10.1007/978-3-319-70697-9_9 ↗
28. Häner, T., Jaques, S., Naehrig, M., Roetteler, M., and Soeken, M. (2020). Improved quantum circuits for elliptic curve discrete logarithms. International Conference on Post-Quantum Cryptography, Springer.10.1007/978-3-030-44223-1_23 ↗
29. Cuccaro, S.A., Draper, T.G., Kutin, S.A., and Moulton, D.P. (2004). A new quantum ripple-carry addition circuit. arXiv.
30. Van Hoof, I. (2019). Space-efficient quantum multiplication of polynomials for binary finite fields with sub-quadratic Toffoli gate count. arXiv.10.26421/QIC20.9-10-1 ↗
31. Bodrato, M., and Zanoni, A. (2006). What About Toom-Cook Matrices Optimality, Centro “Vito Volterra” Università di Roma Tor Vergata.
32. Knuth, D.E. (2014). Art of Computer Programming, Volume 2: Seminumerical Algorithms, Addison-Wesley Professional.
33. Chung, J., and Hasan, M.A. (2007, January 25–27). Asymmetric squaring formulae. Proceedings of the 18th IEEE Symposium on Computer Arithmetic (ARITH’07), Montpellier, France.10.1109/ARITH.2007.11 ↗
34. Circuit depth reduction for gate-model quantum computers10.1038/s41598-020-67014-5 ↗
35. Preskill, J. (2015). Lecture Notes for Ph219/CS219: Quantum Information and Computation Chapter 5, California Institute of Technology.
36. Quantum addition circuits and unbounded fan-out
37. Draper, T.G. (2000). Addition on a quantum computer. arXiv Prepr.
38. Optimal number of controlled-NOT gates to generate a three-qubit state10.1103/PhysRevA.77.032320 ↗
39. Fault-tolerant quantum computation with few qubits10.1038/s41534-018-0085-z ↗
40. Integer division using reciprocals10.1109/ARITH.1991.145558 ↗
41. Shende, V.V., and Markov, I.L. (2008). On the CNOT-cost of TOFFOLI gates. arXiv.
42. Jang, K., Choi, S., Kwon, H., Kim, H., Park, J., and Seo, H. (2020). Grover on Korean Block Ciphers. Appl. Sci., 10.10.3390/app10186407 ↗
43. Abdessaied, N., Amy, M., Soeken, M., and Drechsler, R. (2016, January 18–20). Technology mapping of reversible circuits to Clifford+ T quantum circuits. Proceedings of the 2016 IEEE 46th international symposium on multiple-valued logic (ISMVL), Sapporo, Japan.10.1109/ISMVL.2016.33 ↗
44. Time and space complexity of reversible pebbling10.1051/ita:2004008 ↗
45. High-speed ECC processor over NIST prime fields applied with Toom–Cook multiplication10.1109/TCSI.2018.2878598 ↗