Testing the presence of balanced and bipartite components in a sparse graph is QMA1-hard

Massimiliano Incudini, Casper Gyurik, Riccardo Molteni +1

Determining whether an abstract simplicial complex, a discrete object often approximating a manifold, contains multi-dimensional holes is a task deeply connected to quantum mechani…