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 X 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(kpoly(log n)), where k 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 k = 0(poly(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 nonsparse linear systems.