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:physics/0004016 · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics

Fast algorithm for finding the eigenvalue distribution of very large matrices

Anthony Hams, Hans A. De Raedt

Published Sep 1, 2000• 202 citations
arXivHTMLPDF

Abstract

A theoretical analysis is given of the equation of motion method, due to Alben et al. [Phys. Rev. B 12, 4090 (1975)], to compute the eigenvalue distribution (density of states) of very large matrices. The salient feature of this method is that for matrices of the kind encountered in quantum physics the memory and CPU requirements of this method scale linearly with the dimension of the matrix. We derive a rigorous estimate of the statistical error, supporting earlier observations that the computational efficiency of this approach increases with the matrix size. We use this method and an imaginary-time version of it to compute the energy and specific heat of three different, exactly solvable, spin-1/2 models, and compare with the exact results to study the dependence of the statistical errors on sample and matrix size.

DOI
10.1103/physreve.62.4365

Related papers

DENSITIES OF STATES OF MEGA-DIMENSIONAL HAMILTONIAN MATRICES

Richard N. Silver, Heinrich Röder

We propose a statistical method to estimate densities of states (DOS) and thermodynamic functions of very large Hamiltonian matrices. Orthogonal polynomials are defined on the interval between lower and upper energy bounds. The DOS is represented by a kernel polynomial constructed out of polynomial moments of the DOS and modified to damp the Gibbs phenomenon. The moments are stochastically evaluated using matrixvector multiplications on Gaussian random vectors and the polynomial recurrence relations. The resulting kernel estimate is a controlled approximation to the true DOS, because it also provides estimates of statistical and systematic errors. For a given fractional energy resolution and statistical accuracy, the required cpu time and memory scale linearly in the number of states for sparse Hamiltonians. The method is demonstrated for the two-dimensional Heisenberg anti-ferromagnet with the number of states as large as 2 26 . Results are compared to exact diagonalization where available.

International Journal of Modern Physics C•Aug 1, 1994•151 citations

A novel algorithm for calculation of the extreme eigenvalues of large Hermitian matrices

Yuko Okamoto, Humphrey J. Maris

A new fast algorithm for calculating a few maximum (or minimum) eigenvalues and the corresponding eigenvectors of large N × N Hermitian matrices is presented. The method is based on a molecular dynamics algorithm for N coupled harmonic oscillators. The time step for iteration is chosen so that only the normal mode with the maximum eigenvalues grows exponentially. Other eigenvalues and eigenvectors are obtained one by one from the largest eigenvalue by repeating the process in subspaces orthogonal to the previous modes. The characteristics of the algorithm lie in the simplicity, speed (CPU time α N2), and memory efficiency (O(N) besides the matrix). The effectiveness of the algorithm is illustrated by calculation of the groundstate and first-excited state energies of the Heisenberg model for an antiferromagnetic chain with N up to 16384.

Computer Physics Communications•Jul 1, 1993•16 citations

Computing eigenvalues of matrices in a quantum computer

Changpeng Shao

Eigenproblem arises in a large number of disciplines of sciences and engineering. Combining quantum algorithms to solve linear differential equations, quantum singular value estimation and quantum phase estimation, we propose quantum algorithms to compute the eigenvalues of diagonalizable matrices of two types: matrices that only have real eigenvalues and normal matrices. The quantum algorithms return a quantum state such that the first register stores eigenvalues and the second register stores the corresponding eigenvectors. For normal matrices, the complexity to obtain this quantum state is dominated by the complexity to perform quantum singular value estimation. For the other case, the complexity is determined by the solving of a linear system of differential equations. Under certain conditions (e.g. sparse), the complexities are polylog on the size $n$ of the given matrix. If we perform measurements, then we can obtain all the eigenvalues classically. If $M$ is $s$ sparse, then the complexity is $\widetilde{O}(sn\|M\|_{\max}\kappa^2/\epsilon^2)$, where $\kappa$ is the condition number of the matrix of eigenvectors.

•Dec 17, 2019•4 citations

RANDOMIZED METHOD FOR ESTIMATING THE VON NEUMANN ENTROPY OF LARGE-SCALE DENSITY MATRICES

Hayoung Choi, Xuming Song, Yuanming Shi

In this article the randomized algorithm for estimating the von Neumann entropy of large-scale density matrices is considered. By capturing the dominant eigenspace via a k-rank approximation of the density matrix we estimate the entropy. We analyze the error bound with the eigenvalues of density matrix. Numerical experiments show that the proposed method is extensively efficient for large-scale density matrices.

IEEE Global Conference on Signal and Information Processing•Nov 1, 2018•2 citations

Exact Numerical Evaluations for Two-Dimensional Ising Models with Arbitrary Bond Configurations

Tsuguhiro Tamaribuchi

An algorithm to make exact numerical evaluations for finite-size two-dimensional Ising models with arbitrary bond configurations under the toroidal periodic boundary condition is proposed. The algorithm is based on a modified version of the Cholesky-like factorization (MCLF) method and columnwise matrix inversions of very sparse skew-symmetric matrices. This enables us to exactly evaluate the internal energy, the specific heat and the entropy without use of any numerical differentiation. It also provides a general method to get the numerical value of a Pfaffian with its sign. The amount of memory and the CPU time required to get a result is measured to be proportional to N1.5 ∼1.8 and N2.4 ∼2.8, respectively, where N is the number of the spins. As a demonstration we show temperature dependencies of the specific heat and the internal energy along the Nishimori line for ±J models on lattices with sizes 25 ×25, 50 ×50 and 100 ×100, and we know the performance achieved is very high. Size-dependent anomalous behaviors cannot be seen in the result for the specific heat.

Progress of Theoretical Physics Supplement•Jan 1, 2005•0 citations

An Attempt to Calculate Energy Eigenvalues in Quantum Systems of Large Sizes

Tomo Munehisa, Yasuko Munehisa

We report an attempt to calculate energy eigenvalues of large quantum systems by the diagonalization of an effectively truncated Hamiltonian matrix. For this purpose we employ a specific way to systematically make a set of orthogonal states from a trial wavefunction and the Hamiltonian. In comparison with the Lanczos method, which is quite powerful if the size of the system is within the memory capacity of computers, our method requires much less memory resources at the cost of the extreme accuracy. In this paper we demonstrate that our method works well in the systems of one-dimensional frustrated spins up to 48 sites, of bosons on a chain up to 32 sites and of fermions on a ladder up to 28 sites. We will see this method enables us to study eigenvalues of these quantum systems within reasonable accuracy.

arXiv:cond-mat/9912295•Journal of the Physical Society of Japan•Jul 15, 2000•4 citations
A theoretical analysis is given of the equation of motion method, due to Alben et al. [Phys. Rev. B 12, 4090 (1975)], to compute the eigenvalue distribution (density of states) of very large matrices. The salient feature of this method is that for matrices of the kind encountered in quantum physics the memory and CPU requirements of this method scale linearly with the dimension of the matrix. We derive a rigorous estimate of the statistical error, supporting earlier observations that the computational efficiency of this approach increases with the matrix size. We use this method and an imaginary-time version of it to compute the energy and specific heat of three different, exactly solvable, spin-1/2 models, and compare with the exact results to study the dependence of the statistical errors on sample and matrix size.
We propose a statistical method to estimate densities of states (DOS) and thermodynamic functions of very large Hamiltonian matrices. Orthogonal polynomials are defined on the interval between lower and upper energy bounds. The DOS is represented by a kernel polynomial constructed out of polynomial moments of the DOS and modified to damp the Gibbs phenomenon. The moments are stochastically evaluated using matrixvector multiplications on Gaussian random vectors and the polynomial recurrence relations. The resulting kernel estimate is a controlled approximation to the true DOS, because it also provides estimates of statistical and systematic errors. For a given fractional energy resolution and statistical accuracy, the required cpu time and memory scale linearly in the number of states for sparse Hamiltonians. The method is demonstrated for the two-dimensional Heisenberg anti-ferromagnet with the number of states as large as 2 26 . Results are compared to exact diagonalization where available.
A new fast algorithm for calculating a few maximum (or minimum) eigenvalues and the corresponding eigenvectors of large N × N Hermitian matrices is presented. The method is based on a molecular dynamics algorithm for N coupled harmonic oscillators. The time step for iteration is chosen so that only the normal mode with the maximum eigenvalues grows exponentially. Other eigenvalues and eigenvectors are obtained one by one from the largest eigenvalue by repeating the process in subspaces orthogonal to the previous modes. The characteristics of the algorithm lie in the simplicity, speed (CPU time α N2), and memory efficiency (O(N) besides the matrix). The effectiveness of the algorithm is illustrated by calculation of the groundstate and first-excited state energies of the Heisenberg model for an antiferromagnetic chain with N up to 16384.
Eigenproblem arises in a large number of disciplines of sciences and engineering. Combining quantum algorithms to solve linear differential equations, quantum singular value estimation and quantum phase estimation, we propose quantum algorithms to compute the eigenvalues of diagonalizable matrices of two types: matrices that only have real eigenvalues and normal matrices. The quantum algorithms return a quantum state such that the first register stores eigenvalues and the second register stores the corresponding eigenvectors. For normal matrices, the complexity to obtain this quantum state is dominated by the complexity to perform quantum singular value estimation. For the other case, the complexity is determined by the solving of a linear system of differential equations. Under certain conditions (e.g. sparse), the complexities are polylog on the size nnn of the given matrix. If we perform measurements, then we can obtain all the eigenvalues classically. If MMM is sss sparse, then the complexity is O~(sn∥M∥max⁡κ2/ϵ2)\widetilde{O}(sn\|M\|_{\max}\kappa^2/\epsilon^2)O(sn∥M∥max​κ2/ϵ2), where κ\kappaκ is the condition number of the matrix of eigenvectors.
An algorithm to make exact numerical evaluations for finite-size two-dimensional Ising models with arbitrary bond configurations under the toroidal periodic boundary condition is proposed. The algorithm is based on a modified version of the Cholesky-like factorization (MCLF) method and columnwise matrix inversions of very sparse skew-symmetric matrices. This enables us to exactly evaluate the internal energy, the specific heat and the entropy without use of any numerical differentiation. It also provides a general method to get the numerical value of a Pfaffian with its sign. The amount of memory and the CPU time required to get a result is measured to be proportional to N1.5 ∼1.8 and N2.4 ∼2.8, respectively, where N is the number of the spins. As a demonstration we show temperature dependencies of the specific heat and the internal energy along the Nishimori line for ±J models on lattices with sizes 25 ×25, 50 ×50 and 100 ×100, and we know the performance achieved is very high. Size-dependent anomalous behaviors cannot be seen in the result for the specific heat.
We report an attempt to calculate energy eigenvalues of large quantum systems by the diagonalization of an effectively truncated Hamiltonian matrix. For this purpose we employ a specific way to systematically make a set of orthogonal states from a trial wavefunction and the Hamiltonian. In comparison with the Lanczos method, which is quite powerful if the size of the system is within the memory capacity of computers, our method requires much less memory resources at the cost of the extreme accuracy. In this paper we demonstrate that our method works well in the systems of one-dimensional frustrated spins up to 48 sites, of bosons on a chain up to 32 sites and of fermions on a ladder up to 28 sites. We will see this method enables us to study eigenvalues of these quantum systems within reasonable accuracy.