{"id":"arxiv/2608.22769","url":"https://arxiv.org/abs/2608.22769","tags":["quant-ph","cs.DS"],"score":0,"title":"Classical and quantum spectral density estimation under local graph access","domain":"quant-ph","source":"arxiv","authors":["Rong-Hua Li","Meihao Liao","Yichun Yang"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-08-24","reactions":{}}