Quantum computing has the potential to speed up machine learning methods. One major direction is using quantum linear algebra to solve linear system problems or optimization problems in the machine learning area. Quantum approaches in the literature for different types of least squares problems demonstrate speedups w.r.t. dimension but have disadvantages w.r.t. precision and condition number. In this paper, we discuss how an iterative refinement scheme can deliver an accurate solution without the excessive cost of Quantum Linear System Algorithms (QLSAs). In addition, we propose an adaptive regularization approach that can mitigate the effect of condition number on solution time. In the second part of this paper, we investigate how state-of-the-art Quantum Interior Point Methods (QIPMs) can solve more sophisticated regression problems such as Lasso regression and support vector machine problems, which can be reformulated as quadratic optimization problems.
Quantum computing has the potential to speed up machine learning methods. One major direction is using quantum linear algebra to solve linear system problems or optimization problems in the machine learning area. Quantum approaches in the literature for different types of least squares problems demonstrate speedups w.r.t. dimension but have disadvantages w.r.t. precision and condition number. In this paper, we discuss how an iterative refinement scheme can deliver an accurate solution without the excessive cost of Quantum Linear System Algorithms (QLSAs). In addition, we propose an adaptive regularization approach that can mitigate the effect of condition number on solution time. In the second part of this paper, we investigate how state-of-the-art Quantum Interior Point Methods (QIPMs) can solve more sophisticated regression problems such as Lasso regression and support vector machine problems, which can be reformulated as quadratic optimization problems.
Quantum computing has attracted significant interest in the optimization community because it potentially can solve classes of optimization problems faster than conventional supercomputers. Several researchers proposed quantum computing methods, especially Quantum Interior Point Methods (QIPMs), to solve convex optimization problems, such as Linear Optimization, Semidefinite Optimization, and Second-order Cone Optimization problems. Most of them have applied a Quantum Linear System Algorithm at each iteration to compute a Newton step. However, using quantum linear solvers in QIPMs comes with many challenges, such as having ill-conditioned systems and the considerable error of quantum solvers. This paper investigates how one can efficiently use quantum linear solvers in QIPMs. Accordingly, an Inexact Infeasible Quantum Interior Point Method is developed to solve linear optimization problems. We also discuss how we can get an exact solution by Iterative Refinement without excessive time of quantum solvers. Finally, computational results with a QISKIT implementation of our QIPM using quantum simulators are analyzed.
The growing demand for solving large-scale, data-intensive linear and conic optimization problems, particularly in applications such as artificial intelligence and machine learning, has highlighted the limitations of classical interior point methods (IPMs). Despite their favorable polynomial-time convergence, conventional IPMs often suffer from high per-iteration computational costs, especially for dense problem instances. Recent advances in quantum computing, particularly quantum linear system solvers, offer promising avenues to accelerate the most computationally intensive steps of IPMs. However, practical challenges such as quantum error, hardware noise, and sensitivity to poorly conditioned systems remain significant obstacles. In response, a series of Quantum IPMs (QIPMs) has been developed to address these challenges, incorporating techniques such as feasibility maintenance, iterative refinement, and preconditioning. In this work, we review this line of research with a focus on our recent contributions, including an almost-exact QIPM framework. This hybrid quantum-classical approach constructs and solves the Newton system entirely on a quantum computer, while performing solution updates classically. Crucially, all matrix-vector operations are executed on quantum hardware, enabling the method to achieve an optimal worst-case scalability w.r.t dimension, surpassing the scalability of existing classical and quantum IPMs.
Quantum linear system algorithms (QLSAs) have the potential to speed up Interior Point Methods (IPMs). However, a major bottleneck is the inexactness of quantum tomography to extract classical solutions from quantum states. In addition, QLSAs are sensitive to the condition number, and this sensitivity is exacerbated when the Newton systems arising in IPMs converge to a singular matrix. Recently, an Inexact Feasible Quantum IPM (IF-QIPM) has been developed that addresses the inexactness of QLSAs. However, this method requires a large number of gates and qubits to be implemented. Here, we propose a new IF-QIPM using the normal equation system, which requires fewer gates and qubits. To mitigate the sensitivity to the condition number and other input data-related parameters, we use preconditioning coupled with iterative refinement to obtain better complexity. Finally, we demonstrate the effectiveness of our approach on IBM Qiskit simulators.
Quantum linear system algorithms (QLSAs) have the potential to speed up algorithms that rely on solving linear systems. Interior point methods (IPMs) yield a fundamental family of polynomial-time algorithms for solving optimization problems. IPMs solve a Newton linear system at each iteration to compute the search direction; thus, QLSAs can potentially speed up IPMs. Due to the noise in contemporary quantum computers, quantum-assisted IPMs (QIPMs) only admit an inexact solution to the Newton linear system. Typically, an inexact search direction leads to an infeasible solution, so, to overcome this, we propose an inexact-feasible QIPM (IF-QIPM) for solving linearly constrained quadratic optimization problems. We also apply the algorithm to ℓ1-norm soft margin support vector machine (SVM) problems, and demonstrate that our algorithm enjoys a speedup in the dimension over existing approaches. This complexity bound is better than any existing classical or quantum algorithm that produces a classical solution.
The growing demand for solving large-scale, data-intensive linear and conic optimization problems, particularly in applications such as arti?cial intelligence and machine learning, has highlighted the limitations of classical interior point methods (IPMs). Despite their favorable polynomial-time convergence, conventional IPMs often su!er from high per-iteration computational costs, especially for dense problem instances. Recent advances in quantum computing, particularly quantum linear system solvers, o!er promising avenues to accelerate the most computationally intensive steps of IPMs. However, practical challenges such as quantum error, hardware noise, and sensitivity to poorly conditioned systems remain signi?cant obstacles. In response, a series of Quantum IPMs (QIPMs) has been developed to address these challenges, incorporating techniques such as feasibility maintenance, iterative re?nement, and preconditioning. In this work, we review this line of research with a focus on our recent contributions, including an almost-exact QIPM framework. This hybrid quantum-classical approach constructs and solves the Newton system entirely on a quantum computer, while performing solution updates classically. Crucially, all matrix-vector operations are executed on quantum hardware, enabling the method to achieve an optimal worstcase scalability w.r.t dimension, surpassing the scalability of existing classical and quantum IPMs.
Regression is a cornerstone of statistics and machine learning, with applications spanning science, engineering, and economics. While quantum algorithms for regression have attracted considerable attention, most existing work has focused on linear regression, leaving many more complex yet practically important variants unexplored. In this work, we present a unified quantum framework for accelerating a broad class of regression tasks -- including linear and multiple regression, Lasso, Ridge, Huber, ℓp-, and δp-type regressions -- achieving up to a quadratic improvement in the number of samples m over the best classical algorithms. This speedup is achieved by extending the recent classical breakthrough of Jambulapati et al. (STOC'24) using several quantum techniques, including quantum leverage score approximation (Apers &Gribling, 2024) and the preparation of many copies of a quantum state (Hamoudi, 2022). For problems of dimension n, sparsity r<n, and error parameter ε, our algorithm solves the problem in O(rmn/ε+poly(n,1/ε)) quantum time, demonstrating both the applicability and the efficiency of quantum computing in accelerating regression tasks.