Asymptotic Quantum Algorithm for the Toeplitz Systems

Solving the Toeplitz systems, which is to find the vector \(x\) such that \(T_nx = 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 To...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2018-02
Main Authors: Lin-Chun, Wan, Chao-Hua, Yu, Shi-Jie, Pan, Gao, Fei, Qiao-Yan, Wen, Su-Juan, Qin
Format: Article
Language:English
Subjects:
Algorithms
Continuity (mathematics)
Linear equations
Linear systems
Mathematical analysis
Matrix algebra
Matrix methods
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Solving the Toeplitz systems, which is to find the vector \(x\) such that \(T_nx = 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\textrm{log}^2 n)\), where \(\kappa\) and \(n\) are the condition number and the dimension of \(T_n\) respectively. This implies our algorithm is exponentially faster than the best classical algorithm for the same problem if \(\kappa=O(\textrm{poly}(\textrm{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 non-sparse linear systems.
ISSN:2331-8422
DOI:10.48550/arxiv.1608.02184