2026-07-23T14:40:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12691 2024-03-06T10:50:35Z ddc:004 open_access

Quantum-Inspired Sublinear Algorithm for Solving Low-Rank Semidefinite Programming Chia, Nai-Hui Li, Tongyang Lin, Han-Hsuan Wang, Chunhao Spectral decomposition Semi-definite programming Quantum-inspired algorithm Sublinear algorithm 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 A₁,…,A_τ, we propose a procedure that gives a good approximation of A = A₁+⋯+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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nai-Hui Chia and Tongyang Li and Han-Hsuan Lin and Chunhao Wang 2020 Is Part Of LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2020.23 urn:nbn:de:0030-drops-126919 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.23 eng https://creativecommons.org/licenses/by/3.0/legalcode