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

Computer Physics Communications

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

Yuko Okamoto, Humphrey J. Maris

Published Jul 1, 1993• 16 citations
Publisher

Abstract

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.

DOI
10.1016/0010-4655(93)90131-u

Related papers

Fast algorithm for finding the eigenvalue distribution of very large matrices

Anthony Hams, Hans A. De Raedt

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.

arXiv:physics/0004016•Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics•Sep 1, 2000•202 citations

Numerical solution of larges=1/2 ands=1 Heisenberg antiferromagnetic spin chains using a truncated basis expansion

Mitchel D. Kovarik

A new method of determining the spectra of simple quantum-mechanical spin Hamiltonians by direct Hamiltonian-matrix diagonalization is presented. The method is illustrated by applying it to the isotropic one-dimensional Heisenberg antiferromagnet, for which calculations were performed for longer spin chains than by previous direct Hamiltonian-matrix diagonalizations. For spin s=1/2 it was possible to accurately determine the ground- and first-excited-state energies for chains of length N=32 and 64. For s=1 the longest chain for which a similar computation was performed was N=32; the singlet-triplet Haldane gap is found to be 0.421\ifmmode\pm\else\textpm\fi{}0.005 which is consistent with earlier Monte Carlo results. Long-spin-chain calculations are performed iteratively by solving smaller-chain problems, and constructing from their eigenvalues, and eigenstates, the longer-spin-chain basis and Hamiltonian matrices. The computations were performed on a small computer, which suggests that much larger problems could be handled with a parallel-processing supercomputer.

Physical review. B, Condensed matter•Apr 1, 1990•15 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

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

T. Munehisa, Y. 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.

•Aug 15, 2016•3 citations

Heisenberg-Limited Quantum Eigenvalue Estimation for Non-normal Matrices

Yukun Zhang, Yusen Wu, Xiao Yuan

Estimating the eigenvalues of non-normal matrices is a foundational problem with far-reaching implications, from modeling non-Hermitian quantum systems to analyzing complex fluid dynamics. Yet, this task remains beyond the reach of standard quantum algorithms, which are predominantly tailored for Hermitian matrices. Here we introduce a new class of quantum algorithms that directly address this challenge. The central idea is to construct eigenvalue signals through customized quantum simulation protocols and extract them using advanced classical signal-processing techniques, thereby enabling accurate and efficient eigenvalue estimation for general non-normal matrices. Crucially, when supplied with purified quantum state inputs, our algorithms attain Heisenberg-limited precision--achieving optimal performance. These results extend the powerful guided local Hamiltonian framework into the non-Hermitian regime, significantly broadening the frontier of quantum computational advantage. Our work lays the foundation for a rigorous and scalable quantum computing approach to one of the most demanding problems in linear algebra.

arXiv:2510.19651•Oct 22, 2025•0 citations

Quantum algorithm for dynamic mode decomposition integrated with a quantum differential equation solver

Yuta Mizuno, Tamiki Komatsuzaki

We present a quantum algorithm that analyzes time series data simulated by a quantum differential equation solver. The proposed algorithm is a quantum version of a dynamic mode decomposition algorithm used in diverse fields such as fluid dynamics, molecular dynamics, and epidemiology. Our quantum algorithm can also compute matrix eigenvalues and eigenvectors by analyzing the corresponding linear dynamical system. Our algorithm handles a broad range of matrices, particularly those with complex eigenvalues. The complexity of our quantum algorithm is O ( poly log N ) for an N -dimensional system. This is an exponential speedup over known classical algorithms with at least O ( N ) complexity. Thus, our quantum algorithm is expected to enable high-dimensional dynamical systems analysis and large matrix eigenvalue decomposition, intractable for classical computers. Published by the American Physical Society 2024

arXiv:2310.17783•Physical Review Research•Oct 11, 2024•5 citations
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.
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.
A new method of determining the spectra of simple quantum-mechanical spin Hamiltonians by direct Hamiltonian-matrix diagonalization is presented. The method is illustrated by applying it to the isotropic one-dimensional Heisenberg antiferromagnet, for which calculations were performed for longer spin chains than by previous direct Hamiltonian-matrix diagonalizations. For spin s=1/2 it was possible to accurately determine the ground- and first-excited-state energies for chains of length N=32 and 64. For s=1 the longest chain for which a similar computation was performed was N=32; the singlet-triplet Haldane gap is found to be 0.421\ifmmode\pm\else\textpm\fi{}0.005 which is consistent with earlier Monte Carlo results. Long-spin-chain calculations are performed iteratively by solving smaller-chain problems, and constructing from their eigenvalues, and eigenstates, the longer-spin-chain basis and Hamiltonian matrices. The computations were performed on a small computer, which suggests that much larger problems could be handled with a parallel-processing supercomputer.
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.
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.
Estimating the eigenvalues of non-normal matrices is a foundational problem with far-reaching implications, from modeling non-Hermitian quantum systems to analyzing complex fluid dynamics. Yet, this task remains beyond the reach of standard quantum algorithms, which are predominantly tailored for Hermitian matrices. Here we introduce a new class of quantum algorithms that directly address this challenge. The central idea is to construct eigenvalue signals through customized quantum simulation protocols and extract them using advanced classical signal-processing techniques, thereby enabling accurate and efficient eigenvalue estimation for general non-normal matrices. Crucially, when supplied with purified quantum state inputs, our algorithms attain Heisenberg-limited precision--achieving optimal performance. These results extend the powerful guided local Hamiltonian framework into the non-Hermitian regime, significantly broadening the frontier of quantum computational advantage. Our work lays the foundation for a rigorous and scalable quantum computing approach to one of the most demanding problems in linear algebra.
We present a quantum algorithm that analyzes time series data simulated by a quantum differential equation solver. The proposed algorithm is a quantum version of a dynamic mode decomposition algorithm used in diverse fields such as fluid dynamics, molecular dynamics, and epidemiology. Our quantum algorithm can also compute matrix eigenvalues and eigenvectors by analyzing the corresponding linear dynamical system. Our algorithm handles a broad range of matrices, particularly those with complex eigenvalues. The complexity of our quantum algorithm is O ( poly log N ) for an N -dimensional system. This is an exponential speedup over known classical algorithms with at least O ( N ) complexity. Thus, our quantum algorithm is expected to enable high-dimensional dynamical systems analysis and large matrix eigenvalue decomposition, intractable for classical computers. Published by the American Physical Society 2024