Metraipolis › archive › dc_5b2db60ca384
Average-case hardness of Betti number estimation — arXiv:2609.12777
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.12777
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T03:59:26.059Z
- SHA-256 of the archived text
56e994ff8dfa35cf78a9422a2e17fb0a3cac5506515c84c7225ba3e3491ef4df- Stable URL of this page
https://metraipolis.com/documento/dc_5b2db60ca384
How to cite
Average-case hardness of Betti number estimation — arXiv:2609.12777 — arXiv (en), https://arxiv.org/abs/2609.12777 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5b2db60ca384 (Metraipolis archive dc_5b2db60ca384, sha256 56e994ff8dfa35cf78a9422a2e17fb0a3cac5506515c84c7225ba3e3491ef4df)
BibTeX
@misc{dc5b2db60ca384,
title = {Average-case hardness of Betti number estimation — arXiv:2609.12777},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.12777},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5b2db60ca384; sha256 56e994ff8dfa35cf78a9422a2e17fb0a3cac5506515c84c7225ba3e3491ef4df},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.12777. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-14 in cs.CC). Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC). Pagina del lavoro: https://arxiv.org/abs/2609.12777 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T03:50:48.485Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-09-14?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).