Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

EPJ Quantum Technology

Quantum algorithm for polynomial multiplication and its applications

Shang Bing Gao, Rui‐Chen Huang, Bing‐Xin Liu, Zhenwen Cheng, Honglin Xie, Zhong-Xiang Zhang, Z.P. Zhang, Guang‐Bao Xu, Yu‐Guang Yang

Published Oct 15, 2025• 0 citations
Publisher

Abstract

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.

DOI
10.1140/epjqt/s40507-025-00423-5

Related papers

A quantum algorithm for Toeplitz matrix-vector multiplication

Shang Gao, Yu-Guang 宇光 Yang 杨

Toeplitz matrix-vector multiplication is widely used in various fields, including optimal control, systolic finite field multipliers, multidimensional convolution, etc. In this paper, we first present a non-asymptotic quantum algorithm for Toeplitz matrix-vector multiplication with time complexity O ( κ polylog n ) , where κ and 2n are the condition number and the dimension of the circulant matrix extended from the Toeplitz matrix, respectively. For the case with an unknown generating function, we also give a corresponding non-asymptotic quantum version that eliminates the dependency on the L 1-norm ρ of the displacement of the structured matrices. Due to the good use of the special properties of Toeplitz matrices, the proposed quantum algorithms are sufficiently accurate and efficient compared to the existing quantum algorithms under certain circumstances.

Chinese Physics B•Feb 6, 2023•4 citations

Scalable Quantum Computational Science: A Perspective from Block-Encodings and Polynomial Transformations

Kevin J. Joven, Elin Ranjan Das, Joel Bierman +3 more

Significant developments made in quantum hardware and error correction recently have been driving quantum computing towards practical utility. However, gaps remain between abstract quantum algorithmic development and practical applications in computational sciences. In this Perspective article, we propose several properties that scalable quantum computational science methods should possess. We further discuss how block-encodings and polynomial transformations can potentially serve as a unified framework with the desired properties. Recent advancements on these topics are presented including construction and assembly of block-encodings, and various generalizations of quantum signal processing (QSP) algorithms to perform polynomial transformations. The scalability of QSP methods on parallel and distributed quantum architectures is also highlighted. Promising applications in simulation and observable estimation in chemistry, physics, and optimization problems are presented. We hope this Perspective serves as a gentle introduction of state-of-the-art quantum algorithms to the computational science community, and inspires future development on scalable quantum computational science methodologies that bridge theory and practice.

quant-pharXiv:2511.16738•APL Computational Physics•Nov 24, 2025•2 citations

Core Claim: This paper presents a novel approach to matrix multiplication based on quantum fields, leveraging the unique properties of quantum fields to accelerate computation and enhance algorithmic efficiency.

Jincheng Zhang

Matrix multiplication is a fundamental operation in various fields, from linear algebra to computer graphics. However, traditional methods often suffer from computational bottlenecks when dealing with large matrices, limiting their applicability. This paper introduces a new algorithm employing quantum fields to significantly enhance matrix multiplication efficiency. The core of this approach lies in applying quantum fields to the matrix operations, utilizing their inherent properties to optimize the computation process. We explore a method that dynamically adjusts the quantum field parameters based on the matrix being multiplied, leading to improved convergence and computational speed. The research presented herein demonstrates the effectiveness of this technique through extensive simulations and preliminary analysis. This advancement promises to unlock new possibilities in matrix calculations, particularly for large-scale applications, and offers a viable alternative to conventional methods.

•Sep 7, 2026•0 citations

Core Claim: Develop a quantum spin-based non-symmetric matrix multiplication algorithm capable of efficiently handling matrices with non-symmetric properties, exhibiting adaptive computational efficiency.

Jincheng Zhang

The efficient computation of matrices, particularly those with non-symmetric properties, remains a significant challenge in various scientific and engineering fields. This paper presents a novel quantum spin-based matrix multiplication algorithm designed to address this challenge. We introduce a dynamic adjustment mechanism leveraging the intrinsic self-adaptivity of quantum spin systems to optimize the matrix multiplication process. The algorithm's core mechanism involves a carefully designed quantum circuit that adapts the matrix multiplication operation based on the specific characteristics of the input matrix. This adaptive approach significantly enhances computational efficiency, offering a potential breakthrough in matrix multiplication performance. We demonstrate the effectiveness of this algorithm through theoretical analysis and preliminary experimental validation, highlighting its ability to outperform traditional approaches in certain scenarios. The research explores the potential of quantum spin systems to provide a fundamentally new paradigm in matrix multiplication, offering a promising pathway toward more efficient and scalable computations.

•Sep 6, 2026•0 citations

Quantum algorithm for vector set orthogonal normalization and matrix QR decomposition with polynomial speedup

Zi-Ming Li, Yu-xi Liu

Vector set orthogonal normalization and matrix QR decomposition are fundamental problems in matrix analysis with important applications in many fields. We know that the Gram-Schmidt process is a widely used method to solve these two problems. However, existing methods, including the Gram-Schmidt process, have problems of high complexity, scaling $O({N}^{3})$ in the system dimension $N$, which leads to difficulties when calculating large-scale or ill-conditioned problems. With the development of quantum information processing, a series of quantum algorithms have been proposed, providing advantages and speedups over classical algorithms in many fields. In this paper we propose quantum algorithms to solve these two problems based on the idea of the Gram-Schmidt process and quantum phase estimation. The complexity of proposed quantum algorithms is theoretically and numerically analyzed. We find that our algorithms provide polynomial acceleration over the best-known quantum algorithms and a potential polynomial acceleration over the best-known classical algorithms on these two problems, scaling $O({N}^{2}\mathrm{poly}(logN))$ in the dimension $N$ of the system when ignoring the complexity of state readout or $O({N}^{2}\mathrm{poly}(logN))$ when considering the complexity of state readout.

arXiv:2412.19090•Physical Review A•Aug 11, 2025•1 citation

基于量子计算的非对称矩阵乘法算法

Jincheng Zhang

This paper presents a novel quantum algorithm for matrix multiplication, leveraging quantum superposition and entanglement to achieve significantly enhanced computational speed and quantum advantage compared to classical methods. We propose a unique approach to matrix multiplication based on the quantum state representation of matrices, employing quantum entanglement to dramatically reduce the computational complexity inherent in traditional matrix multiplication. The algorithm demonstrates potential for high-throughput matrix operations, offering a substantial improvement in performance for computationally intensive tasks, particularly within the fields of machine learning and image processing. The proposed method offers a fundamentally new perspective on matrix multiplication, potentially ushering in a new era of quantum computing.

•Sep 2, 2026•0 citations
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.
Toeplitz matrix-vector multiplication is widely used in various fields, including optimal control, systolic finite field multipliers, multidimensional convolution, etc. In this paper, we first present a non-asymptotic quantum algorithm for Toeplitz matrix-vector multiplication with time complexity O ( κ polylog n ) , where κ and 2n are the condition number and the dimension of the circulant matrix extended from the Toeplitz matrix, respectively. For the case with an unknown generating function, we also give a corresponding non-asymptotic quantum version that eliminates the dependency on the L 1-norm ρ of the displacement of the structured matrices. Due to the good use of the special properties of Toeplitz matrices, the proposed quantum algorithms are sufficiently accurate and efficient compared to the existing quantum algorithms under certain circumstances.
Significant developments made in quantum hardware and error correction recently have been driving quantum computing towards practical utility. However, gaps remain between abstract quantum algorithmic development and practical applications in computational sciences. In this Perspective article, we propose several properties that scalable quantum computational science methods should possess. We further discuss how block-encodings and polynomial transformations can potentially serve as a unified framework with the desired properties. Recent advancements on these topics are presented including construction and assembly of block-encodings, and various generalizations of quantum signal processing (QSP) algorithms to perform polynomial transformations. The scalability of QSP methods on parallel and distributed quantum architectures is also highlighted. Promising applications in simulation and observable estimation in chemistry, physics, and optimization problems are presented. We hope this Perspective serves as a gentle introduction of state-of-the-art quantum algorithms to the computational science community, and inspires future development on scalable quantum computational science methodologies that bridge theory and practice.
Matrix multiplication is a fundamental operation in various fields, from linear algebra to computer graphics. However, traditional methods often suffer from computational bottlenecks when dealing with large matrices, limiting their applicability. This paper introduces a new algorithm employing quantum fields to significantly enhance matrix multiplication efficiency. The core of this approach lies in applying quantum fields to the matrix operations, utilizing their inherent properties to optimize the computation process. We explore a method that dynamically adjusts the quantum field parameters based on the matrix being multiplied, leading to improved convergence and computational speed. The research presented herein demonstrates the effectiveness of this technique through extensive simulations and preliminary analysis. This advancement promises to unlock new possibilities in matrix calculations, particularly for large-scale applications, and offers a viable alternative to conventional methods.
The efficient computation of matrices, particularly those with non-symmetric properties, remains a significant challenge in various scientific and engineering fields. This paper presents a novel quantum spin-based matrix multiplication algorithm designed to address this challenge. We introduce a dynamic adjustment mechanism leveraging the intrinsic self-adaptivity of quantum spin systems to optimize the matrix multiplication process. The algorithm's core mechanism involves a carefully designed quantum circuit that adapts the matrix multiplication operation based on the specific characteristics of the input matrix. This adaptive approach significantly enhances computational efficiency, offering a potential breakthrough in matrix multiplication performance. We demonstrate the effectiveness of this algorithm through theoretical analysis and preliminary experimental validation, highlighting its ability to outperform traditional approaches in certain scenarios. The research explores the potential of quantum spin systems to provide a fundamentally new paradigm in matrix multiplication, offering a promising pathway toward more efficient and scalable computations.
Vector set orthogonal normalization and matrix QR decomposition are fundamental problems in matrix analysis with important applications in many fields. We know that the Gram-Schmidt process is a widely used method to solve these two problems. However, existing methods, including the Gram-Schmidt process, have problems of high complexity, scaling O(N3)O({N}^{3})O(N3) in the system dimension NNN, which leads to difficulties when calculating large-scale or ill-conditioned problems. With the development of quantum information processing, a series of quantum algorithms have been proposed, providing advantages and speedups over classical algorithms in many fields. In this paper we propose quantum algorithms to solve these two problems based on the idea of the Gram-Schmidt process and quantum phase estimation. The complexity of proposed quantum algorithms is theoretically and numerically analyzed. We find that our algorithms provide polynomial acceleration over the best-known quantum algorithms and a potential polynomial acceleration over the best-known classical algorithms on these two problems, scaling O(N2poly(logN))O({N}^{2}\mathrm{poly}(logN))O(N2poly(logN)) in the dimension NNN of the system when ignoring the complexity of state readout or O(N2poly(logN))O({N}^{2}\mathrm{poly}(logN))O(N2poly(logN)) when considering the complexity of state readout.
This paper presents a novel quantum algorithm for matrix multiplication, leveraging quantum superposition and entanglement to achieve significantly enhanced computational speed and quantum advantage compared to classical methods. We propose a unique approach to matrix multiplication based on the quantum state representation of matrices, employing quantum entanglement to dramatically reduce the computational complexity inherent in traditional matrix multiplication. The algorithm demonstrates potential for high-throughput matrix operations, offering a substantial improvement in performance for computationally intensive tasks, particularly within the fields of machine learning and image processing. The proposed method offers a fundamentally new perspective on matrix multiplication, potentially ushering in a new era of quantum computing.