Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2506.11341 · Quantum

The Integral Decimation Method for Quantum Dynamics and Statistical Mechanics

Ryan T. Grimm, Alexander J. Staat, Joel David Eaves

Published Apr 13, 2026• 1 citation
arXivHTMLPDF

Abstract

The solutions to many problems in the mathematical, computational, and physical sciences often involve multidimensional integrals. A direct numerical evaluation of the integral incurs a computational cost that is exponential in the number of dimensions, a phenomenon called the curse of dimensionality. The problem is so substantial that one usually employs sampling methods, like Monte Carlo, to avoid integration altogether. Here, we derive and implement a quantum-inspired algorithm to decompose a multidimensional integrand into a product of matrix-valued functions – a spectral tensor train – changing the computational complexity of integration from exponential to polynomial. The algorithm constructs a spectral tensor train representation of the integrand by applying a sequence of quantum gates, where each gate corresponds to an interaction that involves increasingly more degrees of freedom in the action. Because it allows for the systematic elimination of small contributions to the integral through decimation, we call the method integral decimation. The functions in the spectral basis are analytically differentiable and integrable, and in applications to the partition function, integral decimation numerically factorizes an interacting system into a product of non-interacting ones. We illustrate integral decimation by evaluating the absolute free energy and entropy of a chiral XY model as a continuous function of temperature. We also compute the nonequilibrium time-dependent reduced density matrix of a quantum chain with between two and forty levels, each coupled to colored noise. When other methods provide numerical solutions to these models, they quantitatively agree with integral decimation. When conventional methods become intractable, integral decimation can be a powerful alternative.

DOI
10.22331/q-2026-04-13-2064

Related papers

Tensor product methods in numerical simulation of high-dimensional dynamical problems

Sergey Dolgov

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 $10^{10}$ 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.

•Sep 8, 2014•12 citations

Algorithms for discrete and continuous quantum systems

Soumyodipto Mukherjee

This thesis is divided into three chapters. In the first chapter we outline a simple and numerically inexpensive approach to describe the spectral features of the single-impurity Anderson model. The method combines aspects of the density matrix embedding theory (DMET) approach with a spectral broadening approach inspired by those used in numerical renormalization group (NRG) methods. At zero temperature for a wide range of U , the spectral function produced by this approach is found to be in good agreement with general expectations as well as more advanced and complex numerical methods such as DMRG-based schemes. The theory developed here is simply transferable to more complex impurity problems The second chapter outlines the density matrix embedding methodology in the context of electronic structure applications. We formulate analytical gradients for energies obtained from DMET focusing on two scenarios: RHF-in-RHF embedding and FCI-in-RHF embedding. The former involves solving the small embedded system at Restricted Hartree-Fock (RHF) level of theory. This serves to check the validity of the formulas by reproducing the RHF results on the full system for energies and gradients. The latter scenario employs full configuration interaction (FCI) as a high level solver for the small embedded system. Our results show that only Hellmann-Feynman terms, which involve derivatives of one- and two-electron terms in the atomic orbital basis, are required to calculate energy gradients in both cases. We applied our methodology to the problem of H 10 ring dissociation where the analytical gradients matched those obtained numerically. The gradient formulation is applicable to geometry optimization of strongly correlated molecules and solids. It can also be used in ab initio molecular dynamics where forces on nuclei are obtained from DMET energy gradients. In the final chapter we focus on the study of finite-temperature equilibrium properties of quantum systems in continuous space. We formulate an expansion of the partition function in continuous-time and use Monte Carlo to sample terms in the resulting infinite series. Such a strategy has been highly successful in quantum lattice models but has found scant application in off-lattice systems. The Monte Carlo estimate of the average energy of quantum particles in continuous space subject to simple model potentials is found to converge with low statistical error to the exact solutions even when very high perturbation order is required. We outline two ways in which the algorithm can be applied to more complex problems. First, by drawing an analogy between the formulation in continuous-time with the discretized, Trotter factorized version of standard path integral Monte Carlo (PIMC). This allows one to use the suite of standard PIMC moves to carry out the position sampling required to obtain the weight of each time configuration. Finally, we propose an alternate route by fitting the many-particle potential with multidimensional Gaussians which provides an analytical form for the position integrals.

•Jan 1, 2018•0 citations

EXTENSIONS FOR THE RIGID-BODY QUANTUM MONTE CARLO METHOD

Chris Smith

Solving the Schrodinger equation and finding excited states for quantum mechanical many-body systems is a fundamental problem. If this problem is formulated in terms of integrals, the dimensionality of the configuration space is often too high to perform the integrations required directly. This is because the volume of configuration space increases exponentially with dimension quickly, making its complete exploration impossible. Monte Carlo methods provide a way to estimate these integrals by statistically sampling a subset of configuration space, and these methods provide 1/√ N convergence regardless of dimension. For many problems involving the quantum mechanics of molecules there exists a large time scale separation between the high-frequency internal vibrations, and low-frequency intermolecular motions. This separation motivates the rigid-body approximation which freezes internal degrees of freedom in order to study intermolecular effects. The reduction in the dimensionality of configuration space further increases the range of accessible problems. This thesis is devoted to the construction and implementation of algorithms which incorporate the rigid-body approximation into existing Monte Carlo methods for solving the quantum mechanical many-body problem. Monte Carlo estimators are constructed as averages over samples drawn from some probability distribution. If this distribution is known in closed form the samples can be generated by application of the Metropolis algorithm. In most cases the distribution is not known in closed form or even representable with a finite number of variables. If this distribution is the dominant eigenstate of some known operator then a stochastic implementation of the power method can be used to generate the required samples. For the quantum mechanical problem this operator can be taken to be the imaginary-time evolution operator and its application can be represented in terms of random walks. For rigid bodies, this method involves the implementation of rotational Brownian motion. The use of quaternion algebra to implement this rotational motion enhances simplicity, performance, and numerical stability. The method described above can be generalized to investigate excited state properties using correlation function Monte Carlo which is a Monte Carlo implementation of the Rayleigh-Ritz variational method. This generalization requires the construction of a trial subspace which is then subjected to the variational method resulting in a generalized eigenvalue problem. It is important to represent optimized trial states accurately and efficiently. For this purpose, we write trial states as functions of invariant polynomials of the interparticle distances. By reducing the number of free interparticle distances, the rigid-body approximation greatly simplifies

•Jan 1, 2010•0 citations

Tensor Numerical Methods in Quantum Chemistry

Venera Khoromskaia, Boris N. Khoromskij

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.

De Gruyter eBooks•Jun 8, 2018•50 citations

Quantum-inspired algorithms for multivariate analysis: from interpolation to partial differential equations

Juan José García‐Ripoll

In this work we study the encoding of smooth, differentiable multivariate functions in quantum registers, using quantum computers or tensor-network representations. We show that a large family of distributions can be encoded as low-entanglement states of the quantum register. These states can be efficiently created in a quantum computer, but they are also efficiently stored, manipulated and probed using Matrix-Product States techniques. Inspired by this idea, we present eight quantum-inspired numerical analysis algorithms, that include Fourier sampling, interpolation, differentiation and integration of partial derivative equations. These algorithms combine classical ideas – finite-differences, spectral methods – with the efficient encoding of quantum registers, and well known algorithms, such as the Quantum Fourier Transform. When these heuristic methods work , they provide an exponential speed-up over other classical algorithms, such as Monte Carlo integration, finite-difference and fast Fourier transforms (FFT). But even when they don't, some of these algorithms can be translated back to a quantum computer to implement a similar task.

arXiv:1909.06619•Quantum•Apr 15, 2021•82 citations

Unlocking multidimensional integration with quantum adaptive importance sampling

Konstantinos Pyretzidis, Jorge J. Martínez de Lejarza, Germán Rodrigo A

Multidimensional numerical integration is a central ingredient of theoretical predictions in high-energy physics, where multiloop Feynman diagrams and phase-space integrals are computationally demanding due to divergences and complex mathematical structures. Established Adaptive Importance Sampling methods for numerical integration, such as VEGAS, iteratively refine a grid in a separable way, dimension by dimension. This keeps the algorithm scalable but reduces performance when strong inter-variable correlations are present. In this work, we introduce a hybrid quantum-classical algorithm that performs Quantum Adaptive Importance Sampling (QAIS) for multidimensional Monte Carlo integration. Our approach uses a Parametrized Quantum Circuit to encode a non-separable Probability Density Function on a multidimensional grid and allocate samples efficiently in the integration domain. We apply the method to a sharply peaked loop Feynman integral and to multi-modal benchmark integrals. Our results show that QAIS provides an efficient route for high-precision evaluation of multidimensional integrals. Theoretical calculations in particle physics rely on multidimensional integrals that become difficult to evaluate in the presence of correlations. Here, the authors show that a hybrid quantum-classical algorithm implementing Quantum Adaptive Importance Sampling can learn correlated structures efficiently and deliver precise results for nontrivial integrals.

arXiv:2506.19965•Communications Physics•May 22, 2026•6 citations
The solutions to many problems in the mathematical, computational, and physical sciences often involve multidimensional integrals. A direct numerical evaluation of the integral incurs a computational cost that is exponential in the number of dimensions, a phenomenon called the curse of dimensionality. The problem is so substantial that one usually employs sampling methods, like Monte Carlo, to avoid integration altogether. Here, we derive and implement a quantum-inspired algorithm to decompose a multidimensional integrand into a product of matrix-valued functions – a spectral tensor train – changing the computational complexity of integration from exponential to polynomial. The algorithm constructs a spectral tensor train representation of the integrand by applying a sequence of quantum gates, where each gate corresponds to an interaction that involves increasingly more degrees of freedom in the action. Because it allows for the systematic elimination of small contributions to the integral through decimation, we call the method integral decimation. The functions in the spectral basis are analytically differentiable and integrable, and in applications to the partition function, integral decimation numerically factorizes an interacting system into a product of non-interacting ones. We illustrate integral decimation by evaluating the absolute free energy and entropy of a chiral XY model as a continuous function of temperature. We also compute the nonequilibrium time-dependent reduced density matrix of a quantum chain with between two and forty levels, each coupled to colored noise. When other methods provide numerical solutions to these models, they quantitatively agree with integral decimation. When conventional methods become intractable, integral decimation can be a powerful alternative.
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 101010^{10}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.
This thesis is divided into three chapters. In the first chapter we outline a simple and numerically inexpensive approach to describe the spectral features of the single-impurity Anderson model. The method combines aspects of the density matrix embedding theory (DMET) approach with a spectral broadening approach inspired by those used in numerical renormalization group (NRG) methods. At zero temperature for a wide range of U , the spectral function produced by this approach is found to be in good agreement with general expectations as well as more advanced and complex numerical methods such as DMRG-based schemes. The theory developed here is simply transferable to more complex impurity problems The second chapter outlines the density matrix embedding methodology in the context of electronic structure applications. We formulate analytical gradients for energies obtained from DMET focusing on two scenarios: RHF-in-RHF embedding and FCI-in-RHF embedding. The former involves solving the small embedded system at Restricted Hartree-Fock (RHF) level of theory. This serves to check the validity of the formulas by reproducing the RHF results on the full system for energies and gradients. The latter scenario employs full configuration interaction (FCI) as a high level solver for the small embedded system. Our results show that only Hellmann-Feynman terms, which involve derivatives of one- and two-electron terms in the atomic orbital basis, are required to calculate energy gradients in both cases. We applied our methodology to the problem of H 10 ring dissociation where the analytical gradients matched those obtained numerically. The gradient formulation is applicable to geometry optimization of strongly correlated molecules and solids. It can also be used in ab initio molecular dynamics where forces on nuclei are obtained from DMET energy gradients. In the final chapter we focus on the study of finite-temperature equilibrium properties of quantum systems in continuous space. We formulate an expansion of the partition function in continuous-time and use Monte Carlo to sample terms in the resulting infinite series. Such a strategy has been highly successful in quantum lattice models but has found scant application in off-lattice systems. The Monte Carlo estimate of the average energy of quantum particles in continuous space subject to simple model potentials is found to converge with low statistical error to the exact solutions even when very high perturbation order is required. We outline two ways in which the algorithm can be applied to more complex problems. First, by drawing an analogy between the formulation in continuous-time with the discretized, Trotter factorized version of standard path integral Monte Carlo (PIMC). This allows one to use the suite of standard PIMC moves to carry out the position sampling required to obtain the weight of each time configuration. Finally, we propose an alternate route by fitting the many-particle potential with multidimensional Gaussians which provides an analytical form for the position integrals.
Solving the Schrodinger equation and finding excited states for quantum mechanical many-body systems is a fundamental problem. If this problem is formulated in terms of integrals, the dimensionality of the configuration space is often too high to perform the integrations required directly. This is because the volume of configuration space increases exponentially with dimension quickly, making its complete exploration impossible. Monte Carlo methods provide a way to estimate these integrals by statistically sampling a subset of configuration space, and these methods provide 1/√ N convergence regardless of dimension. For many problems involving the quantum mechanics of molecules there exists a large time scale separation between the high-frequency internal vibrations, and low-frequency intermolecular motions. This separation motivates the rigid-body approximation which freezes internal degrees of freedom in order to study intermolecular effects. The reduction in the dimensionality of configuration space further increases the range of accessible problems. This thesis is devoted to the construction and implementation of algorithms which incorporate the rigid-body approximation into existing Monte Carlo methods for solving the quantum mechanical many-body problem. Monte Carlo estimators are constructed as averages over samples drawn from some probability distribution. If this distribution is known in closed form the samples can be generated by application of the Metropolis algorithm. In most cases the distribution is not known in closed form or even representable with a finite number of variables. If this distribution is the dominant eigenstate of some known operator then a stochastic implementation of the power method can be used to generate the required samples. For the quantum mechanical problem this operator can be taken to be the imaginary-time evolution operator and its application can be represented in terms of random walks. For rigid bodies, this method involves the implementation of rotational Brownian motion. The use of quaternion algebra to implement this rotational motion enhances simplicity, performance, and numerical stability. The method described above can be generalized to investigate excited state properties using correlation function Monte Carlo which is a Monte Carlo implementation of the Rayleigh-Ritz variational method. This generalization requires the construction of a trial subspace which is then subjected to the variational method resulting in a generalized eigenvalue problem. It is important to represent optimized trial states accurately and efficiently. For this purpose, we write trial states as functions of invariant polynomials of the interparticle distances. By reducing the number of free interparticle distances, the rigid-body approximation greatly simplifies
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.
In this work we study the encoding of smooth, differentiable multivariate functions in quantum registers, using quantum computers or tensor-network representations. We show that a large family of distributions can be encoded as low-entanglement states of the quantum register. These states can be efficiently created in a quantum computer, but they are also efficiently stored, manipulated and probed using Matrix-Product States techniques. Inspired by this idea, we present eight quantum-inspired numerical analysis algorithms, that include Fourier sampling, interpolation, differentiation and integration of partial derivative equations. These algorithms combine classical ideas – finite-differences, spectral methods – with the efficient encoding of quantum registers, and well known algorithms, such as the Quantum Fourier Transform. When these heuristic methods work , they provide an exponential speed-up over other classical algorithms, such as Monte Carlo integration, finite-difference and fast Fourier transforms (FFT). But even when they don't, some of these algorithms can be translated back to a quantum computer to implement a similar task.
Multidimensional numerical integration is a central ingredient of theoretical predictions in high-energy physics, where multiloop Feynman diagrams and phase-space integrals are computationally demanding due to divergences and complex mathematical structures. Established Adaptive Importance Sampling methods for numerical integration, such as VEGAS, iteratively refine a grid in a separable way, dimension by dimension. This keeps the algorithm scalable but reduces performance when strong inter-variable correlations are present. In this work, we introduce a hybrid quantum-classical algorithm that performs Quantum Adaptive Importance Sampling (QAIS) for multidimensional Monte Carlo integration. Our approach uses a Parametrized Quantum Circuit to encode a non-separable Probability Density Function on a multidimensional grid and allocate samples efficiently in the integration domain. We apply the method to a sharply peaked loop Feynman integral and to multi-modal benchmark integrals. Our results show that QAIS provides an efficient route for high-precision evaluation of multidimensional integrals. Theoretical calculations in particle physics rely on multidimensional integrals that become difficult to evaluate in the presence of correlations. Here, the authors show that a hybrid quantum-classical algorithm implementing Quantum Adaptive Importance Sampling can learn correlated structures efficiently and deliver precise results for nontrivial integrals.