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 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
Fields of Study & Subjects
Quantum Computing Algorithms and Architecture
Quantum Information and Cryptography
Quantum Mechanics and Applications
Publication details
- Journal / source
- Quantum
- Publisher
- Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften
- Volume
- 10
- Pages
- 2067–2067
- Publication date
- 15 April 2026
- Language
- EN