Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma
This research develops classical algorithms to solve sparse Semidefinite Programs (SDPs) faster than previous methods, aiming for sublinear time. The authors create a procedure that mimics quantum efficiency by using randomized L'anczos filtering and sample reuse on structured Gibbs states. This allows them to estimate many expectation values simultaneously, leading to improved performance guarantees over existing classical and quantum solvers.