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

DOI10.4230/LIPICS.MFCS.2020.23arXiv1901.03254MaRDI QIDQ6312290FDOQ6312290

Authors: Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin, Chun-Hao Wang 

Publication date: 10 January 2019

Abstract: 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(mcdotmathrmpoly(logn,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. Technically, our approach aligns with 1) SDP solvers based on the matrix multiplicative weight (MMW) framework by Arora and Kale [TOC '12]; 2) sampling-based dequantizing framework pioneered by Tang [STOC '19]. In order to compute the matrix exponential required in the MMW framework, we introduce two new techniques that may be of independent interest: $$ Weighted sampling: assuming sampling access to each individual constraint matrix $A_1,ldots,A_{au}$, we propose a procedure that gives a good approximation of $A=A_1+cdots+A_{au}$. $$ Symmetric approximation: we propose a sampling procedure that gives the emph{spectral decomposition} of a low-rank Hermitian matrix $A$. To the best of our knowledge, this is the first sampling-based algorithm for spectral decomposition, as previous works only give singular values and vectors.

Mathematics Subject Classification ID

Theory of computing (68Qxx)

This page was built for publication: Quantum-inspired sublinear algorithm for solving low-rank semidefinite programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6312290)