Numerical sign problem

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In applied mathematics, the numerical sign problem is the problem of numerically evaluating the integral of a highly oscillatory function of a large number of variables. Numerical methods fail because of the near-cancellation of the positive and negative contributions to the integral. Each has to be integrated to very high precision in order for their difference to be obtained with useful accuracy.

The sign problem is one of the major unsolved problems in the physics of many-particle systems. It often arises in calculations of the properties of a quantum mechanical system with large number of strongly interacting fermions, or in field theories involving a non-zero density of strongly interacting fermions.


In physics the sign problem is typically (but not exclusively) encountered in calculations of the properties of a quantum mechanical system with large number of strongly interacting fermions, or in field theories involving a non-zero density of strongly interacting fermions. Because the particles are strongly interacting, perturbation theory is inapplicable, and one is forced to use brute-force numerical methods. Because the particles are fermions, their wavefunction changes sign when any two fermions are interchanged (due to the anti-symmetry of the wave function, see Pauli principle). So unless there are cancellations arising from some symmetry of the system, the quantum-mechanical sum over all multi-particle states involves an integral over a function that is highly oscillatory, hence hard to evaluate numerically, particularly in high dimension. Since the dimension of the integral is given by the number of particles, the sign problem becomes severe in the thermodynamic limit. The field-theoretic manifestation of the sign problem is discussed below.

The sign problem is one of the major unsolved problems in the physics of many-particle systems, impeding progress in many areas:

The sign problem in field theory[edit]

[a]In a field theory approach to multi-particle systems, the fermion density is controlled by the value of the fermion chemical potential . One evaluates the partition function by summing over all classical field configurations, weighted by where is the action of the configuration. The sum over fermion fields can be performed analytically, and one is left with a sum over the bosonic fields (which may have been originally part of the theory, or have been produced by a Hubbard–Stratonovich transformation to make the fermion action quadratic)

where represents the measure for the sum over all configurations of the bosonic fields, weighted by

where is now the action of the bosonic fields, and is a matrix that encodes how the fermions were coupled to the bosons. The expectation value of an observable is therefore an average over all configurations weighted by

If is positive, then it can be interpreted as a probability measure, and can be calculated by performing the sum over field configurations numerically, using standard techniques such as Monte Carlo importance sampling.

The sign problem arises when is non-positive. This typically occurs in theories of fermions when the fermion chemical potential is nonzero, i.e. when there is a nonzero background density of fermions. If there is no particle-antiparticle symmetry, and , and hence the weight , is in general a complex number, so Monte Carlo importance sampling cannot be used to evaluate the integral.

Reweighting procedure[edit]

A field theory with a non-positive weight can be transformed to one with a positive weight, by incorporating the non-positive part (sign or complex phase) of the weight into the observable. For example, one could decompose the weighting function into its modulus and phase,

where is real and positive, so

Note that the desired expectation value is now a ratio where the numerator and denominator are expectation values that both use a positive weighting function, . However, the phase is a highly oscillatory function in the configuration space, so if one uses Monte Carlo methods to evaluate the numerator and denominator, each of them will evaluate to a very small number, whose exact value is swamped by the noise inherent in the Monte Carlo sampling process. The "badness" of the sign problem is measured by the smallness of the denominator : if it is much less than 1 then the sign problem is severe. It can be shown (e.g.[5]) that

where is the volume of the system, is the temperature, and is an energy density. The number of Monte Carlo sampling points needed to obtain an accurate result therefore rises exponentially as the volume of the system becomes large, and as the temperature goes to zero.

The decomposition of the weighting function into modulus and phase is just one example (although it has been advocated as the optimal choice since it minimizes the variance of the denominator [6]). In general one could write

where can be any positive weighting function (for example, the weighting function of the theory.)[7] The badness of the sign problem is then measured by

which again goes to zero exponentially in the large-volume limit.

Methods for reducing the sign problem[edit]

The sign problem is NP-hard, implying that a full and generic solution of the sign problem would also solve all problems in the complexity class NP in polynomial time.[8] If (as is generally suspected) there are no polynomial-time solutions to NP problems (see P versus NP problem), then there is no generic solution to the sign problem. This leaves open the possibility that there may be solutions that work in specific cases, where the oscillations of the integrand have a structure that can be exploited to reduce the numerical errors.

In systems with a moderate sign problem, such as field theories at a sufficiently high temperature or in a sufficiently small volume, the sign problem is not too severe and useful results can be obtained by various methods, such as more carefully tuned reweighting, analytic continuation from imaginary to real , or Taylor expansion in powers of .[3][9]

There are various proposals for solving systems with a severe sign problem:

  • Meron-cluster algorithms. These achieve an exponential speed-up by decomposing the fermion world lines into clusters that contribute independently. Cluster algorithms have been developed for certain theories,[5] but not for the Hubbard model of electrons, nor for QCD, the theory of quarks.
  • Stochastic quantization. The sum over configurations is obtained as the equilibrium distribution of states explored by a complex Langevin equation. So far, the algorithm has been found to evade the sign problem in test models that have a sign problem but do not involve fermions.[10]
  • Fixed-node method. One fixes the location of nodes (zeros) of the multiparticle wavefunction, and uses Monte Carlo methods to obtain an estimate of the energy of the ground state, subject to that constraint.[11]
  • Majorana algorithms. Using Majorana fermion representation to perform Hubbard-Stratonovich transformations can help to solve the fermion sign problem of a class of fermionic many-body models.[12][13]
  • Diagrammatic Monte Carlo - based on stochastically and strategically sampling Feynman diagrams[14]

See also[edit]


  1. ^ Sources for this section include Chandrasekharan & Wiese (1999)[5] and Kieu & Griffin (1994),[6] in addition to those cited.


  1. ^ Loh, E. Y.; Gubernatis, J. E.; Scalettar, R. T.; White, S. R.; Scalapino, D. J.; Sugar, R. L. (1990). "Sign problem in the numerical simulation of many-electron systems". Physical Review B. 41 (13): 9301–9307. Bibcode:1990PhRvB..41.9301L. doi:10.1103/PhysRevB.41.9301. PMID 9993272.
  2. ^ de Forcrand, Philippe (2010). "Simulating QCD at finite density". Pos Lat. 010: 010. arXiv:1005.0539. Bibcode:2010arXiv1005.0539D.
  3. ^ a b Philipsen, O. (2008). "Lattice calculations at non-zero chemical potential: The QCD phase diagram". Proceedings of Science. 77: 011. doi:10.22323/1.077.0011.
  4. ^ Anagnostopoulos, K. N.; Nishimura, J. (2002). "New approach to the complex-action problem and its application to a nonperturbative study of superstring theory". Physical Review D. 66 (10): 106008. arXiv:hep-th/0108041. Bibcode:2002PhRvD..66j6008A. doi:10.1103/PhysRevD.66.106008. S2CID 119384615.
  5. ^ a b c Chandrasekharan, Shailesh; Wiese, Uwe-Jens (1999). "Meron-Cluster Solution of Fermion Sign Problems". Physical Review Letters. 83 (16): 3116–3119. arXiv:cond-mat/9902128. Bibcode:1999PhRvL..83.3116C. doi:10.1103/PhysRevLett.83.3116. S2CID 119061060.
  6. ^ a b Kieu, T. D.; Griffin, C. J. (1994). "Monte Carlo simulations with indefinite and complex-valued measures". Physical Review E. 49 (5): 3855–3859. arXiv:hep-lat/9311072. Bibcode:1994PhRvE..49.3855K. doi:10.1103/PhysRevE.49.3855. PMID 9961673. S2CID 46652412.
  7. ^ Barbour, I. M.; Morrison, S. E.; Klepfish, E. G.; Kogut, J. B.; Lombardo, M.-P. (1998). "Results on Finite Density QCD". Nuclear Physics B - Proceedings Supplements. 60 (1998): 220–233. arXiv:hep-lat/9705042. Bibcode:1998NuPhS..60..220B. doi:10.1016/S0920-5632(97)00484-2. S2CID 16172956.
  8. ^ Troyer, Matthias; Wiese, Uwe-Jens (2005). "Computational Complexity and Fundamental Limitations to Fermionic Quantum Monte Carlo Simulations". Physical Review Letters. 94 (17): 170201. arXiv:cond-mat/0408370. Bibcode:2005PhRvL..94q0201T. doi:10.1103/PhysRevLett.94.170201. PMID 15904269. S2CID 11394699.
  9. ^ Schmidt, Christian (2006). "Lattice QCD at Finite Density". Pos Lat. 021: 21.1. arXiv:hep-lat/0610116. Bibcode:2006slft.confE..21S.
  10. ^ Aarts, Gert (2009). "Can Stochastic Quantization Evade the Sign Problem? The Relativistic Bose Gas at Finite Chemical Potential". Physical Review Letters. 102 (13): 131601. arXiv:0810.2089. Bibcode:2009PhRvL.102m1601A. doi:10.1103/PhysRevLett.102.131601. PMID 19392346. S2CID 12719451.
  11. ^ Van Bemmel, H. J. M.; Ten Haaf, D. F. B.; Van Saarloos, W.; Van Leeuwen, J. M. J.; An, G. (1994). "Fixed-Node Quantum Monte Carlo Method for Lattice Fermions" (PDF). Physical Review Letters. 72 (15): 2442–2445. Bibcode:1994PhRvL..72.2442V. doi:10.1103/PhysRevLett.72.2442. hdl:1887/5478. PMID 10055881.
  12. ^ Li, Zi-Xiang; Jiang, Yi-Fan; Yao, Hong (2015). "Solving the fermion sign problem in quantum Monte Carlo simulations by Majorana representation". Physical Review B. 91 (24): 241117. arXiv:1408.2269. Bibcode:2015PhRvB..91x1117L. doi:10.1103/PhysRevB.91.241117. S2CID 86865851.
  13. ^ Li, Zi-Xiang; Jiang, Yi-Fan; Yao, Hong (2016). "Majorana-Time-Reversal Symmetries: A Fundamental Principle for Sign-Problem-Free Quantum Monte Carlo Simulations". Physical Review Letters. 117 (26): 267002. arXiv:1601.05780. Bibcode:2016PhRvL.117z7002L. doi:10.1103/PhysRevLett.117.267002. PMID 28059531. S2CID 24661656.
  14. ^ Houcke, Kris Van; Kozik, Evgeny; Prokof'ev, Nikolay V.; Svistunov, Boris Vladimirovich (2010-01-01). "Diagrammatic Monte Carlo" (PDF). Physics Procedia. 6: 95–105. arXiv:0802.2923. doi:10.1016/j.phpro.2010.09.034. hdl:1854/LU-3234513. ISSN 1875-3892. S2CID 16490610.