Hangleiter Dominik, Roth Ingo, Nagaj Daniel, Eisert Jens
Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, Berlin, Germany.
RCQI, Institute of Physics, Slovak Academy of Sciences, Bratislava, Slovakia.
Sci Adv. 2020 Aug 14;6(33):eabb8341. doi: 10.1126/sciadv.abb8341. eCollection 2020 Aug.
Quantum Monte Carlo (QMC) methods are the gold standard for studying equilibrium properties of quantum many-body systems. However, in many interesting situations, QMC methods are faced with a sign problem, causing the severe limitation of an exponential increase in the runtime of the QMC algorithm. In this work, we develop a systematic, generally applicable, and practically feasible methodology for easing the sign problem by efficiently computable basis changes and use it to rigorously assess the sign problem. Our framework introduces measures of non-stoquasticity that-as we demonstrate analytically and numerically-at the same time provide a practically relevant and efficiently computable figure of merit for the severity of the sign problem. Complementing this pragmatic mindset, we prove that easing the sign problem in terms of those measures is generally an NP-complete task for nearest-neighbor Hamiltonians and simple basis choices by a reduction to the MAXCUT-problem.
量子蒙特卡罗（QMC）方法是研究量子多体系统平衡性质的金标准。然而，在许多有趣的情况下，QMC方法面临符号问题，导致QMC算法运行时间呈指数增长的严重限制。在这项工作中，我们开发了一种系统的、普遍适用的且切实可行的方法，通过高效可计算的基变换来缓解符号问题，并使用它来严格评估符号问题。我们的框架引入了非随机化度量，正如我们通过解析和数值证明的那样，这些度量同时为符号问题的严重程度提供了一个实际相关且高效可计算的品质因数。作为这种务实思维方式的补充，我们证明，对于最近邻哈密顿量和简单的基选择，根据这些度量来缓解符号问题通常是一个NP完全问题，这是通过将其归约为最大割问题来证明的。
