.png){kind=icon}
.png){kind=icon}
Return
QUANTUM SPEEDUPS FOR LINEAR PROGRAMMING VIA INTERIOR POINT METHODS
.png){kind=icon}
PRE
AI
DOI：10.1137/25M1736098.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 root n.poly(d,log(n),log(1/epsilon)), which is sublinear for tall linear programs (i.e., n >> d). 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 A(T)A for a tall matrix A subset of R-nxd. The algorithm uses leverage score sampling in combination with Grover search and returns a \delta-approximation by making O(root nd/delta) row queries to A. 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.
Keywords:
Key words. quantum algorithms
interior point methods
linear programming
spectral approximation
Journal
S
IF:
1.6
Papers:
14
Citations:
0