Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation
Almudena Carrera Vazquez, Aleksandros Sobczyk · Quantum · 2026
Approximating the k -th spectral gap Δ k = | λ k − λ k + 1 | and the corresponding midpoint μ k = λ k + λ k + 1 2 of an N × N Hermitian matrix with eigenvalues λ 1 ≥ λ 2 ≥ … ≥ λ 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 ϵ Δ k using a logarithmic number of qubits. Notably, in the QRAM model, its total complexity (queries and gates) is bounded by O ( N 2 ϵ 2 Δ k 2 p o l y l o g ( N , 1 Δ k , 1 ϵ , 1 δ ) ) , where ϵ , δ ∈ ( 0 , 1 ) are the accuracy and the failure probability, respectively. For large gaps Δ k , this provides a speed-up against the best-known complexities of classical algorithms, namely, O ( N ω p o l y l o g ( N , 1