The question of the computational complexity of the homology problem is a long-standing open problem in computational topology. Here, the authors show that the decision version of the problem is QMA1-hard and the exact counting version of the problem is #BPQ-hard, and discuss implications for topological data analysis.
- Marcos Crichigno
- Tamara Kohler
