Supersymmetry in quantum complexity: clique homology is QMA_1-hard

          @misc{ scivideos_PIRSA:23080030,
            doi = {10.48660/23080030},
            url = {https://pirsa.org/23080030},
            author = {Kohler, Tamara},
            keywords = {},
            language = {en},
            title = {Supersymmetry in quantum complexity: clique homology is QMA_1-hard},
            publisher = {Perimeter Institute for Theoretical Physics},
            year = {2023},
            month = {aug},
            note = {PIRSA:23080030 see, \url{https://scivideos.org/pirsa/23080030}}
          }
          

Abstract

In this talk I will present recent results about the computational complexity of determining homology groups of simplicial complexes, a fundamental task in computational topology. In arXiv:2209.11793 we showed that this decision problem is QMA1-hard. Moreover, we showed that a version of the problem satisfying a suitable promise is contained in QMA. This suggests that the seemingly classical problem may in fact be quantum mechanical. In fact, we were 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, and is inspired by a link with supersymmetric quantum mechanics. In this talk I will focus on how the link with supersymmetry inspired the result, and explain the intuition behind the proof.