|
|
|
|
Code [GitHub] |
Paper [arXiv] |
Solving systems of linear equations is a cornerstone of computational science but becomes exceedingly challenging as the dimensionality increases.
Quantum algorithms have shown promise in tackling this problem efficiently, offering exponential speedups over classical methods.
However, these quantum advantages are often constrained by the condition number of the matrix in question.
In our recent paper, we propose a novel quantum algorithm inspired by the classical proximal point algorithm (PPA).
This meta-algorithm enhances existing quantum linear system solvers by improving their dependence on the condition number, thereby broadening their applicability to more ill-conditioned problems.
By carefully selecting a parameter
Solving systems of linear equations is essential in numerous applications, from scientific computing to machine learning.
Classical algorithms like Gaussian elimination and iterative methods scale poorly with the problem size, often rendering large-scale problems intractable.
Quantum algorithms offer a potential breakthrough by reducing the dependency on problem dimensions from polynomial to logarithmic, as demonstrated by the Harrow-Hassidim-Lloyd (HHL) algorithm.
Despite this, the performance of quantum algorithms is severely impacted by the condition number
Our approach leverages the classical proximal point algorithm (PPA), a method renowned for improving problem conditioning in optimization tasks. By adapting PPA to the quantum domain, we introduce a framework that enhances the performance of existing quantum linear system solvers. The key innovation lies in modifying the matrix to be inverted, thus reducing the effective condition number and improving convergence rates. This method can be seamlessly integrated with various quantum solvers, providing a versatile tool for tackling a broader class of linear system problems.
The Quantum Linear System Problem (QLSP) aims to prepare a quantum state proportional to the solution vector
The condition number
A proper definition of the QLSP problem is as follows:
We present a novel meta-algorithmic framework that enhances the performance of existing quantum linear system solvers. Our contributions are as follows:
Our approach stands out by directly approximating the solution vector
Our proposed algorithm employs the proximal point algorithm (PPA) to iteratively solve the QLSP.
The core idea is to invert the modified matrix
The convergence rate and error bounds of our algorithm are rigorously analyzed.
By carefully choosing the parameter
We also provide a detailed complexity analysis, showing that our method significantly reduces the dependence on the condition number
In Figure 1, we show how the query complexity scales as a function of the condition number
In Figure 2, we show, based on our theoretical analysis, the breakdown of the “improvement” and the “overhead” for two different QLSP solvers as subroutines.
Our proposed framework significantly alleviates the dependency on the condition number in solving the Quantum Linear System Problem (QLSP). By leveraging the proximal point algorithm (PPA), we introduce a meta-algorithm that enhances the performance of existing quantum solvers, broadening their applicability to more challenging, ill-conditioned problems.
Future work will explore several promising directions:
Our work opens new avenues for research in quantum computing and optimization, providing a robust foundation for developing more advanced algorithms that can tackle a wider range of problems.
This work is supported by NSF CMMI no. 2037545, NSF CAREER award no. 2145629, Welch Foundation Grant #A22-0307, a Microsoft Research Award, an Amazon Research Award, and a Ken Kennedy Aspiring Cluster Research award (Rice K2I).