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 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.
Computation of eigenvalues and eigenvectors of a sparse Hermitian matrix is a fundamental problem in algebra, arising both as a problem of independent interest and as a key subroutine in a wide range of computational and scientific applications. In this work, we develop a quantum algorithm that determines the spectrum of a sparse Hermitian matrix, defined as the set of its distinct eigenvalues, and for each eigenvalue, prepares a corresponding eigenvector as a quantum state in its eigenspace. The eigenvalues are represented as binary strings with a prescribed precision, while the corresponding eigenvectors are kept as quantum states, eliminating the need to reconstruct their classical counterparts. The algorithm instead enables estimation of expectation values ⟨x∣M∣x⟩, where ∣x⟩ is a prepared eigenstate and M is an observable. For an n×ns-sparse Hermitian matrix H, dense methods based on Householder tridiagonalization and QR iteration compute all eigenvalues and eigenvectors in O(n3) time. Exploiting sparsity, the Lanczos method computes all eigenvalues in O(n2s) time in exact arithmetic, but recovering all eigenvectors still requires O(n3) time. In contrast, our algorithm runs in time O~(ns2log2n/Δmin), where Δmin denotes the minimum spectral gap of the normalized matrix. For inverse gaps up to Δmin−1=O(n), the most favorable scaling for n distinct eigenvalues, attained by nearly uniformly spaced spectra such as those of perfect-state-transfer spin chains and the Sylvester-Kac matrix, and for sparsity up to s=o(n/logn), the proposed algorithm achieves an improved asymptotic runtime over the classical O(n3) approach for computing all eigenvalues and eigenvectors, under standard sparse-access assumptions.
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.
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 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 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