Abstract We introduce a new quantum optimization algorithm for dense linear programming problems, which can be seen as the quantization of the interior point predictor–corrector algorithm [1] using a quantum linear system algorithm [2]. The (worst case) work complexity of our method is, up to polylogarithmic factors, O ( L n ( n + m ) ‖ M ‖ F ¯ κ ¯ ϵ − 2 ) for n the number of variables in the cost function, m the number of constraints, ϵ −1 the target precision, L the bit length of the input data, ‖ M ‖ F ¯ an upper bound to the Frobenius norm of the linear systems of equations that appear, ‖ M ‖ F , and κ ¯ an upper bound to the condition number κ of those systems of equations. This represents a quantum speed-up in the number n of variables in the cost function with respect to the comparable classical interior point algorithms when the initial matrix of the problem A is dense: if we substitute the quantum part of the algorithm by classical algorithms such as conjugate gradient descent, that would mean the whole algorithm has complexity O ( L n ( n + m ) 2 κ ¯ log ( ϵ − 1 ) ) , or with exact methods, at least O (
Abstract We introduce a new quantum optimization algorithm for dense linear programming problems, which can be seen as the quantization of the interior point predictor–corrector algorithm [1] using a quantum linear system algorithm [2]. The (worst case) work complexity of our method is, up to polylogarithmic factors, O ( L n ( n + m ) ‖ M ‖ F ¯ κ ¯ ϵ − 2 ) for n the number of variables in the cost function, m the number of constraints, ϵ −1 the target precision, L the bit length of the input data, ‖ M ‖ F ¯ an upper bound to the Frobenius norm of the linear systems of equations that appear, ‖ M ‖ F , and κ ¯ an upper bound to the condition number κ of those systems of equations. This represents a quantum speed-up in the number n of variables in the cost function with respect to the comparable classical interior point algorithms when the initial matrix of the problem A is dense: if we substitute the quantum part of the algorithm by classical algorithms such as conjugate gradient descent, that would mean the whole algorithm has complexity O ( L n ( n + m ) 2 κ ¯ log ( ϵ − 1 ) ) , or with exact methods, at least O (
We introduce a new quantum optimization algorithm for dense linear programming problems, which can be seen as the quantization of the interior point predictor-corrector algorithm [1] using a quantum linear system algorithm [2]. The (worst case) work complexity of our method is, up to polylogarithmic factors, O(L root n(n+m)(parallel to M parallel to) over bar (F) (kappa)over bar> over bar epsilon(-2)) for n the number of variables in the cost function,mthe number of constraints,epsilon(-1)the target precision,Lthe bit length of the input data, (parallel to M parallel to) over bar (F) over bar <ian upper bound to the Frobenius norm of the linear systems of equations that appear, <(parallel to M parallel to)over bar>(F), and (kappa) over bar an upper bound to the condition number kappa of those systems of equations. This represents a quantum speed-up in the number n of variables in the cost function with respect to the comparable classical interior point algorithms when the initial matrix of the problem A is dense: if we substitute the quantum part of the algorithm by classical algorithms such as conjugate gradient descent, that would mean the whole algorithm has complexity O(L root n(n + m)(2) (kappa) over bar log(epsilon(-1))), or with exact methods, at least O(L root n(n + m)(2.373)). Also, in contrast with any quantum linear system algorithm, the algorithm described in this article outputs a classical description of the solution vector, and the value of the optimal solution.
The emergence of huge-scale, data-intensive linear optimization (LO) problems in applications such as machine learning has driven the need for more computationally efficient interior point methods (IPMs). While conventional IPMs are polynomial-time algorithms with rapid convergence, their per-iteration cost can be prohibitively high for dense large-scale LO problems. Quantum linear system solvers have shown potential in accelerating the solution of linear systems arising in IPMs. In this work, we introduce a novel almost-exact quantum IPM, where the Newton system is constructed and solved on a quantum computer, while solution updates occur on a classical machine. Additionally, all matrix-vector products are performed on the quantum hardware. This hybrid quantum-classical framework achieves an optimal worst-case scaling of O(n2) for fully dense LO problems. To ensure high precision, despite the limited accuracy of quantum operations, we incorporate iterative refinement techniques both within and outside the proposed IPM iterations. The proposed algorithm has a quantum complexity of O(n1.5κAlog(ε1)) queries to QRAM and O(n2log(ε1)) classical arithmetic operations. Our method outperforms the worst-case complexity of prior classical and quantum IPMs, offering a significant improvement in scalability and computational efficiency.
We present a quantum interior point method (IPM) for semi-definite programs that has a worst-case running time of Õ( n 2.5 / ξ 2 μ κ 3 log(1/ϵ)). The algorithm outputs a pair of matrices ( S,Y ) that have objective value within ϵ of the optimal and satisfy the constraints approximately to error xi. The parameter mu is at most √2 n while kappa is an upper bound on the condition number of the intermediate solution matrices arising in the classical IPM. For the case where κ ≪ n 5/6 , our method provides a significant polynomial speedup over the best-known classical semi-definite program solvers that have a worst-case running time of Õ( n 6 ). For linear programs, our algorithm has a running time of Õ( n 1.5 / ξ 2 μ κ 3 log (1/ϵ)) with the same guarantees and with parameter μ < √2 n . Our technical contributions include an efficient quantum procedure for solving the Newton linear systems arising in the classical IPMs, an efficient pure state tomography algorithm, and an analysis of the IPM where the linear systems are solved approximately. Our results pave the way for the development of quantum algorithms with significant polynomial speedups for applications in optimization and machine learning.
Abstract. We describe a quantum algorithm based on an interior point method for solving a linear program with [Formula: see text] inequality constraints on [Formula: see text] variables. The algorithm explicitly returns a feasible solution that is [Formula: see text]-close to optimal and runs in time [Formula: see text], which is sublinear for tall linear programs (i.e., [Formula: see text]). Our algorithm speeds up the Newton step in the state-of-the-art interior point method of Lee and Sidford [ Solving Linear Programs with Sqrt(rank) Linear System Solves, 2019]. This requires us to efficiently approximate the Hessian and gradient of the barrier function, and these are our main contributions. To approximate the Hessian, we describe a quantum algorithm for the spectral approximation of [Formula: see text] for a tall matrix [Formula: see text]. The algorithm uses leverage score sampling in combination with Grover search and returns a [Formula: see text]-approximation by making [Formula: see text] row queries to [Formula: see text]. This generalizes an earlier quantum speedup for graph sparsification by Apers and de Wolf [ SIAM J. Comput., 51 (2022), pp. 1703–1742]. To approximate the gradient, we use a recent quantum algorithm for multivariate mean estimation by Cornelissen, Hamoudi, and Jerbi [ Near-optimal quantum algorithms for multivariate mean estimation, 2022]. While a naive implementation introduces a dependence on the condition number of the Hessian, we avoid this by preconditioning our random variable using our quantum algorithm for spectral approximation.
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.
Abstract. The use of quantum computing to accelerate complex optimization problems is a burgeoning research field. This paper applies Quantum Linear System Algorithms (QLSAs) to Newton systems within Interior Point Methods (IPMs) to take advantage of quantum speedup in solving Linear Optimization (LO) problems. Due to their inexact nature, QLSAs can be applied only to inexact variants of IPMs. Existing IPMs with inexact Newton directions are infeasible methods due to the inexact nature of their computations. This paper proposes an Inexact-Feasible IPM (IF-IPM) for LO problems, using a novel linear system to generate inexact but feasible steps. We show that this method has [Formula: see text] iteration complexity, analogous to the best exact IPMs, where [Formula: see text] is the number of variables and [Formula: see text] is the binary length of the input data. Moreover, we examine how QLSAs can efficiently solve the proposed system in an iterative refinement (IR) scheme to find the exact solution without excessive calls to QLSAs. We show that the proposed IR-IF-IPM can also be helpful to mitigate the impact of the condition number when a classical iterative method, such as a Conjugate Gradient method or a quantum solver is used at iterations of IPMs. After applying the proposed IF-IPM to the self-dual embedding formulation, we implement it and present illustrative numerical results.