The Monte Carlo method is a powerful scheme to solve many mathematical equations and is in fact, made practical only through high speed computers, particularly for those physical problems that are of high dimensionality. Alternative numerical schemes of spanning high dimensional spaces uniformly with a grid, increase in computational time exponentially with the dimensionality and thus became rapidly impractical as the dimensionality increases. The key to success of a Monte Carlo scheme is that it samples the space selectively, not with some uniform random distribution but where it matters most, by a probability density called an importance function. Furthermore, the Monte Carlo scheme is well adapted to computers since it consists of a simple, highly repetitive algorithm that takes advantage of the fast arithmetic capabilities of the machines. Consideration of how to arrange such calculations efficiently on various machines of different architecture is discussed.
The Monte Carlo method is a powerful scheme to solve many mathematical equations and is in fact, made practical only through high speed computers, particularly for those physical problems that are of high dimensionality. Alternative numerical schemes of spanning high dimensional spaces uniformly with a grid, increase in computational time exponentially with the dimensionality and thus became rapidly impractical as the dimensionality increases. The key to success of a Monte Carlo scheme is that it samples the space selectively, not with some uniform random distribution but where it matters most, by a probability density called an importance function. Furthermore, the Monte Carlo scheme is well adapted to computers since it consists of a simple, highly repetitive algorithm that takes advantage of the fast arithmetic capabilities of the machines. Consideration of how to arrange such calculations efficiently on various machines of different architecture is discussed.
This paper discusses some mathematical aspects related to the use of probabilistic techniques in quantum Monte Carlo (QMC) methods from a physicist’s point of view. A selected list of problems and techniques employed in computational physics and of interest to the applied probability community is presented. One of the variants of QMC approaches based on the Feynman-Kac formula is described in some detail. The problem of numerical efficiency at the heart of physical applications defined in (very) high-dimensional space is discussed and the commonly used solution through importance sampling is presented. Finally, the specific constraints related to fermion systems in QMC are presented and the celebrated “fermion sign problem” (considered as one of the most important open problem in computational physics) is discussed.
High-quality random samples of quantum states are needed for a variety of tasks in quantum information and quantum computation. Searching the high-dimensional quantum state space for a global maximum of an objective function with many local maxima or evaluating an integral over a region in the quantum state space are but two exemplary applications of many. These tasks can only be performed reliably and efficiently with Monte Carlo methods, which involve good samplings of the parameter space in accordance with the relevant target distribution. We show how the Markov-chain Monte Carlo method known as Hamiltonian Monte Carlo, or hybrid Monte Carlo, can be adapted to this context. It is applicable when an efficient parameterization of the state space is available. The resulting random walk is entirely inside the physical parameter space, and the Hamiltonian dynamics enable us to take big steps, thereby avoiding strong correlations between successive sample points while enjoying a high acceptance rate. We use examples of single and double qubit measurements for illustration.
A quantum Monte Carlo method is simply a Monte Carlo method applied to a quantum problem. What distinguishes a quantum Monte Carlo method from a classical one is the initial effort necessary to represent the quantum problem in a form that is suitable for Monte Carlo simulation. It is in making this transformation that the quantum nature of the problem asserts itself not only through such obvious issues as the noncommutivity of the physical variables and the need to symmetrize or antisymmetrize the wave function, but also through less obvious issues such as the sign problem. Almost always, the transformation replaces the quantum degrees of freedom by classical ones, and it is to these classical degrees of freedom that the Monte Carlo method is actually applied. Succeeding chapters present and explain many of the quantum Monte Carlo methods being successfully used on a variety of quantum problems. In Chapters 1 and 2 we focus on discussing what the Monte Carlo method is and why it is useful. The Monte Carlo method The Monte Carlo method is not a specific technique but a general strategy for solving problems too complex to solve analytically or too intensive numerically to solve deterministically. Often a specific strategy incorporates several different Monte Carlo techniques. In what is likely the first journal article to use the phrase “Monte Carlo,” Metropolis and Ulam (1949) discuss this strategy. To paraphrase them, The Monte Carlo method is an iterative stochastic procedure, consistent with a defining relation for some function, which allows an estimate of the function without completely determining it. This is quite different from the colloquialism, “a method that uses random numbers.” Let us examine the definition piece by piece. A key point will emerge. Ulam and Metropolis were presenting the motivation and a general description of a statistical approach to the study of differential and integro-differential equations. These equations were their “defining relation for some function.” The “function” was the solution of these equations. This function is of course unknown a priori. Metropolis, Rosenbluth, Rosenbluth, Teller, and Teller (1953) a few years later would propose a statistical approach to the study of equilibrium statistical mechanics. The defining relation there was a thermodynamic average of a physical quantity over the Boltzmann distribution. The function was the physical quantity, and the unknown its average.
In this brief article, I introduce the various types of quantum Monte Carlo (QMC) methods, in particular, those that are applicable to systems in extreme regimes of temperature and pressure.We give references to longer articles where detailed discussion of applications and algorithms appear. MOTIVATIONOne does QMC for the same reason as one does classical simulations; there is no other method able to treat exactly the quantum many-body problem aside from the direct simulation method where electrons and ions are directly represented as particles, instead of as a "fluid" as is done in mean-field based methods.However, quantum systems are more difficult than classical systems because one does not know the distribution to be sampled, it must be solved for.In fact, it is not known today which quantum problems can be "solved" with simulation on a classical computer in a reasonable amount of computer time.One knows that certain systems, such as most quantum many-body systems in 1D and most bosonic systems are amenable to solution with Monte Carlo methods, however, the "sign problem" prevents making the same statement for systems with electrons in 3D.Some limitations or approximations are needed in practice.On the other hand, in contrast to simulation of classical systems, one does know the Hamiltonian exactly: namely charged particles interacting with a Coulomb potential.Given sufficient computer resources, the results can be of quite high quality and for systems where there is little reliable experimental data.For this reason, QMC methods, though more expensive, are useful to benchmark and validate results from other methods.The two main applications that we will discuss in this review are the "electronic structure problem"; computing the energy of the an interacting systems of electrons and fixed ions, and the problem of quantum effects of the nuclei. RANDOM WALK AND MARKOV CHAINSMost QMC algorithms are based on random walks, known mathematically as Markov chains.This is a general class of algorithms, introduced in the famous work by Metropolis, the Rosenbluths and the Tellers (1953) for sampling any probability distribution.Let us denote the desired distribution as Π(S), where the variable "S" represents the state of the walk, for example the coordinates of all of the particles.In a random walk, one invents some moving rules (transition probabilities) for changing the state of the system so that the probability of being in state S n+1 in the (n+1) step, given that the random walk was S n is given by T(S n ; S n+1 ).By
… as suggested by Fermi, the time-independent Schrödinger equation … can be interpreted as describing the behavior of a system of particles each of which performs a random walk, i.e., diffuses isotropically and at the same time is subject to multiplication, which is determined by the value of the point function V. N. Metropolis and S. Ulam, 1949 Summary In the projector quantum Monte Carlo method, one uses a function of the hamiltonian to sample a distribution proportional to the exact ground-state wavefunction, and thereby computes exact matrix elements of it. An importance sampling transformation makes the algorithm much more efficient. In this chapter we introduce and develop the diffusion Monte Carlo method, which involves drifting, branching random walks. For any excited state, including any system with more than two electrons, one encounters the sign problem, limiting the direct application of these algorithms for most fermion systems. Instead, by using approximate fixed-node or fixed-phase boundary conditions, one can achieve efficiency similar to variational Monte Carlo. We also discuss the application of the projector method in a basis of Slater determinants. In this chapter, we discuss a different quantum Monte Carlo method, projector Monte Carlo (PMC). This general method was first suggested by Fermi [1049]; see the quote at the start of this chapter by two of the inventors of the Monte Carlo method. An implementation of PMC was tried out in the early days of computing [1050]. Advances in methodology, in particular importance sampling, resulted in a significant large-scale application: the exact calculation of the ground-state properties of 256 hard-sphere bosons by Kalos, Levesque, and Verlet [1051] in 1974. Calculations for electronic systems and the fixednode approximation were introduced by Anderson [1052, 1053]. One of the most important projector MC algorithms, the diffusion Monte Carlo algorithm with importance sampling for fermions, was used to compute the correlation energy of homogeneous electron gas by Ceperley and Alder [109] in 1980; the resulting HEG correlation energy was crucial in the development of density functional calculations. Types and properties of projectors In this method, a many-body projector G ( R , R ) = Ĝ is repeatedly applied to filter out the exact many-body ground state from an initial state; the operation of the projector is carried out with a random walk, hence the name of this class of methods.
With advances in algorithms and growing computing powers, quantum Monte Carlo (QMC) methods have become a leading contender for high accuracy calculations for the electronic structure of realistic systems. The performance gain on recent HPC systems is largely driven by increasing parallelism: the number of compute cores of a SMP and the number of SMPs have been going up, as the Top500 list attests. However, the available memory as well as the communication and memory bandwidth per element has not kept pace with the increasing parallelism. This severely limits the applicability of QMC and the problem size it can handle. OpenMP/MPI hybrid programming provides applications with simple but effective solutions to overcome efficiency and scalability bottlenecks on large-scale clusters based on multi/many-core SMPs. We discuss the design and implementation of hybrid methods in QMCPACK and analyze its performance on current HPC platforms characterized by various memory and communication hierarchies.