Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:cond-mat/0008457 · Nuclear Physics B - Proceedings Supplements

Quasi-sparse eigenvector diagonalization and stochastic error correction

Dean Lee

Published Dec 1, 2000• 4 citations
arXivHTMLPDF
DOI
10.1016/s0920-5632(00)00913-0

Related papers

Introduction to stochastic error correction methods

Dean Lee, Nathan Salwen, Mark Windoloski

arXiv:hep-lat/0010039•Physics Letters B•Mar 1, 2001•36 citations

Good error-correcting codes based on very sparse matrices (vol 45, pg 339, 1999)

Djc MacKay

•Jul 1, 2001•3 citations

Error Correcting Codes Based on Probabilistic Decoding and Sparse Matrices

Hironori Uchikawa

Mathematics for industry•Jan 1, 2014•0 citations

Errata for "good error-correcting codes based on very sparse matrices"

David Mackay

IEEE Transactions on Information Theory•Jul 1, 2001•13 citations

Non-perturbative Methods in Modal Field Theory

Nathan Salwen

Several issues in the modal approach to quantum field theory are discussed. Within the formalism of spherical field theory, differential renormalization is presented and shown to result in a finite number of renormalization parameters. Computations of the massless Thirring model in 1+1 dimensions are presented using this approach. Diagonalization techniques in periodic field theory are demonstrated. Issues of very large Hilbert spaces are considered and several approaches are presented. The quasi sparse eigenvector (QSE) approach takes advantage of the relatively small number of basis states that typically contribute significantly to any particular eigenvector. Stochastic correction methods use Monte Carlo calculations to calculate higher order corrections to the quasi sparse result. The quasi sparse eigenvector method and stochastic error correction are applied to the Hubbard model. With U/t=4, the shift in the ground energy below the U=0 value is found to within 1% for the 8x8 Hubbard model with 25/64 filling.

arXiv:hep-lat/0212035•Dec 19, 2002•6 citations

Polynomial-time exact diagonalization via sparse guided eigenwalks

Zachary E. Chin, Mario Motta, Javier Robledo Moreno +3 more

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.

quant-pharXiv:2606.23967•Jun 24, 2026•1 citation
Several issues in the modal approach to quantum field theory are discussed. Within the formalism of spherical field theory, differential renormalization is presented and shown to result in a finite number of renormalization parameters. Computations of the massless Thirring model in 1+1 dimensions are presented using this approach. Diagonalization techniques in periodic field theory are demonstrated. Issues of very large Hilbert spaces are considered and several approaches are presented. The quasi sparse eigenvector (QSE) approach takes advantage of the relatively small number of basis states that typically contribute significantly to any particular eigenvector. Stochastic correction methods use Monte Carlo calculations to calculate higher order corrections to the quasi sparse result. The quasi sparse eigenvector method and stochastic error correction are applied to the Hubbard model. With U/t=4, the shift in the ground energy below the U=0 value is found to within 1% for the 8x8 Hubbard model with 25/64 filling.
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 2n2^n2n-dimensional, poly(n){\rm poly}(n)poly(n)-sparse Hamiltonian has an O(1)\mathcal{O}(1)O(1)-sparse extremal eigenvector and one support element is known, then an exact eigenvector with the same eigenvalue can be computed classically in poly(n){\rm poly}(n)poly(n) time. The same conclusion follows when the O(1)\mathcal{O}(1)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.