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

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

Pablo A. M. Casares, Martín Delgado, Miguel Ángel

Published Nov 6, 2020• 14 citations
OpenAlex

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 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.

Related papers

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

P A M Casares, M A 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•15 citations

Optimal Scaling Quantum Interior Point Method for Linear Optimization

Mohammadhossein Mohammadisiahroudi, Zeguan Wu, Pouya Sampourmahani +2 more

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 $\mathcal{O}(n^2)$ 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 $\mathcal{O}(n^{1.5} κ_A \log(\frac{1}ε))$ queries to QRAM and $\mathcal{O}(n^2 \log(\frac{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.

quant-pharXiv:2512.04510•IEEE International Conference on Quantum Computing and Engineering (QCE)•Dec 5, 2025•0 citations

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•95 citations

Quantum Speedups for Linear Programming via Interior Point Methods

Simon Apers, Sander Gribling

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.

arXiv:2311.03215•SIAM Journal on Computing•Feb 6, 2026•3 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•8 citations

Quantum Linear System Algorithm for Dense Matrices

Leonard Wossnig, Zhikuan Zhao, Anupam Prakash

Solving linear systems of equations is a frequently encountered problem in machine learning and optimization. Given a matrix $A$ and a vector $\mathbf{b}$ the task is to find the vector $\mathbf{x}$ such that $A\mathbf{x}=\mathbf{b}$. We describe a quantum algorithm that achieves a sparsity-independent runtime scaling of $\mathcal{O}\mathbf{(}{\ensuremath{\kappa}}^{2}\sqrt{n}\text{polylog}(n)/\ensuremath{\epsilon}\mathbf{)}$ for an $n\ifmmode\times\else\texttimes\fi{}n$ dimensional $A$ with bounded spectral norm, where $\ensuremath{\kappa}$ denotes the condition number of $A$, and $\ensuremath{\epsilon}$ is the desired precision parameter. This amounts to a polynomial improvement over known quantum linear system algorithms when applied to dense matrices, and poses a new state of the art for solving dense linear systems on a quantum computer. Furthermore, an exponential improvement is achievable if the rank of $A$ is polylogarithmic in the matrix dimension. Our algorithm is built upon a singular value estimation subroutine, which makes use of a memory architecture that allows for efficient preparation of quantum states that correspond to the rows of $A$ and the vector of Euclidean norms of the rows of $A$.

arXiv:1704.06174•Physical Review Letters•Jan 31, 2018•222 citations
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 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 (
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)\mathcal{O}(n^2)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ε))\mathcal{O}(n^{1.5} κ_A \log(\frac{1}ε))O(n1.5κA​log(ε1​)) queries to QRAM and O(n2log⁡(1ε))\mathcal{O}(n^2 \log(\frac{1}ε))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.
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.
Solving linear systems of equations is a frequently encountered problem in machine learning and optimization. Given a matrix AAA and a vector b\mathbf{b}b the task is to find the vector x\mathbf{x}x such that Ax=bA\mathbf{x}=\mathbf{b}Ax=b. We describe a quantum algorithm that achieves a sparsity-independent runtime scaling of $\mathcal{O}\mathbf{(}{\ensuremath{\kappa}}^{2}\sqrt{n}\text{polylog}(n)/\ensuremath{\epsilon}\mathbf{)}$ for an $n\ifmmode\times\else\texttimes\fi{}n$ dimensional AAA with bounded spectral norm, where $\ensuremath{\kappa}$ denotes the condition number of AAA, and $\ensuremath{\epsilon}$ is the desired precision parameter. This amounts to a polynomial improvement over known quantum linear system algorithms when applied to dense matrices, and poses a new state of the art for solving dense linear systems on a quantum computer. Furthermore, an exponential improvement is achievable if the rank of AAA is polylogarithmic in the matrix dimension. Our algorithm is built upon a singular value estimation subroutine, which makes use of a memory architecture that allows for efficient preparation of quantum states that correspond to the rows of AAA and the vector of Euclidean norms of the rows of AAA.