{"ID":2877291,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.21002","arxiv_id":"2508.21002","title":"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=\\frac{λ_k+λ_{k+1}}{2}$ of an $N\\times N$ Hermitian matrix with eigenvalues $λ_1\\geqλ_2\\geq\\ldots\\geqλ_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\\left( \\frac{N^2}{ε^{2}Δ_k^2}\\mathrm{polylog}\\left( N,\\frac{1}{Δ_k},\\frac{1}ε,\\frac{1}δ\\right)\\right)$, where $ε,δ\\in(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 \\left( N^ω\\mathrm{polylog} \\left( N,\\frac{1}{Δ_k},\\frac{1}ε\\right)\\right)$, where $ω\\lesssim 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.","short_abstract":"Approximating the $k$-th spectral gap $Δ_k=|λ_k-λ_{k+1}|$ and the corresponding midpoint $μ_k=\\frac{λ_k+λ_{k+1}}{2}$ of an $N\\times N$ Hermitian matrix with eigenvalues $λ_1\\geqλ_2\\geq\\ldots\\geqλ_N$, is an important special case of the eigenproblem with numerous applications in science and engineering. In this work, we...","url_abs":"https://arxiv.org/abs/2508.21002","url_pdf":"https://arxiv.org/pdf/2508.21002v3","authors":"[\"Almudena Carrera Vazquez\",\"Aleksandros Sobczyk\"]","published":"2025-08-28T17:04:18Z","proceeding":"quant-ph","tasks":"[\"quant-ph\",\"cs.DS\",\"math.NA\"]","methods":"[]","has_code":false}