https://doi.org/10.1140/epjqt/s40507-025-00423-5
Research
Quantum algorithm for polynomial multiplication and its applications
1
School of Artificial Intelligence, Shandong Women’s University, 250300, Jinan, China
2
College of Computer Science and Technology, Beijing University of Technology, 100124, Beijing, China
3
School of Data and Computer Science, Shandong Women’s University, 250300, Jinan, China
4
Business School, Shandong Normal University, 250358, Jinan, China
5
Science and Technology Research Institute, China Three Gorges Corporation, 101199, Beijing, China
6
College of Computer Science and Engineering, Shandong University of Science and Technology, 266590, Qingdao, China
Received:
26
February
2025
Accepted:
22
September
2025
Published online:
15
October
2025
Polynomial multiplication is a fundamental operation in various fields of science and engineering. This paper proposes a quantum algorithm for polynomial multiplication that achieves improved efficiency over classical approaches. The core innovation is the use of a quantum Fourier transform with digital encoding. The practical utility and versatility of this algorithm are highlighted through its application to several related computational problems, including string matching, Toeplitz matrix-vector multiplication, and matrix decomposition algorithm. Furthermore, an enhanced version of the quantum polynomial multiplication algorithm is introduced, offering improvements in both execution process and time complexity.
Key words: Quantum computation / Quantum algorithm / Polynomial multiplication / String matching / Toeplitz matrix-vector multiplication / Matrix decomposition algorithm
© The Author(s) 2025
Open Access This article is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License, which permits any non-commercial use, sharing, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if you modified the licensed material. You do not have permission under this licence to share adapted material derived from this article or parts of it. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by-nc-nd/4.0/.
