PaperlayerView exact revision on arXiv

Source-linked AI summary

Average-case hardness of Betti number estimation

Sergii Strelchuk, Sathyawageeswar Subramanian, Adam Wesołowski

arXiv:2609.12777v1quant-phcs.CC

TL;DR

Betti-number estimation has established worst-case hardness, but its complexity on random inputs was unresolved. The paper reduces planted clique to estimation on random clique complexes and derives conditional hardness results for classical and quantum TDA. Under the relevant conjectures, the reduction also bounds where quantum advantage can be sought, while leaving application-derived distributions open.

  • Problem

    Worst-case complexity results do not determine whether Betti-number estimation is hard on random inputs, whose homology may be concentrated in a narrow dimension band.

    Source: §1 · p. 3

  • Method

    The paper reduces planted clique to Betti-number estimation on the balanced planted-clique distribution, leaving the graph instance unchanged.

    Source: §1 · p. 4

  • Results

    Under the classical and quantum planted-clique conjectures, no polynomial-time algorithm achieves success probability 1/2 + δ for any constant δ > 0 on the stated estimation task.

    Source: §1 · p. 5, §2.1 · p. 7

  • Takeaways & Limitations

    The reduction filters proposed quantum-advantage regimes toward instance families that evade it, including examples with clique density, inverse-polynomial Laplacian gaps, and large normalized Betti numbers.

    Source: §1 · p. 5

    The planted-clique distribution is not claimed to model typical TDA data, and comparable hardness results for application-derived distributions remain open.

    Source: §1 · p. 5

Abstract

from arXiv · show

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.

1 Introduction

The introduction asks whether Betti-number estimation is hard on natural random inputs, since prior complexity results concerned worst-case instances. It motivates a planted-clique reduction and describes consequences for classical and quantum TDA, while noting that application-derived distributions remain an open setting.

1 Introduction

  • Prior qTDA work gives efficiency guarantees under density, spectral-gap, and normalized-Betti-number promises, while related classical algorithms use closely related density and gap assumptions.Generic complexes may have normalized Betti numbers too small for informative estimates precisely where state preparation is easiest.Source: §1 · p. 3
  • Worst-case hardness results do not settle average-case Betti-number estimation, and the complexity of the task under a natural input distribution had remained open.Random clique complexes can have homology concentrated in a narrow band of dimensions, so worst-case instances may be rare among random inputs.Source: §1 · p. 4
  • The planted-clique conjecture supplies an average-case hardness primitive, with known algorithms above k = Ω(√n) and no efficient algorithm known in a stated smaller range.The introduction notes that the conjecture supports constant-advantage hardness statements, but an edge-counting test prevents ruling out all inverse-polynomial advantage.Source: §1 · p. 4
  • The paper uses the balanced planted-clique distribution D_k, whose reduction leaves the graph unchanged, but does not claim that D_k models typical TDA data.Comparable hardness results for distributions arising in applications remain open.Source: §1 · pp. 4–5
  • The reduction's implications frame quantum-advantage search around instance families that evade it, including examples with clique density, inverse-polynomial Laplacian gaps, and large normalized Betti numbers.The introduction also states that the reduction gives average-case hardness results for related TDA tasks.Source: §1 · pp. 4–5

1.1 Organisation

  • The paper proceeds from the main theorem and reduction to algorithmic consequences, quantum-advantage implications, related TDA corollaries, and open problems.It also introduces notation, planted-clique definitions, and the local-access model before presenting the reduction.Source: §1.1 · p. 6

2 Contributions

The paper reduces planted-clique detection to Betti number estimation, establishing conditional average-case hardness for classical and quantum TDA. Its reduction is identical in both settings, while the quantum result relies on a new conjecture.

2 Contributions

  • The paper presents the first conditional average-case hardness reduction for TDA, connecting planted-clique hardness to computational algebraic topology.It also proposes a framework for investigating algebraic-topology questions with graph-theoretic tools.Source: §2 · p. 6
  • Under Assumptions 1 and 2, no classical or quantum polynomial-time estimator achieves additive error below 1/2 with success probability at least 1/2+δ over D_k.The theorem applies when (2+ε) log n < k < n^(1/2−ε) and d=k−2.Source: §2 · p. 6

2.1 Technical overview

  • Truncating at dimension k−2 turns the planted clique’s full simplex into a boundary sphere, yielding β_(k−2)=0 in the null case and at least 1 in the planted case.The reduction is the identity on the graph input, so the Betti problem has the same planted-clique input distribution.Source: §2.1 · p. 7

2.2 Classical and quantum results

  • The same reduction applies classically and quantumly; the quantum hardness is conditional on the introduced quantum planted-clique conjecture.A quantum polynomial-time Betti estimator in the hard regime would falsify that conjecture, while the corresponding problems could remain classically hard.Source: §2.2 · p. 7

3 Background

The background defines clique complexes, homology, and the planted-clique detection problem, then specifies how Betti estimation can use a graph’s local oracle access. The computational challenge is extracting a global spectral quantity from that description.

3.1 Notation

  • A clique complex includes vertex sets whose vertices are pairwise adjacent; its Betti number counts independent cycles that are not boundaries of higher-dimensional chains.The paper works with real coefficients and describes the d-skeleton Laplacian used for spectral characterization.Source: §3.1 · pp. 7–8
  • The combinatorial Hodge theorem identifies harmonic chains with homology classes, supporting Laplacian-based Betti algorithms.On the d-skeleton, there are no (d+1)-simplices, so the filling term in the Laplacian vanishes.Source: §3.1 · p. 8

3.2 Random graphs and the planted-clique problem

  • Planted-clique detection distinguishes G(n, 1/2) from a graph with a uniformly chosen k-clique added; the intermediate regime between logarithmic and square-root scales is believed intractable.The largest clique in the null model is about 2 log2 n with high probability; for k ≳ √n, spectral algorithms can detect the plant.Source: §3.2 · p. 9

3.3 Input and access model

  • A graph provides efficient local access to the implicit complex and Laplacian, but the target is the global quantity dim ker Δ_d.The complex and Laplacian can be exponentially large to construct explicitly, while local Laplacian queries can be answered in polynomial time.Source: §3.3 · p. 9

4 Reduction from PC to Betti number estimation

The reduction encodes planted-clique detection as a 0-versus-at-least-1 Betti-number gap in a truncated clique complex, yielding conditional average-case hardness for classical and quantum estimators. The argument also extends to other skeleton dimensions and constant edge probabilities, while edge counting limits the hardness statement to constant advantage.

4 Reduction from PC to Betti number estimation

  • The null complex has β_(k−2) = 0 w.h.p., while truncating the planted k-clique produces a boundary sphere with β_(k−2) ≥ 1 w.h.p., enabling planted-clique detection.The reduction uses the d-skeleton at d = k − 2; the planted value may exceed 1.Source: §4 · p. 10
  • For (2 + ϵ) log n < k < n^(1/2−ϵ) and d = k − 2, no polynomial-time classical or quantum estimator achieves additive error below 1/2 with success probability 1/2 + δ on Dk, under the respective planted-clique assumptions.The quantum result concerns algorithms with a classical output estimate.Source: §4 · p. 11
  • The theorem's constant-advantage threshold is optimal in this formulation: edge counting achieves Θ(k²/n) advantage, so ruling out all inverse-polynomial advantage is impossible.For k = n^(1/2−α), the edge-counting advantage is k²/n = n^(−2α).Source: §4 · p. 11

4.1 Reduction for different values of d

  • For other skeleton dimensions d with d log n → ∞, the reduction still applies and the planted Betti-number signal strengthens as d decreases, although non-planted clique noise also increases.The simpler choice d = k − 2 suffices for the complexity result.Source: §4.1 · p. 12

4.2 Reduction for arbitrary constant p

  • For every constant edge probability p, planted-clique hardness transfers to Betti-number estimation on the corresponding mixture Dk.Source: §4.2 · p. 12

5 Algorithmic implications

The paper frames quantum advantage as requiring classical hardness alongside three efficiency promises, all at growing dimension. Its results exclude planted-clique mixtures as a source of such advantage and identify what remains missing from a possible structural template.

5 Algorithmic implications

  • A quantum advantage requires a growing-dimension family that is classically hard while satisfying all three LGZ efficiency promises: polynomial-time state preparation, an adequate spectral gap, and a non-exponentially-small normalized Betti number.At bounded constant dimension, the classical estimator already matches the quantum one.Source: §5 · p. 12
  • The planted-clique mixture Dk is ruled out as an advantage regime, while weighted-graph instances provide a template for gap, Betti-number, and classical hardness but lack a natural distribution satisfying state-preparation efficiency.The paper leaves open whether another natural family can exhibit quantum advantage.Source: §5 · p. 13

6 Identifying regions with average-case quantum advantage

The paper maps where average-case hardness rules out quantum advantage and where it does not reach. In Kahle’s non-trivial homology window, Betti numbers are near-maximal, the planted-clique reduction fails, and a growing-dimension regime remains a plausible but unresolved candidate.

6.1 Non-trivial homology in random clique-complexes

  • Inside Kahle’s non-trivial homology window, the normalized Betti number is 1 − o(1), so almost every d-simplex supports a non-trivial homology class w.h.p.Outside the density window, βd vanishes; within it, homology is close to maximal.Source: §6.1 · pp. 13–14

6.2 No reduction in the non-trivial homology window

  • Kahle’s window lies below the planted-clique hard range, and its null-case Betti number is already near-maximal, so the reduction’s empty-null 0-versus-1 signal is unavailable.Source: §6.2 · p. 14

6 Identifying regions with average-case quantum advantage

  • The analysis partitions the (d, α) landscape into a PC-hard region, bounded dimensions, and a growing-dimension homology window as a candidate region for average-case quantum advantage.Source: §6.3 · p. 14

6.3 Region for average-case quantum-advantage

  • The PC-hard region and bounded dimension rule out quantum advantage, but in the growing-dimension window the reduction does not apply and advantage remains open despite inefficient state preparation with known techniques.In the PC-hard region, the invariant carries no information on typical inputs; in bounded dimension, classical estimation is efficient.Source: §6.3 · p. 14

7 Implications

The section derives classical and quantum TDA hardness corollaries from planted-clique assumptions, extending from simplex and Betti-number tasks to homology, cycle, state-preparation, and spectral problems. It also identifies limits of the reduction and conditions relevant to seeking quantum advantage.

7 Implications

  • The corollaries use quantum planted-clique assumptions, while the classical versions follow by replacing them with established classical hardness assumptions.The section distinguishes worst-case clique-complex results from average-case results on d-skeleta under Dk in the local-access model.Source: §7 · p. 15

7.1 Simple corollaries about simplicial complexes

  • At the critical dimension, simplex search and uniform simplex-state preparation are hard under the strong search planted-clique conjecture.Finding a (k−2)-simplex yields a (k−1)-clique that recovers k−1 planted vertices; the uniform simplex state is the LGZ pipeline's input state.Source: §7.1 · p. 15
  • The simplex corollary is not a Betti-number result and applies only at d = k −2; for d ≪ k, sampling a d-simplex is trivial in both cases.At d = k −2, the conditional hardness of simplex-existence testing is distinct from the density obstruction, which makes preparation slow because simplices are rare.Source: §7.1 · p. 15

7.2 Corollaries in Topological Data Analysis

  • Finite multiplicative approximations and additive error below 1/2 are hard; for d = Θ(log n) and k = n^(1/2−ε), the additive tolerance can reach exp(c log^2 n).The larger tolerance is stated for the indicated parameter regime and a constant c > 0.Source: §7.2 · p. 16
  • For (2 + ε) log2 n ≤ d + 1 = o(k), normalized Betti-number estimation βd / fd is hard at additive error below 1/2.The corollary is under the planted-clique conjecture and rules out constant-advantage efficient estimation on the stated graph distributions.Source: §7.2 · p. 16
  • Under the stated assumptions, homology-vanishing decisions and recovery of nonzero (k−2)-cycles or nontrivial-class representatives are average-case hard.The cycle-recovery result uses the strong search version of planted-clique hardness; the homology-vanishing corollary applies to Dk, not to the broader clique-complex family.Source: §7.2 · pp. 17–18
  • The strong search conjecture also makes harmonic-state preparation hard, while Assumption 2 makes low-energy eigenvalue counting hard at additive error below 1/2.For the spectral result, the threshold λ is fixed in (0, k) in the hard planted-clique regime.Source: §7.2 · p. 17

7.3 Other implications

  • The reduction transfers planted-clique lower bounds to restricted models, while the identified region for possible quantum advantage still has a state-preparation obstacle.In that region, instance-specific efficient state preparation could permit instance- or family-specific advantage; the section also notes the lower bounds do not cover the region.Source: §7.3.1 · p. 18, §7.3.2 · p. 18

8 Open problems

The open problems seek to extend the average-case framework, connect it to biological applications, and clarify what would constitute quantum advantage. They also point to unresolved opportunities in cryptography and succinct complexity.

8 Open problems

  • A candidate for quantum advantage should combine efficient simplex sampling and state preparation, efficient boundary or Laplacian access, a suitable spectral gap, and informative inverse-polynomial precision.The most interesting spectral regime is an inverse-polynomial normalized gap that tends to zero; at constant gap, classical polynomial-filter algorithms may also be polynomial-time.Source: §8 · pp. 18–19

8.1 Extensions of the average-case hardness framework

  • The average-case framework remains to be tested under other natural distributions and access models, with uniform lower bounds on normalized Hodge gaps identified as valuable.The text also calls for separating invariant concentration from the computational difficulty of estimating it at a specified precision.Source: §8.1 · pp. 19–20
  • Open directions include converse reductions and distributional completeness, extensions to persistent and multiparameter homology, and hardness for directed, path, and higher-order complexes.For directed flag complexes, orienting an undirected graph by a total vertex order gives an isomorphic clique complex; comparable constructions for grounded path homology remain open.Source: §8.1 · p. 19
  • Further framework questions concern average-case spectral and sampling parameters and the complexity of rank, nullity, and low-energy estimation for succinct boundary matrices.The succinctly represented problem differs from rank computation on an explicitly listed sparse matrix, which is polynomial-time solvable.Source: §8.1 · pp. 19–20

8.2 Biological applications

  • Biological qTDA directions include online and zigzag analysis of evolving tissues, directed biological networks, and higher-order models of genuine joint interactions.For evolving data, one question is whether simplex or harmonic states can serve as warm starts across time; higher-order models should be assessed against graph-based prediction and sampling costs.Source: §8.2 · p. 20

8.3 Quantum advantage

  • Quantum-versus-classical comparisons should use common access assumptions and include classical sparse reduction, path-integral, Krylov, Chebyshev, and stochastic Lanczos methods.The text also asks whether reusing states, block encodings, or spectral estimates across correlated queries can yield amortized advantage.Source: §8.3 · p. 20

8.4 Cryptography

  • The paper leaves open whether average-case Betti-number hardness can support proof-of-work verification or standard cryptographic primitives such as one-way functions.The proposed cryptographic basis could also involve homology vanishing, homology localization, or related succinct linear-algebra problems.Source: §8.4 · pp. 20–21
Loading 2609.12777v1…