Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation

Abstract

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)polylog( 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^(ω)polylog ( N,(1)/(Δ_k),(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^2) query lower bound for deciding the existence of a spectral gap in a binary (albeit non-symmetric) matrix.