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.
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.
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 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. Graph sparsification underlies a large number of algorithms, ranging from approximation algorithms for cut problems to solvers for linear systems in the graph Laplacian. In its strongest form, “spectral sparsification” reduces the number of edges to near-linear in the number of nodes, while approximately preserving the cut and spectral structure of the graph. In this work we demonstrate a polynomial quantum speedup for spectral sparsification and many of its applications. In particular, we give a quantum algorithm that, given a weighted graph with [Formula: see text] nodes and [Formula: see text] edges, outputs a classical description of an [Formula: see text]-spectral sparsifier in sublinear time [Formula: see text]. This contrasts with the optimal classical complexity [Formula: see text]. We also prove that our quantum algorithm is optimal up to polylog-factors. The algorithm builds on a string of existing results on sparsification, graph spanners, quantum algorithms for shortest paths, and efficient constructions for [Formula: see text]-wise independent random strings. Our algorithm implies a quantum speedup for solving Laplacian systems and for approximating a range of cut problems such as min cut and sparsest cut.
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.
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.
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.