论文标题
集团同源性是QMA1- hard
Clique Homology is QMA1-hard
论文作者
论文摘要
我们解决了确定简单复合物的同源组的计算复杂性的长期问题，这是20年前Kaibel和Pfetsch提出的计算拓扑的基本任务。我们表明，这个决策问题是QMA1-HARD。此外，我们表明，QMA中包含满足合适承诺和某些约束的问题的一个版本。这表明看似古典的问题实际上可能是量子机械的。实际上，我们能够通过表明该问题仍然是QMA1-HARD的情况下，可以显着加强这一点。该证明结合了哈密顿复杂性和同源代数的许多技术。我们在拓扑数据分析中讨论对量子优势问题的潜在影响。
We tackle the long-standing question of the computational complexity of determining homology groups of simplicial complexes, a fundamental task in computational topology, posed by Kaibel and Pfetsch 20 years ago. We show that this decision problem is QMA1-hard. Moreover, we show that a version of the problem satisfying a suitable promise and certain constraints is contained in QMA. This suggests that the seemingly classical problem may in fact be quantum mechanical. In fact, we are able to significantly strengthen this by showing that the problem remains QMA1-hard in the case of clique complexes, a family of simplicial complexes specified by a graph which is relevant to the problem of topological data analysis. The proof combines a number of techniques from Hamiltonian complexity and homological algebra. We discuss potential implications for the problem of quantum advantage in topological data analysis.
