Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR LemmaResearch Paper
Semidefinite programs underlie approximation algorithms such as Goemans–Williamson, the sum-of-squares hierarchy, and basic tasks in quantum information. They are also the main example of a claimed large quantum speedup for a continuous optimization problem. For sparse SDPs with matrices and constraints, the best known classical solver had…