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

Nai Hui Chia, Tongyang Li, Han Hsuan Lin, Chunhao Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations


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 · poly(log n, r, 1/ε)) given access to a sampling-based low-overhead data structure for the constraint matrices, where ε 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 A1, . . ., Aτ , we propose a procedure that gives a good approximation of A = A1 + · · · + Aτ . Symmetric approximation: we propose a sampling procedure that gives the 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.

Original languageEnglish (US)
Title of host publication45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020
EditorsJavier Esparza, Daniel Kral�, Daniel Kral�
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771597
StatePublished - Aug 1 2020
Event45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020 - Prague, Czech Republic
Duration: Aug 25 2020Aug 26 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020
Country/TerritoryCzech Republic

All Science Journal Classification (ASJC) codes

  • Software


Dive into the research topics of 'Quantum-inspired sublinear algorithm for solving low-rank semidefinite programming'. Together they form a unique fingerprint.

Cite this