Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations
作者： Matthias Troyer , Uwe-Jens Wiese
DOI: 10.1103/PHYSREVLETT.94.170201
关键词: NP 、 Time complexity 、 Numerical sign problem 、 Computational complexity theory 、 Computer science 、 Statistical physics 、 Diffusion Monte Carlo 、 Sign (mathematics) 、 Quantum Monte Carlo 、 Monte Carlo method
摘要: Quantum Monte Carlo simulations, while being efficient for bosons, suffer from the "negative sign problem" when applied to fermions--causing an exponential increase of computing time with number particles. A polynomial solution problem is highly desired since it would provide unbiased and numerically exact method simulate correlated quantum systems. Here we show that such a almost certainly unattainable by proving nondeterministic (NP) hard, implying generic also solve all problems in complexity class NP time.
arxiv.org
harvard.edu
unirioja.es
arxiv-vanity.com参考文章(12)
Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, Edward Teller, Equation of State Calculations by Fast Computing Machines The Journal of Chemical Physics. ,vol. 21, pp. 1087- 1092 ,(1953) , 10.1063/1.1699114
Anders W. Sandvik, Juhani Kurkijärvi, Quantum Monte Carlo simulation method for spin systems Physical Review B. ,vol. 43, pp. 5950- 5961 ,(1991) , 10.1103/PHYSREVB.43.5950
F Barahona, On the computational complexity of Ising spin glass models Journal of Physics A. ,vol. 15, pp. 3241- 3253 ,(1982) , 10.1088/0305-4470/15/10/028
Naomichi Hatano, Masuo Suzuki, Representation basis in quantum Monte Carlo calculations and the negative-sign problem Physics Letters A. ,vol. 163, pp. 246- 249 ,(1992) , 10.1016/0375-9601(92)91006-D
Tota Nakamura, Vanishing of the negative-sign problem of quantum Monte Carlo simulations in one-dimensional frustrated spin systems Physical Review B. ,vol. 57, ,(1998) , 10.1103/PHYSREVB.57.R3197
H. G. Evertz, The loop algorithm Advances in Physics. ,vol. 52, pp. 1- 66 ,(2003) , 10.1080/0001873021000049195
Shailesh Chandrasekharan, Uwe-Jens Wiese, Meron-Cluster Solution of Fermion Sign Problems Physical Review Letters. ,vol. 83, pp. 3116- 3119 ,(1999) , 10.1103/PHYSREVLETT.83.3116
D. M. Arnow, M. H. Kalos, Michael A. Lee, K. E. Schmidt, Green’s function Monte Carlo for few fermion problems The Journal of Chemical Physics. ,vol. 77, pp. 5562- 5572 ,(1982) , 10.1063/1.443762
M. H. Kalos, Francesco Pederiva, Exact Monte Carlo Method for Continuum Fermion Systems Physical Review Letters. ,vol. 85, pp. 3547- 3551 ,(2000) , 10.1103/PHYSREVLETT.85.3547
Markus Greiner, Olaf Mandel, Tilman Esslinger, Theodor W. Hänsch, Immanuel Bloch, Quantum Phase Transition From a Superfluid to a Mott Insulator in a Gas of Ultracold Atoms Nature. ,vol. 415, pp. 39- 44 ,(2002) , 10.1038/415039A