Asymptotic Quantum Algorithm for the Toeplitz Systems

Abstract

Solving the Toeplitz systems, which is to find the vector $x$ such that $T_{n}x=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 {\text{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(\text{poly}(\text{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.

10 pages

References in corpus (8)

• Quantum cryptography: Public key distribution and coin tossing
• Quantum algorithm for solving linear systems of equations
• Quantum random access memory
• Quantum Data Fitting
• A quantum linear system algorithm for dense matrices
• Quantum algorithm and circuit design solving the Poisson equation
• Quantum algorithm for association rules mining
• Efficient quantum circuits for Toeplitz and Hankel matrices

Cited by in corpus (15)

• Variational Quantum algorithm for Poisson equation
• Improved quantum algorithm for A-optimal projection
• Quantum algorithms for anomaly detection using amplitude estimation
• Quantum Circulant Preconditioner for Linear System of Equations
• A brief introduction to quantum algorithms
• Quantum algorithm for Neighborhood Preserving Embedding
• Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra
• Quantum mean centering for block-encoding-based quantum algorithm
• Quantum Alternating Operator Ansatz for Solving the Minimum Exact Cover Problem
• Quantum Algorithm for Unsupervised Anomaly Detection
• Quantum algorithms for group convolution, cross-correlation, and equivariant transformations
• Quantum algorithm for logistic regression
• Bayesian machine learning for Boltzmann machine in quantum-enhanced feature spaces
• Quantum Conditional Random Field
• Preconditioned Block Encodings for Quantum Linear Systems