量子科技中心_量科网

尽管其定义并不自然，但随机马氏量子马氏算法（StoqMA）在哈密顿量复杂性中扮演着核心角色，例如在Cubitt与Montanaro（SICOMP 2016）关于哈密顿量复杂性的分类定理中。此外，它位于NP的两个随机化扩展——马氏算法（MA）与阿瑟-马氏算法（AM）之间。因此，理解随机马氏量子马氏算法的确切能力（并希望将其与更自然的复杂性类归并）出于不同原因具有重要意义。在本工作中，该团队通过证明随机稀疏哈密顿量问题（StoqSH）属于随机马氏量子马氏算法，进一步推进了对这一复杂性类的理解。由于随机局部哈密顿量问题是随机马氏量子马氏算法困难的，这意味着随机稀疏哈密顿量问题是随机马氏量子马氏算法完备的。研究人员通过证明随机稀疏哈密顿量问题的可分离版本是随机马氏量子马氏算法(2)完备的来补充这一结果，其中随机马氏量子马氏算法(2)是接收两个非纠缠证明的随机马氏量子马氏算法版本。