Betti number estimation likely remains hard for classical and quantum algorithms
Average-case hardness of Betti number estimation
Computational Complexity
Summary
Estimating Betti numbers helps understand the shape and connectivity of complex structures, but it’s generally hard to do efficiently. The authors show that even on average, this task is as tough as finding a hidden large group in random graphs, a known difficult problem. They argue this hardness applies not only to classical computer programs but also to quantum computers if certain assumptions hold. This means some topological data analysis challenges probably can't be solved quickly by current or near-future algorithms.
What this means in practice
- •For topological data analysts: Understand that fast, highly accurate Betti number estimation is unlikely to be possible under common computational assumptions.
- •For quantum software developers: Gauge the limitations of quantum algorithms for topological data problems based on a new quantum planted clique conjecture.
A theory result. No direct application yet.
Authors
Sergii Strelchuk, Sathyawageeswar Subramanian, Adam Wesołowski
Abstract
We establish the average-case hardness of Betti number estimation on random clique complexes via a reduction from the planted clique problem. We further show that our reduction implies a series of hardness results for many problems in both classical and quantum Topological Data Analysis (qTDA). Under the classical planted clique conjecture, no randomized polynomial-time Betti number estimator achieves additive error below $\tfrac12$ with constant advantage. Under a new quantum planted clique conjecture that we introduce, the same conclusion holds for quantum polynomial-time algorithms. We also obtain related conditional hardness results for homology vanishing, additive approximations with larger error tolerances, preparation of simplex and harmonic states, cycle recovery, and counting eigenvalues at low energy. Our reduction clarifies the structural requirements for quantum advantage in TDA and provides a new lens to investigate the classical and quantum complexity of related problems.