Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation

Approximating the k-th spectral gap Δₖ=|λₖ-λₖ₊₁| and the corresponding midpoint μₖ=λₖ+λₖ₊₁2 of an N× N Hermitian matrix with eigenvalues λ₁≥λ₂≥…≥λ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 εΔₖ using a logarithmic number of qubits. Notably, in the QRAM model, its total complexity (queries and gates) is bounded by O( N²ε²Δₖ²polylog( N,1/Δₖ,1ε,1δ)), where ε,δ∈(0,1) are the accuracy and the success probability, respectively. For large gaps Δₖ, this provides a speed-up against the best-known complexities of classical algorithms, namely, O ( N^ωpolylog ( N,1/Δₖ,1ε)), where ω 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 Ω(N²) query lower bound for deciding the existence of a spectral gap in a binary (albeit non-symmetric) matrix.