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:hep-lat/0010095 · International Journal of Modern Physics A

THE ROLE OF DIAGONALIZATION WITHIN A DIAGONALIZATION/MONTE CARLO SCHEME

Dean Lee

Published Sep 1, 2001• 1 citation
arXivHTMLPDF

Abstract

We discuss a method called quasi-sparse eigenvector diagonalization which finds the most important basis vectors of the low energy eigenstates of a quantum Hamiltonian. It can operate using any basis, either orthogonal or non-orthogonal, and any sparse Hamiltonian, either Hermitian, non-Hermitian, finite-dimensional, or infinite-dimensional. The method is part of a new computational approach which combines both diagonalization and Monte Carlo techniques.

DOI
10.1142/s0217751x01009430

Related papers

Quasi-sparse eigenvector diagonalization and stochastic error correction

Dean Lee

We briefly review the diagonalization of quantum Hamiltonians using the quasisparse eigenvector (QSE) method. We also introduce the technique of stochastic error correction, which systematically removes the truncation error of the QSE result by stochastically sampling the contribution of the remaining basis states. 1 Quasi-sparse eigenvector method Quasi-sparse eigenvector (QSE) diagonalization is a new computational method which finds approximate low-lying eigenvalues and eigenvectors for a general quantum field Hamiltonian H [1]. It handles the exponential increase in the dimension of Fock space by exploiting the sparsity of the Hamiltonian. The method is most effective when the splitting between low-lying eigenvalues is not too small compared to the size of the Hamiltonian off-diagonal entries. In such cases the low-lying eigenvectors are quasi-sparse, meaning that the vector is dominated by a small fraction of its largest components. The QSE algorithm is applied using the following steps: (1) Select a subset of orthonormal basis vectors {ei1, · · · , ein} and call the

•Jan 1, 2000•1 citation

TUTORIAL ON QUASI-SPARSE EIGENVECTOR DIAGONALIZATION

Dean Lee

We review several topics related to the diagonalization of quantum field Hamiltonians using the quasi-sparse eigenvector (QSE) method.

arXiv:hep-th/0007010•International Workshop on Non-Perturbative Methods and Lattice QCD•Apr 1, 2001•0 citations

MONTE CARLO DIAGONALIZATION OF VERY LARGE MATRICES: APPLICATION TO FERMION SYSTEMS

Hans A. De Raedt, Wolfgang von der Linden

All known Quantum-Monte-Carlo algorithms for fermions suffer from the so-called “minus-sign-problem” which is detrimental to the application of these simulation methods to fermion systems at very low temperatures and/or of very many lattice sites. We identify the origin of this fundamental problem, demonstrate that it is a very general feature, not necessarily related to the presence of fermionic degrees of freedom. We describe an novel algorithm which does not suffer from the minus-sign problem. Illustrative results for the two-dimensional Hubbard model are presented

International Journal of Modern Physics C•Feb 1, 1992•6 citations

Diagonalization of Hamiltonians for Many-Body Systems by Auxiliary Field Quantum Monte Carlo Technique

Michio Honma, T. Mizusaki, Takaharu Otsuka

We propose a Monte Carlo method for solving the quantum many-body interacting systems. Mean fields dominating the structure of low-lying states are selected by a Monte Carlo method, which generates optimum many-body basis states for diagonalizing the Hamiltonian consisting of one- and two-body terms. Not only the ground state but also low-lying excited states are obtained with their wave functions. Results are examined by comparison to exact values.

Physical Review Letters•Aug 14, 1995•159 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•0 citations

Power methods

James E. Gubernatis, Naoki Kawashima, Philipp Werner

Quantum Monte Carlo versions of the power method for finding ground states come with different names, including the projector method, diffusion Monte Carlo, and Green's function Monte Carlo. These quantum Monte Carlo methods are primarily adoptions of methods developed for classical problems. We summarize the basics of deterministic power methods, detail key features of Monte Carlo power methods, and put these concepts into the context of quantum ground state calculations. We conclude the chapter by outlining power methods that allow the computation of a few excited states. In the computation of excited states, we encounter sign problems, which are discussed inmore detail in Chapter 11. Themethods and techniques of the present chapter are very general and most usefully applied to systems of Bosons and to systems of Fermions and quantum spins that do not suffer from a sign problem. Deterministic direct and inverse power methods The power method is over a century old. As a deterministic method, it originally was combined with the deflation technique (Meyer, 2000; Stewart, 2001b) as a method to compute all the eigenvalues and eigenvectors of small matrices. Today, its deterministic use is limited primarily to special applications involving very large, sparse matrices. Many of these applications are in the study of quantum lattice models as the corresponding Hamiltonian matrices are typically very sparse. In these applications, we can perhaps initially store in computer memory the relatively small number of nonzero matrix elements and all the vectors. Soon, because of what is undoubtedly the now familiar exponentially increasing number of basis states that determines the order of the Hamiltonian matrix and hence the size of our vectors, we reach the point where computer memory restrictions allow us to store only a few vectors and we need to compute the matrix elements on the fly. When we have problems for which we cannot even store all the components of one vector, the power method's expression as a Monte Carlo procedure is our only option. With it, we can compute a few of the extremal eigenvalues, that is, a few of the largest or smallest eigenvalues. The mathematical basis for the method is simple.

Cambridge University Press eBooks•Jan 31, 2016•0 citations
We discuss a method called quasi-sparse eigenvector diagonalization which finds the most important basis vectors of the low energy eigenstates of a quantum Hamiltonian. It can operate using any basis, either orthogonal or non-orthogonal, and any sparse Hamiltonian, either Hermitian, non-Hermitian, finite-dimensional, or infinite-dimensional. The method is part of a new computational approach which combines both diagonalization and Monte Carlo techniques.
We briefly review the diagonalization of quantum Hamiltonians using the quasisparse eigenvector (QSE) method. We also introduce the technique of stochastic error correction, which systematically removes the truncation error of the QSE result by stochastically sampling the contribution of the remaining basis states. 1 Quasi-sparse eigenvector method Quasi-sparse eigenvector (QSE) diagonalization is a new computational method which finds approximate low-lying eigenvalues and eigenvectors for a general quantum field Hamiltonian H [1]. It handles the exponential increase in the dimension of Fock space by exploiting the sparsity of the Hamiltonian. The method is most effective when the splitting between low-lying eigenvalues is not too small compared to the size of the Hamiltonian off-diagonal entries. In such cases the low-lying eigenvectors are quasi-sparse, meaning that the vector is dominated by a small fraction of its largest components. The QSE algorithm is applied using the following steps: (1) Select a subset of orthonormal basis vectors {ei1, · · · , ein} and call the
All known Quantum-Monte-Carlo algorithms for fermions suffer from the so-called “minus-sign-problem” which is detrimental to the application of these simulation methods to fermion systems at very low temperatures and/or of very many lattice sites. We identify the origin of this fundamental problem, demonstrate that it is a very general feature, not necessarily related to the presence of fermionic degrees of freedom. We describe an novel algorithm which does not suffer from the minus-sign problem. Illustrative results for the two-dimensional Hubbard model are presented
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.
Quantum Monte Carlo versions of the power method for finding ground states come with different names, including the projector method, diffusion Monte Carlo, and Green's function Monte Carlo. These quantum Monte Carlo methods are primarily adoptions of methods developed for classical problems. We summarize the basics of deterministic power methods, detail key features of Monte Carlo power methods, and put these concepts into the context of quantum ground state calculations. We conclude the chapter by outlining power methods that allow the computation of a few excited states. In the computation of excited states, we encounter sign problems, which are discussed inmore detail in Chapter 11. Themethods and techniques of the present chapter are very general and most usefully applied to systems of Bosons and to systems of Fermions and quantum spins that do not suffer from a sign problem. Deterministic direct and inverse power methods The power method is over a century old. As a deterministic method, it originally was combined with the deflation technique (Meyer, 2000; Stewart, 2001b) as a method to compute all the eigenvalues and eigenvectors of small matrices. Today, its deterministic use is limited primarily to special applications involving very large, sparse matrices. Many of these applications are in the study of quantum lattice models as the corresponding Hamiltonian matrices are typically very sparse. In these applications, we can perhaps initially store in computer memory the relatively small number of nonzero matrix elements and all the vectors. Soon, because of what is undoubtedly the now familiar exponentially increasing number of basis states that determines the order of the Hamiltonian matrix and hence the size of our vectors, we reach the point where computer memory restrictions allow us to store only a few vectors and we need to compute the matrix elements on the fly. When we have problems for which we cannot even store all the components of one vector, the power method's expression as a Monte Carlo procedure is our only option. With it, we can compute a few of the extremal eigenvalues, that is, a few of the largest or smallest eigenvalues. The mathematical basis for the method is simple.