Monte Carlo simulations are a powerful tool for elucidating the properties of complex systems, but when applied to fermionic quantum systems, quantum Monte Carlo (QMC) algorithms suffer from the so-called ``negative sign problem,'' causing the computational effort to grow exponentially with problem size. Here we demonstrate that the fermion sign problem originates in topological properties of the configurations. Using the widely used determinantal approaches, that remove the trivial sign problem due to particle exchange, we prove that the negative sign of a configuration is a topological invariant---an imaginary time counterpart of the Aharonov-Anandan phase---and reduces to a Berry phase in the adiabatic limit. This provides an intriguing connection between QMC simulations and classification of topological states.
Monte Carlo simulations are a powerful tool for elucidating the properties of complex systems, but when applied to fermionic quantum systems, quantum Monte Carlo (QMC) algorithms suffer from the so-called ``negative sign problem,'' causing the computational effort to grow exponentially with problem size. Here we demonstrate that the fermion sign problem originates in topological properties of the configurations. Using the widely used determinantal approaches, that remove the trivial sign problem due to particle exchange, we prove that the negative sign of a configuration is a topological invariant---an imaginary time counterpart of the Aharonov-Anandan phase---and reduces to a Berry phase in the adiabatic limit. This provides an intriguing connection between QMC simulations and classification of topological states.
Sign problem in quantum Monte Carlo (QMC) simulation appears to be an extremely hard yet interesting problem. In this article, we present a pedagogical overview on the origin of the sign problem in various quantum Monte Carlo simulation techniques, ranging from the world-line and stochastic series expansion Monte Carlo for boson and spin systems to the determinant and momentum-space quantum Monte Carlo for interacting fermions. We point out the basis dependency of the sign problem and summarize the progresses to cure, ease and even make use of the sign problem over the years, such as symmetry analysis of the underlying Hamiltonian, basis optimization in writting down the partition functions and many others. Moreover, we state that although traditional lore saying that in case of sign problem, the average sign in QMC simulation approaches zero exponentially fast with the space-time volume of the configurational space, there are recent breakthroughs showing this is not always the case and based on the properties of the partition function for finite size systems, one could distinguish when the average sign has the usual exponential scaling and when it is bestowed with an algebraic scaling at the low temperature limit. Fermionic QMC simulations with such algebraic sign problems have been successfully carried out for extended Hubbard-type and quantum Moiré lattice models.
Quantum Monte Carlo simulations, while being efficient for bosons, suffer from the "negative sign problem" when applied to fermions--causing an exponential increase of the computing time with the number of particles. A polynomial time solution to the sign problem is highly desired since it would provide an unbiased and numerically exact method to simulate correlated quantum systems. Here we show that such a solution is almost certainly unattainable by proving that the sign problem is nondeterministic polynomial (NP) hard, implying that a generic solution of the sign problem would also solve all problems in the complexity class NP in polynomial time.
Sign problems in fermion quantum Monte Carlo (QMC) simulation appears to be an extremely hard problem. Traditional lore passing around for years tells people that when there is a sign problem, the average sign in QMC simulation approaches zero exponentially fast with the space-time volume of the configurational space. We, however, analytically show this is not always the case and manage to find physical bounds for the average sign. Our understanding is based on a direct connection between the sign bounds and a well-defined partition function of the reference system and could distinguish when the bounds have the usual exponential scaling and when they are bestowed on an algebraic scaling at the low-temperature limit. We analytically explain such algebraic sign problems found in flat-band moir\'e lattice models at the low-temperature limit. At finite temperature, a domain-size argument based on sign bounds also explains the connection between sign behavior and finite-temperature phase transition. Sign bounds, as a well-defined observable, may have the ability to ease or even make use of the sign problem.
The infamous sign problem leads to an exponential complexity in Monte Carlo simulations of generic many-body quantum systems.Nevertheless, many phases of matter are known to admit a sign-problem-free representative, allowing efficient simulations on classical computers.Motivated by long-standing open problems in many-body physics, as well as fundamental questions in quantum complexity, the possibility of intrinsic sign problems, where a phase of matter admits no sign-problem-free representative, was recently raised but remains largely unexplored.Here we establish the existence of an intrinsic sign problem in a broad class of gapped, chiral, topological phases of matter.Within this class, we exclude the possibility of stoquastic Hamiltonians for bosons (or "qudits") and of sign-problem-free determinantal Monte Carlo algorithms for fermions.The intrinsically sign-problematic class of phases we identify is defined in terms of topological invariants with clear observable signatures: the chiral central charge and the topological spins of anyons.We obtain analogous results for phases that are spontaneously chiral, and present evidence for an extension of our results that applies to both chiral and nonchiral topological matter.
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.
Quantum Monte Carlo (QMC) simulations involving fermions have a notorious sign problem. Some well-known exceptions to the auxiliary field QMC algorithm rely on the factorizibility of the fermion determinant. Recently, a fermionic QMC algorithm [C. Wu, J. Hu, and S. Zhang, Phys. Rev. Lett. 91, 186402 (2003)] has been found in which the fermion determinant may not necessarily be factorizable, but can instead be expressed as a product of complex conjugate pairs of eigenvalues, thus eliminating the sign problem for a much wider class of models. In this paper, we present the general conditions for the applicability of this algorithm and point out that it is deeply related to the time-reversal symmetry of the fermion matrix. We apply this method to various models of strongly correlated systems at all doping levels and lattice geometries, and show that many phases can be simulated without the sign problem.