.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
Organization
Cited Papers
ShareSave
ShareSaveEfficient Use of Quantum Linear System Algorithms in Inexact Infeasible IPMs for Linear Optimization
PREAI
ShareSaveOptimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits.png)
QUANTUM
OAAI
QUANTUMIF5.4
OAAIShareSaveShareSaveShareSave
View more