Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2311.03215 · SIAM Journal on Computing

Quantum Speedups for Linear Programming via Interior Point Methods

Simon Apers, Sander Gribling

Published Feb 6, 2026• 39 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1137/25m1736098

Related papers

A Quantum Interior Point Method for LPs and SDPs

Iordanis Kerenidis, Anupam Prakash

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.

arXiv:1808.09266•ACM Transactions on Quantum Computing•Oct 2, 2020•115 citations

A quantum interior-point predictor–corrector algorithm for linear programming

P A M Casares, Miguel Angel Martin-Delgado

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 (

arXiv:1902.06749•Journal of Physics A Mathematical and Theoretical•Sep 1, 2020•24 citations

Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving

Simon Apers, Ronald de Wolf

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.

arXiv:1911.07306•SIAM Journal on Computing•Dec 15, 2022•26 citations

An Inexact Feasible Interior Point Method for Linear Optimization with High Adaptability to Quantum Computers

Mohammadhossein Mohammadisiahroudi, Ramin Fakhimi, Zeguan Wu +1 more

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.

arXiv:2307.14445•SIAM Journal on Optimization•Oct 7, 2025•17 citations

An Inexact Feasible Quantum Interior Point Method for Linearly Constrained Quadratic Optimization

Zeguan Wu, Mohammadhossein Mohammadisiahroudi, Brandon Augustino +2 more

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.

arXiv:2301.05357•Entropy•Feb 10, 2023•20 citations

Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma

Fernando G. S. L. Brandão, Alexander M. Dalzell, András Gilyén +1 more

We give the first sublinear-time classical solvers for sparse semidefinite programs in the bounded-radius regime, without low-rank assumptions or Frobenius norm dependence on the constraint matrices. For constant precision and bounded primal and dual radii, prior quantum algorithms of Brandão et al. (2019) and van Apeldoorn and Gilyén (2019) achieved $\widetilde{O}(\sqrt{n}+\sqrt{m})$ dependence on matrix dimension $n$ and constraint number $m$. Compared with the $\widetilde{O}(mn)$ runtime of existing classical methods, this suggests a quartic quantum speedup when $m \approx n$. Beyond a usual Grover speedup, this separation relies on the Quantum OR lemma, whose sample-reuse mechanism decouples the cost of Gibbs-state preparation from constraint search. We show that this reuse mechanism is classically realizable for sparse SDPs. Our main technical contribution is a classical procedure for simultaneously estimating many expectation values with respect to a sparse Hamiltonian's Gibbs state. This combines randomized Lánczos filtering with an efficient sampling-based estimator. We also introduce a stochastic online-learning framework for SDP solving, substantially improving accuracy-dependence over standard oracle-based MMWU approaches. Let $s$ denote the the input matrix sparsity and $γ:=Rr/\varepsilon$ capture dependence on the primal $(R)$ and dual $(r)$ radii as well as target accuracy $(\varepsilon)$. When $γ^2\leq\min\{m,n/s\}$, our solver runs in time $\widetilde{O}\left(nsγ^{4.5}+msγ^2\right)$. For $γ=O(1)$, this is $\widetilde{O}\left((n+m)s\right)$ and sublinear in the $O(mns)$ input size. Similar to the quantum algorithms, this matches known lower bounds with respect to $m$ and $n$, up to logarithmic factors. This implies that, with respect to dimensions $m$ and $n$, there is no super-quadratic quantum advantage for generic sparse SDP solving.

quant-pharXiv:2609.40302•Oct 1, 2026•0 citations
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.
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.
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.
We give the first sublinear-time classical solvers for sparse semidefinite programs in the bounded-radius regime, without low-rank assumptions or Frobenius norm dependence on the constraint matrices. For constant precision and bounded primal and dual radii, prior quantum algorithms of Brandão et al. (2019) and van Apeldoorn and Gilyén (2019) achieved O~(n+m)\widetilde{O}(\sqrt{n}+\sqrt{m})O(n​+m​) dependence on matrix dimension nnn and constraint number mmm. Compared with the O~(mn)\widetilde{O}(mn)O(mn) runtime of existing classical methods, this suggests a quartic quantum speedup when m≈nm \approx nm≈n. Beyond a usual Grover speedup, this separation relies on the Quantum OR lemma, whose sample-reuse mechanism decouples the cost of Gibbs-state preparation from constraint search. We show that this reuse mechanism is classically realizable for sparse SDPs. Our main technical contribution is a classical procedure for simultaneously estimating many expectation values with respect to a sparse Hamiltonian's Gibbs state. This combines randomized Lánczos filtering with an efficient sampling-based estimator. We also introduce a stochastic online-learning framework for SDP solving, substantially improving accuracy-dependence over standard oracle-based MMWU approaches. Let sss denote the the input matrix sparsity and γ:=Rr/εγ:=Rr/\varepsilonγ:=Rr/ε capture dependence on the primal (R)(R)(R) and dual (r)(r)(r) radii as well as target accuracy (ε)(\varepsilon)(ε). When γ2≤min⁡{m,n/s}γ^2\leq\min\{m,n/s\}γ2≤min{m,n/s}, our solver runs in time O~(nsγ4.5+msγ2)\widetilde{O}\left(nsγ^{4.5}+msγ^2\right)O(nsγ4.5+msγ2). For γ=O(1)γ=O(1)γ=O(1), this is O~((n+m)s)\widetilde{O}\left((n+m)s\right)O((n+m)s) and sublinear in the O(mns)O(mns)O(mns) input size. Similar to the quantum algorithms, this matches known lower bounds with respect to mmm and nnn, up to logarithmic factors. This implies that, with respect to dimensions mmm and nnn, there is no super-quadratic quantum advantage for generic sparse SDP solving.