This page contains supplementary files for the paper Numerical Algebraic Geometry for Energy Computations on Tensor Train Varieties. In this article, we study energy minimization problems from quantum chemistry through the viewpoint of computational algebraic geometry. Specifically, we minimize the Rayleigh quotient of a Hamiltonian restricted to a tensor train (TT) variety. The complex critical points of this optimization problem approximate the eigenstates of a quantum system, while the global minimizer approximates the ground state. We call the number of these complex critical points the Rayleigh–Ritz (RR) degree. The paper develops several new geometric and computational tools for understanding TT varieties. We characterize situations in which such varieties are Segre products, describe their defining ideals, and provide a birational parametrization via products of Grassmannians. Using methods from numerical algebraic geometry, we compute all critical points of the Rayleigh–Ritz optimization problem for various TT and determinantal varieties. We use these results to benchmark state-of-the-art methods, the Alternating Linear Scheme and Density Matrix Renormalization Group. Our experiments reveal, in small cases, the presence of multiple local minima and demonstrate that ALS may converge to suboptimal solutions. Along the way, we study the Rayleigh-Ritz degree, and we introduce the Rayleigh-Ritz discriminant, which describes Hamiltonians that lead to deficient number of critical points. The supplementary files included here contain additional data, scripts, and examples that complement the theoretical results presented in the paper.
This page contains supplementary files for the paper Numerical Algebraic Geometry for Energy Computations on Tensor Train Varieties. In this article, we study energy minimization problems from quantum chemistry through the viewpoint of computational algebraic geometry. Specifically, we minimize the Rayleigh quotient of a Hamiltonian restricted to a tensor train (TT) variety. The complex critical points of this optimization problem approximate the eigenstates of a quantum system, while the global minimizer approximates the ground state. We call the number of these complex critical points the Rayleigh–Ritz (RR) degree. The paper develops several new geometric and computational tools for understanding TT varieties. We characterize situations in which such varieties are Segre products, describe their defining ideals, and provide a birational parametrization via products of Grassmannians. Using methods from numerical algebraic geometry, we compute all critical points of the Rayleigh–Ritz optimization problem for various TT and determinantal varieties. We use these results to benchmark state-of-the-art methods, the Alternating Linear Scheme and Density Matrix Renormalization Group. Our experiments reveal, in small cases, the presence of multiple local minima and demonstrate that ALS may converge to suboptimal solutions. Along the way, we study the Rayleigh-Ritz degree, and we introduce the Rayleigh-Ritz discriminant, which describes Hamiltonians that lead to deficient number of critical points. The supplementary files included here contain additional data, scripts, and examples that complement the theoretical results presented in the paper.
We study energy minimization problems in quantum chemistry through the lens of computational algebraic geometry. We focus on minimizing the Rayleigh quotient of a Hamiltonian over a tensor train variety. The complex critical points of this problem approximate eigenstates of the quantum system, with the global minimum approximating the ground state. We call the number of critical points the Rayleigh-Ritz degree. We first study the Rayleigh-Ritz degree and introduce the Rayleigh-Ritz discriminant, which describes Hamiltonians that lead to a deficient number of critical points. We then specialize this framework to tensor train varieties: we identify instances when they are Segre products of projective spaces, report what we know about their defining ideals, and present a birational parametrization from products of Grassmannians. We use homotopy continuation to compute all critical points of this optimization problem over various tensor train and determinantal varieties. Finally, we use these results to benchmark state-of-the-art methods, the Alternating Linear Scheme and Density Matrix Renormalization Group.
The tensor train (TT) is a popular way of representing high-dimensional hyper-rectangular data structures called tensors. It is widely used, for example, in quantum chemistry under the name “matrix product state”. The complexity of the TT model mainly depends on the bond dimensions that connect TT cores, constituting the model. Unlike canonical polyadic decomposition, the TT model complexity may depend on the order of the modes/indices in the data structures or the order of the core tensors in the TT, in general. This letter aims to provide methods for optimizing the order of the modes to reduce the bond dimensions. Since the number of possible orderings of the cores is exponentially high, we propose a greedy algorithm that provides a suboptimal solution. We consider three problem setups, i.e., specifications of the tensor: tensor given by a list of all its elements, tensor described by a TT model with some default order of the modes, and tensor obtained by sampling a multivariate function.
The tensor train (TT) approximation of electronic wave functions lies at the core of the quantum chemistry density matrix renormalization group (QC-DMRG) method, a recent state-of-the-art method for numerically solving the N-electron Schrödinger equation. It is well known that the accuracy of TT approximations is governed by the decay of the associated singular values, which in turn strongly depends on the ordering of the one-body basis. Here we find that the singular values s1≥s2≥⋯≥sd of tensors representing ground states of noninteracting Hamiltonians possess a surprising inversion symmetry, s1sd=s2sd−1=s3sd−2=…, thus reducing the tail behavior to the leading singular value and a single hidden invariant, which moreover depends explicitly on the ordering of the basis. For correlated wave functions, we find that the tail is upper bounded by a suitable superposition of the invariants. Optimizing the invariants or their superposition thus provides a new ordering scheme for QC-DMRG. Numerical tests on simple examples, i.e., linear combinations of a few Slater determinants, show that the new scheme reduces the tail of the singular values by several orders of magnitude over existing methods, including the widely used Fiedler order.
Quantification of stochastic or quantum systems by a joint probability density or wave function is a notoriously difficult computational problem, since the solution depends on all possible states (or realizations) of the system. Due to this combinatorial flavor, even a system containing as few as ten particles may yield as many as 1010 discretized states. None of even modern supercomputers are capable to cope with this curse of dimensionality straightforwardly, when the amount of quantum particles, for example, grows up to more or less interesting order of hundreds. A traditional approach for a long time was to avoid models formulated in terms of probabilistic functions, and simulate particular system realizations in a randomized process. Since different times in different communities, data-sparse methods came into play. Generally, they aim to define all data points indirectly, by a map from a low amount of representers, and recast all operations (e.g. linear system solution) from the initial data to the effective parameters. The most advanced techniques can be applied (at least, tried) to any given array, and do not rely explicitly on its origin. The current work contributes further progress to this area in the particular direction: tensor product methods for separation of variables. The separation of variables has a long history, and is based on the following elementary concept: a function of many variables may be expanded as a product of univariate functions. On the discrete level, a function is encoded by an array of its values, or a tensor. Therefore, instead of a huge initial array, the separation of variables allows to work with univariate factors with much less efforts. The dissertation contains a short overview of existing tensor representations: canonical PARAFAC, Hierarchical Tucker, Tensor Train (TT) formats, as well as the artificial tensorisation, resulting in the Quantized Tensor Train (QTT) approximation method. The contribution of the dissertation consists in both theoretical constructions and practical numerical algorithms for high-dimensional models, illustrated on the examples of the Fokker-Planck and the chemical master equations. Both arise from stochastic dynamical processes in multiconfigurational systems, and govern the evolution of the probability function in time. A special focus is put on time propagation schemes and their properties related to tensor product methods. We show that these applications yield large-scale systems of linear equations, and prove analytical separable representations of the involved functions and operators. We propose a new combined tensor format (QTT-Tucker), which descends from the TT format (hence TT algorithms may be generalized smoothly), but provides complexity reduction by an order of magnitude. We develop a robust iterative solution algorithm, constituting most advantageous properties of the classical iterative methods from numerical analysis and alternating density matrix renormalization group (DMRG) techniques from quantum physics. Numerical experiments confirm that the new method is preferable to DMRG algorithms. It is as fast as the simplest alternating schemes, but as reliable and accurate as the Krylov methods in linear algebra.
Abstract The tensor renormalization group (TRG) is a highly effective method for calculating the free energy of lattice models and has demonstrated exceptional accuracy for several low-dimensional systems. However, its application to higher-dimensional models is often hampered by a large memory footprint and high computational cost. In this paper, we propose a new algorithm, “tt-lattice”, which approximates the tensor at each lattice vertex using a tensor train (tt) decomposition. The algorithm is designed to maintain the tt-format throughout the TRG computation, which significantly reduces both memory usage and computational cost. For a uniform lattice model, the computational cost of tt-lattice scales as O(d2log(L)χ6), with the largest intermediate tensor size of O(χ4), where d is the lattice dimension, L is the linear size of each lattice axis, and χ is the cutoff of the number of lattice edge states. To validate our algorithm, we conducted numerical experiments on a Gaussian field model, for which the exact free energy is computable in any lattice dimensions. The results demonstrate that the tt-lattice method can calculate the free energy with reasonable accuracy even for a 10D lattice model with modern computational architectures.
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.