Asymptotic quantum algorithm for the Toeplitz systems

Solving the Toeplitz systems, which involves finding the vector $x$ such that $T_{n}x=b$ given an $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 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 \mathrm{poly}(logn))$, where $\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 $\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.