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:0906.0501 · Physical Review B

Diffusion Monte Carlo: Exponential scaling of computational cost for large systems

Norbert Nemec

Published Jan 26, 2010• 35 citations
arXivHTMLPDF

Abstract

The computational cost of a Monte Carlo algorithm can only be meaningfully discussed when taking into account the magnitude of the resulting statistical error. Aiming for a fixed error per particle, we study the scaling behavior of the diffusion Monte Carlo method for large quantum systems. We identify the correlation within the population of walkers as the dominant scaling factor for large systems. While this factor is negligible for small and medium sized systems that are typically studied, it ultimately shows exponential scaling. The scaling factor can be estimated straightforwardly for each specific system and we find that is typically only becomes relevant for systems containing more than several hundred atoms.

DOI
10.1103/physrevb.81.035119

Related papers

Population size bias in diffusion Monte Carlo

Massimo Boninsegni, Saverio Moroni

The size of the population of random walkers required to obtain converged estimates in diffusion Monte Carlo (DMC) increases dramatically with system size. We illustrate this by comparing ground state energies of small clusters of parahydrogen (up to 48 molecules) computed by DMC and path integral ground state (PIGS) techniques. We contend that the bias associated with a finite population of walkers is the most likely cause of quantitative numerical discrepancies between PIGS and DMC energy estimates reported in the literature, for this few-body Bose system. We discuss the viability of DMC as a general-purpose ground state technique, and argue that PIGS, and even finite temperature methods, enjoy more favorable scaling, and are therefore a superior option for systems of large size.

arXiv:1209.1663•Physical Review E•Nov 28, 2012•55 citations

Calculation of Intermolecular Interactions via Diffusion Monte Carlo

Kevin E. Gasperich

Quantum chemistry is a useful tool that provides insight into the properties and behavior of chemical systems. Modern software packages have made quantum chemistry methods more easily accessible, and the continued increase in available computational resources has allowed them to be applied to larger systems at higher levels of theory. Two significant problems that the field faces are the high computational complexity of high-level methods and the shift toward parallelism in high performance computing architectures. This work examines the treatment of weakly interacting molecular systems with the fixed-node diffusion Monte Carlo (DMC) method. DMC and other quantum Monte Carlo (QMC) methods offer a possible solution to both of the aforementioned problems: they can produce near-exact results with a lower scaling (with respect to problem size) than other similarly-accurate methods, and they are inherently parallel, so there is little additional cost associated with distributing the work of a single QMC calculation across a large number of processing units. The only error in DMC that is not systematically improvable is the constraint of a fixed nodal surface of the many-particle wave function of the system being studied. There are many cases in which a single Slater determinant trial function is sufficient to obtain accurate results, but there are others in which more sophisticated multi-determinant trial functions are necessary. Furthermore, it is non-trivial to generate nodal surfaces of similar quality for isolated and interacting molecules, so cancellation of errors is not guaranteed. We examine the use of different single- and multi-determinant trial functions in DMC calculations on small chemical systems with the goal of further understanding how to construct appropriate trial functions for molecules and clusters.

•Jan 16, 2020•0 citations

Diffusion Monte Carlo computational cost scales exponentially for large systems

Norbert Nemec

•Jun 2, 2009•0 citations

The quantum Monte Carlo method—electron correlation from random numbers (abstract only)

Richard J. Needs

The fixed-node diffusion quantum Monte Carlo (DMC) method is the most accurate method known for calculating the energies of large many-particle quantum systems. The key element of the method is the development of accurate trial many-body wavefunctions which control the statistical efficiency of the calculations and the accuracy obtained. Accurate wavefunctions can be obtained by building correlation effects on top of mean field descriptions such as density functional theory. The wavefunctions can be improved by introducing multi-determinants, pairing functions, and backflow transformations. The calculations are expensive, but the method scales well with system size and calculations on 1000 particles are possible. Some recent applications of the DMC method to atoms, molecules and solids will be presented.

Journal of Physics Condensed Matter•Jan 24, 2008•1 citation

Towards Correlated Sampling for the Fixed-Node Diffusion Quantum Monte Carlo Method

Raphael Berner, René Petz, Arne Lüchow

Most methods of quantum chemistry calculate total energies rather than directly the energy differences that are of interest to chemists. In the case of statistical methods like quantum Monte Carlo the statistical errors in the absolute values need to be considerably smaller than their difference. The calculation of small energy differences is therefore particularly time consuming. Correlated sampling techniques provide the possibility to compute directly energy differences by simulating the underlying systems with the same stochastic process. The smaller the energy difference the smaller its statistical error. Correlated sampling is well established in variational quantum Monte Carlo, but it is much more difficult to implement in diffusion quantum Monte Carlo because of the fixed node approximation. A correlated sampling formalism and a corresponding algorithm based on a transformed Schrödinger equation having the form of a Kolmogorov’s backward equation is derived. The numerical verification of the presented algorithm is given for the harmonic oscillator. The extension of the algorithm to electron structure calculations is discussed.

Zeitschrift für Naturforschung A•Jun 2, 2014•0 citations

Response to "Exponential challenges in unbiasing quantum Monte Carlo algorithms with quantum computers"

Joonho Lee, David R. Reichman, Ryan Babbush +4 more

A recent preprint by Mazzola and Carleo numerically investigates exponential challenges that can arise for the QC-QMC algorithm introduced in our work, "Unbiasing fermionic quantum Monte Carlo with a quantum computer." As discussed in our original paper, we agree with this general concern. However, here we provide further details and numerics to emphasize that the prospects for practical quantum advantage in QC-QMC remain open. The exponential challenges in QC-QMC are dependent on (1) the choice of QMC methods, (2) the underlying system, and (3) the form of trial and walker wavefunctions. While one can find difficult examples with a specific method, a specific system, and a specific walker/trial form, for some combinations of these choices, the approach is potentially more scalable than other near-term quantum algorithms. Future research should aim to identify examples for which QC-QMC enables practical quantum advantage.

arXiv:2207.13776•Jul 27, 2022•14 citations
The computational cost of a Monte Carlo algorithm can only be meaningfully discussed when taking into account the magnitude of the resulting statistical error. Aiming for a fixed error per particle, we study the scaling behavior of the diffusion Monte Carlo method for large quantum systems. We identify the correlation within the population of walkers as the dominant scaling factor for large systems. While this factor is negligible for small and medium sized systems that are typically studied, it ultimately shows exponential scaling. The scaling factor can be estimated straightforwardly for each specific system and we find that is typically only becomes relevant for systems containing more than several hundred atoms.
The size of the population of random walkers required to obtain converged estimates in diffusion Monte Carlo (DMC) increases dramatically with system size. We illustrate this by comparing ground state energies of small clusters of parahydrogen (up to 48 molecules) computed by DMC and path integral ground state (PIGS) techniques. We contend that the bias associated with a finite population of walkers is the most likely cause of quantitative numerical discrepancies between PIGS and DMC energy estimates reported in the literature, for this few-body Bose system. We discuss the viability of DMC as a general-purpose ground state technique, and argue that PIGS, and even finite temperature methods, enjoy more favorable scaling, and are therefore a superior option for systems of large size.
Quantum chemistry is a useful tool that provides insight into the properties and behavior of chemical systems. Modern software packages have made quantum chemistry methods more easily accessible, and the continued increase in available computational resources has allowed them to be applied to larger systems at higher levels of theory. Two significant problems that the field faces are the high computational complexity of high-level methods and the shift toward parallelism in high performance computing architectures. This work examines the treatment of weakly interacting molecular systems with the fixed-node diffusion Monte Carlo (DMC) method. DMC and other quantum Monte Carlo (QMC) methods offer a possible solution to both of the aforementioned problems: they can produce near-exact results with a lower scaling (with respect to problem size) than other similarly-accurate methods, and they are inherently parallel, so there is little additional cost associated with distributing the work of a single QMC calculation across a large number of processing units. The only error in DMC that is not systematically improvable is the constraint of a fixed nodal surface of the many-particle wave function of the system being studied. There are many cases in which a single Slater determinant trial function is sufficient to obtain accurate results, but there are others in which more sophisticated multi-determinant trial functions are necessary. Furthermore, it is non-trivial to generate nodal surfaces of similar quality for isolated and interacting molecules, so cancellation of errors is not guaranteed. We examine the use of different single- and multi-determinant trial functions in DMC calculations on small chemical systems with the goal of further understanding how to construct appropriate trial functions for molecules and clusters.
The fixed-node diffusion quantum Monte Carlo (DMC) method is the most accurate method known for calculating the energies of large many-particle quantum systems. The key element of the method is the development of accurate trial many-body wavefunctions which control the statistical efficiency of the calculations and the accuracy obtained. Accurate wavefunctions can be obtained by building correlation effects on top of mean field descriptions such as density functional theory. The wavefunctions can be improved by introducing multi-determinants, pairing functions, and backflow transformations. The calculations are expensive, but the method scales well with system size and calculations on 1000 particles are possible. Some recent applications of the DMC method to atoms, molecules and solids will be presented.
Most methods of quantum chemistry calculate total energies rather than directly the energy differences that are of interest to chemists. In the case of statistical methods like quantum Monte Carlo the statistical errors in the absolute values need to be considerably smaller than their difference. The calculation of small energy differences is therefore particularly time consuming. Correlated sampling techniques provide the possibility to compute directly energy differences by simulating the underlying systems with the same stochastic process. The smaller the energy difference the smaller its statistical error. Correlated sampling is well established in variational quantum Monte Carlo, but it is much more difficult to implement in diffusion quantum Monte Carlo because of the fixed node approximation. A correlated sampling formalism and a corresponding algorithm based on a transformed Schrödinger equation having the form of a Kolmogorov’s backward equation is derived. The numerical verification of the presented algorithm is given for the harmonic oscillator. The extension of the algorithm to electron structure calculations is discussed.
A recent preprint by Mazzola and Carleo numerically investigates exponential challenges that can arise for the QC-QMC algorithm introduced in our work, "Unbiasing fermionic quantum Monte Carlo with a quantum computer." As discussed in our original paper, we agree with this general concern. However, here we provide further details and numerics to emphasize that the prospects for practical quantum advantage in QC-QMC remain open. The exponential challenges in QC-QMC are dependent on (1) the choice of QMC methods, (2) the underlying system, and (3) the form of trial and walker wavefunctions. While one can find difficult examples with a specific method, a specific system, and a specific walker/trial form, for some combinations of these choices, the approach is potentially more scalable than other near-term quantum algorithms. Future research should aim to identify examples for which QC-QMC enables practical quantum advantage.