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

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κ∊ ¯ ⁻²) for n the number of variables in the cost function, m the number of constraints, ∊⁻¹ 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)²κ¯ log(∊⁻¹)), or with exact methods, at least O(L√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.