A Quantum Algorithm for Computing All Eigenvalues and Eigenstates of Sparse Hermitian Matrices

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.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-12
DOI
https://doi.org/10.48550/arxiv.2611.16610
Primary Topic
Quantum Computing Algorithms and Architecture
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

A Quantum Algorithm for Computing All Eigenvalues and Eigenstates of Sparse Hermitian Matrices

Goutam Paul, Krishnakanta Barik
arXiv (Cornell University)
Quantum Computing Algorithms and Architecture
preprint

A Quantum Algorithm for Computing All Eigenvalues and Eigenstates of Sparse Hermitian Matrices

Goutam Paul, Krishnakanta Barik
preprint en

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.

arXiv (Cornell University)
Quantum Computing Algorithms and Architecture
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon