EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
4331. Quantum speedups for linear programming via interior point methods
Invited abstract in session TA-42: Quantum Computing for Continuous Optimization, stream Quantum Computing Optimization.
Tuesday, 8:30-10:00Room: 98 (building: 306)
Authors (first author is the speaker)
| 1. | Sander Gribling
|
| Tilburg University |
Abstract
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 eps-close to optimal, and runs in time O(sqrt{n} poly(d,log(n),log(1/eps)) 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 [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 A^T A for a tall n-by-d matrix A. The algorithm uses leverage score sampling in combination with Grover search, and returns a delta-approximation by making O(sqrt{nd}/delta) 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.
Keywords
- Continuous Optimization
- Algorithms
Status: accepted
Back to the list of papers