{"id":"arxiv/2609.40302","url":"https://arxiv.org/abs/2609.40302","tags":["quant-ph","cs.DS"],"score":0,"title":"Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma","domain":"quant-ph","source":"arxiv","authors":["Fernando G. S. L. Brandão","Alexander M. Dalzell","András Gilyén","Francisca Vasconcelos"],"reviews":0,"subject":"quant-ph","summary":"We give the first sublinear-time classical solvers for sparse semidefinite programs in the bounded-radius regime, without low-rank assumptions or Frobenius norm dependence on the constraint matrices. For constant precision and bounded primal and dual radii, prior quantum algorithms of Brandão et al. (2019) and van Apeldoorn and Gilyén (2019) achieved $\\widetilde{O}(\\sqrt{n}+\\sqrt{m})$ dependence on matrix dimension $n$ and constraint number $m$. Compared with the $\\widetilde{O}(mn)$ runtime of existing classical methods, this suggests a quartic quantum speedup when $m \\approx n$. Beyond a…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}