Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation

Quantum 10, 2067 (2026).

https://doi.org/10.22331/q-2026-04-15-2067

Approximating the $k$-th spectral gap $Delta_k=|lambda_k-lambda_{k+1}|$ and the corresponding midpoint $mu_k=frac{lambda_k+lambda_{k+1}}{2}$ of an $Ntimes N$ Hermitian matrix with eigenvalues $lambda_1geqlambda_2geqldotsgeqlambda_N$, is an important special case of the eigenproblem with numerous applications in science and engineering. In this work, we present a quantum algorithm which approximates these values up to additive error $epsilonDelta_k$ using a logarithmic number of qubits. Notably, in the QRAM model, its total complexity (queries and gates) is bounded by $Oleft( frac{N^2}{epsilon^{2}Delta_k^2}mathrm{polylog}left( N,frac{1}{Delta_k},frac{1}{epsilon},frac{1}{delta}right)right)$, where $epsilon,deltain(0,1)$ are the accuracy and the failure probability, respectively. For large gaps $Delta_k$, this provides a speed-up against the best-known complexities of classical algorithms, namely, $O left( N^{omega}mathrm{polylog} left( N,frac{1}{Delta_k},frac{1}{epsilon}right)right)$, where $omegalesssim 2.371$ is the matrix multiplication exponent. A key technical step in the analysis is the preparation of a suitable random initial state, which ultimately allows us to efficiently count the number of eigenvalues that are smaller than a threshold, while maintaining a quadratic complexity in $N$. In the black-box access model, we also report an $Omega(N^2)$ query lower bound for deciding the existence of a spectral gap in a binary (albeit non-symmetric) matrix.