Quantum Circulant Preconditioner for Linear System of Equations

Abstract

We consider the quantum linear solver for $Ax=b$ with the circulant preconditioner $C$. The main technique is the singular value estimation (SVE) introduced in [I. Kerenidis and A. Prakash, Quantum recommendation system, in ITCS 2017]. However, some modifications of SVE should be made to solve the preconditioned linear system $C^{-1}Ax=C^{-1}b$. Moreover, different from the preconditioned linear system considered in [B. D. Clader, B. C. Jacobs, C. R. Sprouse, Preconditioned quantum linear system algorithm, Phys. Rev. Lett., 2013], the circulant preconditioner is easy to construct and can be directly applied to general dense non-Hermitian cases. The time complexity depends on the condition numbers of $C$ and $C^{-1}A$, as well as the Frobenius norm $\Vert A{\Vert }_F$.

References in corpus (21)

• Quantum algorithm for solving linear systems of equations
• Quantum support vector machine for big data classification
• Quantum principal component analysis
• Quantum fingerprinting
• Quantum random access memory
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum algorithms for supervised and unsupervised machine learning
• Quantum Data Fitting
• Preconditioned quantum linear system algorithm
• A quantum linear system algorithm for dense matrices
• Quantum algorithms and the finite element method
• Quantum Hopfield neural network
• Experimental Quantum Computing to Solve Systems of Linear Equations
• Quantum gradient descent for linear systems and least squares
• Quantum singular value decomposition of non-sparse low-rank matrices
• Experimental realization of quantum algorithm for solving linear systems of equations
• Solving systems of linear equations on a quantum computer
• Solving Systems of Linear Equations with a Superconducting Quantum Processor
• Asymptotic Quantum Algorithm for the Toeplitz Systems
• A quantum algorithm for simulating non-sparse Hamiltonians

Cited by in corpus (13)

• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation
• Quantum Computing and Preconditioners for Hydrological Linear Systems
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• Quantum algorithms for group convolution, cross-correlation, and equivariant transformations
• Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems
• Quantum tensor singular value decomposition with applications to recommendation systems
• On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number
• A quantum-inspired algorithm for approximating statistical leverage scores
• Quantum Realization of the Finite Element Method
• Quantum linear system algorithm with optimal queries to initial state preparation
• Preconditioned Block Encodings for Quantum Linear Systems
• Quantum Algorithm for a Convergent Series of Approximations towards the Exact Solution of the Lowest Eigenstates of a Hamiltonian