Content deleted Content added
mNo edit summary |
→Methods for reducing the sign problem: Quantum computers are not believed to be able to solve NP-complete problems in polynomial time. |
||
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
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>
Line 68:
* 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==
| |||