Asymptotic quantum algorithm for the Toeplitz systems
Lin‐Chun Wan, Chao‐Hua Yu, Shi‐Jie Pan, Fei Gao, Qiaoyan Wen, Su‐Juan Qin · Physical Review A · 2018
Solving the Toeplitz systems, which involves finding the vector $x$ such that ${T}_{n}x=b$ given an $n\ifmmode\times\else\texttimes\fi{}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(\ensuremath{\kappa}\mathrm{poly}(logn))$, where $\ensuremath{\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 $\ensuremath{\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.