Answers are grounded in this paper and cite their sources.
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 x|M|x, where x is a prepared eigenstate and M is an observable. For an n × n s-sparse Hermitian matrix H, dense methods based on Householder tridiagonalization and QR iteration compute all eigenvalues and eigenvectors in O(n³) time. Exploiting sparsity, the Lanczos method computes all eigenvalues in O(n² s) time in exact arithmetic, but recovering all eigenvectors still requires O(n³) time. In contrast, our algorithm runs in time Õ(n s² log² n / Δₘᵢₙ), where Δₘᵢₙ denotes the minimum spectral gap of the normalized matrix. For inverse gaps up to Δₘᵢₙ⁻¹ = 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(√n/log n), the proposed algorithm achieves an improved asymptotic runtime over the classical O(n³) approach for computing all eigenvalues and eigenvectors, under standard sparse-access assumptions.
No takes yet. Share an insight, caveat, or question.
Barik et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: