We present algorithmic improvements for fast and memory-efficient use of discrete spatial symmetries in exact diagonalization computations of quantum many-body systems. These techniques allow us to work flexibly in the reduced basis of symmetry-adapted wave functions. Moreover, a parallelization scheme for the Hamiltonian-vector multiplication in the Lanczos procedure for distributed memory machines avoiding load-balancing problems is proposed. We demonstrate that using these methods low-energy properties of systems of up to 50 spin-$1/2$ particles can be successfully determined.
We present algorithmic improvements for fast and memory-efficient use of discrete spatial symmetries in exact diagonalization computations of quantum many-body systems. These techniques allow us to work flexibly in the reduced basis of symmetry-adapted wave functions. Moreover, a parallelization scheme for the Hamiltonian-vector multiplication in the Lanczos procedure for distributed memory machines avoiding load-balancing problems is proposed. We demonstrate that using these methods low-energy properties of systems of up to 50 spin-1/2 particles can be successfully determined.
Abstract A many-body Hamiltonian can be block-diagonalized by expressing it in terms of symmetry-adapted basis states. Finding the group orbit representatives of these basis states and their corresponding symmetries is currently a memory/computational bottleneck on classical computers during exact diagonalization. We apply Grover’s search in the form of a minimization procedure to solve this problem. Our quantum solution provides an exponential reduction in memory, and a quadratic speedup in time over classical methods. We discuss explicitly the full circuit implementation of Grover minimization as applied to this problem, finding that the oracle only scales as polylog in the size of the group, which acts as the search space. Further, we design an error mitigation scheme that, with no additional qubits, reduces the impact of bit-flip errors on the computation, with the magnitude of mitigation directly correlated with the error rate, improving the utility of the algorithm in the Noisy Intermediate Scale Quantum era.
Exact diagonalization (ED) is a cornerstone technique in quantum many-body physics, enabling precise solutions to the many-body Schrödinger equation for interacting quantum systems. Despite its utility in studying ground states, excited states, and dynamical behaviors, the exponential growth of the Hilbert space with system size presents significant computational challenges. We introduce XDiag, an open-source software package designed to combine advanced and efficient algorithms for ED with and without symmetry-adapted bases with user-friendly interfaces. Implemented in C++ for computational efficiency and wrapped in Julia for ease of use, XDiag provides a comprehensive toolkit for ED calculations. Key features of XDiag include the first publicly accessible implementation of sublattice coding algorithms for large-scale spin system diagonalizations, efficient Lin table algorithms for symmetry lookups, and random-hashing techniques for distributed memory parallelization. The library supports various Hilbert space types (e.g., spin-1/2, electron, and t-J models), facilitates symmetry-adapted block calculations, and automates symmetry considerations. The package is complemented by extensive documentation, a user guide, reproducible benchmarks demonstrating near-linear scaling on thousands of CPU cores, and over 20 examples covering ground-state calculations, spectral functions, time evolution, and thermal states. By integrating high-performance computing with accessible scripting capabilities, XDiag allows researchers to perform state-of-the-art ED simulations and explore quantum many-body phenomena with unprecedented flexibility and efficiency.
Exact diagonalization is a well-established method for simulating small quantum systems. Its applicability is limited by the exponential growth of the Hamiltonian matrix that needs to be diagonalized. Physical symmetries are usually utilized to reduce the matrix dimension, and distributed-memory parallelism is employed to explore larger systems. This paper focuses on an implementation of the core distributed algorithms, with a special emphasis on the matrix-vector product. Instead of the conventional MPI+X paradigm, Chapel is chosen as the language in this work.
The physics of strongly correlated materials poses one of the most challenging problems in condensed-matter sciences. Standard approximations applicable to wide classes of materials such as the local density approximation fail, due to the importance of the Coulomb repulsion between localized electrons. Instead, we resort to non-perturbative many-body methods. The calculations are, however, only feasible for rather small model systems. The full Hamiltonian of a real material is approximated by a model Hamiltonian comprising only the most important electronic degrees of freedom, while the effect of all other electrons is included in an average way by renormalizing the parameters. Realistic calculations of strongly correlated materials need to include sufficiently many of these electronic degrees of freedom. The new generation of massively parallel supercomputers allows for these realistic calculations. However, exploiting their computational power requires newly devised algorithms. As a solver we use the Lanczos method, which needs the full many-body state of the correlated system. It is thus limited by the available main memory. The foremost problem for a distributed-memory implementation is that the multiplication of the Hamiltonian to the many-body state leads to highly non-local memory access patterns. A simple yet important observation leads to an efficient solution: in the kinetic term of the Hamiltonian the electron-spin is conserved. Thus, writing the many-body vector as a matrix v(iup,idn), where the indices label spin-configurations, we find that the hopping term only connects vector elements that differ in one index. Hence, storing entire slices v(iup,:) on one node, the kinetic term for the spin-down electrons is local to that process. After transposing v, the same is true for the hopping of the spin-up electrons. With an efficient matrix transpose, implemented via MPI collectives, we thus obtain a version of the Lanczos method that efficiently well on JUBL, Jülich's Blue Gene/L. Using the code we treated two-orbital Hubbard Models which show interesting Mott-band insulator transitions. Kohn's criterium which determines the phase of a system by ground-state properties alone, namely the response of the ground-state energies to a vector potential, was employed. This vector potential can be equivalently regarded as a change in boundary conditions, requiring complex wave vectors. We found that half-filled systems become metallic in the region between a band and Mott insulating phase. To extrapolate to infinite system sizes and therefore getting access to an arbitrarily high resolution in reciprocal space, we use cluster perturbation theory (CPT). It works by diagonalizing a finite cluster exactly and then treating the hopping between identical clusters perturbatively in strong coupling perturbation theory. This leads to an effectively infinite chain. Due to our efficient Lanczos implementation it is possible to calculate relatively large clusters, minimizing finite-size effects. The combination of our Lanczos code and CPT allowed for a treatment of the the organic metal TTF-TCNQ. We were able to solve a long-standing problem in the interpretation of its experimental spectra. Being an interesting one-dimensional metal TTF-TCNQ has been studied thoroughly for more than 30 years. Theoretical estimates as well as experimental measurements suggest values for the parameters of the Hubbard model t and U. With these values Hubbard model calculations show qualitatively the same features as APRES experiments, namely the signatures of spin-charge separation at the Gamma-point. But in order to fit the experimental data to the numerical calculations t has to be doubled, which translates into a broadening of the spectra. This ad-hoc adjustment is not only unsatisfactory but also the temperature dependence of the spectral function is incorrectly reproduced. We resolved this problem by properly including nearest-neighbor Coulomb interactions. Recent DFT calculations show that indeed the commonly used values of t and U are correct. But Coulomb interactions between electrons on neighboring sites are also significant and must not be neglected. Thus, we studied the effect of the next-neighbor interaction parameter V being at about U/2. Including V in our Lanczos calculations for obtaining the angular-integrated spectral function shows that its effect is to broaden the spectra, comparable to increasing the value of t. Moreover, we found that doubling t indeed mimics the effect of Vapprox U/2. Surprisingly, the broadening of the spectrum as a result of V can be understood in first-order Rayleigh-Schrödinger perturbation theory.
The essence of quantum magnetism lies in correlated many-body states. They determine the physical properties beyond paramagnetism. Even constructions as simple as singlets or triplets cannot be understood without the mathematical concept of superpositions. This is even more evident if time evolution of quantum states and phenomena such as quantum coherenceQuantum coherence are considered. The major approach to assess correlated many-body states in quantum magnetism of molecules is exact diagonalizationDiagonalization of the many-body Hamiltonian describing the physical system. Symmetries are of great help when tackling the numerical task of matrix diagonalization since they allow to decompose a problem of large Hilbert spaceHilbert space dimension into a number of smaller problems. This approach will be presented first. It rests on the identification of the available symmetries—e.g., U(1), SU(2), as well as point groupsPoint group—and their application. However, the applicability of exact diagonalizationDiagonalization is limited by the exponential growth of the Hilbert spaceHilbert space of the spin system with the number of spins: $$\dim \left( {\mathcal{H}} \right) = \mathop \prod \nolimits_{i} \left( {2 s_{i} + 1} \right)$$ . Nowadays, complex Hermitian matricesHermitian matrices of a linear dimension of about 100,000 can be completely diagonalized on supercomputers which limits the number of spins depending on their size si to just a few. I will therefore present a very accurate approximation to exact diagonalization that rests on Lanczos procedures and the concept of typicality. The most popular version, the finite-temperature Lanczos methodFinite-Temperature Lanczos Method (FTLM), allows to evaluate low-energy spectroscopic data, thermal averages as well as time evolutions for systems with Hilbert space dimensions of up to about 1011. Hands-on experience and examples will be provided.
Exact diagonalization (ED) is one of the most reliable and established numerical methods of quantum many-body theory.It is precise, unbiased, and general enough to be applicable to a huge variety of problems in condensed matter physics.Mathematically, ED is a linear algebra problem involving a matrix called the Hamiltonian.For a system of spin-1/2 particles, the size of this matrix scales exponentially (as O(2 N )) with the number of particles N .Very fast scaling of memory requirements with system size is the main computational challenge of the method.There are a few techniques allowing one to lower the amount of storage used by the Hamiltonian.For example, one can store only the non-zero elements of the Hamiltonian.This is beneficial when the Hamiltonian is sparse, which is usually the case in condensed matter physics.One can even take it one step further and avoid storing the matrix altogether by instead computing matrix elements on the fly.