Classical and quantum spectral density estimation under local graph access
2026-08-24 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study how to estimate the spectral density (a certain summary of graph structure) of a graph by looking at it locally through queries. They show that a previous classical method by Cohen-Steiner et al. is essentially the best possible, requiring an exponential number of queries in terms of the error tolerance. They then explore a quantum approach and find that quantum algorithms can achieve similar accuracy with only a polynomial number of queries, showing a significant improvement. They also prove a lower bound on the number of quantum queries needed, indicating the quantum method's efficiency gains are real but limited.
spectral density estimationnormalized adjacency matrixlocal access modelWasserstein-1 distancequantum algorithmsquery complexitygraph theorylower boundexponential vs polynomial complexity
Authors
Rong-Hua Li, Meihao Liao, Yichun Yang
Abstract
We study spectral density estimation for the normalized adjacency matrix of an unweighted graph under local access model. Previously, Cohen-Steiner et al. [KDD 2018] proposed an algorithm for $\varepsilon$-approximate spectral density estimation in the Wasserstein-1 distance, using $2^{O(1/\varepsilon)}$ local queries to the graph. In this paper, we prove that every constant-success estimator with Wasserstein--$1$ error at most $\eps$ requires $2^{Ω(1/\eps)}$ queries, showing that the Cohen-Steiner algorithm is optimal up to constant in the exponent. This resolves the open problem left by previous researches Jin et al. [COLT 2023] and Peng et al. [COLT 2026]. We then turn to quantum local access model. We give an $\widetilde O(\eps^{-3})$-query algorithm estimating the spectral density with Wasserstein-1 error at most $\eps$. Finally, we prove a $\widetildeΩ(\eps^{-4/3})$ quantum lower bound when the graph is sufficiently large. As a result, quantum local access model changes the dependence on $\eps$ from exponential to polynomial.