Sign problem in full configuration interaction quantum Monte Carlo: Linear and sublinear representation regimes for the exact wave function

We investigate the sign problem for full configuration interaction quantum Monte Carlo (FCIQMC), a stochastic algorithm for finding the ground-state solution of the Schrödinger equation with substantially reduced computational cost compared with exact diagonalization. We find $k$-space Hubbard models for which the solution is yielded with storage that grows sublinearly in the size of the many-body Hilbert space, in spite of using a wave function that is simply a linear combination of states. The FCIQMC algorithm is able to find this sublinear scaling regime without bias and with only a choice of the Hamiltonian basis. By means of a demonstration we solve for the energy of a 70-site half-filled system (with a space of ${10}^{38}$ determinants) in 250 core hours, substantially quicker than the $\sim {10}^{36}$ core hours that would be required by exact diagonalization. This is the largest space that has been sampled in an unbiased fashion. The challenge for the recently developed FCIQMC method is made clear: Expand the sublinear scaling regime while retaining exact-on-average accuracy. We comment upon the relationship between this and the scaling law previously observed in the initiator adaptation (i-FCIQMC). We argue that our results change the landscape for the development of FCIQMC and related methods.

Figure 1

These two panels describe how we are able to identify plateaus. In (a), the decrease in $U$ is shown to obscure the plateau. The bold, black (red online), dashed annotation indicates the $U=0.5$ population growth averaged over 100 random number seeds. In (b), we show that the population at the plateau corresponds to the maximum value of histogram of the population (although, in general, variable bin widths were used). These two panels share a common key.

Figure 2

Analysis of all plateaus found in this study. In (a), plateau heights are plotted against the sizes of space. In (b) the scaling trends are summarized in a diagram relating it to system parameters. In (a), the following bold, black (red online) annotations have been made. The solid line indicates the $N_{\mathrm{plat}}=N_{\det }$, where we are storing one walker per determinant (on average) across the simulation and the storage becomes comparable to FCI (unshaded region). The dashed line indicates where $U=1.0$ would be if it retained the same plateau height scaling as high $U$ values. The size of space was calculated by a Monte Carlo method and takes into account momentum symmetry [26].