Everyone is welcome to attend the QuSoft seminar with Marcos Crichigno. Title: Complexity of the Homology Problem and Quantum Advantage in TDA.
Abstract: I will report on a soon-to-appear result answering the question of the computational complexity of finding k-dimensional holes in simplicial complexes, a fundamental task in computational topology, posed nearly 20 years ago. As I’ll show, the decision problem is QMA_1-hard and contained in QMA, showing that the problem is intrinsically quantum mechanical. Underlying this is a relation between homology and the ground states of supersymmetric many-body systems. Possible implications for quantum advantage in topological data analysis (TDA) will be discussed.
Please contact Jop Briet fot the zoomlink if you want to join online.