Quantum-inspired sublinear algorithm for solving low-rank semidefinite programming

Understand

Semidefinite programming (SDP) is a central topic in mathematical optimization with extensive studies on its efficient solvers.

• In this paper, we present a proof-of-principle sublinear-time algorithm for solving SDPs with low-rank constraints; specifically, given an SDP with $m$ constraint matrices, each of dimension $n$ and rank $r$, our algorithm can compute any entry and efficient descriptions of the spectral decomposition of the solution matrix.
• The algorithm runs in time $O(m\cdot\mathrm{poly}(\log n,r,1/\varepsilon))$ given access to a sampling-based low-overhead data structure for the constraint matrices, where $\varepsilon$ is the precision of the solution.
• In addition, we apply our algorithm to a quantum state learning task as an application.