aiqbench analysis
This research demonstrates that a specific classical algorithmic technique, inspired by the Quantum OR lemma, can solve sparse semidefinite programs in sublinear time without relying on quantum hardware. By decoupling Gibbs-state preparation from constraint search, the authors achieve performance comparable to theoretical quantum speedups for this specific problem class, effectively showing where classical methods have caught up to quantum advantages in optimization.
Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma
arXiv:2609.40302v1 Announce Type: new 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\~ao et al. (2019) and van Apeldoorn and Gily\'en (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 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 $s$ denote the the input matrix sparsity and $\gamma:=Rr/\varepsilon$ capture dependence on the primal $(R)$ and dual $(r)$ radii as well as target accuracy $(\varepsilon)$. When $\gamma^2\leq\min\{m,n/s\}$, our solver runs in time $\widetilde{O}\left(ns\gamma^{4.5}+ms\gamma^2\right)$. For $\gamma=O(1)$, this is $\widetilde{O}\left((n+m)s\right)$ 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.
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 $\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 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 $\gamma:=Rr/\varepsilon$ capture dependence on the primal $(R)$ and dual $(r)$ radii as well as target accuracy $(\varepsilon)$. When $\gamma^2\leq\min\{m,n/s\}$, our solver runs in time $\widetilde{O}\left(ns\gamma^{4.5}+ms\gamma^2\right)$. For $\gamma=O(1)$, this is $\widetilde{O}\left((n+m)s\right)$ 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.
Quantum Physics (quant-ph); Data Structures and Algorithms (cs.DS)
arXiv:2609.40302 [quant-ph]
(or arXiv:2609.40302v1 [quant-ph] for this version)
https://doi.org/10.48550/arXiv.2609.40302 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 352 words
Related coverage
A brief history of quantum vs classical computational advantage
Quantum Journal · Sep 1, 2026
On the quantum computational complexity of classical linear dynamics with geometrically local interactions: Dequantization and universality
Quantum Journal · Aug 3, 2026
Edward Farhi, The Physicist Behind QAOA
Quantum Zeitgeist · Aug 30, 2026
Researchers Achieve Near Optimal Solutions for Complex Problems with New Solver
Quantum Zeitgeist · Oct 7, 2026