.png){kind=icon}
.png){kind=icon}
Return
A Quantum Interior Point Method for LPs and SDPs
.png){kind=icon}
OA
AI
DOI：10.1145/3406306.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We present a quantum interior point method (IPM) for semi-definite programs that has a worst-case running time of (O) over tilde (n(2.5)/xi(2) mu kappa(3) log(1/c)). The algorithm outputs a pair of matrices (S, Y) that have objective value within epsilon of the optimal and satisfy the constraintsv approximately to error xi. The parameter mu is at most root 2n while kappa is an upper bound on the condition number of the intermediate solution matrices arising in the classical IPM. For the case where kappa << n(5/6), our method provides a significant polynomial speedup over the best-known classical semi-definite program solvers that have a worst-case running time of O(n(6)). For linear programs, our algorithm has a running time of (O) over tilde (n(1.5)/xi(2) mu kappa(3) log(1/epsilon)) with the same guarantees and with parameter mu < root 2n. Our technical contributions include an efficient quantum procedure for solving the Newton linear systems arising in the classical IPMs, an efficient pure state tomography algorithm, and an analysis of the IPM where the linear systems are solved approximately. Our results pave the way for the development of quantum algorithms with significant polynomial speedups for applications in optimization and machine learning.
Keywords:
Quantum algorithms
semi-definite programming
linear programming
interior point methods
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
A
IF:
6.8
Papers:
539
Citations:
508