arXiv · 12 Nov 2026
A Quantum Algorithm for Computing All Eigenvalues and Eigenstates of Sparse Hermitian Matrices
Krishnakanta Barik, Goutam Paul
Citations by database
Each database indexes a different set of journals, preprints and books, so they are shown side by side rather than blended.
- OpenCitations0
Citations per year
The current year is still counting.
- 2026 so far0
Abstract
Computation of eigenvalues and eigenvectors of a sparse Hermitian matrix is a fundamental problem in algebra, arising both as a problem of independent interest and as a key subroutine in a wide range of computational and scientific applications. In this work, we develop a quantum algorithm that determines the spectrum of a sparse Hermitian matrix, defined as the set of its distinct eigenvalues, and for each eigenvalue, prepares a corresponding eigenvector as a quantum state in its eigenspace. The eigenvalues are represented as binary strings with a prescribed precision, while the corresponding eigenvectors are kept as quantum states, eliminating the need to reconstruct their classical counterparts. The algorithm instead enables estimation of expectation values $\braket{x|M|x}$, where $\ket{x}$ is a prepared eigenstate and $M$ is an observable. For an $n \times n$ $s$-sparse Hermitian matrix $H$, dense methods based on Householder tridiagonalization and QR iteration compute all eigenvalues and eigenvectors in $\mathcal{O}(n^3)$ time. Exploiting sparsity, the Lanczos method computes all eigenvalues in $\mathcal{O}(n^2 s)$ time in exact arithmetic, but recovering all eigenvectors still requires $\mathcal{O}(n^3)$ time. In contrast, our algorithm runs in time $\tilde{\mathcal{O}}(n s^2 \log^2 n / Δ_{\min})$, where $Δ_{\min}$ denotes the minimum spectral gap of the normalized matrix. For inverse gaps up to $Δ_{\min}^{-1} = \mathcal{O}(n)$, the most favorable scaling for $n$ distinct eigenvalues, attained by nearly uniformly spaced spectra such as those of perfect-state-transfer spin chains and the Sylvester-Kac matrix, and for sparsity up to $s = o(\sqrt{n}/\log n)$, the proposed algorithm achieves an improved asymptotic runtime over the classical $\mathcal{O}(n^3)$ approach for computing all eigenvalues and eigenvectors, under standard sparse-access assumptions.
What the data shows
- No database records a citation yet, as is usual for a paper this new.
Graph
This paper in the middle, its authors and their most-cited papers below, the papers it cites to the left and the papers citing it to the right. The timeline lays every paper out by year.
Select a node for its details. Drag to pan, scroll to zoom, drag a node to move it.
Start with
Cited by 0 papers
Who cites this paper, from open citation data, with Crossref's record of each; the 100 newest when there are more.
References (0)
What it cites, from open citation data, with Crossref's record of each.