Asymptotic quantum algorithm for the Toeplitz systems

Solving the Toeplitz systems, which involves finding the vector x such that Tₙx=b given an n×n Toeplitz matrix Tₙ 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(κpoly(logn)), where κ and n are the condition number and the dimension of Tₙ, respectively. This implies our algorithm is exponentially faster than its classical counterpart if κ=O(poly(logn)). Since no assumption on the sparseness of Tₙ is demanded in our algorithm, it can serve as an example of quantum algorithms for solving nonsparse linear systems.