Content deleted Content added
→Overview: | Add: chapter, title. | Use this tool. Report bugs. | #UCB_Gadget |
m lc per MOS:SECTIONCAPS Tags: Visual edit Mobile edit Mobile web edit Advanced mobile edit |
||
| (One intermediate revision by one other user not shown) | |||
Line 57:
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>{{Cite journal |arxiv=cond-mat/0408370 |doi=10.1103/PhysRevLett.94.170201 |pmid=15904269 |bibcode=2005PhRvL..94q0201T |title=Computational Complexity and Fundamental Limitations to Fermionic Quantum Monte Carlo Simulations |journal=Physical Review Letters |volume=94 |issue=17 |pages=170201 |year=2005 |last1=Troyer |first1=Matthias |last2=Wiese |first2=Uwe-Jens |s2cid=11394699 }}</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 series|Taylor expansion]] in powers of <math>\mu</math>.<ref name='Philipsen'/><ref>{{Cite
=== List:
There are various proposals for solving systems with a severe sign problem:
| |||