We present the new Singular-Value Decomposition Multigrid POTFIT (SVD-MGPF), a grid-based tensor decomposition algorithm for large dimensional systems with particular focus on Quantum Dynamical problems. SVD-MGPF constitutes a generalisation of our previous (eigenvalue- decomposition based) EVD-MGPF method [1]. Both MGPF methods provide the Tucker decomposition of a target tensor (e.g. a potential energy surface). For such, a fine grid, the one needed to accurately represent the system, and a coarse one, a subset of the former, are defined. Tucker factor matrices are obtained from a series of POTFIT [2] decompositions carried out on grids which are fine for some degrees of freedom and coarse for the rest. The core tensor is obtained by overlapping these factor matrices with the values of the original tensor on the coarse grid. The difference between SVD-MGPF and EVD-MGPF (or POTFIT) lies in the fact that the Tucker factor matrices are obtained through singular value decompositions of one-particle potential density matrices instead of eigenvalue ones. This is shown to remove the numerical instabilities present in MGPF. Additionally, a black-box method for the choice of the coarse grid choice is proposed. The novelty of the latter is that it leads to a fully-relaxed non-product coarse grid. [1] D. Pel\'aez, H.-D. Meyer, J. Chem. Phys. {\bf 138} 014108, (2013). [2] A. Jaeckle, H.-D. Meyer, J. Chem. Phys. {\bf 104} 7974 (1996).
We present the new Singular-Value Decomposition Multigrid POTFIT (SVD-MGPF), a grid-based tensor decomposition algorithm for large dimensional systems with particular focus on Quantum Dynamical problems. SVD-MGPF constitutes a generalisation of our previous (eigenvalue- decomposition based) EVD-MGPF method [1]. Both MGPF methods provide the Tucker decomposition of a target tensor (e.g. a potential energy surface). For such, a fine grid, the one needed to accurately represent the system, and a coarse one, a subset of the former, are defined. Tucker factor matrices are obtained from a series of POTFIT [2] decompositions carried out on grids which are fine for some degrees of freedom and coarse for the rest. The core tensor is obtained by overlapping these factor matrices with the values of the original tensor on the coarse grid. The difference between SVD-MGPF and EVD-MGPF (or POTFIT) lies in the fact that the Tucker factor matrices are obtained through singular value decompositions of one-particle potential density matrices instead of eigenvalue ones. This is shown to remove the numerical instabilities present in MGPF. Additionally, a black-box method for the choice of the coarse grid choice is proposed. The novelty of the latter is that it leads to a fully-relaxed non-product coarse grid. [1] D. Pel'aez, H.-D. Meyer, J. Chem. Phys. {\bf 138} 014108, (2013). [2] A. Jaeckle, H.-D. Meyer, J. Chem. Phys. {\bf 104} 7974 (1996).
The multi-layer multi-configuration time-dependent Hartree method (ML-MCTDH) is a highly efficient scheme for studying the dynamics of high-dimensional quantum systems. Its use is greatly facilitated if the Hamiltonian of the system possesses a particular structure through which the multi-dimensional matrix elements can be computed efficiently. In the field of quantum molecular dynamics, the effective interaction between the atoms is often described by potential energy surfaces (PES), and it is necessary to fit such PES into the desired structure. For high-dimensional systems, the current approaches for this fitting process either lead to fits that are too large to be practical, or their accuracy is difficult to predict and control. This article introduces multi-layer Potfit (MLPF), a novel fitting scheme that results in a PES representation in the hierarchical tensor (HT) format. The scheme is based on the hierarchical singular value decomposition, which can yield a near-optimal fit and give strict bounds for the obtained accuracy. Here, a recursive scheme for using the HT-format PES within ML-MCTDH is derived, and theoretical estimates as well as a computational example show that the use of MLPF can reduce the numerical effort for ML-MCTDH by orders of magnitude, compared to the traditionally used Potfit representation of the PES. Moreover, it is shown that MLPF is especially beneficial for high-accuracy PES representations, and it turns out that MLPF leads to computational savings already for comparatively small systems with just four modes.
The multi-layer multi-configuration time-dependent Hartree method (ML-MCTDH) is a highly efficient scheme for studying the dynamics of high-dimensional quantum systems. Its use is greatly facilitated if the Hamiltonian of the system possesses a particular structure through which the multi-dimensional matrix elements can be computed efficiently. In the field of quantum molecular dynamics, the effective interaction between the atoms is often described by potential energy surfaces (PES), and it is necessary to fit such PES into the desired structure. For high-dimensional systems, the current approaches for this fitting process either lead to fits that are too large to be practical, or their accuracy is difficult to predict and control. This article introduces multi-layer Potfit (MLPF), a novel fitting scheme that results in a PES representation in the hierarchical tensor (HT) format. The scheme is based on the hierarchical singular value decomposition, which can yield a near-optimal fit and give strict bounds for the obtained accuracy. Here, a recursive scheme for using the HT-format PES within ML-MCTDH is derived, and theoretical estimates as well as a computational example show that the use of MLPF can reduce the numerical effort for ML-MCTDH by orders of magnitude, compared to the traditionally used POTFIT representation of the PES. Moreover, it is shown that MLPF is especially beneficial for high-accuracy PES representations, and it turns out that MLPF leads to computational savings already for comparatively small systems with just four modes.
Abstract Tensors are increasingly ubiquitous in various areas of applied mathematics and computing, and tensor decompositions are of practical significance and benefit many applications in data completion, image processing, computer vision, collaborative filtering, etc. Recently, Kilmer and Martin propose a new tensor factorization strategy, tensor singular value decomposition (t-svd), which extends the matrix singular value decomposition to tensors. However, computing t-svd for high dimensional tensors costs much computation and thus cannot efficiently handle large scale datasets. Motivated by advantage of quantum computation, in this paper, we present a quantum algorithm of t-svd for third-order tensors and then extend it to order-p tensors. We prove that our quantum t-svd algorithm for a third-order N dimensional tensor runs in time N polylog ( N ) if we do not recover classical information from the quantum output state. Moreover, we apply our quantum t-svd algorithm to context-aware multidimensional recommendation systems, where we just need to extract partial classical information from the quantum output state, thus achieving low time complexity.
The conventional numerical methods when applied to multidimensional problems suffer from the so-called "curse of dimensionality", that cannot be eliminated by using parallel architectures and high performance computing. The novel tensor numerical methods are based on a "smart" rank-structured tensor representation of the multivariate functions and operators discretized on Cartesian grids thus reducing solution of the multidimensional integral-differential equations to 1D calculations. We explain basic tensor formats and algorithms and show how the orthogonal Tucker tensor decomposition originating from chemometrics made a revolution in numerical analysis, relying on rigorous results from approximation theory. Benefits of tensor approach are demonstrated in ab-initio electronic structure calculations. Computation of the 3D convolution integrals for functions with multiple singularities is replaced by a sequence of 1D operations, thus enabling accurate MATLAB calculations on a laptop using 3D uniform tensor grids of the size up to 10 15 . Fast tensor-based Hartree-Fock solver, incorporating the grid-based low-rank factorization of the two-electron integrals, serves as a prerequisite for economical calculation of the excitation energies of molecules. Tensor approach suggests efficient grid-based numerical treatment of the long-range electrostatic potentials on large 3D finite lattices with defects.The novel range-separated tensor format applies to interaction potentials of multi-particle systems of general type opening the new prospects for tensor methods in scientific computing. This research monograph presenting the modern tensor techniques applied to problems in quantum chemistry may be interesting for a wide audience of students and scientists working in computational chemistry, material science and scientific computing.
Abstract Researchers have put a lot of effort into reducing the gap between current quantum processing units (QPU) capabilities and their potential supremacy.One approach is to keep supplementary computations in the CPU, and use QPU only for the core of the problem. In this work, we address the complexity of quantum algorithm of arbitrary quantum state initialization, an important building block of quantum data analysis and machine learning.QPUs do not outperform classical machines with existing precise initialization algorithms.Hence, many studies propose an approximate but robust quantum state initialization.Cutting a quantum state into a product of (almost) independent partitions with the help of CPU reduces the number of two-qubit gates, and correspondingly minimizes the loss of state fidelity in the quantum part of the algorithm.To find the least entangled qubits, current methods compute the singular value decomposition (SVD) for each qubit separately with CPU.In this paper, we optimize CPU usage and memory resource bottlenecks.We consider Tucker tensor decomposition as an alternative to the CPU-based SVD in a single low-entangled qubit detection task without the loss of solution quality.Both proposed methods outperform the SVD in time and memory for systems of at least ten qubits. We achieve an order faster implementation and two orders less memory usage for a system of 15 qubits.
Machine learning and data mining algorithms are becoming increasingly important in analyzing large volume, multi-relational and multi--modal datasets, which are often conveniently represented as multiway arrays or tensors. It is therefore timely and valuable for the multidisciplinary research community to review tensor decompositions and tensor networks as emerging tools for large-scale data analysis and data mining. We provide the mathematical and graphical representations and interpretation of tensor networks, with the main focus on the Tucker and Tensor Train (TT) decompositions and their extensions or generalizations. Keywords: Tensor networks, Function-related tensors, CP decomposition, Tucker models, tensor train (TT) decompositions, matrix product states (MPS), matrix product operators (MPO), basic tensor operations, multiway component analysis, multilinear blind source separation, tensor completion, linear/multilinear dimensionality reduction, large-scale optimization problems, symmetric eigenvalue decomposition (EVD), PCA/SVD, huge systems of linear equations, pseudo-inverse of very large matrices, Lasso and Canonical Correlation Analysis (CCA) (This is Part 1)