Average-case hardness of Betti number estimation

AI summary

Overview

Research area: Quantum complexity theory and quantum topological data analysis (qTDA), specifically average-case hardness of Betti number estimation on random clique complexes.

Technical level: Advanced. The paper assumes familiarity with simplicial homology, the combinatorial Laplacian, and hardness conjectures used in average-case complexity (the planted clique conjecture).

Scope (one sentence): The paper proves that estimating Betti numbers of clique complexes drawn from the planted-clique distribution is hard on average for both classical and quantum polynomial-time algorithms, conditional on classical and newly introduced quantum planted-clique conjectures, and extends this to a family of related qTDA tasks.

What This Paper Is About

Betti numbers count the independent "holes" in a shape at each dimension, and quantum algorithms have been proposed to estimate them faster than classical methods on large datasets. Prior hardness results for these problems were all worst-case, meaning they relied on adversarial inputs rather than inputs drawn from a natural distribution. This paper asks whether Betti number estimation stays hard when the input graph is random, and answers yes for the distribution induced by the planted clique problem, for classical and quantum algorithms alike.

Key Contributions

1. First conditional average-case hardness reduction for topological data analysis. The paper reduces the planted clique problem to Betti number estimation on clique complexes, and the reduction is the identity on the graph instance, so the hardness attaches directly to the same input distribution.

2. A main theorem covering both classical and quantum algorithms. Under the classical planted clique conjecture, no randomized polynomial-time algorithm estimates the relevant Betti number to additive error below 1/2 with success probability at least 1/2 + δ over the distribution D_k, for any constant δ > 0. Under a new quantum planted clique conjecture introduced in the paper, the same conclusion holds for quantum polynomial-time algorithms with a classical output estimate.

3. A new conjecture and its consequences. The quantum planted clique conjecture (qPC) is stated in the same constant-advantage form as the classical one. The authors note that an exponential quantum speedup for Betti number estimation under D_k would falsify qPC and would also imply the first average-case quantum speedup, assuming the classical planted clique conjecture stands.

4. A web of corollaries for other qTDA tasks. Conditional average-case hardness is derived for homology vanishing, homology localization, simplex-state preparation, harmonic-state preparation and harmonic representatives, normalized Betti number estimation, simplex search and sampling, low-lying spectral density, multiplicative and coarse additive approximation, and related problems, as depicted in Figure 1 of the paper.

Main Findings

• The reduction is geometrically simple. The clique complex of a complete graph on k vertices is a full (k−1)-simplex, which is contractible and therefore contributes no non-trivial homology. Truncating the complex at dimension d = k−2 deletes that top face and leaves its boundary, a simplicial sphere ∂σ^{k−1} ≅ S^{k−2}, which carries one non-trivial homology class.

• Null versus planted values. For k ≥ (2+ε) log₂ n, a graph from G(n, 1/2) has no (k−1)-clique with high probability, so β_{k−2}(skel_{k−2}X(G₀)) = 0. In the planted case, β_{k−2}(skel_{k−2}X(G)) ≥ 1 with high probability. Deciding whether β_{k−2} is 0 or at least 1 therefore decides planted clique, so additive error below 1/2 suffices to distinguish.

• The hardness comes from the mixture, not from either component. The paper notes that the constant algorithm "output 0" solves the problem exactly with probability 1−o(1) over G(n, 1/2), and "output 1" does so over G(n, 1/2, k). No single algorithm handles the balanced distribution D_k = 1/2 G(n, 1/2) + 1/2 G(n, 1/2, k).

• The constant-advantage form is optimal in a precise sense. Edge counting and thresholding achieves success probability 1/2 + Θ(k²/n) on each distribution, and k²/n = n^{−2α} for k = n^{1/2−α}. The paper states that ruling out all inverse-polynomial advantage is false, citing an invalidated published hardness framework as an example of this pitfall. The equivalence results of Hirahara and Shimizu are used to argue that constant-advantage hardness at every constant advantage is equivalent to the standard conjecture.

• Signal grows at lower dimensions but so does noise. For a d-skeleton of a k-clique, the planted case adds binom(k−1, d+1) non-trivial homology classes in dimension d, and the corresponding normalized quantity is 1 − (d+1)/k. The paper uses a Markov-type bound P(C > a) ≤ 2 log n / a to show the reduction carries through for any d with d / log n → ∞, while noting that the background noise of d-cliques from the planted distribution also grows as d decreases.

• The argument extends to other edge densities. The paper notes that average-case planted clique hardness holds for every constant p, so the same style of reduction applies to distributions D_k with p = const; the provided text truncates at this point in Section 4.2.

• Average-case results complement, rather than replace, worst-case ones. Exact Betti number computation is #P-hard and multiplicative approximation is NP-hard; deciding whether homology of a clique complex vanishes is NP-hard, with QMA placement for a gapped weighted-graph version; estimating low-lying spectral density of a succinctly specified sparse Hermitian matrix is DQC1-hard, and computing minimal cycle representatives is NP-hard to approximate. The new results give an average-case statement over D_k for related tasks.

• Implications for quantum advantage in TDA are two-directional. Negatively, under D_k Betti number estimation and related qTDA tasks remain hard, and at the critical dimension even the state-preparation step of the pipeline is infeasible, for reasons independent of the known density obstruction. Positively, any claimed quantum advantage must live in instance families that evade this reduction, for example complexes that are clique-dense, have inverse-polynomially gapped Laplacians, have large normalized Betti numbers, and remain classically hard for reasons other than planted clique structure.

Methodology in Plain English

The authors do not run experiments; this is a complexity-theory paper built on a reduction. They take the planted clique problem, a well-studied average-case problem in which one must distinguish an Erdős–Rényi random graph from the same graph with a hidden clique added, and show that solving Betti number estimation on the clique complex of that graph would solve planted clique.

The trick is dimension truncation. A planted clique, viewed as a clique complex, is a solid simplex with no holes, so it is topologically invisible. By keeping only the d-dimensional skeleton with d = k−2, the authors strip away the top-dimensional face of that simplex and leave its boundary, which is a sphere with one hole. Meanwhile a graph with no planted clique almost surely has no (k−1)-clique at all, so its Betti number in that dimension is zero. The two cases are therefore separated by a single unit, and any estimator accurate to better than 1/2 with a constant edge over random guessing would reveal which case produced the graph.

The authors then verify that the graph alone, accessed through local queries, is enough to specify the complex and its combinatorial Laplacian in polynomial time. A d-simplex is named by a (d+1)-subset of vertices using O(d log n) bits, testing whether a label is a simplex takes binom(d+1,2) edge look-ups, and the non-zero entries of any row of Δ_d can be enumerated among O(dn) candidates. Building the Laplacian explicitly is exponential in d, but querying it locally is efficient, so the only super-polynomial cost lies in extracting the global quantity dim ker Δ_d. They then transfer this single reduction into corollaries for many other qTDA tasks, and derive unconditional lower bounds against low-degree tests, statistical-query algorithms, and polynomial-size sum-of-squares certificates for the homology vanishing problem.

Why This Matters

Impact on research. Every prior hardness result in qTDA was worst-case, using adversarial instances. This paper supplies average-case hardness over a distribution that is standard in the average-case complexity literature, and does so with a reduction that leaves the input graph unchanged. It also adds a quantum version of the planted clique conjecture, which allows the same reduction to constrain quantum algorithms. The authors frame the result as a filter: it rules out one tempting route to quantum advantage and tells algorithm designers which structural regimes remain open. It sits between the worst-case quantum hardness results (spanning #P, NP, QMA, and DQC1 hardness) and the random-topology theory showing that clique complexes of Erdős–Rényi graphs have homology concentrated in a narrow band of dimensions.

Real-world applications cited in the paper (as domains where TDA is used):

• Biological data analysis and cancer research.
• Voting data analysis.
• Financial time series analysis.
• Medical imaging.
• Modeling the human brain with random complexes.
• Machine learning and computer vision tasks such as object matching, object detection, and Structure from Motion (SfM).

Industry relevance. Groups building or benchmarking quantum algorithms for topological data analysis now have a concrete class of instances on which quantum speedup cannot be claimed without falsifying a planted-clique-style conjecture. The paper is explicit that it does not claim D_k is a statistical model for the data typically encountered in TDA, so the practical scope of the hardness claim is bounded, and establishing comparable results for application distributions is left open.

Future Directions

• Hardness for application-relevant distributions. The authors state that it remains open to establish comparable hardness results for distributions of complexes that arise in actual TDA applications, rather than the balanced planted-clique mixture.

• Locating genuine quantum-advantage regimes. The reduction defines a boundary that proposed speedups must cross: instance families that are clique-dense, have inverse-polynomially gapped Laplacians, have large normalized Betti numbers, and are classically hard for reasons other than planted clique structure. Finding such families is the open constructive problem the paper poses.

• The quantum planted clique conjecture itself. Whether a polynomial-time quantum algorithm can solve planted clique in the conjectured hard window is left open. A quantum algorithm for Betti number estimation in this regime would falsify qPC while leaving the problem classically hard under the classical conjecture.

• Extending the reduction to other parameters and skeletons. The paper discusses how the argument behaves for other skeleton dimensions d (requiring d / log n → ∞) and for other constant edge densities p, and several of these extensions are only sketched in the provided text. The paper also closes with a discussion section listing open problems, though the truncated content does not enumerate them.

Target Audience

Quantum computing and complexity theory researchers, particularly those working on quantum algorithms for topological data analysis, average-case reductions, and fine-grained hardness. It is also relevant to classical TDA practitioners who want to understand which computational regimes are provably hard, and to algorithm designers evaluating claims of quantum advantage in data analysis. Readers without a background in simplicial homology, the combinatorial Laplacian, and hardness conjectures will find the main theorem difficult to parse, though the geometric core of the reduction (a solid simplex losing its top face to become a sphere) is accessible in plain terms.

Authors’ 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.