Abstract
Solving the Toeplitz systems, which involves finding the vector such that given an Toeplitz matrix and a vector , 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 , where and are the condition number and the dimension of , respectively. This implies our algorithm is exponentially faster than its classical counterpart if . Since no assumption on the sparseness of is demanded in our algorithm, it can serve as an example of quantum algorithms for solving nonsparse linear systems.
- Received 31 January 2018
DOI:https://doi.org/10.1103/PhysRevA.97.062322
©2018 American Physical Society