Quantum speedups for linear programming via interior point methods

We describe a quantum algorithm based on an interior point method for solving a linear program with 𝑛 inequality constraints on 𝑑 variables. The algorithm explicitly returns a feasible solution that is 𝜀-close to optimal and runs in time √𝑛 ⋅poly⁡(𝑑,log⁡(𝑛),log⁡(1/𝜀)), which is sublinear for tall linear programs (i.e., 𝑛 ≫𝑑). 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 𝐴𝑇⁢𝐴 for a tall matrix 𝐴 ∈ℝ𝑛×𝑑. The algorithm uses leverage score sampling in combination with Grover search and returns a 𝛿-approximation by making 𝑂⁢(√𝑛⁢𝑑/𝛿) row queries to 𝐴. 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.