Numerical sign problem: Difference between revisions

Revision as of 06:55, 11 April 2012

Revision as of 19:07, 5 December 2012

Line 1:

The '''numerical sign problem''' refers to the difficulty 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 [[fermion|fermions]]s, or in field theories involving a non-zero density of strongly-interacting fermions.

==The sign problem in physics==

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 [[fermion|fermions]]s, 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 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, and 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:

* 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. Loh et. al., "Sign problem in the numerical simulation of many-electron systems" [http://prb.aps.org/abstract/PRB/v41/i13/p9301_1 Phys. Rev. B 41, 9301–9307 (1990)]</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|neutron stars]]s.

* Particle physics. It prevents the use of [[Lattice QCD]] to predict the phases and properties of [[quark matter]]. <ref name='Philipsen'>O. Philipsen, "Lattice calculations at non-zero chemical potential: The QCD phase diagram", [http://pos.sissa.it//archive/conferences/077/011/Confinement8_011.pdf PoS Confinement8 011 (2008)], Plenary talk at Quark Confinement and the Hadron Spectrum 8, Mainz, Germany, Sept 2008</ref>

==The sign problem in field theory==

(References for this section: ,<ref name='Wiese-cluster'/>,<ref name='Kieu'/>).

In a field theory approach to multi-particle systems, the fermion density is controlled by the value of the fermion [[chemical potential]] <math>\mu</math>. One evaluates the [[Partition_function_Partition function (quantum_field_theoryquantum field theory)|partition function]] <math>Z</math> by summing over all classical field configurations, weighted by <math>\exp(-S)</math> where <math>S</math> is the action of the configuration. The sum over fermion fields can be performed analytically, and one is left with a sum over the [[Boson|bosonicboson]]ic fields <math>\sigma</math> (which may have been originally part of the theory, or have been produced by a [[Hubbard-Stratonovich transformation]] to make the fermion action quadratic)

:<math>Z = \int D \sigma \; \rho[\sigma]</math>

Line 44:

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, <math>p[\sigma]</math>. However, the phase <math>\exp(i\theta[\sigma])</math> 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 <math>\langle \exp(i\theta[\sigma]) \rangle_p</math>: if it is much less than 1 then the sign problem is severe.

It can be shown (e.g. <ref name='Wiese-cluster'/>) that

:<math>\langle \exp(i\theta[\sigma]) \rangle_p \propto \exp(-f V/T)</math>

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.

Line 56:

==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. Troyer, U.-J. Wiese, "Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations", [http://prl.aps.org/abstract/PRL/v94/i17/e170201 Phys. Rev. Lett. 94, 170201 (2005)], [http://arxiv.org/abs/cond-mat/0408370 arXiv:cond-mat/0408370]</ref>. If (as is generally suspected) there are no polynomial-time solutions to NP-hard 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. Schmidt, "Lattice QCD at Finite Density", PoS LAT2006 021 (2006) [http://arxiv.org/abs/hep-lat/0610116 arXiv:/hep-lat/0610116], plenary talk at 24th International Symposium on Lattice Field Theory.</ref>

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. Schmidt, "Lattice QCD at Finite Density", PoS LAT2006 021 (2006) [http://arxiv.org/abs/hep-lat/0610116 arXiv:/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 in to clusters that contribute independently. Cluster algorithms have been developed for certain theories ,<ref name='Wiese-cluster'>S. Chandrasekharan and U.-J. Wiese, "Meron-Cluster Solution of Fermion Sign Problems", [http://prl.aps.org/abstract/PRL/v83/i16/p3116_1 Phys. Rev. Lett. 83, 3116–3119 (1999)] [http://arxiv.org/abs/cond-mat/9902128 arXiv:cond-mat/9902128]</ref>, 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. <ref>G. Aarts, "Can stochastic quantization evade the sign problem? The relativistic Bose gas at finite chemical potential", [http://prl.aps.org/abstract/PRL/v102/i13/e131601 Phys. Rev. Lett. 102, 131601 (2009)], [http://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. J. M. van Bemmel et al, "Fixed-node quantum Monte Carlo method for lattice fermions", [http://prl.aps.org/abstract/PRL/v72/i15/p2442_1 Phys. Rev. Lett. 72, 2442–2445 (1994)]</ref>

==References==

<references/>

{{DEFAULTSORT:Numerical Sign Problem}}