Marvian Milad, Lidar Daniel A, Hen Itay
Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, MA, 02139, USA.
Department of Electrical and Computer Engineering, University of Southern California, Los Angeles, CA, 90089, USA.
Nat Commun. 2019 Apr 5;10(1):1571. doi: 10.1038/s41467-019-09501-6.
Quantum many-body systems whose Hamiltonians are non-stoquastic, i.e., have positive off-diagonal matrix elements in a given basis, are known to pose severe limitations on the efficiency of Quantum Monte Carlo algorithms designed to simulate them, due to the infamous sign problem. We study the computational complexity associated with 'curing' non-stoquastic Hamiltonians, i.e., transforming them into sign-problem-free ones. We prove that if such transformations are limited to single-qubit Clifford group elements or general single-qubit orthogonal matrices, finding the curing transformation is NP-complete. We discuss the implications of this result.
哈密顿量为非随机的量子多体系统，即在给定基下具有正的非对角矩阵元，由于臭名昭著的符号问题，已知会对旨在模拟它们的量子蒙特卡罗算法的效率造成严重限制。我们研究与“治愈”非随机哈密顿量相关的计算复杂性，即将它们转化为无符号问题的哈密顿量。我们证明，如果这种变换限于单量子比特克利福德群元素或一般的单量子比特正交矩阵，那么找到治愈变换是NP完全问题。我们讨论了这一结果的影响。
