Current browse context:
quant-ph
Change to browse by:
References & Citations
Quantum Physics
Title: Quantum speedups for linear programming via interior point methods
(Submitted on 6 Nov 2023 (v1), last revised 11 Apr 2024 (this version, v2))
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 $\varepsilon$-close to optimal, and runs in time $\sqrt{n} \cdot \mathrm{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 \emph{spectral approximation} of $A^T A$ for a tall matrix $A \in \mathbb R^{n \times d}$. 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.
Submission history
From: Sander Gribling [view email][v1] Mon, 6 Nov 2023 16:00:07 GMT (40kb)
[v2] Thu, 11 Apr 2024 14:00:04 GMT (41kb)
Link back to: arXiv, form interface, contact.