Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma
En palabras de los autores
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\~ao et al. (2019) and van Apeldoorn and Gily\'en (2019) achieved dependence on matrix dimension and constraint number . Compared with the runtime of existing classical methods, this suggests a quartic quantum speedup when . Beyond a usual Grover speedup, this separation relies on the Quantum OR lemma, whose sample-reuse mechanism decouples the cost of Gibbs-state preparation from constraint search. We show that this reuse mechanism is classically realizable for sparse SDPs. Our main technical contribution is a classical procedure for simultaneously estimating many expectation values with respect to a sparse Hamiltonian's Gibbs state. This combines randomized L\'anczos filtering with an efficient sampling-based estimator. We also introduce a stochastic online-learning framework for SDP solving, substantially improving accuracy-dependence over standard oracle-based MMWU approaches. Let denote the the input matrix sparsity and capture dependence on the primal and dual radii as well as target accuracy . When , our solver runs in time . For , this is and sublinear in the input size. Similar to the quantum algorithms, this matches known lower bounds with respect to and , up to logarithmic factors. This implies that, with respect to dimensions and , there is no super-quadratic quantum advantage for generic sparse SDP solving.
Apareció: jueves, 1 de octubre. arXiv. Preprint, todavía sin revisión por pares.