{"id":"arxiv/2609.12777","url":"https://arxiv.org/abs/2609.12777","tags":["quant-ph","cs.CC"],"score":0,"title":"Average-case hardness of Betti number estimation","domain":"quant-ph","source":"arxiv","authors":["Sergii Strelchuk","Sathyawageeswar Subramanian","Adam Wesołowski"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-11","reactions":{}}