Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918493212901376 |
|---|---|
| author | Vazquez, Almudena Carrera Sobczyk, Aleksandros |
| author_facet | Vazquez, Almudena Carrera Sobczyk, Aleksandros |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_21002 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation Vazquez, Almudena Carrera Sobczyk, Aleksandros Quantum Physics Data Structures and Algorithms Numerical Analysis 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. |
| title | Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation |
| topic | Quantum Physics Data Structures and Algorithms Numerical Analysis |
| url | https://arxiv.org/abs/2508.21002 |