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.
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 ε-approximate spectral density estimation in the Wasserstein-1 distance, using 2O(1/ε) 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 O(\eps−3)-query algorithm estimating the spectral density with Wasserstein-1 error at most \eps. Finally, we prove a Ω(\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.
Near-Optimal Bounds on the Density of Low-Energy States of k-Local Hamiltonians and Faster Quantum Algorithms
Low-energy estimation and state preparation for general k-local Hamiltonians are fundamental challenges in quantum complexity theory. Buhrman et al.~ [BGLGST, PRL 2025] recently broke the natural Grover bound O∗(2n/2) for both problems, with the improvement depending on the relative accuracy ε and the locality k. In this work, we present faster exponential quantum algorithms for these problems, where the binary entropy function governs the runtime exponent. For sufficiently small ε/k, our algorithms improve the exponent by a factor of log(k/ε) over [BGLGST, PRL 2025]. Our main technical result is an entropy-governed lower bound on the dimension of the Hamiltonian's low-energy subspace, obtained by depolarizing its ground state. For fixed k, this bound is optimal up to constant factors in the exponent. The same framework yields tighter bounds for Heisenberg, XY, and Ising models on arbitrary interaction graphs.
We study the computational complexity of estimating the normalized trace 2−nTr[f(A)] for a log-local Hamiltonian A acting on n qubits. This problem arises naturally in the DQC1 model, yet its complexity is only understood for a limited class of functions f(x).
We show that if f(x) is a continuous function with approximate degree Ω(poly(n)), then estimating 2−nTr[f(A)] up to constant additive error is DQC1-complete, under a technical condition on the polynomial approximation error of f(x). This condition holds for a broad class of functions, including exponentials, trigonometric functions, logarithms, and inverse-type functions. We further prove that when A is sparse, the classical query complexity of this problem is exponential in the approximate degree. Together, these results identify the approximate degree as the key parameter governing the complexity of normalized trace estimation: it characterizes both the quantum complexity (via efficient DQC1 algorithms) and the classical hardness, yielding an exponential quantum-classical separation. Our proof develops a unified framework that cleanly combines circuit-to-Hamiltonian constructions, periodic Jacobi operators, and tools from polynomial approximation theory, including the Chebyshev equioscillation theorem.
This paper gives quantum query lower bounds for two relational graph problems, triangle listing and explicit multiplicative spanner construction, in the general graph query model, where quantum adjacency, degree and neighborhood queries are all available in arbitrary superposition. Both results are obtained by reductions via intermediate multi-block search problems. We extend the quantum query recording framework by Zhandry (CRYPTO 2019) and Hamoudi and Magniez (ToCT 2023) to handle a recording architecture for bidirectional oracles and give a generic blockwise soundness framework, which for arbitrary families of local accepting projectors, gives an exact operator-norm characterization of their maximum overlap with the subspace of bounded weight records. Using the intermediate search problems, we exhibit a family of n-vertex graphs with Θ(n) triangles on which listing any constant fraction of the triangles requires Ω(n3/2−o(1)) quantum queries. This is the first nontrivial quantum lower bound for triangle listing, a question raised by Jiang and Peng (ICML 2026). Further, we show that, for every fixed k≥7, constructing a multiplicative k-spanner requires Ω(n1+2μk1) quantum queries, where μk=k/3+O(1). For k∈{7,8} the bound is Ω(n5/4), which matches what would be implied by an unproven instance of the Erdős girth conjecture, and for large k the exponent 1+2k3 exceeds the 1+3k4 implied by the provable high girth dense graphs due to Lazebnik, Ustimenko and Woldar, 1995.
We study the minimum weight cycle problem (MWC) and the minimum weight triangle problem (MWT) in the quantum query model, for n-vertex graphs with integer edge weights in [M] given by their adjacency matrix. Roditty and Vassilevska Williams showed that the two problems are classically equivalent. We show that an exact minimum weight cycle of an undirected graph can be found with O~(n19/12) queries, while Ω(n3/2) queries are necessary. The algorithm learns only the n7/6 lightest vertex pairs, uses quantum counting to locate weight thresholds above them, applies a strict form of the Moore bound to bound the optimum and the size of each weight class, and searches the classes for the few heavy edges of an optimal cycle with nested quantum walks. A simpler version gives O~(n5/3) queries, and searching for fewer heavy edges trades queries for approximation, with a 2-approximation in O~(n8/5) queries and a tight O(logn)-approximation in O~(n3/2) queries. In contrast, MWT costs O(n9/7logM) queries, so the classical equivalence becomes a polynomial separation. For cycles of constant length we give explicit exponents, such as O~(n125/83) for the minimum weight 5-cycle, and we prove that deciding whether a graph has a k-cycle of total weight exactly zero requires Ω(n2−2/(⌊k/2⌋+1)) queries for every constant k≥4. Finally, non-adaptive learning graphs cannot beat n2 for cycles of about logn edges, and we conjecture that exact MWC on directed graphs requires n2−o(1) queries.
We study the query complexity of estimating scalar summaries of zigzag bar lifetimes from snapshot-adjacency bits.
For graphs G1,…,Gm on n labeled vertices, let ℓb be the snapshot lifetime of a degree-one bar b of the intersection zigzag. For a probability generating function φ(x)=E[xR], the statistic Fφ=∑bφ(ℓb/m) includes normalized degree-r total persistence and the mean generalized rank over a uniform time window. An exact identity underlies our algorithm: sample R uniform times; the expected generalized rank between their minimum and maximum equals Fφ. For graphs that rank is the circuit rank of an intersection graph, so a nonlinear barcode functional becomes an average of edge and component counts, and no barcode is computed.
Without spectral-gap, homology-state, or QRAM assumptions, this gives a quantum estimator with additive error εn and O(m(K+n)/ε) queries when a bound K≥Fφ is supplied, against O(mmin{n2,(K+n)/ε2}) classically, and an adaptive quantum variant with the same instance dependence. These estimators are optimal in two regimes. For every fixed power weight xr, r≥2, and for the uniform-window mean, the worst-case complexities are Θ(nm/ε) quantum and Θ(n2m) classical. On sparse instances, under an explicit split-leakage promise met by power and binomial weights of logarithmic degree and the promise Fφ≤K, they are Θ(mK/ε) and Θ(mmin{n2,K/ε2}). The classical lower bounds hold against fully adaptive algorithms, and fewer than m such statistics cannot determine the positive-lifetime histogram. All bounds concern snapshot access; with an explicit update stream, near-linear full-barcode algorithms are known.
We give a quantum algorithm for a novel type of black-box problem: identifying a hidden d-regular base graph G on n vertices from oracle access to an obfuscated version of it, rather than traversing it. From G we build the spired graph Gspire in three steps: each vertex is lifted into an exponentially large cluster, with adjacent clusters joined by a random bipartite graph; each cluster is then crowned with a balanced spire; finally, all vertices are randomly relabelled. Specializing to G=K2 recovers the welded-trees graph.
Our algorithm is conceptually simple: a continuous-time quantum walk on Gspire, followed by a single Hadamard test at a classically precomputed time t∗; the algorithm returns the candidate whose predicted amplitude is closest to the measurement. The design rests on a rigorous spectral theory: from the apex of any spire, the walk is confined to a polynomial-dimensional invariant subspace evolving under the adjacency matrix of a simpler towered graph Gtower; that matrix block-diagonalizes into n independent tridiagonal systems of size n, each solved in closed form by a Chebyshev secular equation. Efficient numerics enabled by this decomposition supply t∗ and the predicted amplitudes.
On the prism graphs Ym versus the Möbius ladders Mm (each on n=2m vertices), the numerical study supports a precise conjecture that O(n2/logn) measurements at evolution time of order m2 suffice to distinguish the two families; we have tested 4≤m≤5121 (n up to 10242). By analogy with the welded-trees lower bounds, we further conjecture that any classical algorithm requires queries exponential in n. Together these conjectures point to an exponential quantum speedup for the identification of an obfuscated base graph.