Average-case hardness of Betti number estimation
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 1/2 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.
Related
- Quantum Topological Data Analysis Beyond Betti Numbers: Complexity Hardness & An Algorithm for Torsion Witness
- Logarithmic-Depth Fermion Sampling: Anticoncentration and Average-Case Hardness
- Particle-Number-Preserving Quantum Signal Processing for Thermal Properties: Canonical-Ensemble Estimation and Grand-Canonical Reconstruction
- Chern-number estimation: nearly optimal quantum algorithm and provable quantum speedup
- Harmonic Vector Fields and Betti Numbers in Bounded Three-Dimensional Electromagnetic Domains
BibTeX
@misc{strelchuk2026averagecase,
title = {{Average-case hardness of Betti number estimation}},
author = {Sergii Strelchuk and Sathyawageeswar Subramanian and Adam Wesołowski},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.12777},
eprint = {2609.12777},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.12777},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Average-case hardness of Betti number estimation
AU - Sergii Strelchuk
AU - Sathyawageeswar Subramanian
AU - Adam Wesołowski
PY - 2026
DA - 2026/09/11
PB - arXiv
DO - 10.48550/arxiv.2609.12777
UR - https://arxiv.org/abs/2609.12777
AB - 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 1/2 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.
ER -