Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma
Abstract
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 Õ(√n+√m) dependence on matrix dimension n and constraint number m. Compared with the Õ(mn) runtime of existing classical methods, this suggests a quartic quantum speedup when m ≈ n. 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ánczos 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 s denote the the input matrix sparsity and γ:=Rr/ε capture dependence on the primal (R) and dual (r) radii as well as target accuracy (ε). When γ2≤min{m,n/s}, our solver runs in time Õ(nsγ4.5+msγ2). For γ=O(1), this is Õ((n+m)s) and sublinear in the O(mns) input size. Similar to the quantum algorithms, this matches known lower bounds with respect to m and n, up to logarithmic factors. This implies that, with respect to dimensions m and n, there is no super-quadratic quantum advantage for generic sparse SDP solving.
Related
- Smart Machine Learning for Solving the Full Electron-Nuclear Schrödinger Equation with a Quantum-Chemically Inspired Wavefunction Ansatz
- Solving Graph Coloring Problems Using Feedback-Based Algorithm for Quantum Optimization
- Resource and entanglement study of a hybrid qudit-qubit quantum algorithm for solving the integer programming problem
- Quantum-Classical Neural Networks for Solving Lindblad Master Equations
- Quantum HHL Algorithm for Solving 1D Linear Advection Equation Using Explicit and Implicit Finite Difference Schemes
BibTeX
@misc{brandao2026solving,
title = {{Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma}},
author = {Fernando G. S. L. Brandão and Alexander M. Dalzell and András Gilyén and Francisca Vasconcelos},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.40302},
eprint = {2609.40302},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.40302},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma
AU - Fernando G. S. L. Brandão
AU - Alexander M. Dalzell
AU - András Gilyén
AU - Francisca Vasconcelos
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.40302
UR - https://arxiv.org/abs/2609.40302
AB - 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 Õ(√n+√m) dependence on matrix dimension n and constraint number m. Compared with the Õ(mn) runtime of existing classical methods, this suggests a quartic quantum speedup when m ≈ n. 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ánczos 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 s denote the the input matrix sparsity and γ:=Rr/ε capture dependence on the primal (R) and dual (r) radii as well as target accuracy (ε). When γ^2≤min{m,n/s}, our solver runs in time Õ(nsγ^4.5+msγ^2). For γ=O(1), this is Õ((n+m)s) and sublinear in the O(mns) input size. Similar to the quantum algorithms, this matches known lower bounds with respect to m and n, up to logarithmic factors. This implies that, with respect to dimensions m and n, there is no super-quadratic quantum advantage for generic sparse SDP solving.
ER -