关于求解非随机哈密顿量的计算复杂性

On the computational complexity of curing non-stoquastic Hamiltonians.

作者信息

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.

DOI:10.1038/s41467-019-09501-6

PMID:30952854

原文链接:https://pmc.ncbi.nlm.nih.gov/articles/PMC6450938/

Abstract

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完全问题。我们讨论了这一结果的影响。