A quantum algorithm for Toeplitz matrix-vector multiplication

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 $\mathcal{O}(\kappa \mathrm{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₁-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.