|
The sign problem is one of the major unsolved problems in the physics of many-particle systems, impeding progress in many areas:
* [[Condensed matter physics]] — It prevents the numerical solution of systems with a high density of strongly correlated electrons, such as the [[Hubbard model]].<ref>E.{{cite Lohjournal et al|doi=10., "Sign problem in the numerical simulation of many-electron systems" [http:1103//prbPhysRevB.aps.org/abstract/PRB/v41/i13/p9301_1 Phys. Rev. B 41, 9301–9307 (1990)].9301}}</ref>
* [[Nuclear physics]] — It prevents the ''[[ab initio]]'' calculation of properties of [[nuclear matter]] and hence limits our understanding of [[atomic nucleus|nuclei]] and [[neutron star]]s.
* [[Quantum field theory]] — It prevents the use of [[lattice QCD]]<ref>{{Cite journal|author=de Forcrand, Philippe|title=Simulating QCD at finite density|journal=Pos Lat|volume=010|year=2010|arxiv=1005.0539}}</ref> to predict the phases and properties of [[quark matter]].<ref name='Philipsen'>{{cite journal |last=Philipsen |first=O. Philipsen,|year=2008 "|title=Lattice calculations at non-zero chemical potential: The QCD phase diagram", [|url=http://pos.sissa.it//archive/conferences/077/011/Confinement8_011.pdf PoS Confinement8 011|journal=Proceedings (2008)],of Plenary talk at Quark Confinement and the Hadron Spectrum 8, Mainz, Germany, Sept 2008Science}}</ref> (In [[lattice field theory]], the problem is also known as the '''complex action problem'''<!--boldface per WP:R#PLA-->.)<ref>K.{{cite N.journal Anagnostopoulos, J|doi=10. Nishimura, "A new approach to the complex-action problem and its application to a nonperturbative study of superstring theory", [https:1103//wwwPhysRevD.researchgate.net/publication/2050924_New_approach_to_the_complex-action_problem_and_its_application_to_a_nonperturbative_study_of_superstring_theory Phys. Rev. D 66(10), 2001].106008}}</ref>
==The sign problem in field theory==
where <math>V</math> is the volume of the system, <math>T</math> is the temperature, and <math>f</math> 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 <ref name='Kieu'>T.{{cite D.journal Kieu and C|doi=10. J. Griffin, "Monte Carlo simulations with indefinite and complex-valued measures", [http:1103//prePhysRevE.aps49.org/abstract/PRE/v49/i5/p3855_1 Phys. Rev. E 49, 3855–3859 (1994)]3855}}</ref>). In general one could write
:<math>\rho[\sigma] = p[\sigma] \frac{\rho[\sigma]}{p[\sigma]}</math>
where <math>p[\sigma]</math> can be any positive weighting function (for example, the weighting function of the <math>\mu=0</math> theory.)<ref>I.{{cite Barbour et al, "Results on finite density QCD", Nucl. Phys. Proc. Suppl. 60A 220–234 (1998), [https://arxiv.org/abs/hep-lat/9705042 arXiv:|eprint=hep-lat/9705042], presented at International Workshop on Lattice QCD on Parallel Computers, Tsukuba, Japan}}</ref> The badness of the sign problem is then measured by
:<math>\left\langle \frac{\rho[\sigma]}{p[\sigma]}\right\rangle_p \propto \exp(-f V/T)</math>
which again goes to zero exponentially in the large-volume limit.
==Methods for reducing the sign problem==
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.<ref>M.{{Cite Troyer,journal U.|arxiv=cond-J.mat/0408370 Wiese, "Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations", [http://prl|doi=10.aps.org1103/abstract/PRL/v94/i17/e170201 PhysPhysRevLett. Rev94. Lett. 94, 170201 (2005)], [https://arxiv.org/abs/cond-mat/0408370 arXiv:cond-mat/0408370]}}</ref> 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 <math>\mu</math> to real <math>\mu</math>, or Taylor expansion in powers of <math>\mu</math>.<ref name='Philipsen'/><ref>C.{{Cite Schmidt, "Lattice QCD at Finite Density", PoS LAT2006 021 (2006) [https://arxiv.org/abs/hep-lat/0610116 arXiv:/|eprint=hep-lat/0610116], plenary talk at 24th International Symposium on Lattice Field Theory.}}</ref>
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,<ref name='Wiese-cluster'>S.{{cite Chandrasekharanjournal and U|doi=10.-J. Wiese, "Meron-Cluster Solution of Fermion Sign Problems", [http:1103//prlPhysRevLett.aps83.org/abstract/PRL/v83/i16/p3116_13116 Phys. Rev. Lett. 83, 3116–3119 (1999)] [https://|arxiv.org/abs/cond-mat/9902128 arXiv:=cond-mat/9902128]}}</ref> but not for the Hubbard model of electrons, nor for [[Quantum chromodynamics|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.<ref>G.{{cite Aarts,journal "Can stochastic quantization evade the sign problem? The relativistic Bose gas at finite chemical potential", [http://prl|doi=10.aps.org1103/abstract/PRL/v102/i13/e131601 PhysPhysRevLett. Rev102. Lett. 102, 131601 (2009)], [https://|arxiv.org/abs/0810.2089 arXiv:=0810.2089]}}</ref>
* 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.<ref>H.{{cite J.journal M|doi=10. van Bemmel et al, "Fixed-node quantum Monte Carlo method for lattice fermions", [http:1103//prlPhysRevLett.aps72.org/abstract/PRL/v72/i15/p2442_1 Phys. Rev. Lett. 72, 2442–2445 (1994)]2442}}</ref>
* Majorana algorithms. Using Majorana fermion representation to perform Hubbard-Stratenovich transformations can help to solve the fermion sign problem of a class of fermionic many-body models.<ref>Zi-Xiang{{cite Li,journal Yi-Fan Jiang, and Hong Yao, "Solving the fermion sign problem in quantum Monte Carlo simulations by Majorana representation", [https://journals.aps.org/prb/abstract/|doi=10.1103/PhysRevB.91.241117 Phys. Rev. B 91, 241117(R) (2015)], [https://|arxiv.org/abs/=1408.2269 arXiv:1408.2269]}}</ref><ref>Zi-Xiang{{Cite Li,journal Yi-Fan Jiang, and Hong Yao, "Majorana-Time-Reversal Symmetries: A Fundamental Principle for Sign-Problem-Free Quantum Monte Carlo Simulations", [https://journals.aps.org/prl/abstract/|doi=10.1103/PhysRevLett.117.267002 Phys. Rev. Lett. 117, 267002 (2016)], [https://|arxiv.org/abs/1601.05780 arXiv:=1601.05780]}}</ref>
==See also==
| 