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

Journal of Computational Chemistry

Efficient algorithm for “on‐the‐fly” error analysis of local or distributed serially correlated data

David R. Kent, Richard P. Muller, Amos G. Anderson, William A. Goddard, Michael T. Feldmann

Published May 2, 2007• 22 citations
Publisher

Abstract

We describe the Dynamic Distributable Decorrelation Algorithm (DDDA) which efficiently calculates the true statistical error of an expectation value obtained from serially correlated data "on-the-fly," as the calculation progresses. DDDA is an improvement on the Flyvbjerg-Petersen renormalization group blocking method (Flyvberg and Peterson, J Chem Phys 1989, 91, 461). This "on-the-fly" determination of statistical quantities allows dynamic termination of Monte Carlo calculations once a specified level of convergence is attained. This is highly desirable when the required precision might take days or months to compute, but cannot be accurately estimated prior to the calculation. Furthermore, DDDA allows for a parallel implementation which requires very low communication, O(log(2)N), and can also evaluate the variance of a calculation efficiently "on-the-fly." Quantum Monte Carlo calculations are presented to illustrate "on-the-fly" variance calculations for serial and massively parallel Monte Carlo calculations.

DOI
10.1002/jcc.20746

Related papers

Manager–worker‐based model for the parallelization of quantum Monte Carlo on heterogeneous and homogeneous networks

Michael T. Feldmann, Julian C. Cummings, David R. Kent +2 more

A manager-worker-based parallelization algorithm for Quantum Monte Carlo (QMC-MW) is presented and compared with the pure iterative parallelization algorithm, which is in common use. The new manager-worker algorithm performs automatic load balancing, allowing it to perform near the theoretical maximal speed even on heterogeneous parallel computers. Furthermore, the new algorithm performs as well as the pure iterative algorithm on homogeneous parallel computers. When combined with the dynamic distributable decorrelation algorithm (DDDA) [Feldmann et al., J Comput Chem 28, 2309 (2007)], the new manager-worker algorithm allows QMC calculations to be terminated at a prespecified level of convergence rather than upon a prespecified number of steps (the common practice). This allows a guaranteed level of precision at the least cost. Additionally, we show (by both analytic derivation and experimental verification) that standard QMC implementations are not "perfectly parallel" as is often claimed.

Journal of Computational Chemistry•Oct 5, 2007•10 citations

New quantum Monte Carlo algorithms to efficiently utilize massively parallel computers

David R. Kent

The exponential growth in computer power over the past few decades has been a huge boon to computational chemistry, physics, biology, and materials science. Now, a standard workstation or Linux cluster can calculate semi-quantitative properties of moderately sized systems. The next step in computational science is developing better algorithms which allow quantitative calculations of a system's properties. A relatively new class of algorithms, known collectively as Quantum Monte Carlo (QMC), has the potential to quantitatively calculate the properties of molecular systems. Furthermore, QMC scales as $O(N^3)$ or better. This makes possible very high-level calculations on systems that are too large to be examined using standard high-level methods. This thesis develops (1) an efficient algorithm for determining "on-the-fly" the statistical error in serially correlated data, (2) a manager-worker parallelization algorithm for QMC that allows calculations to run on heterogeneous parallel computers and computational grids, (3) a robust algorithm for optimizing Jastrow functions which have singularities for some parameter values, and (4) a proof-of-concept demonstrating that it is possible to find transferable parameter sets for large classes of compounds.

•Feb 27, 2003•2 citations

Quantum Monte Carlo: Quest to Get Bigger, Faster, and Cheaper

Feldmann, Michael Todd

We reexamine some fundamental Quantum Monte Carlo (QMC) algorithms with the goal of making QMC more mainstream and efficient. Two major themes exist: (1) Make QMC faster and cheaper, and (2) Make QMC more robust and easier to use. A fast "on-the-fly" algorithm to extract uncorrelated estimators from serially correlated data on a huge network is presented, DDDA. A very efficient manager-worker algorithm for QMC parallelization is presented, QMC-MW. Reduced expense VMC optimization procedure is presented to better guess initial Jastrow parameter sets for hydrocarbons, GJ. I also examine the formation and decomposition of aminomethanol using a variety of methods including a test of the hydrocarbon GJ set on these oxygen- and nitrogen-containing systems. The QMC program suite QMcBeaver is available from the authors in its entirety while a user's and developer's manual is attached as supplementary material.

•Jan 25, 2012•0 citations

Fast Accurate Quantum Monte Carlo without Metropolis Adjustment

Reuben Cohn-Gordon, Gabriel Pescia, Sumner N. Hearth +3 more

In quantum systems, physical quantities of interest can be expressed as expectation values of a probability distribution, which allows their estimation by Markov Chain Monte Carlo (MCMC) methods. This approach, an instance of Quantum Monte Carlo (QMC), plays a central role in obtaining predictions of system properties relevant to condensed matter and high energy physics. The use of Hamiltonian dynamics to design a Markov kernel, known as Hybrid or Hamiltonian Monte Carlo (HMC), is widespread in quantum applications. In this context, it is standard to use an HMC kernel that is ``adjusted'' with the Metropolis-Hastings (MH) criterion, so that estimates of expectations converge to their true value in the limit of infinite sample size. However, recent work in computational statistics suggests that an \emph{unadjusted} HMC kernel can be significantly more efficient, while safely maintaining an asymptotic bias which is small relative to the error arising from the variance of the finite sample size. We adapt this approach to the QMC setting, focusing on a challenging and high-dimensional \emph{spin-fermion} model of a quantum phase transition. We find that unadjusted methods outperform adjusted HMC in terms of effective sample size per gradient call, while retaining accurate results.

arXiv:2611.10187•Nov 6, 2026•0 citations

Efficient calculation of unbiased expectation values in diffusion quantum Monte Carlo

Manolo C. Per, Ian K. Snook, Salvy P. Russo

Despite the proven utility of quantum Monte Carlo methods in addressing the quantum many-body problem, many important observables are difficult to calculate due to the presence of large, and sometimes divergent, statistical errors. The present state of the art allows the construction of renormalized estimators which result in finite variances, but which invariably include some systematic bias. We present a simple method for calculating unbiased expectation values of local operators in the diffusion quantum Monte Carlo method which is applicable to both bare and renormalized estimators, allowing the accurate calculation of important properties such as forces.

Physical Review B•Nov 29, 2012•12 citations

Quantum speedup of Monte Carlo methods

Ashley Montanaro

Monte Carlo methods use random sampling to estimate numerical quantities which are hard to compute deterministically. One important example is the use in statistical physics of rapidly mixing Markov chains to approximately compute partition functions. In this work, we describe a quantum algorithm which can accelerate Monte Carlo methods in a very general setting. The algorithm estimates the expected output value of an arbitrary randomized or quantum subroutine with bounded variance, achieving a near-quadratic speedup over the best possible classical algorithm. Combining the algorithm with the use of quantum walks gives a quantum speedup of the fastest known classical algorithms with rigorous performance bounds for computing partition functions, which use multiple-stage Markov chain Monte Carlo techniques. The quantum algorithm can also be used to estimate the total variation distance between probability distributions efficiently.

arXiv:1504.06987•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Aug 26, 2015•431 citations
We describe the Dynamic Distributable Decorrelation Algorithm (DDDA) which efficiently calculates the true statistical error of an expectation value obtained from serially correlated data "on-the-fly," as the calculation progresses. DDDA is an improvement on the Flyvbjerg-Petersen renormalization group blocking method (Flyvberg and Peterson, J Chem Phys 1989, 91, 461). This "on-the-fly" determination of statistical quantities allows dynamic termination of Monte Carlo calculations once a specified level of convergence is attained. This is highly desirable when the required precision might take days or months to compute, but cannot be accurately estimated prior to the calculation. Furthermore, DDDA allows for a parallel implementation which requires very low communication, O(log(2)N), and can also evaluate the variance of a calculation efficiently "on-the-fly." Quantum Monte Carlo calculations are presented to illustrate "on-the-fly" variance calculations for serial and massively parallel Monte Carlo calculations.
A manager-worker-based parallelization algorithm for Quantum Monte Carlo (QMC-MW) is presented and compared with the pure iterative parallelization algorithm, which is in common use. The new manager-worker algorithm performs automatic load balancing, allowing it to perform near the theoretical maximal speed even on heterogeneous parallel computers. Furthermore, the new algorithm performs as well as the pure iterative algorithm on homogeneous parallel computers. When combined with the dynamic distributable decorrelation algorithm (DDDA) [Feldmann et al., J Comput Chem 28, 2309 (2007)], the new manager-worker algorithm allows QMC calculations to be terminated at a prespecified level of convergence rather than upon a prespecified number of steps (the common practice). This allows a guaranteed level of precision at the least cost. Additionally, we show (by both analytic derivation and experimental verification) that standard QMC implementations are not "perfectly parallel" as is often claimed.
The exponential growth in computer power over the past few decades has been a huge boon to computational chemistry, physics, biology, and materials science. Now, a standard workstation or Linux cluster can calculate semi-quantitative properties of moderately sized systems. The next step in computational science is developing better algorithms which allow quantitative calculations of a system's properties. A relatively new class of algorithms, known collectively as Quantum Monte Carlo (QMC), has the potential to quantitatively calculate the properties of molecular systems. Furthermore, QMC scales as O(N3)O(N^3)O(N3) or better. This makes possible very high-level calculations on systems that are too large to be examined using standard high-level methods. This thesis develops (1) an efficient algorithm for determining "on-the-fly" the statistical error in serially correlated data, (2) a manager-worker parallelization algorithm for QMC that allows calculations to run on heterogeneous parallel computers and computational grids, (3) a robust algorithm for optimizing Jastrow functions which have singularities for some parameter values, and (4) a proof-of-concept demonstrating that it is possible to find transferable parameter sets for large classes of compounds.
We reexamine some fundamental Quantum Monte Carlo (QMC) algorithms with the goal of making QMC more mainstream and efficient. Two major themes exist: (1) Make QMC faster and cheaper, and (2) Make QMC more robust and easier to use. A fast "on-the-fly" algorithm to extract uncorrelated estimators from serially correlated data on a huge network is presented, DDDA. A very efficient manager-worker algorithm for QMC parallelization is presented, QMC-MW. Reduced expense VMC optimization procedure is presented to better guess initial Jastrow parameter sets for hydrocarbons, GJ. I also examine the formation and decomposition of aminomethanol using a variety of methods including a test of the hydrocarbon GJ set on these oxygen- and nitrogen-containing systems. The QMC program suite QMcBeaver is available from the authors in its entirety while a user's and developer's manual is attached as supplementary material.
In quantum systems, physical quantities of interest can be expressed as expectation values of a probability distribution, which allows their estimation by Markov Chain Monte Carlo (MCMC) methods. This approach, an instance of Quantum Monte Carlo (QMC), plays a central role in obtaining predictions of system properties relevant to condensed matter and high energy physics. The use of Hamiltonian dynamics to design a Markov kernel, known as Hybrid or Hamiltonian Monte Carlo (HMC), is widespread in quantum applications. In this context, it is standard to use an HMC kernel that is ``adjusted'' with the Metropolis-Hastings (MH) criterion, so that estimates of expectations converge to their true value in the limit of infinite sample size. However, recent work in computational statistics suggests that an \emph{unadjusted} HMC kernel can be significantly more efficient, while safely maintaining an asymptotic bias which is small relative to the error arising from the variance of the finite sample size. We adapt this approach to the QMC setting, focusing on a challenging and high-dimensional \emph{spin-fermion} model of a quantum phase transition. We find that unadjusted methods outperform adjusted HMC in terms of effective sample size per gradient call, while retaining accurate results.
Despite the proven utility of quantum Monte Carlo methods in addressing the quantum many-body problem, many important observables are difficult to calculate due to the presence of large, and sometimes divergent, statistical errors. The present state of the art allows the construction of renormalized estimators which result in finite variances, but which invariably include some systematic bias. We present a simple method for calculating unbiased expectation values of local operators in the diffusion quantum Monte Carlo method which is applicable to both bare and renormalized estimators, allowing the accurate calculation of important properties such as forces.
Monte Carlo methods use random sampling to estimate numerical quantities which are hard to compute deterministically. One important example is the use in statistical physics of rapidly mixing Markov chains to approximately compute partition functions. In this work, we describe a quantum algorithm which can accelerate Monte Carlo methods in a very general setting. The algorithm estimates the expected output value of an arbitrary randomized or quantum subroutine with bounded variance, achieving a near-quadratic speedup over the best possible classical algorithm. Combining the algorithm with the use of quantum walks gives a quantum speedup of the fastest known classical algorithms with rigorous performance bounds for computing partition functions, which use multiple-stage Markov chain Monte Carlo techniques. The quantum algorithm can also be used to estimate the total variation distance between probability distributions efficiently.