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

Chinese Physics B

A quantum algorithm for Toeplitz matrix-vector multiplication

Shang Gao, Yu-Guang 宇光 Yang 杨

Published Feb 6, 2023• 4 citations
Publisher

Abstract

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.

DOI
10.1088/1674-1056/acb914

Related papers

Quantum Algorithms for the Multiplication of Circulant Matrices and Vectors

Lu Hou, Zhenyu Huang, Chang Lv

This article presents two quantum algorithms for computing the product of a circulant matrix and a vector. The arithmetic complexity of the first algorithm is O(Nlog2N) in most cases. For the second algorithm, when the entries in the circulant matrix and the vector take values in C or R, the complexity is O(Nlog2N) in most cases. However, when these entries take values from positive real numbers, the complexity is reduced to O(log3N) in most cases, which presents an exponential speedup compared to the classical complexity of O(NlogN) for computing the product of a circulant matrix and vector. We apply this algorithm to the convolution calculation in quantum convolutional neural networks, which effectively accelerates the computation of convolutions. Additionally, we present a concrete quantum circuit structure for quantum convolutional neural networks.

Information•Aug 1, 2024•1 citation

Asymptotic quantum algorithm for the Toeplitz systems

Lin‐Chun Wan, Chao‐Hua Yu, Shi‐Jie Pan +3 more

Solving the Toeplitz systems, which involves finding the vector $x$ such that ${T}_{n}x=b$ given an $n\ifmmode\times\else\texttimes\fi{}n$ Toeplitz matrix ${T}_{n}$ and a vector $b$, has a variety of applications in mathematics and engineering. In this paper, we present a quantum algorithm for solving the linear equations of Toeplitz matrices, in which the Toeplitz matrices are generated by discretizing a continuous function. It is shown that our algorithm's complexity is nearly $O(\ensuremath{\kappa}\mathrm{poly}(logn))$, where $\ensuremath{\kappa}$ and $n$ are the condition number and the dimension of ${T}_{n}$, respectively. This implies our algorithm is exponentially faster than its classical counterpart if $\ensuremath{\kappa}=O(\mathrm{poly}(logn))$. Since no assumption on the sparseness of ${T}_{n}$ is demanded in our algorithm, it can serve as an example of quantum algorithms for solving nonsparse linear systems.

arXiv:1608.02184•Physical Review A•Jun 15, 2018•57 citations

Quantum Algorithm for the Toeplitz Systems

Lin‐Chun Wan, Chao‐Hua Yu, Shi‐Jie Pan +2 more

Solving the Toeplitz systems, which is to find the vector $x$ such that $T_nx = b$ given a $n\times n$ Toeplitz matrix $T_n$ and a vector $b$, has a variety of applications in mathematics and engineering. In this paper, we present a quantum algorithm for solving the Toeplitz systems, in which a quantum state encoding the solution with error $\epsilon$ is generated. It is shown that our algorithm's complexity is nearly linear in the condition number, and polylog in the dimensions $n$ and in the inverse error $\epsilon^{-1}$. This implies our algorithm is exponentially faster than the best classical algorithm for the same problem if the condition number of $T_n$ is $O(\textrm{poly}(\textrm{log}\,n))$. Since no assumption on the sparseness of $T_n$ is demanded in our algorithm, the algorithm can serve as an example of quantum algorithms for solving non-sparse linear systems.

•Aug 7, 2016•1 citation

Quantum algorithm for polynomial multiplication and its applications

Shang Bing Gao, Rui‐Chen Huang, Bing‐Xin Liu +6 more

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.

EPJ Quantum Technology•Oct 15, 2025•0 citations

Quantum Algorithms for Modulated Circulant Matrix Vector Multiplication

Kimy Agudelo, Aldo Quelopana Cristina Manzaneda

Modulated circulant matrices form a special class of N-parametric circulant matrices, recently introduced in the literature, with a structured spectral decomposition based on a Vandermonde type basis. Motivated by this definition, in this work we define the Modulated Quantum Fourier Transform (MQFT), a quantum primitive tailored to this matrix family.

quant-pharXiv:2606.09618•Jun 9, 2026•0 citations

Efficient quantum circuits for dense and non-unitary operators

Sisi Zhou, J. B. Wang

Circulant matrices are an important family of operators, which have a wide range of applications in science and engineering related fields. They are in general non-sparse and non-unitary. In this paper, we present efficient quantum circuits to implement circulant operators using fewer resources and with lower complexity than existing methods. Moreover, our quantum circuits can be readily extended to the implementation of Toeplitz, Hankel, and block circulant matrices. Efficient quantum algorithms to implement the inverses and products of circulant operators are also provided.

arXiv:1607.07149•Jul 25, 2016•2 citations
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.
This article presents two quantum algorithms for computing the product of a circulant matrix and a vector. The arithmetic complexity of the first algorithm is O(Nlog2N) in most cases. For the second algorithm, when the entries in the circulant matrix and the vector take values in C or R, the complexity is O(Nlog2N) in most cases. However, when these entries take values from positive real numbers, the complexity is reduced to O(log3N) in most cases, which presents an exponential speedup compared to the classical complexity of O(NlogN) for computing the product of a circulant matrix and vector. We apply this algorithm to the convolution calculation in quantum convolutional neural networks, which effectively accelerates the computation of convolutions. Additionally, we present a concrete quantum circuit structure for quantum convolutional neural networks.
Solving the Toeplitz systems, which involves finding the vector xxx such that Tnx=b{T}_{n}x=bTn​x=b given an $n\ifmmode\times\else\texttimes\fi{}n$ Toeplitz matrix Tn{T}_{n}Tn​ and a vector bbb, has a variety of applications in mathematics and engineering. In this paper, we present a quantum algorithm for solving the linear equations of Toeplitz matrices, in which the Toeplitz matrices are generated by discretizing a continuous function. It is shown that our algorithm's complexity is nearly $O(\ensuremath{\kappa}\mathrm{poly}(logn))$, where $\ensuremath{\kappa}$ and nnn are the condition number and the dimension of Tn{T}_{n}Tn​, respectively. This implies our algorithm is exponentially faster than its classical counterpart if $\ensuremath{\kappa}=O(\mathrm{poly}(logn))$. Since no assumption on the sparseness of Tn{T}_{n}Tn​ is demanded in our algorithm, it can serve as an example of quantum algorithms for solving nonsparse linear systems.
Solving the Toeplitz systems, which is to find the vector xxx such that Tnx=bT_nx = bTn​x=b given a n×nn\times nn×n Toeplitz matrix TnT_nTn​ and a vector bbb, has a variety of applications in mathematics and engineering. In this paper, we present a quantum algorithm for solving the Toeplitz systems, in which a quantum state encoding the solution with error ϵ\epsilonϵ is generated. It is shown that our algorithm's complexity is nearly linear in the condition number, and polylog in the dimensions nnn and in the inverse error ϵ−1\epsilon^{-1}ϵ−1. This implies our algorithm is exponentially faster than the best classical algorithm for the same problem if the condition number of TnT_nTn​ is O(poly(log n))O(\textrm{poly}(\textrm{log}\,n))O(poly(logn)). Since no assumption on the sparseness of TnT_nTn​ is demanded in our algorithm, the algorithm can serve as an example of quantum algorithms for solving non-sparse linear systems.
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.
Circulant matrices are an important family of operators, which have a wide range of applications in science and engineering related fields. They are in general non-sparse and non-unitary. In this paper, we present efficient quantum circuits to implement circulant operators using fewer resources and with lower complexity than existing methods. Moreover, our quantum circuits can be readily extended to the implementation of Toeplitz, Hankel, and block circulant matrices. Efficient quantum algorithms to implement the inverses and products of circulant operators are also provided.