Quantum Monte Carlo versions of the power method for finding ground states come with different names, including the projector method, diffusion Monte Carlo, and Green's function Monte Carlo. These quantum Monte Carlo methods are primarily adoptions of methods developed for classical problems. We summarize the basics of deterministic power methods, detail key features of Monte Carlo power methods, and put these concepts into the context of quantum ground state calculations. We conclude the chapter by outlining power methods that allow the computation of a few excited states. In the computation of excited states, we encounter sign problems, which are discussed inmore detail in Chapter 11. Themethods and techniques of the present chapter are very general and most usefully applied to systems of Bosons and to systems of Fermions and quantum spins that do not suffer from a sign problem. Deterministic direct and inverse power methods The power method is over a century old. As a deterministic method, it originally was combined with the deflation technique (Meyer, 2000; Stewart, 2001b) as a method to compute all the eigenvalues and eigenvectors of small matrices. Today, its deterministic use is limited primarily to special applications involving very large, sparse matrices. Many of these applications are in the study of quantum lattice models as the corresponding Hamiltonian matrices are typically very sparse. In these applications, we can perhaps initially store in computer memory the relatively small number of nonzero matrix elements and all the vectors. Soon, because of what is undoubtedly the now familiar exponentially increasing number of basis states that determines the order of the Hamiltonian matrix and hence the size of our vectors, we reach the point where computer memory restrictions allow us to store only a few vectors and we need to compute the matrix elements on the fly. When we have problems for which we cannot even store all the components of one vector, the power method's expression as a Monte Carlo procedure is our only option. With it, we can compute a few of the extremal eigenvalues, that is, a few of the largest or smallest eigenvalues. The mathematical basis for the method is simple.
Quantum Monte Carlo versions of the power method for finding ground states come with different names, including the projector method, diffusion Monte Carlo, and Green's function Monte Carlo. These quantum Monte Carlo methods are primarily adoptions of methods developed for classical problems. We summarize the basics of deterministic power methods, detail key features of Monte Carlo power methods, and put these concepts into the context of quantum ground state calculations. We conclude the chapter by outlining power methods that allow the computation of a few excited states. In the computation of excited states, we encounter sign problems, which are discussed inmore detail in Chapter 11. Themethods and techniques of the present chapter are very general and most usefully applied to systems of Bosons and to systems of Fermions and quantum spins that do not suffer from a sign problem. Deterministic direct and inverse power methods The power method is over a century old. As a deterministic method, it originally was combined with the deflation technique (Meyer, 2000; Stewart, 2001b) as a method to compute all the eigenvalues and eigenvectors of small matrices. Today, its deterministic use is limited primarily to special applications involving very large, sparse matrices. Many of these applications are in the study of quantum lattice models as the corresponding Hamiltonian matrices are typically very sparse. In these applications, we can perhaps initially store in computer memory the relatively small number of nonzero matrix elements and all the vectors. Soon, because of what is undoubtedly the now familiar exponentially increasing number of basis states that determines the order of the Hamiltonian matrix and hence the size of our vectors, we reach the point where computer memory restrictions allow us to store only a few vectors and we need to compute the matrix elements on the fly. When we have problems for which we cannot even store all the components of one vector, the power method's expression as a Monte Carlo procedure is our only option. With it, we can compute a few of the extremal eigenvalues, that is, a few of the largest or smallest eigenvalues. The mathematical basis for the method is simple.
… 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.
Projection methods such as Green's function and diffusion Monte Carlo are commonly used to calculate the leading eigenvalue and eigenvector of operators or large matrices. They thereby give access to ground state properties of quantum systems, and finite temperature properties of classical statistical mechanical systems having a transfer matrix. The basis of these approaches is a stochastic application of the power method in which a "projection" operator is applied iteratively. For the systematic errors to be small, the number of iterations must be large; however, in that limit, the statistical errors grow tremendously. We present an analytical study of the main variance reduction methods used for dealing with this problem. In particular, we discuss the consequences of guiding, replication, and population control on statistical and systematic errors.
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.
We introduce a semistochastic implementation of the power method to compute, for very large matrices, the dominant eigenvalue and expectation values involving the corresponding eigenvector. The method is semistochastic in that the matrix multiplication is partially implemented numerically exactly and partially stochastically with respect to expectation values only. Compared to a fully stochastic method, the semistochastic approach significantly reduces the computational time required to obtain the eigenvalue to a specified statistical uncertainty. This is demonstrated by the application of the semistochastic quantum Monte Carlo method to systems with a sign problem: the fermion Hubbard model and the carbon dimer.
A novel scheme to solve the quantum eigenvalue problem through the imaginary-time Green function Monte Carlo method is presented. This method is applicable not only to the ground states, but also to the excited states of generic system. We demonstrate the actual utility of the method with the numerical examples on three simple systems. Typeset using REVTEX 1 The stochastic quantization has been successfully applied in recent years to the various problems of physics ranging from quantum chromo dynamics to the plasmon oscillation [1-3]. While it can handle very complex systems which is usually beyond the approach either by the direct diagonalization or by the perturbation, it has been only applicable to the calculation of the ground state properties of the system. In this paper, we propose a new method based on the imaginary-time Green function Monte Carlo approach, which is extendable to the excited states of Hamiltonian system. We have primarily in mind the non-relativistic quantum few body problem such as encountered in nuclear physics [4-6].
In this chapter, we discuss the fixed-node and constrained-path Monte Carlo methods for computing the ground state properties of systems of interacting electrons. These methods are arguably the two most powerful ones presently available for doing such calculations, but they are approximate. By sacrificing exactness, they avoid the exponential scaling of the Monte Carlo errors with system size that typically accompanies the simulation of systems of interacting electrons. This exponential scaling is called the Fermion sign problem . After a few general comments about the sign problem, we outline both methods, noting points of similarity and difference, plus points of strength and weakness. We also discuss the constrained-phase method, an extension of the constrained-path method, which controls the phase problem that develops when the ground state wave function cannot be real. Sign problem The “sign problem” refers to the exponential increase of the Monte Carlo errors with increasing system size or decreasing temperature (e.g., Loh et al., 1990, 2005; Gubernatis and Zhang, 1994) that often accompanies a Markov chain simulation whose limiting distribution is not everywhere positive. Such a case generally arises in simulations of Fermion and frustrated quantum-spin systems. It seems so inherent to Monte Carlo simulations of Fermion systems that the phrase “the sign problem” to many seems almost synonymous with the phrase “the Fermion sign problem.” Explanations for the cause of the sign problem vary and are still debated. In this chapter, we choose to summarize two explanations that seem to connect the causes in ground state Fermion simulations in the continuum and on the lattice. The sign problem, of course, is not limited to ground state calculations or even to Fermion simulations. While the cause we discuss in Sections 11.2 and 11.3 focuses on the low-lying states of diffusion-like operators, several topological pictures have been proposed (Muramatsu et al., 1992; Samson, 1993; Gubernatis and Zhang, 1994; Samson, 1995). Some of these discussions are done in the context of the zero- and finite-temperature determinant methods (Muramatsu et al., 1992; Gubernatis and Zhang, 1994). Others are done more analytically from a Feynman path-integral point of view (Samson, 1993, 1995). Some are for particles with statistics other than Fermions. The presentation of the sign problem in this chapter is appropriate for the Monte Carlo methods discussed in this chapter.