Quantum-inspired classical sublinear-time algorithm for solving low-rank semidefinite programming via sampling approaches

  • 2019-01-10 16:26:15
  • Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin, Chunhao Wang
  • 1

Abstract

Semidefinite programming (SDP) is a central topic in mathematicaloptimization with extensive studies on its efficient solvers. Recently, quantumalgorithms with superpolynomial speedups for solving SDPs have been proposedassuming access to its constraint matrices in quantum superposition. Mutuallyinspired by both classical and quantum SDP solvers, in this paper we present asublinear classical algorithm for solving low-rank SDPs which is asymptoticallyas good as existing quantum algorithms. Specifically, given an SDP with $m$constraint matrices, each of dimension $n$ and rank $\mathrm{poly}(\log n)$,our algorithm gives a succinct description and any entry of the solution matrixin time $O(m\cdot\mathrm{poly}(\log n,1/\varepsilon))$ given access to asample-based low-overhead data structure of the constraint matrices, where$\varepsilon$ is the precision of the solution. In addition, we apply ouralgorithm to a quantum state learning task as an application. Technically, our approach aligns with both the SDP solvers based on thematrix multiplicative weight (MMW) framework and the recent studies ofquantum-inspired machine learning algorithms. The cost of solving SDPs by MMWmainly comes from the exponentiation of Hermitian matrices, and we propose twonew technical ingredients (compared to previous sample-based algorithms) forthis task that may be of independent interest: $\bullet$ Weighted sampling: assuming sampling access to each individualconstraint matrix $A_{1},\ldots,A_{\tau}$, we propose a procedure that gives agood approximation of $A=A_{1}+\cdots+A_{\tau}$. $\bullet$ Symmetric approximation: we propose a sampling procedure that giveslow-rank spectral decomposition of a Hermitian matrix $A$. This improves uponprevious sampling procedures that only give low-rank singular valuedecompositions, losing the signs of eigenvalues.

 

Introduction (beta)

None

 

Conclusion (beta)

None