# Quantum speedups for linear programming via interior point methods

arXiv: https://arxiv.org/abs/2311.03215 · HTML: https://mlsanity.com/paper/2311.03215/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Nov 2023.

## Built on by (most cited first, 3 of 3)

- [Sublinear Time Quantum Algorithm for Attention Approximation](https://mlsanity.com/paper/2602.00874/) (2026)
- [On Quantum Perceptron Learning via Quantum Search](https://mlsanity.com/paper/2503.17308/) (2025)
- [Quantum Algorithms for Projection-Free Sparse Convex Optimization](https://mlsanity.com/paper/2507.08543/) (2025)

## Abstract (arXiv)

We describe a quantum algorithm based on an interior point method for solving a linear program with n inequality constraints on d variables. The algorithm explicitly returns a feasible solution that is varepsilon-close to optimal, and runs in time √n · poly(d,log(n),log(1/varepsilon)) which is sublinear for tall linear programs (i.e., n gg d). Our algorithm speeds up the Newton step in the state-of-the-art interior point method of Lee and Sidford [FOCS '14]. 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 AT A for a tall matrix A ∈ mathbb Rn × d. The algorithm uses leverage score sampling in combination with Grover search, and returns a δ-approximation by making O(√nd/δ) row queries to A. This generalizes an earlier quantum speedup for graph sparsification by Apers and de Wolf [FOCS '20]. To approximate the gradient, we use a recent quantum algorithm for multivariate mean estimation by Cornelissen, Hamoudi and Jerbi [STOC '22]. While a naive implementation introduces a dependence on the condition number of the Hessian, we avoid this by pre-conditioning our random variable using our quantum algorithm for spectral approximation.