Complexity of supersymmetric systems and the (co)homology problem

We consider the complexity of the local Hamiltonian problem in the context of fermionic Hamiltonians with N = 2 supersymmetry and show that the problem remains QMA-complete. Our main motivation for studying this is the well-known fact that the ground state energy of a supersymmetric system is exactly zero if and only if a certain cohomology group is nontrivial. This opens the door to bringing the tools of Hamiltonian complexity to study the computational complexity of a large number of algorithmic problems that arise in homological algebra, including problems in algebraic topology, algebraic geometry, and group theory. We take the first steps in this direction by introducing the k-local Cohomology problem and showing that it is QMA1-hard and, for a large class of instances, is contained in QMA. We then consider the complexity of estimating normalized Betti numbers and show that this problem is hard for the quantum complexity class DQC1, and for a large class of instances is contained in BQP. In light of these results, we argue that it is natural to frame many of these homological problems in terms of finding ground states of supersymmetric fermionic systems. As an illustration of this perspective we discuss in some detail the model of Fendley, Schoutens, and de Boer consisting of hard-core fermions on a graph, whose ground state structure encodes l-dimensional holes in the independence complex of the graph. This offers a new perspective on existing quantum algorithms for topological data analysis and suggests new ones.

• View at Publisher

Free Full Text ( Final Version , 1mb )