Classical and quantum spectral density estimation under local graph access

This paper establishes a sharp classical–quantum separation for estimating the eigenvalue distribution of a graph’s normalized adjacency matrix under local access, measured in Wasserstein-1 distance. Classically, it proves that any constant-success estimator with error at most ε needs 2^{Ω(1/ε)} graph queries on simple unweighted graphs, matching the earlier 2^{O(1/ε)} algorithm in its dependence on ε. The lower-bound construction uses Cayley graphs derived from Type-I and Type-II self-dual binary codes, whose spectra remain indistinguishable until local exploration discovers hidden code relations. In the quantum local-access model, coherent degree, neighbor, and pair-oracle queries enable a projected-unitary encoding after high-degree truncation, followed by Grover-based neighbor-state preparation, quantum phase estimation, and quantum ℓ∞ amplitude estimation. This yields an estimator using Õ(ε^{-3}) queries, Õ(ε^{-2}) additional classical runtime, and success probability 2/3, while a parity-controlled cycle construction and the polynomial method prove a quantum lower bound of Õ(ε^{-4/3}) queries. Thus quantum access changes the ε dependence from exponential to polynomial, although the upper and lower bounds do not yet match. The paper also notes that GPT-5.6 Sol inspired the lower-bound construction, while the proofs were human-written or substantially revised.