The complexity of quantum many-body problems scales exponentially with the size of the system, rendering any finite-size scaling analysis a formidable challenge. This is particularly true for methods based on the full representation of the wave function, where one simply accepts the enormous Hilbert space dimensions and performs linear algebra operations, e.g., for finding the ground state of the Hamiltonian. If the system satisfies an underlying symmetry where an operator with a degenerate spectrum commutes with the Hamiltonian, it can be block-diagonalized, thus reducing the complexity at the expense of additional bookkeeping. At the most basic level required for Krylov space techniques (like the Lanczos algorithm), it is necessary to implement a matrix-vector product of a block of the Hamiltonian with arbitrary block-wavefunctions, potentially without holding the Hamiltonian block in memory. An efficient implementation of this operation requires the calculation of the position of an arbitrary basis vector in the canonical ordering of the basis of the block. We present here an elegant and powerful, multi-dimensional approach to this problem for the U(1) U ( 1 ) symmetry appearing in problems with particle number conservation. Our divide-and-conquer algorithm uses multiple subsystems and hence generalizes previous approaches to make them scalable. In addition to the theoretical presentation of our algorithm, we provide DanceQ, a flexible and modern – header only – C++20 implementation to manipulate, enumerate, and map to its index any basis state in a given particle number sector as open source software under https://DanceQ.gitlab.io/danceq.
The complexity of quantum many-body problems scales exponentially with the size of the system, rendering any finite-size scaling analysis a formidable challenge. This is particularly true for methods based on the full representation of the wave function, where one simply accepts the enormous Hilbert space dimensions and performs linear algebra operations, e.g., for finding the ground state of the Hamiltonian. If the system satisfies an underlying symmetry where an operator with a degenerate spectrum commutes with the Hamiltonian, it can be block-diagonalized, thus reducing the complexity at the expense of additional bookkeeping. At the most basic level required for Krylov space techniques (like the Lanczos algorithm), it is necessary to implement a matrix-vector product of a block of the Hamiltonian with arbitrary block-wavefunctions, potentially without holding the Hamiltonian block in memory. An efficient implementation of this operation requires the calculation of the position of an arbitrary basis vector in the canonical ordering of the basis of the block. We present here an elegant and powerful, multi-dimensional approach to this problem for the U(1) U ( 1 ) symmetry appearing in problems with particle number conservation. Our divide-and-conquer algorithm uses multiple subsystems and hence generalizes previous approaches to make them scalable. In addition to the theoretical presentation of our algorithm, we provide DanceQ, a flexible and modern – header only – C++20 implementation to manipulate, enumerate, and map to its index any basis state in a given particle number sector as open source software under https://DanceQ.gitlab.io/danceq.
The complexity of quantum many-body problems scales exponentially with the size of the system, rendering any finite-size scaling analysis a formidable challenge. This is particularly true for methods based on the full representation of the wave function, where one simply accepts the enormous Hilbert space dimensions and performs linear algebra operations, e.g., for finding the ground state of the Hamiltonian. If the system satisfies an underlying symmetry where an operator with a degenerate spectrum commutes with the Hamiltonian, it can be block-diagonalized, thus reducing the complexity at the expense of additional bookkeeping. At the most basic level required for Krylov space techniques (like the Lanczos algorithm), it is necessary to implement a matrix-vector product of a block of the Hamiltonian with arbitrary block-wavefunctions, potentially without holding the Hamiltonian block in memory. An efficient implementation of this operation requires the calculation of the position of an arbitrary basis vector in the canonical ordering of the basis of the block. We present here an elegant and powerful, multi-dimensional approach to this problem for the U(1) U ( 1 ) symmetry appearing in problems with particle number conservation. Our divide-and-conquer algorithm uses multiple subsystems and hence generalizes previous approaches to make them scalable. In addition to the theoretical presentation of our algorithm, we provide DanceQ, a flexible and modern – header only – C++20 implementation to manipulate, enumerate, and map to its index any basis state in a given particle number sector as open source software under https://DanceQ.gitlab.io/danceq.
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 (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.
Iterative methods that operate with the full Hamiltonian matrix in the untrimmed Hilbert space of a finite system continue to be important tools for the study of one- and two-dimensional quantum spin models, in particular in the presence of frustration. To reach sensible system sizes such numerical calculations heavily depend on the use of symmetries. We describe a divide-and-conquer strategy for implementing translation symmetries of finite spin clusters, which efficiently uses and extends the "sublattice coding" of H. Q. Lin [Phys. Rev. B 42, 6561 (1990)]. With our method, the Hamiltonian matrix can be generated on-the-fly in each matrix vector multiplication, and problem dimensions beyond 10^{11} become accessible.
In ab-initio quantum chemistry, solving the electronic structure problem of a molecular system of interest to obtain an approximation of the ground and, in some cases, the excited state energies is a core and central task in various quantum chemistry processes. These include, but certainly not limited to, the calculation of the activation energy–that is the minimal energy required to launch a given chemical reaction–, the dipole and multipole moments which describe the polarity of the molecule, performing the optimization of the geometry of the molecule and searching for transition states. Furthermore, many quantum chemistry applications are predicated, not merely on the approximation of the ground state energy, but also on the corresponding first order derivatives. The body of literature of classical algorithms approximating the ground state energy and its first order derivative is extensively rich with a plethora of methods such as self-consistent mean-field methods, coupled-cluster methods, density matrix renormalization group and many more, each of which has intrinsic set of properties and characteristics that makes it suitable for specific tasks and cases. However, classical methods face a practically insurmountable challenge: the efficient computation of high accuracy approximation of ground state energies of large system sizes. This is fundamentally because the electronic structure problem provably belongs to the complexity class of QMA-hard problems. Which also means that it is out of reach for quantum algorithms as well in general. However, with certain assumptions that are expected to hold molecules of interest–that so far proved to be classically challenging because the required accuracy set by the standard of chemical accuracy threshold (generally held in quantum chemistry)– quantum algorithms can efficiently treat such cases. While originally theorized by Richard Feynmann as a potentially efficient way of simulating some classically intractable many-body systems, quantum computing has since proven to have a stronger and richer potential paving the way for the inception of new algorithms such as Shor’s algorithm for integer factorization, HHL for solving linear system of equation and Grover’s algorithm for constrained binary search, just to name a few. These algorithms provably exhibit an improvement rate that goes respectively exponentially and quadratically in the time complexity. Quantum chemistry is considered a prominent candidate to benefit from quantum computing given the variety of quantum algorithms put forth to solve the electronic structure problem of particular systems of interest. These quantum algorithm proposals can be broadly categorized in three main categories that span the spectrum: from noisy intermediate scale quantum (NISQ) computers to early and full scale fault tolerant quantum ((E)FTQC) computers. Firstly, the variational quantum eigensolver (VQE) family of quantum algorithms which variationally search for the ground state energy through the optimization of the energy of a parametrized state prepared in a quantum computer using an ansatz. Secondly, the quantum Krylov subspace diagonalization (QKSD) methods, which generate a subspace of the original Hilbert space and efficiently produce the lowest energy in said subspace as its output. Lastly, we have the quantum phase estimation (QPE) algorithms, which provably produce the ground state energy in Heisenberg scaling presenting hence a provable efficient solution. In this thesis, we firstly set to work on the problem of efficient Hamiltonian linear combination of unitaries (LCU) representation. This is mainly motivated by the wide-range impact an efficient compression of the Hamiltonian can potentially have on several quantum algorithms such as VQE, QPE...etc. We designed a method that efficiently compress the Hamiltonian representation in a way that is beneficially impactful across the set of the aforementioned quantum algorithms. Namely, we motivate and present in Sections 1.3 and 1.4 respectively, the regularized compressed double-factorization (RC-DF) and show how it reduces the energy measurement complexity both in terms of number of distinct observables and number of samples. Moreover, it also reduces the total depth of the quantum phase estimation circuit thanks to its low normalization factor. Secondly, given the importance of the energy derivatives, in Sections 2.1 and 2.2, we introduce and present an efficient quantum algorithm for the calculation of the analytic gradient of VQE energies of double-factorized Hamiltonians. Furthermore, in Section 2.1, we expand on the utility of RC-DF by presenting a quantum algorithm that determines the analytic gradient of energies measured with respect to RC-DF Hamiltonains. Third, in Section 3.1, we summarize the theoretical results of purification error-mitigation techniques, namely echo verification and virtual distillation. In Section 3.2, we report on the results of the experimental bench mark, of said techniques, performed on on Google’s Sycamore device to validate the theoretical scaling of error suppression and extrapolate the resources needed for classically intractable system sizes. Fourth, in Section 4 we establish the challenges of computing energy gradients in a quantum Krylov frame work. To overcome the problem, we provide, in Section 4.3, an efficient quantum algorithm for calculating energy derivative obtained through QKSD procedures. Our approach shows how the QKSD ground state can be prepared using quantum signal processing (QSP) and reduces the number of observables to O(1) per reduced density matrix (RDM). Lastly, in light of the importance of quantum RAMs due to their utility in a variety of quantum algorithms that require efficient initial state preparation, as explained in Section 5.5, we address the problematic exponential depth of the bucket-brigade QRAM (when decomposed). We present in Section 5.6 a very efficient Clifford+T decomposition of the bucket-brigade QRAM, which preserves the linear scaling of the depth of the circuit without introducing any additional ancilla.
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.