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:1209.3044 · The Journal of Chemical Physics

The effect of quantization on the full configuration interaction quantum Monte Carlo sign problem

Michael Kolodrubetz, James S. Spencer, Bryan K. Clark, W. M. C. Foulkes

Published Jan 11, 2013• 30 citations
arXivHTMLPDF

Abstract

The sign problem in full configuration interaction quantum Monte Carlo (FCIQMC) without annihilation can be understood as an instability of the psi-particle population to the ground state of the matrix obtained by making all off-diagonal elements of the Hamiltonian negative. Such a matrix, and hence the sign problem, is basis dependent. In this paper, we discuss the properties of a physically important basis choice: first versus second quantization. For a given choice of single-particle orbitals, we identify the conditions under which the fermion sign problem in the second quantized basis of antisymmetric Slater determinants is identical to the sign problem in the first quantized basis of unsymmetrized Hartree products. We also show that, when the two differ, the fermion sign problem is always less severe in the second quantized basis. This supports the idea that FCIQMC, even in the absence of annihilation, improves the sign problem relative to first quantized methods. Finally, we point out some theoretically interesting classes of Hamiltonians where first and second quantized sign problems differ, and others where they do not.

DOI
10.1063/1.4773819

Related papers

A second-quantized red herring in full configuration-interaction Monte Carlo

Michael Kolodrubetz, Bryan K. Clark

This paper deals with the sign problem in full configuration-interaction quantum Monte Carlo. After putting this article on the arxiv, it was pointed out to us that our argument applies to a number of model Hamiltonians we considered numerically but not to the most generic case. Please see arxiv: 1209.3044, where we have a corrected comprehensive discussion of the necessary and sufficient conditions for when the sign problem for a given Hamiltonian (and basis) differ between first and second quantization.

arXiv:1202.0525•Feb 2, 2012•1 citation

Emergence of Critical Phenomena in Full Configuration Interaction Quantum Monte Carlo

James J. Shepherd, Lauretta R. Schwarz, Robert E. Thomas +3 more

There has been recent literature discussion on the origin and severity of the `sign problem' in full configuration interaction quantum Monte Carlo (FCIQMC) and its `initiator' adaptation (i-FCIQMC), methods of interest and potential because they allow for exact (FCI) ground-state solutions to be obtained often at a much reduced computational cost. In this study we aim to use a simple order parameter, describing the `sign structure' of the stochastic wavefunction representation, to empirically characterise the fundamentally different collective behaviour of the walker population in both methods.

arXiv:1209.4023•Sep 18, 2012•0 citations

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

James J. Shepherd, Gustavo E. Scuseria, James S. Spencer

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\"odinger 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 $\ensuremath{\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.

arXiv:1407.4800•Physical Review B•Oct 27, 2014•35 citations

The sign problem and population dynamics in the full configuration interaction quantum Monte Carlo method

J. S. Spencer, Nick S. Blunt, W. M. C. Foulkes

The recently proposed full configuration interaction quantum Monte Carlo method allows access to essentially exact ground-state energies of systems of interacting fermions substantially larger than previously tractable without knowledge of the nodal structure of the ground-state wave function. We investigate the nature of the sign problem in this method and how its severity depends on the system studied. We explain how cancellation of the positive and negative particles sampling the wave function ensures convergence to a stochastic representation of the many-fermion ground state and accounts for the characteristic population dynamics observed in simulations.

arXiv:1110.5479•The Journal of Chemical Physics•Feb 6, 2012•108 citations

The Sign Problem in Density Matrix Quantum Monte Carlo

Hayley Petras, William Z. Van Benschoten, Sai Kumar Ramadugu +1 more

High Resolution Image Download MS PowerPoint Slide Density matrix quantum Monte Carlo (DMQMC) is a recently developed method for stochastically sampling the N -particle thermal density matrix to obtain exact-on-average energies for model and ab initio systems. We report a systematic numerical study of the sign problem in DMQMC based on simulations of atomic and molecular systems. In DMQMC, the density matrix is written in an outer product basis of Slater determinants. In principle, this means that DMQMC needs to sample a space that scales in the system size, N, as O[(exp(N)) 2 ]. In practice, removing the sign problem requires a total walker population that exceeds a system-dependent critical walker population ( N c ), imposing limitations on both storage and compute time. We establish that N c for DMQMC is the square of N c for FCIQMC. By contrast, the minimum N c in the interaction picture modification of DMQMC (IP-DMQMC) is only linearly related to the N c for FCIQMC. We find that this difference originates from the difference in propagation of IP-DMQMC versus canonical DMQMC: the former is asymmetric, whereas the latter is symmetric. When an asymmetric mode of propagation is used in DMQMC, there is a much greater stochastic error and is thus prohibitively expensive for DMQMC without the interaction picture adaptation. Finally, we find that the equivalence between IP-DMQMC and FCIQMC seems to extend to the initiator approximation, which is often required to study larger systems with large basis sets. This suggests that IP-DMQMC offers a way to ameliorate the cost of moving between a Slater determinant space and an outer product basis.

arXiv:2102.00080•Journal of Chemical Theory and Computation•Sep 21, 2021•7 citations

Partial node configuration-interaction Monte Carlo as applied to the Fermi polaron

Michael Kolodrubetz, Bryan K. Clark

Finding the ground state of a fermionic Hamiltonian using quantum Monte Carlo (QMC) is a very difficult problem, due to the Fermi sign problem. While still scaling exponentially, full configuration-interaction Monte Carlo (FCIQMC) mitigates some of the exponential variance by allowing annihilation of noise---whenever two walkers arrive at the same configuration with opposite signs, they are removed from the simulation. While FCIQMC has been quite successful for quantum chemistry problems, its application to problems in condensed systems has been limited. In this paper, we apply the FCIQMC algorithm to the Fermi polaron problem, which provides an ideal test bed for improving the algorithm, although since we restrict the number of many-body excitations, our algorithm is more precisely a QMC implementation of the configuration-interaction method (CIQMC). In its simplest form, CIQMC is unstable for even a fairly small system sizes. However, with a series of algorithmic improvements, we are able to significantly increase its effectiveness. We modify fixed node QMC to work in these systems, introduce a well chosen importance sampled trial wave function, a partial node approximation, and a variant of release node. Finally, we develop a way to perform CIQMC directly in the thermodynamic limit.

arXiv:1204.1490•Physical Review B•Aug 6, 2012•21 citations
The sign problem in full configuration interaction quantum Monte Carlo (FCIQMC) without annihilation can be understood as an instability of the psi-particle population to the ground state of the matrix obtained by making all off-diagonal elements of the Hamiltonian negative. Such a matrix, and hence the sign problem, is basis dependent. In this paper, we discuss the properties of a physically important basis choice: first versus second quantization. For a given choice of single-particle orbitals, we identify the conditions under which the fermion sign problem in the second quantized basis of antisymmetric Slater determinants is identical to the sign problem in the first quantized basis of unsymmetrized Hartree products. We also show that, when the two differ, the fermion sign problem is always less severe in the second quantized basis. This supports the idea that FCIQMC, even in the absence of annihilation, improves the sign problem relative to first quantized methods. Finally, we point out some theoretically interesting classes of Hamiltonians where first and second quantized sign problems differ, and others where they do not.
This paper deals with the sign problem in full configuration-interaction quantum Monte Carlo. After putting this article on the arxiv, it was pointed out to us that our argument applies to a number of model Hamiltonians we considered numerically but not to the most generic case. Please see arxiv: 1209.3044, where we have a corrected comprehensive discussion of the necessary and sufficient conditions for when the sign problem for a given Hamiltonian (and basis) differ between first and second quantization.
There has been recent literature discussion on the origin and severity of the `sign problem' in full configuration interaction quantum Monte Carlo (FCIQMC) and its `initiator' adaptation (i-FCIQMC), methods of interest and potential because they allow for exact (FCI) ground-state solutions to be obtained often at a much reduced computational cost. In this study we aim to use a simple order parameter, describing the `sign structure' of the stochastic wavefunction representation, to empirically characterise the fundamentally different collective behaviour of the walker population in both methods.
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\"odinger equation with substantially reduced computational cost compared with exact diagonalization. We find kkk-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 1038{10}^{38}1038 determinants) in 250 core hours, substantially quicker than the $\ensuremath{\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.
The recently proposed full configuration interaction quantum Monte Carlo method allows access to essentially exact ground-state energies of systems of interacting fermions substantially larger than previously tractable without knowledge of the nodal structure of the ground-state wave function. We investigate the nature of the sign problem in this method and how its severity depends on the system studied. We explain how cancellation of the positive and negative particles sampling the wave function ensures convergence to a stochastic representation of the many-fermion ground state and accounts for the characteristic population dynamics observed in simulations.
High Resolution Image Download MS PowerPoint Slide Density matrix quantum Monte Carlo (DMQMC) is a recently developed method for stochastically sampling the N -particle thermal density matrix to obtain exact-on-average energies for model and ab initio systems. We report a systematic numerical study of the sign problem in DMQMC based on simulations of atomic and molecular systems. In DMQMC, the density matrix is written in an outer product basis of Slater determinants. In principle, this means that DMQMC needs to sample a space that scales in the system size, N, as O[(exp(N)) 2 ]. In practice, removing the sign problem requires a total walker population that exceeds a system-dependent critical walker population ( N c ), imposing limitations on both storage and compute time. We establish that N c for DMQMC is the square of N c for FCIQMC. By contrast, the minimum N c in the interaction picture modification of DMQMC (IP-DMQMC) is only linearly related to the N c for FCIQMC. We find that this difference originates from the difference in propagation of IP-DMQMC versus canonical DMQMC: the former is asymmetric, whereas the latter is symmetric. When an asymmetric mode of propagation is used in DMQMC, there is a much greater stochastic error and is thus prohibitively expensive for DMQMC without the interaction picture adaptation. Finally, we find that the equivalence between IP-DMQMC and FCIQMC seems to extend to the initiator approximation, which is often required to study larger systems with large basis sets. This suggests that IP-DMQMC offers a way to ameliorate the cost of moving between a Slater determinant space and an outer product basis.
Finding the ground state of a fermionic Hamiltonian using quantum Monte Carlo (QMC) is a very difficult problem, due to the Fermi sign problem. While still scaling exponentially, full configuration-interaction Monte Carlo (FCIQMC) mitigates some of the exponential variance by allowing annihilation of noise---whenever two walkers arrive at the same configuration with opposite signs, they are removed from the simulation. While FCIQMC has been quite successful for quantum chemistry problems, its application to problems in condensed systems has been limited. In this paper, we apply the FCIQMC algorithm to the Fermi polaron problem, which provides an ideal test bed for improving the algorithm, although since we restrict the number of many-body excitations, our algorithm is more precisely a QMC implementation of the configuration-interaction method (CIQMC). In its simplest form, CIQMC is unstable for even a fairly small system sizes. However, with a series of algorithmic improvements, we are able to significantly increase its effectiveness. We modify fixed node QMC to work in these systems, introduce a well chosen importance sampled trial wave function, a partial node approximation, and a variant of release node. Finally, we develop a way to perform CIQMC directly in the thermodynamic limit.