Polynomial-time exact diagonalization via sparse guided eigenwalks

• URL: http://arxiv.org/abs/2606.23967v1
• Date: Mon, 22 Jun 2026 21:47:24 GMT
• Title: Polynomial-time exact diagonalization via sparse guided eigenwalks
• Abstract summary: We introduce the eigenwalk problem, which seeks the support of a sparse eigenvector of a Hermitian matrix.<n>We prove that for every sparse eigenvector, there exists a sparse eigenvector with the same eigenvalue whose support is tightly localized in the graph.<n>The results hold with no assumptions on the degeneracy, locality, spectral width, or spectral gap of the Hamiltonian.
• Score: 2.8221337927464547
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Computing quantum ground states is generically difficult, but additional structure can sometimes allow diagonalization to be recast as a more feasible problem. For example, when the desired ground state is sparse in a given basis, diagonalization can be facilitated via graph search. We make this reformulation precise by introducing the eigenwalk problem, which seeks the support of a sparse eigenvector of a Hermitian matrix by exploring the graph induced by its nonzero entries. However, it is not obvious whether the relevant support vertices must always be efficiently reachable by a search on the graph. To resolve this question, we prove that for every sparse eigenvector, there exists a (possibly different) sparse eigenvector with the same eigenvalue whose support is tightly localized in the graph, with diameter scaling only linearly in the sparsity and independently of the total number of vertices. As a consequence, if a $2^n$-dimensional, ${\rm poly}(n)$-sparse Hamiltonian has an $\mathcal{O}(1)$-sparse extremal eigenvector and one support element is known, then an exact eigenvector with the same eigenvalue can be computed classically in ${\rm poly}(n)$ time. The same conclusion follows when the $\mathcal{O}(1)$-sparse eigenvector is non-extremal, provided that it is sparser than every eigenvector with a different eigenvalue. These results hold with no assumptions on the degeneracy, locality, spectral width, or spectral gap of the Hamiltonian, and the underlying support-localization principle also extends to problems beyond exact diagonalization, such as sparse principal component analysis.

Related papers

• Complex Interpolation of Matrices with an application to Multi-Manifold Learning [12.540068560688958]
  We study the spectral properties of the $A1-x Bx$ for $0 leq x leq 1$.<n>The presence of common structures' in $A$ and $Bx|$ can be investigated using this perspective.<n>These results give rise to and provide theoretical justification for a multi-manifold learning framework that identifies common and distinct latent structures in multiview data.
  arXiv  Detail & Related papers  (2026-04-15T17:40:37Z)
• Exponential quantum advantages for practical non-Hermitian eigenproblems [9.59420259768862]
  We develop a quantum algorithm to address general non-Hermitian eigenvalue problems.<n>Our method combines a fuzzy quantum eigenvalue detector with a divide-and-conquer strategy to efficiently isolate relevant eigenvalues.<n>We discuss the broad applications in detecting spontaneous $PT$-symmetry breaking, estimating Liouvillian gaps, and analyzing classical Markov processes.
  arXiv  Detail & Related papers  (2024-01-22T16:29:08Z)
• Re-Analyze Gauss: Bounds for Private Matrix Approximation via Dyson Brownian Motion [28.431572772564518]
  Given a symmetric matrix $M$ and a vector $lambda$, we present new bounds on the Frobenius-distance utility of the Gaussian mechanism for approximating $M$ by a matrix. Our bounds depend on both $lambda$ and the gaps in the eigenvalues of $M$, and hold whenever the top $k+1$ eigenvalues of $M$ have sufficiently large gaps.
  arXiv  Detail & Related papers  (2022-11-11T18:54:01Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  A basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = Omega(, d2/mathrmpolylog(d),)$. Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix.
  arXiv  Detail & Related papers  (2022-08-19T18:00:34Z)
• Sign and Basis Invariant Networks for Spectral Graph Representation Learning [75.18802152811539]
  We introduce SignNet and BasisNet -- new neural architectures that are invariant to all requisite symmetries and hence process collections of eigenspaces in a principled manner. Our networks are theoretically strong for graph representation learning -- they can approximate any spectral graph convolution. Experiments show the strength of our networks for learning spectral graph filters and learning graph positional encodings.
  arXiv  Detail & Related papers  (2022-02-25T23:11:59Z)
• Improved analysis of randomized SVD for top-eigenvector approximation [16.905540623795467]
  We present a novel analysis of the randomized SVD algorithm of citethalko2011finding and derive tight bounds in many cases of interest. Notably, this is the first work that provides non-trivial bounds of $R(hatmathbfu)$ for randomized SVD with any number of iterations.
  arXiv  Detail & Related papers  (2022-02-16T11:12:07Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  It was previously shown that the functionals $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. Here, we show that $|mathbb E[R(z)] - tilde R(z)|_F
  arXiv  Detail & Related papers  (2021-09-06T14:21:43Z)
• Minimax Estimation of Linear Functions of Eigenvectors in the Face of Small Eigen-Gaps [95.62172085878132]
  Eigenvector perturbation analysis plays a vital role in various statistical data science applications. We develop a suite of statistical theory that characterizes the perturbation of arbitrary linear functions of an unknown eigenvector. In order to mitigate a non-negligible bias issue inherent to the natural "plug-in" estimator, we develop de-biased estimators.
  arXiv  Detail & Related papers  (2021-04-07T17:55:10Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative GLASSO and Projection [58.5350491065936]
  We consider a structural assumption on the graph Laplacian matrix $L$. The first $K$ eigenvectors of $L$ are pre-selected, e.g., based on domain-specific criteria. We design an efficient hybrid graphical lasso/projection algorithm to compute the most suitable graph Laplacian matrix $L* in H_u+$ given $barC$.
  arXiv  Detail & Related papers  (2020-10-25T18:12:50Z)
• Cospectrality preserving graph modifications and eigenvector properties via walk equivalence of vertices [0.0]
  Cospectrality is a powerful generalization of exchange symmetry and can be applied to all real-valued symmetric matrices. We show that the powers of a matrix with cospectral vertices induce further local relations on its eigenvectors. Our work paves the way for flexibly exploiting hidden structural symmetries in the design of generic complex network-like systems.
  arXiv  Detail & Related papers  (2020-07-15T10:54:31Z)
• Tackling small eigen-gaps: Fine-grained eigenvector estimation and inference under heteroscedastic noise [28.637772416856194]
  Two fundamental challenges arise in eigenvector estimation and inference for a low-rank matrix from noisy observations. We propose estimation and uncertainty quantification procedures for an unknown eigenvector. We establish optimal procedures to construct confidence intervals for the unknown eigenvalues.
  arXiv  Detail & Related papers  (2020-01-14T04:26:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.