Asymptotic Quantum Algorithm for the Toeplitz Systems

Abstract

Solving the Toeplitz systems, which is to find the vector $x$ such that $T_nx = b$givenan$n\times n$Toeplitzmatrix$T_n$andavector$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(\kappa {\text{log}}^{2}n)$, where $\kappa$ and $n$ are the condition number and the dimension of $T_n$ respectively. This implies our algorithm is exponentially faster than the best classical algorithm for the same problem if $\kappa =O(\text{poly}(\text{log}n))$. 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 non-sparse linear systems.