betaFeedback

WorksPhysics and Astronomy

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 12\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.

Identifying regions with average-case quantum advantage

Non-trivial homology in random clique-complexes

No reduction in the non-trivial homology window

Region for average-case quantum-advantage

Implications

Simple corollaries about simplicial complexes

Corollaries in Topological Data Analysis

Other implications

Restricted models (unconditional).

Achieving quantum advantage

Open problems

Extensions of the average-case hardness framework

Biological applications

Quantum advantage

Cryptography

Introduction

Topological Data Analysis is a framework for studying the shape of complex data in high dimensions. One of its basic invariants is the Betti number βd\beta_d, which is the dimension of the dd-th homology group and counts independent homology classes in dimension dd. TDA has been applied to biological data [49], voting data [35], and financial time series [15]. It has also been used in cancer research [39, 40] and medical imaging [43]. For large complexes, constructing and reducing the relevant boundary matrices can be computationally expensive. This has motivated a long line of work on quantum algorithms for Betti number estimation. See Ref. [22] for an early review. Complexity results have also identified limitations of quantum algorithms for related topological problems [17, 44]. These worst-case results do not, however, determine the complexity of instances that may be drawn from a specified distribution. In this work, we study the classical and quantum average-case hardness of Betti number estimation under the distribution associated with the planted clique problem.

Quantum algorithms for computing Betti numbers. Lloyd, Garnerone, and Zanardi (LGZ) [34] were the first to propose a quantum algorithm that estimates the normalized Betti number βd/fd\beta_d/f_d to inverse-polynomial additive error. A decade of follow-up work has both built this sketch into a genuine pipeline and, simultaneously optimised the algorithms. On the constructive side, these works have given rigorous analyses of the spectral gap and density dependencies [22, 21], extension to persistent Betti numbers [23], qubit- and depth-efficient implementations [50, 36, 4], and end-to-end resource estimates for candidate advantage regimes [10]. On the limiting side, the efficiency guarantee has been understood to rest on three promises:

  1. the complex must be clique-dense (else the simplex state cannot be prepared efficiently);

  1. the spectral gap of Δd\Delta_d must be at least inverse polynomial;

  1. and the normalized Betti number must not be exponentially small.

Path-integral and Krylov-type classical algorithms estimate normalized Betti numbers under closely related density and gap assumptions [1, 10], eroding the speedup exactly where the quantum algorithm is efficient. Furthermore, Schmidhuber and Lloyd observed that generic complexes have normalized Betti numbers so small that the estimate carries no information precisely where state preparation is easiest [44].

The worst-case complexity landscape. In parallel, a sequence of hardness results has outlined the intrinsic difficulty of problems in qTDA. Computing Betti numbers of a clique complex exactly is #P-hard, and approximating them, even to within a multiplicative factor, is NP-hard [44]. Computing the Euler characteristic (an alternating sum of the number of faces (elements) of dimensions ii in the complex) is already #P-hard for general abstract complexes [42]. Deciding whether the homology of a clique complex vanishes is NP-hard [3]. Cade and Crichigno established this for the closely related cohomology problem of supersymmetric systems [11], Crichigno and Kohler for clique complexes [13], and King and Kohler for the gapped (promise) version on weighted graphs, which they also place inside QMA [30]. For the estimation task the sharpest calibration is due to Gyurik, Cade, and Dunjko [21]: estimating the low-lying spectral density of a succinctly specified sparse Hermitian matrix is DQC1-hard, so an efficient classical simulation of the quantum estimation pipeline on all inputs would collapse the one-clean-qubit model. On the related problem of homology localization, Chen and Freedman proved that computing minimal cycle representatives of homology classes is NP-hard to approximate [12].

All of these results are worst-case: the hard instances are adversarial, and none of them addresses the complexity of Betti-number estimation on the inputs TDA is typically run on. For instance, the theory of random topology shows that clique complexes of Erdős–Rényi graphs have highly structured homology: for X(G(n,p))X(G(n,p)) for a fixed 0<p<10 < p < 1 the nontrivial homology statistically concentrates in a narrow band of dimensions and vanishes outside it [28, 29], so the measure of the set of worst-case instances may simply be extremely close to zero on random inputs. Whether any natural distribution over inputs makes Betti-number estimation hard on average for classical and quantum algorithms alike has, to our knowledge, remained open. It is this gap that we address in this paper.

Average-case hardness from planted clique. Our source of average-case hardness is the planted clique problem, introduced by Jerrum [27] and Kučera [31]: distinguish an Erdős–Rényi random graph G(n,12)G(n,\frac{1}{2}) from the same graph with a clique planted on kk random vertices that we call G(n,12,k)G(n,\frac{1}{2},k). Spectral and combinatorial algorithms succeed in polynomial time for k=Ω(n)k = \Omega(\sqrt{n}) [2, 14, 16], while for (2+ε)log⁡2n≤k≤n1/2−ε(2+\varepsilon)\log_2 n \le k \le n^{1/2-\varepsilon} no efficient algorithm is known despite three decades of effort. The conjecture that none exists is supported by unconditional lower bounds in every standard restricted model: statistical-query algorithms [19], the sum-of-squares hierarchy [7], Lovász–Schrijver relaxations [20], bounded-depth circuits [41], the Metropolis process [27], and low-degree polynomial tests [32, 47]. On this basis, the planted clique conjecture (PC) has become a standard hardness primitive for average-case reductions, underlying lower bounds for sparse PCA [9], submatrix detection [38], community detection [26], certification of restricted isometry [33], Nash-equilibrium approximation [24], and a web of further problems [7, 5, 37]. Recently, Hirahara and Shimizu proved that many formalizations of PC are essentially equivalent [25]. Their equivalences supply two ingredients we use throughout this work. First, hardness at every constant distinguishing advantage is equivalent to the standard conjecture, which lets us state our theorem for algorithms succeeding with probability 12+δ\frac{1}{2}+\delta for arbitrarily small constant δ>0\delta> 0. Second, their results calibrate exactly how far such statements can be pushed: a folklore edge-counting test distinguishes the two distributions with advantage Θ(k2/n)\Theta(k^2/n) [48, 25], so no reduction can rule out all inverse-polynomial advantage, a subtlety that has invalidated at least one published hardness framework [18] as noted by [25]. Therefore, our constant-advantage statement for (q)TDA is also optimal in this sense. In [25] the authors further identify a detection–recovery gap [25, 8]: while detection admits the Θ(k2/n)\Theta(k^2/n)-advantage edge count, recovering the clique is hard under PC conjecture even with success probability n−cn^{-c} for every constant cc, a distinction our corollaries inherit. Figure 1 depicts all implications we have identified as corollaries of our main result. In particular, state preparation for the LGZ algorithm, homology localization, vanishing homology, Betti number to large additive approximation, are all hard on average under the distribution DkD_k originating from Erdős–Rényi clique complexes.

Illustration of selected implications of the reduction from planted clique problem to Betti number estimation

Figure 1. Illustration of selected implications of the reduction from planted clique problem to Betti number estimation. The references in each box link the worst-case hardness variant corresponding to our average-case results. To the best of the authors knowledge the remaining problems do not have an established worst-case hardness.

The importance of the distribution choice. Average-case hardness is inherently defined over some fixed choice of a distribution D(x)D(x) of problem instances xx. Different choices of D(x)D(x) might lead to different average-case hardness statements, thus a choice of D(x)D(x) should be well motivated. In this work we adopt the distribution Dk=12G(n,12)+12G(n,12,k)D_k = \frac{1}{2}G(n,\frac{1}{2}) + \frac{1}{2}G(n,\frac{1}{2},k) from the planted clique problem, which naturally derives from the Erdős–Rényi distribution G(n,12)G(n,\frac{1}{2}) (see sec 3.1 for definitions). Erdős–Rényi distribution is a very common and well studied distribution of random complexes [28, 29, 45, 46] which has been shown to be relevant to modeling the human brain [46], as well as to machine learning and computer vision tasks such as object matching, object detection, and Structure from Motion (SfM) [45]. We use the balanced distribution for the planted clique problem. This choice is useful because planted clique is widely used in average-case reductions and because our reduction leaves the graph instance unchanged. We do not claim that DkD_k is a statistical model for the data usually encountered in TDA. It remains open to establish comparable hardness results for distributions arising in applications.

A new lens on quantum advantage in TDA. Our results carry implications in two directions for the prospect of quantum advantage. Negatively, they close off one tempting argument: Betti number estimation and other aforementioned qTDA tasks remain hard on natural random inputs, so under this distribution one cannot witness a quantum speedup and moreover, at the critical dimension, even the pipeline’s state-preparation step is infeasible, for reasons independent of the well-known density obstruction [21, 44, 10]. Positively, they sharpen the search: any demonstration of quantum advantage in TDA must locate instance families that evade our reduction. For example, complexes that are clique-dense with inverse-polynomially gapped Laplacians and large normalized Betti numbers and remain classically hard for reasons other than the planted clique structure. We show that under the distribution of instances coming from the planted clique problem the problem of Betti number estimation is hard for both classical and quantum algorithms. The reduction thus functions as a filter on proposed advantage regimes, and clarifies the boundary between the worst-case quantum hardness results [11, 13, 30, 21] and the average-case landscape closer to the practical data on which TDA is expected to operate.

Organisation

The remainder of the paper is organised as follows. Section 2 introduces our main theorem, the average-case hardness of Betti-number estimation on clique complexes drawn from the graph distribution of the planted clique problem. Section 3 fixes notation and recalls the definitions of planted-clique problem, clique complexes and Betti numbers, and the local access model through which the graph specifies the complex and its combinatorial Laplacian in polynomial time. Section 4 gives the reduction from planted clique to Betti-number estimation, proves Theorem 2.1, and discusses how the argument behaves for skeleta of other dimensions and random graphs with varying parameter pp. Section 5 draws out the algorithmic consequences. Section 6 outlines how our contribution helps with the search for quantum advantage in qTDA. Section 7 derives the corollaries for other tasks of quantum Topological Data Analysis, namely normalized Betti number estimation, homology vanishing, homology localization, simplex-and harmonic-state preparation and the low-lying spectral density, and compares them with worst-case state-preparation hardness. Section 8 closes with a discussion and a list of open problems.

Contributions

Our results connect the hardness of the well known problem in graph theory, namely the planted clique problem, to a family of problems in computational algebraic topology, known broadly under the name of topological data analysis. We give the first conditional average-case hardness reduction for problems in topological data analysis. Our work provides a new framework that allows one to investigate questions in algebraic topology via graph theoretical tools. Based on the established classical planted clique conjecture [25, 31, 27] we derive the classical average-case hardness results. We further introduce the quantum planted clique conjecture (see 2), based on which we derive the quantum conditional average-case hardness of Betti number estimation (and other problems) of clique complexes drawn from the planted clique distribution Dk=12G(n,12)+12G(n,12,k)D_k = \frac{1}{2}G\left(n,\frac{1}{2}\right) + \frac{1}{2}G\left(n,\frac{1}{2},k\right). A demonstration of an exponential quantum speedup for the Betti number estimation under DkD_k would not only falsify the quantum planted clique conjecture but also imply the first average-case quantum speedup (assuming the classical planted clique conjecture stands).

In section 4 we prove the following:

Theorem 2.1 (Average-case hardness of Betti number estimation). Let k=k(n)k = k(n) satisfy the inequality (2+ϵ)log⁡n<k<n1/2−ϵ(2+\epsilon)\log n < k < n^{1/2-\epsilon} and set d=k−2d = k - 2. For every constant δ>0\delta> 0, the following statements hold. Under Assumption 1, no randomized polynomial-time algorithm estimates

βd(skel⁡dX(G))\beta_d(\operatorname{skel}_d X(G))

to additive error below 12\frac{1}{2} with success probability at least 12+δ\frac{1}{2}+\delta over G∼DkG \sim D_k. Under Assumption 2, no quantum polynomial-time algorithm with a classical output estimate satisfies the same guarantee.

See section 3 for definitions of Betti and section 4 for the statement of planted-clique conjectures. In section 7 we extend the scope of the average-case hardness results to a family of problems in topological data analysis and other problems related to Betti number estimation, the extent of results is depicted in Figure 1.

Technical overview

We give a simple reduction from planted clique problem to the Betti-number estimation on clique complexes. The starting observation is that the clique complex of a complete graph on kk vertices is a k−1k-1 simplex σk−1\sigma^{k-1}, which is contractible, so planting a kk-clique contributes no non-trivial homology classes. The reduction proceeds by fixing the dimension kk in the PC window (see 2) and truncating the complex at dimension d=k−2d=k-2, the planted kk-clique a topologically invisible full simplex becomes the boundary sphere ∂σk−1≅Sk−2\partial\sigma^{k-1}\cong S^{k-2}, contributing a non-trivial homology class while the null complex has, with high probability, no (k−2)(k-2)-simplex at all. Consequently βk−2\beta_{k-2} equals 0 in the null case and is at least 1 in the planted case, and any algorithm estimating it to additive error below 12\frac{1}{2} decides planted clique. Our main theorem states that, under the classical and quantum PC conjectures, no polynomial-time classical or quantum algorithm achieves this with success probability 12+δ\frac{1}{2}+\delta for any constant δ>0\delta>0 over Dk=12G(n,12)+12G(n,12,k)D_k=\frac{1}{2}G(n,\frac{1}{2})+\frac{1}{2}G(n,\frac{1}{2},k). Notably, the input to the Betti problem is the random graph itself and the reduction is the identity on the instance so the hardness attaches to the same input distribution. We also present our result as complementing the worst-case #P-, NP-, QMA1_1-, and DQC1_1-hardness results above [11, 1, 13, 21] with an average-case statement, and complementing random-topology theory [28, 29] with a computational hardness statement.

Classical and quantum results

We highlight that the reduction presented in section 4 is the same both classically and in the quantum setting. Under the well established classical planted clique conjecture (Assumption 1) Betti number estimation and other problems mentioned in section 7 are classically average-case hard. We introduce a quantum clique conjecture (assumption 2) under which the conditional average-case hardness follows in the quantum setting. A polynomial time quantum algorithm for Betti number estimation in the hard regime would render the conjecture false and the problems in section 7 quantum-average-case easy, while remaining classical average-case hard. This remains an open problem.

Background

Notation

Unless stated otherwise, all asymptotics are taken as the number of vertices n→∞n\to\infty, and log denotes log⁡2\log_2. We write [n]={1,…,n}[n]=\{1,\ldots,n\} and ([n]j)\binom{[n]}{j} for the family of jj-element subsets of [n][n]. We use the standard Landau symbols O(⋅)O(\cdot), o(⋅)o(\cdot), Ω(⋅)\Omega(\cdot), Θ(⋅)\Theta(\cdot), and write f≲gf\lesssim g as shorthand for f=O(g)f=O(g). An event E=EnE=E_n holds with high probability (w.h.p.) if Pr⁡[En]→1\Pr[E_n]\to1 as n→∞n\to\infty. Two fixed positive constants recur throughout: ε>0\varepsilon>0 is used to delimit the window of the planted-clique conjecture, and δ>0\delta>0 denotes a distinguishing advantage. We say a randomised or quantum algorithm is efficient if it runs in time poly⁡(n)\operatorname{poly}(n).

Graphs and random models. GG denotes a simple graph on vertex set [n][n]. The Erdős–Rényi distribution G(n,12)G(n,\frac{1}{2}) includes each of the (n2)\binom{n}{2} edges independently with probability 12\frac{1}{2}; the planted distribution G(n,12,k)G(n,\frac{1}{2},k) is obtained from G0∼G(n,12)G_0\sim G(n,\frac{1}{2}) by choosing a uniformly random kk-subset S⊆[n]S\subseteq[n] and adding every edge inside SS. PClique(n,k)(n,k) is the associated detection problem (Definition 1), and cmax⁡(G)c_{\max}(G) the size of a largest clique of GG.

Simplicial and clique complexes. An (abstract) simplicial complex KK on vertex set [n][n] is a family of subsets of [n][n] such that any σ,τ\sigma,\tau satisfy: σ∈K\sigma\in K and τ⊆σ\tau\subseteq\sigma then τ∈K\tau\in K. A set σ∈K\sigma\in K of cardinality d+1d+1 is a dd-simplex, and its subsets of cardinality dd are its d−1d-1-faces or facets of σ\sigma. We write KdK_d for the set of dd-simplices of KK and fd(K)=∣Kd∣f_d(K)=|K_d| for their number.

For a graph GG on [n][n], the clique complex (or flag complex) X(G)X(G) is the simplicial complex whose dd-simplices are exactly the (d+1)(d+1)-cliques of GG; equivalently, a set of vertices is a simplex iff it is pairwise adjacent. Thus X(G)X(G) is determined by the graph alone, and we identify a dd-simplex with the (d+1)(d+1)-subset of [n][n] that spans it. The dd-skeleton skel⁡dX(G)\operatorname{skel}_d X(G) retains every face of dimension ≤d\le d and discards all faces of dimension >d>d. Writing fd(G):=fd(X(G))f_d(G) := f_d(X(G)) for the number of dd-simplices (equivalently, of (d+1)(d+1)-cliques), independence of the (n2)\binom{n}{2} edges gives (in the Erdős–Rényi model with p=1/2p=1/2)

Efd(G)=(nd+1)2−(d+12),(1)\mathbb{E}f_d(G) = \binom{n}{d+1}2^{-\binom{d+1}{2}}, \tag*{(1)}

since a (d+1)(d+1)-clique requires all (d+12)\binom{d+1}{2} of its edges to be present.

Chains, boundaries, and homology. We work over R\mathbb{R} throughout. A jj-chain is a formal real linear combination of the oriented jj-simplices of KK, and the jj-chains form a vector space Cj=Cj(K;R)C_j = C_j(K;\mathbb{R}). The boundary map ∂j:Cj→Cj−1\partial_j: C_j \to C_{j-1} sends each jj-simplex to the signed sum of the (j−1)(j-1)-simplices on its boundary; it records the oriented boundary of a chain. Its defining property is that the boundary of a boundary is empty, ∂j−1∂j=0\partial_{j-1}\partial_j = 0.

Two subgroups of CjC_j carry the topological content. The group of jj-cycles

Zj=ker⁡∂j={c∈Cj:∂jc=0}Z_j = \ker\partial_j = \{c \in C_j: \partial_jc = 0\}

consists of the closed chains, those with empty boundary. The group of jj-boundaries

Bj=im⁡∂j+1={∂j+1c:c∈Cj+1}B_j = \operatorname{im}\partial_{j+1} = \{\partial_{j+1}c: c \in C_{j+1}\}

consists of the chains that are themselves the boundary of some (j+1)(j+1)-chain, that is, the cycles already filled in by (j+1)(j+1)-simplices sitting one dimension above. Since the boundary of a boundary is empty, every boundary is a cycle, so Bj⊆ZjB_j \subseteq Z_j. Homology records the cycles that are left over: the closed jj-cycles that do not bound any higher-dimensional part of the complex. The jj-th homology and Betti number are

Hj(K)=Zj/Bj,βj(K)=dim⁡Hj(K),(2)H_j(K) = Z_j/B_j,\qquad\beta_j(K) = \dim H_j(K), \tag*{(2)}

so βj\beta_j counts the independent cycles that do not bound any higher dimensional structures. Concretely β0\beta_0 is the number of connected components, β1\beta_1 the number of independent loops, and βd\beta_d the number of independent dd-dimensional voids. Real coefficients agree with rational ones and with the integral rank, βj(K)=rank⁡ZHj(K;Z)\beta_j(K) = \operatorname{rank}_{\mathbb{Z}} H_j(K;\mathbb{Z}); over Fp\mathbb{F}_p the dimension of HjH_j can be strictly larger, by the torsion contribution.

The combinatorial Laplacian and Hodge theory. The combinatorial Laplacian in dimension dd is

Δd=∂d†∂d+∂d+1∂d+1†,(3)\Delta_d = \partial_d^{\dagger}\partial_d + \partial_{d+1}\partial_{d+1}^{\dagger}, \tag*{(3)}

a positive-semidefinite operator on CdC_d. The combinatorial Hodge theorem identifies harmonic chains with homology classes, so that for every finite complex KK,

βd(K)=dim⁡Hd(K)=dim⁡ker⁡Δd(K).(4)\beta_d(K) = \dim H_d(K) = \dim\ker\Delta_d(K). \tag*{(4)}

This spectral characterisation is what makes Betti numbers amenable to Laplacian-based (in particular quantum) algorithms. We will work almost exclusively with a top skeleton K=skel⁡dX(G)K = \operatorname{skel}_d X(G), in which there are no (d+1)(d+1)-simplices, so ∂d+1=0\partial_{d+1} = 0 and the second (“filling”) term of (3) vanishes. Then Δd=∂d†∂d\Delta_d = \partial_d^{\dagger}\partial_d and (4) collapses to the elementary identity

βd(skel⁡dX(G))=dim⁡ker⁡∂d=fd(G)−rank⁡∂d.(5)\beta_d(\operatorname{skel}_d X(G)) = \dim\ker\partial_d = f_d(G) - \operatorname{rank}\partial_d. \tag*{(5)}

Random graphs and the planted-clique problem

G(n,12)G(n,\frac{1}{2}) denotes the Erdős–Rényi graph on vertex set [n]={1,…,n}[n] = \{1,\ldots,n\} in which each of the (n2)\binom{n}{2} edges is present independently with probability 12\frac{1}{2}. The planted distribution G(n,12,k)G(n,\frac{1}{2},k) is obtained by drawing G0∼G(n,12)G_0 \sim G(n,\frac{1}{2}), choosing a uniformly random kk-subset S⊆[n]S \subseteq[n], and adding every edge within SS.

Definition 1 (Planted-clique detection). PCLIQUE⁡(n,k)\operatorname{PCLIQUE}(n,k) is the task of deciding, given a random graph GG drawn from G(n,12)G(n,\frac{1}{2}) (the null case) whether or not it has been modified by planting a kk-clique resulting in G(n,12,k)G(n,\frac{1}{2},k) (the planted case). In other words, the problem is to decide which case it is (whether the graph comes from the distribution G(n,12)G(n,\frac{1}{2}) or not).

The largest clique size of G(n,12)G(n,\frac{1}{2}) is Cmax⁡(G(n,12))=(2+o(1))log⁡2nC_{\max}(G(n,\frac{1}{2})) = (2+o(1))\log_2 n w.h.p. For k<(2−ε)log⁡2nk < (2-\varepsilon)\log_2 n the plant is information-theoretically undetectable; for k≳nk \gtrsim\sqrt{n} spectral algorithms detect it in polynomial time. The intermediate window is believed intractable.

Input and access model

This subsection makes precise the sense in which “estimating a Betti number of X(G)X(G)” is a problem whose input is the Erdős–Rényi random graph.

Definition 2 (Betti number estimation). BETTI⁡\operatorname{BETTI} takes as input a graph GG on [n][n] vertices and an integer dd, and asks for an estimate of

βd(skel⁡dX(G))\beta_d(\operatorname{skel}_d X(G))

with coefficients in R\mathbb{R}. The exact version asks for the value of the Betti number. An additive approximation with error η>0\eta> 0 outputs β^\hat{\beta} satisfying

∣β^−βd∣<η.\lvert\hat{\beta}-\beta_d\rvert< \eta.

For C≥1C \ge1, a CC-multiplicative approximation outputs β^\hat{\beta} satisfying

βdC≤β^≤Cβd.\frac{\beta_d}{C} \le\hat{\beta} \le C\beta_d.

When βd=0\beta_d = 0, this definition requires β^=0\hat{\beta}=0. We write BETTI⁡(d)\operatorname{BETTI}(d) when the dimension is fixed.

The complex skel⁡dX(G)\operatorname{skel}_d X(G) and its Laplacian Δd\Delta_d have up to fd=nΘ(d)f_d = n^{\Theta(d)} simplices. The Laplacian and the complex are specified implicitly by GG through a local oracle:

  • a dd-simplex is named by a (d+1)(d+1)-subset of [n][n], a label of O(dlog⁡n)O(d\log n) bits;

  • testing whether a label is a simplex is (d+12)\binom{d+1}{2} edge look-ups in GG;

  • the non-zero entries of any row of Δd=∂dT∂d\Delta_d = \partial_d^{\mathsf{T}}\partial_d correspond to dd-simplices sharing a (d−1)(d-1)-face with the given one, enumerable by local clique checks among O(dn)O(dn) candidates.

Thus from GG alone one can answer any local query about Δd\Delta_d in poly⁡(n)\operatorname{poly}(n) time, this is a standard and efficient access model, and one of the reasons people study clique complexes. The graph is a polynomial-size exact description of the implicit complex; constructing the Laplacian Δd\Delta_d explicitly is exponential but is not required, whereas querying it locally is efficient. Consequently the only conceivable super-polynomial cost lies in extracting the global spectral quantity dim⁡ker⁡Δd\dim\ker\Delta_d from this local description which is precisely the difficulty of the Betti number estimation.

Reduction from PC to Betti number estimation

Assumption 1 (Classical planted-clique conjecture, PC). There is a range of plant sizes

(2+ε)log⁡2n≤k≤n1/2−ε(2+\varepsilon)\log_{2} n \le k \le n^{1/2-\varepsilon}

in which no randomized polynomial-time classical algorithm distinguishes G(n,12)G(n,\frac{1}{2}) from G(n,12,k)G(n,\frac{1}{2},k) with advantage ≥δ\ge\delta, for any constant δ>0\delta> 0.

Assumption 2 (Quantum planted-clique conjecture, qPC). There is a range of plant sizes

(2+ε)log⁡2n≤k≤n1/2−ε(2+\varepsilon)\log_{2} n \le k \le n^{1/2-\varepsilon}

in which no polynomial-time quantum algorithm distinguishes G(n,12)G(n,\frac{1}{2}) from G(n,12,k)G(n,\frac{1}{2},k) with advantage ≥δ\ge\delta, for any constant δ>0\delta> 0.

This constant-advantage form is equivalent to the standard formulations of the conjecture by the equivalences of Hirahara–Shimizu [25], so nothing stronger than the usual assumption is being made. It is a standard detection form of the conjecture, it has been used to show the average-case hardness of sparse PCA, community detection, and related problems, and is supported by unconditional lower bounds against the Sum-of-Squares, statistical-query, and low-degree-polynomial models.

Fix kk in the PC window 2 and set d=k−2d = k - 2. We show estimating βk−2(skel⁡k−2X(G))\beta_{k-2}(\operatorname{skel}_{k-2} X(G)) w.h.p. decides the planted clique problem.

Lemma 4.1 (Null value). For k≥(2+ε)log⁡2nk \ge(2+\varepsilon)\log_{2} n, w.h.p. G0∼G(n,12)G_{0} \sim G(n,\frac{1}{2}) has no (k−1)(k-1)-clique, whence βk−2(skel⁡k−2X(G0))=0\beta_{k-2}(\operatorname{skel}_{k-2} X(G_{0})) = 0.

Proof. The expected number of (k−1)(k-1)-cliques is (nk−1)2−(k−12)≤(n2−(k−2)/2)k−1\binom{n}{k-1}2^{-\binom{k-1}{2}} \le(n2^{-(k-2)/2})^{k-1}. For k≥(2+ε)log⁡2nk \ge(2+\varepsilon)\log_{2} n the base is n−ε/2+o(1)→0n^{-\varepsilon/2+o(1)} \to0, so by Markov’s inequality no (k−1)(k-1)-clique exists w.h.p. Then skel⁡k−2X(G0)\operatorname{skel}_{k-2} X(G_{0}) has no (k−2)(k-2)-simplex at all: fk−2=0f_{k-2} = 0, and βk−2=0\beta_{k-2} = 0.

Lemma 4.2 (Planted value). For k≥(2+ε)log⁡2nk \ge(2+\varepsilon)\log_{2} n, w.h.p. over G(n,12,k)G(n,\frac{1}{2},k), βk−2(skel⁡k−2X(G))≥1\beta_{k-2}(\operatorname{skel}_{k-2} X(G)) \ge1.

Proof. The planted kk-clique is a complete graph, corresponding to a clique complex that is the full simplex σk−1\sigma^{k-1}. Truncating at dimension k−2k-2 deletes its unique top (k−1)(k-1)-face and leaves the boundary ∂σk−1≅Sk−2\partial\sigma^{k-1} \cong S^{k-2}, a simplicial (k−2)(k-2)-sphere with βk−2=1\beta_{k-2} = 1. By Lemma 4.1, w.h.p. the original graph likely contributes no (k−2)(k-2)-simplex outside the planted structure, so w.h.p. the only (k−2)(k-2)-simplices in skel⁡k−2X(G)\operatorname{skel}_{k-2} X(G) are the kk facets of the plant. These alone support exactly one nontrivial homology class, contributing βk−2=dim⁡ker⁡∂k−2=1\beta_{k-2} = \dim\ker\partial_{k-2} = 1. Nevertheless, it is possible that edges from the plant complete another kk-clique in the graph resulting in more than one non-trivial homology class in dimension d=k−2d = k - 2, i.e. βd≥1\beta_d \ge1 in the planted case.

Remark. For the sake of the reduction it is sufficient that the Betti number in dimension dd increases to 1 in the planted case, even though it might increase to a value higher than 1.

Lemma 4.3 (Deciding PC via Betti number). For k≥(2+ε)log⁡2nk \ge(2+\varepsilon)\log_{2} n, w.h.p. over the distribution defining PCLIQUE⁡(n,k)\operatorname{PCLIQU E}(n,k),

βk−2(skel⁡k−2X(G))≥1⟺[G is from the planted case].\beta_{k-2}(\operatorname{skel}_{k-2} X(G)) \ge1 \Longleftrightarrow[G\text{ is from the planted case}].
βk−2(skel⁡k−2X(G))=0⟺[G is from the null case].\beta_{k-2}(\operatorname{skel}_{k-2} X(G)) = 0 \Longleftrightarrow[G\text{ is from the null case}].

Proof. Immediate from Lemmas 4.1 and 4.2: the value is 0 in the null case and equal to 1 in the planted case, each w.h.p.

Theorem 2.1 [Average-case hardness of Betti number estimation] Let k=k(n)k = k(n) satisfy the inequality (2+ϵ)log⁡n<k<n1/2−ϵ(2 + \epsilon)\log n < k < n^{1/2-\epsilon}, and set d=k−2d = k - 2. For every constant δ>0\delta> 0, the following statements hold. Under Assumption 1, no randomized polynomial-time algorithm estimates

βd(skel⁡dX(G))\beta_d(\operatorname{skel}_d X(G))

to additive error below 12\frac{1}{2} with success probability at least 12+δ\frac{1}{2} + \delta over G∼DkG \sim D_k. Under Assumption 2, no quantum polynomial-time algorithm with a classical output estimate satisfies the same guarantee.

Proof. Suppose an efficient AA solves BETTI(k−2)(k - 2) to additive error <12< \frac{1}{2} with success probability ≥12+δ\geq\frac{1}{2} + \delta over DkD_k. Define a detector for PCLIQUE(n,k)(n,k): on input GG, form skel⁡k−2X(G)\operatorname{skel}_{k-2}X(G), run AA, and output PLANTED iff A(skel⁡k−2X(G))≥12A(\operatorname{skel}_{k-2}X(G)) \geq\frac{1}{2}.

Write s0=Pr⁡G∼G(n,12)[A succeeds]s_0 = \Pr_{G\sim G(n,\frac{1}{2})}[A\text{ succeeds}] and s1=Pr⁡G∼G(n,12,k)[A succeeds]s_1 = \Pr_{G\sim G(n,\frac{1}{2},k)}[A\text{ succeeds}]. Since DkD_k is the balanced mixture, the hypothesis says 12(s0+s1)≥12+δ\frac{1}{2}(s_0 + s_1) \geq\frac{1}{2} + \delta, i.e.

s0+s1≥1+2δ.(6)s_0 + s_1 \geq1 + 2\delta. \tag*{(6)}

Note that (6) bounds neither s0s_0 nor s1s_1 individually. Let η=η(n)=o(1)\eta= \eta(n) = o(1) bound the probability of the bad events of Lemmas 4.1 and 4.2.

Planted case. Except with probability η\eta we have βk−2≥1\beta_{k-2} \geq1; on the success event of AA the additive error <12< \frac{1}{2} forces A(G,k−2)>12A(G,k-2) > \frac{1}{2}, so

Pr⁡G∼G(n,12,k)[output PLANTED]≥s1−η.\Pr_{G\sim G(n,\frac{1}{2},k)}[\text{output PLANTED}] \geq s_1 - \eta.

Null case. Except with probability η\eta we have βk−2=0\beta_{k-2} = 0; on the success event the estimate lies below 12\frac{1}{2}, so the detector outputs NULL. Hence

Pr⁡G∼G(n,12)[output PLANTED]≤(1−s0)+η.\Pr_{G\sim G(n,\frac{1}{2})}[\text{output PLANTED}] \leq(1-s_0) + \eta.

Subtracting and applying (6), the advantage is at least

(s1−η)−(1−s0+η)=(s0+s1)−1−2η≥2δ−2η≥δ(s_1-\eta) - (1-s_0+\eta) = (s_0+s_1)-1-2\eta\geq2\delta-2\eta\geq\delta

for all large nn, since δ>0\delta> 0 is constant and η=o(1)\eta= o(1). This contradicts Assumptions 1 and 2 in the classical and quantum settings respectively.

Remark (Why the distribution is hard). Neither component of DkD_k is hard alone: by Lemma 4.1 the constant algorithm “output 0” solves BETTI(k−2)(k - 2) exactly with probability 1−o(1)1-o(1) over G(n,12)G(n,\frac{1}{2}), and by Lemma 4.2 “output 1” does so over G(n,12,k)G(n,\frac{1}{2},k). The hardness is that no single algorithm can handle the input distribution DkD_k.

Remark (Optimality of the constant-advantage form for the decision problem.). The constant δ>0\delta> 0 in Theorem 2.1 cannot be improved to an inverse polynomial: counting edges and thresholding yields an efficient algorithm that estimates βk−2\beta_{k-2} to additive error <12< \frac{1}{2} with success probability 12+Θ(k2/n)\frac{1}{2}+\Theta(k^2/n) on each distribution, and k2/n=n−2αk^2/n=n^{-2\alpha} for k=n1/2−αk=n^{1/2-\alpha}. Thus Theorem 2.1 is stated at the strongest success-probability threshold consistent with this trivial distinguisher; ruling out advantage ≫k2/n\gg k^2/n is possible under the optimal decision form of PC, but ruling out all inverse-polynomial advantage is false.

Remark (Relation to worst-case results). Deciding whether HdH_d of a clique complex vanishes is QMA1_1-hard, and computing Betti numbers is #P-hard (NP-hard for approximations), in the worst case. Theorem 2.1 is a new average-case result on the distribution DkD_k.

Reduction for different values of dd

In the previous section we have described a reduction which looks at the dd-skeleton for a particular choice of dd, namely d=k−2d = k - 2. In principle, we can use skeleta of the simplicial complex in other dimensions too. The argument, however, becomes more nuanced. The closer dd is to the bottom of the hard PC range, i.e. d→(2+ϵ)log⁡nd \to(2 + \epsilon) \log n, the Betti number signal βd\beta_d from the planted clique becomes stronger because a dd-skeleton of a kk-clique, adds (k−1d+1)\binom{k-1}{d+1} non-trivial homology classes in dimension dd. However, even though the signal for the choice of smaller dd increases, the background noise of the non-planted dd-cliques coming from the G(n,12,k)G(n,\frac{1}{2},k) distribution also increases as dd decreases. Even though for the complexity theoretic purposes the reduction carries through for a simple choice of d=k−2d = k - 2, it might be instructive to look at the mapping for different choices of the skeleton dimension.

Markov’s inequality assures us that when we look at the dd-skeleton of the complex X(G)X(G) then the probability of a C=d−1C = d - 1 clique existing in the graph G(n,12)G(n,\frac{1}{2}) is

P(C>a)≤2log⁡na(7)P(C > a) \leq\frac{2 \log n}{a} \tag*{(7)}

thus for any dd-clique such that dlog⁡n→∞\frac{d}{\log n} \to\infty, we can set a=da = d and have an assurance that no dd-clique exists w.h.p. (probability 1 as nn goes to infinity). Thus the reduction of theorem 2.1 applies for every such dd, and the planted Betti number signal (change in the number of distinct homology classes in dimension dd) gets stronger at smaller dd.

Reduction for arbitrary constant pp

The average-case planted clique hardness holds for every constant value of parameter pp [25]. Thus for any distribution Dk\mathcal{D}_k with p=const⁡p = \operatorname{const}, the average-case hardness of planted clique transfers to Betti number estimation on clique complexes from Dk\mathcal{D}_k.

Algorithmic implications

Because we have established the hardness of Betti number estimation on random clique complexes, it is natural to ask which of the ingredients that make quantum algorithms efficient are present, and which are not. We organise this section around the three promises under which the LGZ quantum algorithm is efficient, recalled from the introduction:

(P1) the complex is clique-dense, so the uniform simplex state ∣ψd⟩∝∑σ∈Xd(G)∣σ⟩|\psi_d\rangle\propto\sum_{\sigma\in X_d(G)} |\sigma\rangle can be prepared in polynomial time;

(P2) the combinatorial Laplacian Δd\Delta_d has an at least polynomially small spectral gap, so 1/gap⁡=poly⁡(n)1/\operatorname{gap} = \operatorname{poly}(n);

(P3) the normalized Betti number βd/fd\beta_d/f_d is not exponentially small.

An advantage requires a family that is quantumly easy while classically hard, hence, by the previous paragraphs and by [4], a family on which (P1), (P2) and (P3) hold simultaneously at a growing dimension, since at bounded constant dimension the classical estimator already matches the quantum one. The Erdős–Rényi model cannot supply this: at growing dimension its clique density is small, (P1) fails (see proof of 4.1), and neither algorithm is efficient. Any candidate family must therefore lie outside the distribution Dk\mathcal{D}_k, and it must in addition be classically hard for a reason other than a hidden planted clique, because the planted structure, we have shown, is equally opaque to quantum algorithms. Concretely, a candidate family should satisfy the promises P1,P2,P3 and be classically hard. The gapped clique-homology instances on weighted graphs of King and Kohler [30], which are QMA1\mathrm{QMA}_{1}-hard, are contained in QMA\mathrm{QMA} and come with an inverse-polynomial promise gap, are the natural structural template for P2, P3 and classical hardness; what is missing is a natural distribution over such instances that satisfies P1. In this light Theorem 2.1 functions as a filter on proposed advantage regimes: it removes the entire family Dk=12G(n,p)+12G(n,p,k)\mathcal{D}_{k} = \frac{1}{2}G(n,p) + \frac{1}{2}G(n,p,k) for any constant pp and, with it, any average-case advantage argument that would draw its classical hardness from planted-clique-type hidden structure. It remains entirely plausible that there exists a natural family of instances which exhibits quantum advantage, and the results obtained in this work are a stepping stone that clarifies the complexity landscape and makes it clearer what kind of instances might exhibit quantum advantage.

Identifying regions with average-case quantum advantage

For the clique complex X(G(n,p))X(G(n,p)) with p=n−αp = n^{-\alpha}, Kahle’s theorems[28] place the dd-th homology in a narrow band of densities:

βd(X(G(n,p)))>0 w.h.p.⟺1d+1<α<1d,(8)\beta_{d}(X(G(n,p))) > 0\ \mathrm{w.h.p.} \quad\Longleftrightarrow\quad\frac{1}{d+1} < \alpha< \frac{1}{d}, \tag*{(8)}

with βd=0\beta_{d} = 0 below the window (too sparse to support dd-cycles) and above it (dense enough that (d+1)(d+1)-faces fill every dd-cycle). Two features of the window matter here. In particular, the claim from [28] is even stronger, namely in the non-trivial region, the non-trivial homology is close to maximal, i.e. βdfd=1\frac{\beta_{d}}{f_{d}} = 1 w.h.p. Even more interestingly, we can show the non-trivial homology regime falls outside of the average-case hard region and our reduction breaks down also due to almost maximal Betti number in the Kahle window (no planted signal can be detected), possibly indicating a quantum advantage regime (subject to no efficient classical algorithms).

Non-trivial homology in random clique-complexes

Write p=n−αp = n^{-\alpha} and let X(G(n,p))X(G(n,p)) be the random clique (flag) complex, with fdf_{d} the number of its dd-simplices, so Efd=(nd+1)p(d+12)\mathbb{E}f_{d} = \binom{n}{d+1}p^{\binom{d+1}{2}}. Kahle’s theorems locate the homology of X(G(n,p))X(G(n,p)) in a single band of densities, and show it is empty outside that band.

Theorem 6.1 (Kahle, concentration of homology in one dimension [28]). For any d≥1d \ge1 and let p=n−αp = n^{-\alpha} with

1d+1<α<1d.\frac{1}{d+1} < \alpha< \frac{1}{d}.

Then w.h.p. H~i(X(G(n,p)))=0\widetilde{H}_{i}(X(G(n,p))) = 0 for every i≠di \ne d, and βd(X(G(n,p)))>0\beta_{d}(X(G(n,p))) > 0.

Theorem 6.2 (Kahle, vanishing outside the window [28, 29]). For any d≥1d \ge1 and let p=n−αp = n^{-\alpha}. If α>1d\alpha> \frac{1}{d} (too sparse to support dd-cycles) or α<1d+1\alpha< \frac{1}{d+1} (dense enough that (d+1)(d+1)-faces fill every dd-cycle), then βd(X(G(n,p)))=0\beta_{d}(X(G(n,p))) = 0 w.h.p.

Theorems 6.1 and 6.2 give the equivalence

βd(X(G(n,p)))>0 w.h.p.⟺1d+1<α<1d.(9)\beta_{d}(X(G(n,p))) > 0\ \mathrm{w.h.p.} \quad\Longleftrightarrow\quad\frac{1}{d+1} < \alpha< \frac{1}{d}. \tag*{(9)}

Inside the window the statement is quantitatively stronger: the homology is not merely non-zero but close to maximal, a sharpening already implicit in Kahle’s Euler-characteristic computation, which admits a short direct proof [29].

Lemma 6.3 (Near-maximal homology in the window (Theorem 3.8 from [28])). If α\alpha satisfies (8), then w.h.p.

βd(X(G(n,p)))=(1−o(1))fd.(10)\beta_{d}(X(G(n,p))) = (1 - o(1))f_{d}. \tag*{(10)}

Thus in the window fdf_d dominates its neighbouring face counts, so almost every dd-simplex supports a non-trivial homology class: the normalized Betti number is 1−o(1)1-o(1). We are also going to show that the reduction presented in section 4 does not hold in the Kahle’s window. It is therefore the natural place to ask whether an average-case quantum advantage can be demonstrated in that window, since the average-case hardness reduction breaks down.

No reduction in the non-trivial homology window

The reduction of Section 4 decides planted clique by reading a 00-versus-(≥1)(\ge1) gap in βd\beta_d, and that gap is manufactured by truncating the complex at d=k−2d=k-2: truncation turns the contractible planted simplex σk−1\sigma^{k-1} into the boundary sphere ∂σk−1≅Sk−2\partial\sigma^{k-1}\cong S^{k-2}, whose non-trivial homology contributes the signal. Inside Kahle’s window neither ingredient is available. First, the window lives at dimension d≈1/αd\approx1/\alpha, which for constant pp is Θ(log⁡1/pn)\Theta(\log_{1/p} n), slightly but sharply below the lower threshold of the hard window of planted clique ((2+o(1))log⁡1/pn)((2+o(1))\log_{1/p} n). So the empty-null case that the reduction exploits does not occur here. Secondly, the null-case Betti number is already near-maximal[28]. The following proposition shows in a simple way why the reduction of theorem2.1 does not apply to the non-trivial homology region identified by Kahle.

Proposition 6.4 (Kahle’s window lies below the PC-hard range). Let p=n−αp=n^{-\alpha} and let dd satisfy 1d+1<α<1d\frac{1}{d+1}<\alpha<\frac{1}{d}, d>1d>1. Then d+2<(2+ϵ)log⁡1/pnd+2<(2+\epsilon)\log_{1/p}n for every ϵ>0\epsilon>0 and nn large. Hence no kk in the PC window 2 satisfies k=d+2k=d+2, and Lemma 4.1 fails at every dimension in the window.

Proof. log⁡1/pn=1/α\log_{1/p}n=1/\alpha, so the PC window requires k≥(2+ϵ)/αk\ge(2+\epsilon)/\alpha, while α>1/(d+1)\alpha>1/(d+1) gives d+2<1/α+2d+2<1/\alpha+2.

Region for average-case quantum-advantage

Our results, together with the classical algorithm of [1] and the efficient state preparation problem[21, 44], partition the (d,α)(d,\alpha) landscape of Erdős–Rényi clique complexes into three regions, and by elimination we arrive at a single candidate for average-case quantum advantage.

  • PC-hard region (((2+ϵ)log⁡n<d<n1/2−ϵ)((2+\epsilon)\log n<d<n^{1/2-\epsilon})). The null complex is empty w.h.p., βd=0\beta_d=0, and the planted clique creates the only homology. This is where Theorem 2.1 rules out average-case advantage: Betti estimation is PC-hard, but it is hard for both classical and quantum algorithms and, by Schmidhuber–Lloyd [44], the invariant carries no information on typical inputs. Thus no quantum advantage.

  • Bounded dimension (d=O(1)d=O(1)). The window is nonempty here only for α=Θ(1)\alpha=\Theta(1), and there the normalized Betti number is estimated in polynomial time classically [1]. Any quantum algorithm is matched by a classical one. Thus quantum advantage is ruled out.

  • The window at growing dimension (1d+1<α<1d\frac{1}{d+1}<\alpha<\frac{1}{d}, d→∞d\to\infty). Here the normalized Betti number is near-maximal (P3), the gap can be favourable (P2), and, by 6.4, the planted-clique reduction provably fails. One remaining obstacle is (P1) which causes the quantum state preparation step to be inefficient with known techniques. Nevertheless, the main observation is that the average-case hardness we establish for the problem does not reach into this region. This is the interesting and non-trivial regime our reduction does not affect and the question of average-case quantum advantage remains open and plausible.

Implications

In this section we present the corollaries of our reduction from section 4. We work with the quantum hardness assumptions for planted clique (assumptions 2, 3), but all corollaries hold for classical computation if the quantum conjectures are replaced with the more established classical hardness assumptions.

We introduce the following quantum version of the strong search PC conjecture, for the classical version we refer the reader to [25]. This will be of use for some of the corollaries.

Assumption 3 (Quantum version of the strong search conjecture [25]). For any constants α∈(0,1/2)\alpha\in(0,1/2) and c>0c > 0, any (classical randomized [25]) quantum polynomial-time algorithm fails to find a kk-clique in G(n,12,k)G(n,\frac{1}{2},k) with probability 1−n−c1-n^{-c} (the probability of success is inverse polynomial) for all sufficiently large nn and k≤n1/2−αk \le n^{1/2-\alpha}.

Usually the worst-case complexity results refer to a random clique complex X(G)X(G); average-case results from this work are about the dd-skeleton of a clique complex from distribution Dk\mathcal{D}_k in the same local-access model.

Simple corollaries about simplicial complexes

Corollary 1 (Simplex search). Under the strong search PC conjecture 3, for every inverse polynomial δ\delta no efficient algorithm outputs, with probability ≥δ\ge\delta over G∼G(n,12,k)G \sim G(n,\frac{1}{2},k), a single (k−2)(k-2)-simplex of X(G)X(G).

Proof. A (k−2)(k-2)-simplex is a (k−1)(k-1)-clique; by Lemma 4.2 any such clique is w.h.p. contained in the plant, so its vertices are k−1k-1 of the kk plant vertices, verifiable by (k−12)\binom{k-1}{2} edge queries. This recovers a large clique, contradicting strong search PC.

Remark (This is not a Betti-number corollary). Corollary 2 uses only that the null complex is empty in dimension k−2k-2; it makes no reference to homology and is a consequence of the planted clique conjecture directly. We include it because it is the input subroutine of the quantum pipeline (below), but we flag that its hardness does not route through Theorem 2.1. It also holds only at the critical dimension: for d≪kd \ll k the null complex is dense in dimension dd and sampling a dd-simplex is trivial in both cases.

Corollary 2 (Simplex-state preparation). Under the strong search version of PC, no efficient quantum algorithm prepares, to constant trace distance and with probability ≥n−c\ge n^{-c} over G∼G(n,12,k)G \sim G(n,\frac{1}{2},k), the uniform simplex state

∣ψk−2⟩∝∑σ∈Xk−2(G)∣σ⟩.\lvert\psi_{k-2}\rangle\propto\sum_{\sigma\in X_{k-2}(G)} \lvert\sigma\rangle.

Proof. If ρ\rho is within trace distance 14\frac{1}{4} of ∣ψk−2⟩⟨ψk−2∣\lvert\psi_{k-2}\rangle\langle\psi_{k-2}\rvert, then measuring ρ\rho in the computational basis returns a (k−2)(k-2)-simplex with probability ≥12\ge\frac{1}{2}.

Remark (Implications for the LGZ pipeline). ∣ψk−2⟩\lvert\psi_{k-2}\rangle is exactly the input state of the LGZ algorithm [34]: the pipeline first prepares the uniform superposition over dd-simplices, then applies phase estimation to Δd\Delta_d. Corollary 2 shows that at d=k−2d=k-2 this first step is already average-case hard on the G(n,12,k)G(n,\frac{1}{2},k) family. One clarification is essential to state the implication correctly. This is distinct from the well-known density obstruction to LGZ [21, 10]: LGZ preparation costs O((fd(nd+1))−1/2)O\left(\left(\frac{f_d}{\binom{n}{d+1}}\right)^{-1/2}\right) by amplitude amplification, which is inefficient when the clique density is small. That obstruction is unconditional; ours is conditional on the PC conjecture. At d=k−2d=k-2 both obstructions are present but they are not the same statement: density says “preparation is slow because simplices are rare,” whereas Corollary 2 says “preparation is hard on average because deciding whether any simplex exists is planted-clique-hard.”

Corollaries in Topological Data Analysis

Comparison of worst-case and average-case hardness of quantum topological data analysis tasks

Figure 2. Illustration of comparison of the worst-case vs average-case hardness of various problems related to Topological Data Analysis. The hardness of exact and approximate Betti number computations follows from [44], QMA1_1-hardness follows from [13](see remark 7.2), DQC1_1-hardness from [21], NP-hardness of approximate homology localization from [12].

Corollary 3 (Multiplicative and coarse additive approximation). Under Assumption 2, no efficient algorithm outputs any finite multiplicative approximation of βd\beta_d with success probability ≥12+δ\ge\frac{1}{2}+\delta for a constant δ>0\delta> 0. Moreover, at d=k−2d = k - 2 no efficient algorithm estimates βk−2\beta_{k-2} to additive error <12< \frac{1}{2} with such probability; and for d=Θ(log⁡n)d = \Theta(\log n) with k=n1/2−εk = n^{1/2-\varepsilon} the additive error may be relaxed to exp⁡(clog⁡2n)\exp(c\log^2 n) for a constant c>0c > 0 and the conclusion still holds.

Proof. A multiplicative approximation distinguishes βd=0\beta_d = 0 from βd≥1\beta_d \ge1: any finite factor maps 0 to 0 and a positive integer to a positive number. By Lemma 4.3 this decides the planted case, so Theorem 2.1 applies. For the additive claim at d=k−2d = k - 2 the value gap is exactly 1, giving error tolerance <12< \frac{1}{2}. For d≪kd \ll k, Lemma 4.2 gives planted value ≥(k−1d+1)\ge\binom{k-1}{d+1} while the null value is 0 w.h.p.; with d+1>(2+ε)log⁡nd + 1 > (2 + \varepsilon)\log n and k=n1/2−εk = n^{1/2-\varepsilon} one has (k−1d+1)=exp⁡(Θ(log⁡2n))\binom{k-1}{d+1} = \exp(\Theta(\log^2 n)), so any additive approximation to error <12(k−1d+1)=exp⁡(clog⁡2n)< \frac{1}{2}\binom{k-1}{d+1} = \exp(c\log^2 n) still separates the two cases.

Corollary 4 (Normalized Betti-number estimation). *Under PC, fix kk in the window 22 and any dd with (2+ε)log⁡2n≤d+1=o(k)(2+\varepsilon)\log_2 n \le d+1 = o(k). Then no efficient algorithm estimates βd(skel⁡dX(G))fd(G)\frac{\beta_d(\operatorname{skel}_d X(G))}{f_d(G)} to additive error <12< \frac{1}{2} with success probability ≥12+δ\ge\frac{1}{2}+\delta, for any constant δ>0\delta> 0, over G∼G(n,12)G \sim G(n,\frac{1}{2}) vs. G(n,12,k)G(n,\frac{1}{2},k).

Proof. Null: since d+1≥(2+ε)log⁡2nd+1 \ge(2+\varepsilon)\log_2 n, Lemma 4.1 (with d+1d+1 for k−1k-1) gives βd,fd=0\beta_d,f_d=0 w.h.p., so βd/fd=0\beta_d/f_d=0. We set βd/fd:=0\beta_d/f_d:=0 when fd=0f_d=0. Planted: the plant contributes (k−1d+1)\binom{k-1}{d+1} independent nonbounding dd-cycles (its dd-skeleton is a wedge of that many dd-spheres), which survive in ker⁡∂d\ker\partial_d, so βd≥(k−1d+1)\beta_d \ge\binom{k-1}{d+1}; and the expected number of (d+1)(d+1)-cliques outside the plant is ∑j≤d(kj)(n−kd+1−j)2−(d+12)+(j2)=o((kd+1))\sum_{j\le d}\binom{k}{j}\binom{n-k}{d+1-j}2^{-\binom{d+1}{2}+\binom{j}{2}}=o\left(\binom{k}{d+1}\right) (dominated by the j=dj=d term (kd)2d(d+1)/2n1+ε\binom{k}{d}\frac{2^{d(d+1)/2}}{n^{1+\varepsilon}}, using 2d≥12nε2^d\ge\frac{1}{2}n^{\varepsilon}), so fd=(1+o(1))(kd+1)f_d=(1+o(1))\binom{k}{d+1} w.h.p. Hence βd/fd≥(1−o(1))(1−d+1k)=1−o(1)\beta_d/f_d\ge(1-o(1))\left(1-\frac{d+1}{k}\right)=1-o(1). The two values 00 and 1−o(1)1-o(1) are separated by >12>\frac{1}{2}, so thresholding an error at ε<12\varepsilon<\frac{1}{2} decides PClique as in Theorem 2.1.

Remark (Relation to the LGZ target precision). βd/fd\beta_d/f_d is exactly the quantity the LGZ algorithm and its descendants estimate [35, 21], and they aim for inverse-polynomial additive error. Corollary 4 shows hardness already at additive error <12<\frac{1}{2}. The apparent paradox with the algorithms’ efficiency is resolved by their promises: LGZ is efficient only when the normalized Betti number is not small and the simplex state is efficiently preparable, and our planted family violates the second promise (see Corollary 2).

Corollary 5 (Homology vanishing). Under Assumption 2, no efficient algorithm decides whether Hd(skel⁡dX(G))=0H_d(\operatorname{skel}_d X(G))=0 with success probability ≥12+δ\ge\frac{1}{2}+\delta for a constant δ>0\delta>0.

Proof. The null and planted values of βd\beta_d are 00 and ≥1\ge1 w.h.p.: the boundary sphere ∂σk−1≅Sk−2\partial\sigma^{k-1}\cong S^{k-2} has βk−2≥1\beta_{k-2}\ge1 (Lemma 4.2). Deciding Hd=0H_d=0 therefore decides the planted case, and Theorem 2.1 applies.

Corollary 6 (Homology localization and cycle representatives). Under the strong search version (not merely deciding whether the clique was planted) of PC [25], for every constant c>0c>0 no efficient algorithm outputs, with probability ≥n−c\ge n^{-c} over G∼G(n,12,k)G\sim G(n,\frac{1}{2},k), any nonzero (k−2)(k-2)-cycle of skel⁡k−2X(G)\operatorname{skel}_{k-2}X(G). Equivalently any representative of a nontrivial class in Hk−2H_{k-2}, exact or within any ℓ2\ell_2-distance <1k<\frac{1}{\sqrt{k}} of a genuine cycle. In particular computing minimal-weight cycle representatives is average-case hard.

Proof. By Lemma 4.2 every nonzero cycle is a multiple of zz, whose support is all kk facets of the plant. Any vector within ℓ2\ell_2-distance <1k<\frac{1}{\sqrt{k}} of the normalised cycle z/kz/\sqrt{k} has all kk facet coordinates nonzero (each coordinate of z/kz/\sqrt{k} has magnitude 1/k1/\sqrt{k}), so reading off its support and verifying each facet by (k−12)\binom{k-1}{2} edge queries recovers k−1k-1 plant vertices. This contradicts the strong search version of PC as in Corollary 1. Minimal-weight representatives are a special case of Corollary 1, giving an average-case analogue of the worst-case hardness of [12].

Corollary 7 (Harmonic-state preparation). Under the strong search version of PC, no efficient quantum algorithm prepares, to constant trace distance and with probability ≥n−c\ge n^{-c} over G∼G(n,12,k)G\sim G(n,\frac{1}{2},k), the maximally mixed state Π0/βk−2\Pi_0/\beta_{k-2} on ker⁡Δk−2\ker\Delta_{k-2}.

Proof. By Lemma 4.2 the kernel is at least one-dimensional at d=k−2d=k-2, so Π0/βk−2=∣hG⟩⟨hG∣\Pi_0/\beta_{k-2}=|h_G\rangle\langle h_G|, and would correspond to homology localization (Corollary 6) and measuring the state would reveal the planted clique.

Corollary 8 (Low-lying spectral density). Fix threshold λ∈(0,k)\lambda\in(0,k) for any kk in the hard regime for planted clique. Under Assumption 2, no efficient algorithm estimates the eigenvalue count N<λ(Δk−2):=#{eigenvalues of Δk−2 in [0,λ)}N_{<\lambda}(\Delta_{k-2}):=\#\{\text{eigenvalues of }\Delta_{k-2}\text{ in }[0,\lambda)\} to additive error <12<\frac{1}{2} with success probability ≥12+δ\ge\frac{1}{2}+\delta for a constant δ>0\delta>0.

Proof. The spectrum of Δk−2\Delta_{k-2} on the planted skeleton is {0}∪{k}\{0\}\cup\{k\}, so for any λ∈(0,k)\lambda\in(0,k) the count N<λN_{<\lambda} equals the multiplicity of 00, namely βk−2=1\beta_{k-2}=1; in the null case Δk−2\Delta_{k-2} acts on the zero space and N<λ=0N_{<\lambda}=0. Thus N<λN_{<\lambda} equals βk−2\beta_{k-2} on both distributions, and Theorem 2.1 applies.

Remark (Average-case analogue of the DQC1-hard LLSD problem). Estimating the low-lying spectral density of a succinctly specified sparse Hermitian operator is the DQC1-hard problem identified by [21] as the computational core of quantum TDA: LGZ-type algorithms estimate exactly this count for Δd\Delta_d. Corollary 8 gives its average-case analogue on the natural input distribution.

Remark. Deciding whether HdH_d of a clique complex vanishes is QMA1_1-hard in the worst case [13, 11]. Corollary 5 is not an average-case statement about that family. Rather, Corollary 5 gives average-case hardness, on the distribution Dk\mathcal{D}_k of which clique homology is the worst-case-hard subfamily. Whether homology vanishing of the clique complex itself is hard on average under any other natural distribution remains open.

Other implications

In this section we mention other implications of the findings presented in this work.

Restricted models (unconditional).

Because the reduction is direct and the problem instance remains on the same graph, the unconditional planted-clique lower bounds transfer to every estimation problem above with no conjecture. Concretely: no low-degree polynomial test [32, 47] and no statistical-query algorithm [19] distinguishes the null and planted values of βd\beta_d in the PC window; and by the sum-of-squares lower bound for planted clique [7], no polynomial-size, constant-degree sum-of-squares certificate proves Hd(skel⁡dX(G))=0H_d(\operatorname{skel}_d X(G))=0 for G∼G(n,12)G \sim G(n,\frac{1}{2}), even though this vanishing holds w.h.p.

Achieving quantum advantage

The ongoing search for quantum advantage in quantum Topological Data Analysis has resulted in the number of complexity results which rule out specific families of problems. In this work we show that both classical and quantumly the Betti number estimation problem as well as all the problems described in section 7 are hard on average under the widely believed planted clique conjecture. We have identified a region where our reduction does not reach, leaving the average-case hardness question open. Moreover the identified region exhibits non-trivial homology, large spectral gaps, but still suffers from the state-preparation problem (P1), rendering existing quantum algorithms inefficient. However, for instances in this region if one identifies perhaps instance specific efficient techniques for state-preparation then one might be capable of demonstrating instance- or family-specific quantum advantage.

Open problems

Our work opens up several directions for extending the understanding of qqTDA in the average-case setting. Our results also clarify what would be required to obtain a convincing application of qqTDA. A candidate family of instances to demonstrate quantum advantage should ideally satisfy the following conditions:

  1. the relevant simplices can be sampled approximately uniformly in polynomial time, and the corresponding simplex state can be prepared efficiently;

  1. a suitably normalized boundary operator or the combinatorial Laplacian can be implemented efficiently;

(iii) the smallest nonzero eigenvalue of the combinatorial Laplacian satisfies

λmin⁡+(Δ~d)≥1poly⁡(n);\lambda_{\min}^{+}(\widetilde{\Delta}_d) \ge\frac{1}{\operatorname{poly}(n)};

(iv) the required output is informative at inverse-polynomial additive precision.

The most interesting spectral regime appears to be one in which the normalized gap is inverse polynomial but tends to zero with the input size. At constant gap, existing classical polynomial-filter algorithms may also run in polynomial time. We conclude with a list of open problems that we hope will bring the complexity theory behind qTDA closer to practical applications.

Extensions of the average-case hardness framework

  1. Average-case complexity under other natural distributions. Determine the average-case complexity of Betti-number estimation under probability distributions other than the balanced planted-clique distribution considered here.

Even for pure Erdős–Rényi flag complexes, it remains necessary to distinguish probabilistic concentration of the invariant from the computational complexity of estimating it at a specified precision.

  1. Converse reductions and distributional completeness. Determine whether planted clique can be recovered from a suitable Betti-number oracle in both directions, or whether Betti-number estimation is complete for a natural class of planted distributional problems. More generally, identify transformations between hidden subgraph problems and topological estimation problems that preserve the input distribution, success probability, and relevant access model.

  1. Persistent and multiparameter extensions. Extend our reduction to persistent homology and multiparameter persistence. A natural starting point is the skeletal filtration

Fm(G)=skel⁡mX(G).F_m(G) = \operatorname{skel}_m X(G).

In the planted case, the boundary class created in Fk−2(G)F_{k-2}(G) becomes trivial when the planted (k−1)(k-1)-simplex is restored in Fk−1(G)F_{k-1}(G). This suggests average-case hardness of deciding whether

ker⁡(Hk−2(Fk−2(G))⟶Hk−2(Fk−1(G)))\operatorname{ker}\left(H_{k-2}(F_{k-2}(G)) \longrightarrow H_{k-2}(F_{k-1}(G))\right)

is nonzero. It would be useful to obtain analogous results for rank invariants, image persistence, cokernel persistence, and selected multiparameter Hilbert-function queries. This would complement existing quantum algorithms for persistent Betti numbers [23].

  1. Directed, path, and higher-order complexes. Extend the average-case hardness results to directed flag complexes, path homology, hypergraph complexes, and other higher-order constructions. An undirected graph can be oriented according to a total vertex order, producing an acyclic directed graph whose directed flag complex is isomorphic to the original clique complex. This gives an immediate route to hardness results for directed flag homology. It remains open whether a comparable construction exists for grounded path homology and related directed persistence theories.

  1. Average-case spectral and sampling parameters. Determine the typical scaling of

fd(nd+1),λmin⁡+(Δ~d),βdfd,\frac{f_d}{\binom{n}{d+1}}, \qquad\lambda_{\min}^{+}(\widetilde{\Delta}_d), \qquad\frac{\beta_d}{f_d},

under natural probability distributions. The analysis should distinguish membership access, local sparse-row access, approximate simplex sampling, coherent state preparation, and block encoding. Uniform lower bounds on the normalized Hodge gap for growing dimension would be particularly valuable.

  1. Succinct boundary-matrix complexity. Formalize the complexity of rank, nullity, and low-energy spectral estimation for exponentially large boundary matrices given through a compact graph or hypergraph description. The resulting problem is different from rank computation for an explicitly listed sparse matrix, which is polynomial-time solvable. It would be useful to identify complete problems for natural succinct-access models and to determine which classical restricted-model lower bounds transfer to them.

Biological applications

  1. Online and zigzag qTDA for evolving tissues. Develop quantum algorithms for time-dependent sequences

K0⟷K1⟷⋯⟷KT,K_0 \longleftrightarrow K_1 \longleftrightarrow\cdots\longleftrightarrow K_T,

in which simplices can both appear and disappear. An important question is whether a simplex state or harmonic state prepared at time tt can be used as a warm start at time t+1t+1, leading to an amortized advantage over repeated classical matrix reduction. This has a number of practical biological applications which include tumour evolution, immune-cell migration, and vascular remodelling.

  1. Directed topology of biological flow and signalling. Develop qTDA methods for directed biological networks, including signalling pathways, gene-regulatory networks, metabolic networks, vascular flow, neuronal circuits, and polarized molecular interactions.

  1. Higher-order topology in multi-omics and cellular interactions. Construct biologically motivated simplicial or hypergraph models in which a higher-dimensional simplex represents a genuine joint interaction rather than only the clique completion of pairwise edges. Examples include multi-cell signalling events, protein complexes, gene-regulatory modules, microbiome communities and beyond. One should determine whether higher-order topological features improve prediction beyond graph-based models and whether the corresponding simplices can be sampled without enumerating the full complex.

Quantum advantage

  1. Common access models for classical and quantum algorithms. Compare quantum algorithms with the corresponding classical algorithms under the same input assumptions. The comparison should include exact sparse boundary reduction, path-integral estimators, Krylov and Chebyshev methods, stochastic Lanczos quadrature, and application-specific sampling algorithms [4, 10].

  1. Amortized advantage. Many applications rely on performing the same topological computation over many scales, time points, parameter values, candidate molecules, or bootstrap samples. Determine whether quantum states, block encodings, or spectral estimates can be reused across related instances. An amortized advantage over a long sequence of correlated queries may be achievable even when no advantage is present for a single isolated complex.

Cryptography

  1. Betti-number estimation as a proof-of-work problem. Determine whether the average-case hardness of Betti-number estimation can be combined with an efficient verification mechanism.

  1. Cryptographic primitives based on topological problems. Determine whether average-case hardness of Betti-number estimation, homology vanishing, homology localization, or related succinctly represented linear-algebra problems can be used to construct standard cryptographic primitives such as one-way functions.

Acknowledgements

Strelchuk acknowledges support from the Wellcome Leap as part of the Q4Bio Program and the Royal Society University Research Fellowship. Subramanian acknowledges support from the Royal Society through a University Research Fellowship.

References

  1. [1]Simon Apers, Sander Gribling, Sayantan Sen, and Dániel Szabó. A (simple) classical algorithm for estimating Betti numbers in the quantum regime, 2022. arXiv:2211.09618.DOI
  2. [2]Noga Alon, Michael Krivelevich, and Benny Sudakov. Finding a large hidden clique in a random graph. Random Structures & Algorithms, 13(3-4):457–466, 1998.
  3. [3]Michał Adamaszek and Juraj Stacho. Complexity of simplicial homology and independence complexes of chordal graphs. Computational Geometry, 57:8–18, 2016.DOI
  4. [4]Ismail Yunus Akhalwaya, Shashanka Ubaru, Kenneth L. Clarkson, Mark S. Squillante, Vishnu Jejjala, Yang-Hui He, Kugendran Naidoo, Vasileios Kalantzis, and Lior Horesh. Topological data analysis on noisy quantum computers, 2022. arXiv:2209.09371.arxiv.org/abs/2209.09371
  5. [5]Matthew S. Brennan and Guy Bresler. Reducibility and statistical-computational gaps from secret leakage. In Proceedings of the 33rd Conference on Learning Theory (COLT), pages 648–847, 2020.arxiv.org/abs/2005.08099
  6. [7]Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh K. Kothari, Ankur Moitra, and Aaron Potechin. A nearly tight sum-of-squares lower bound for the planted clique problem. SIAM Journal on Computing, 48(2):687–735, 2019.
  7. [8]Guy Bresler and Tianze Jiang. Detection-recovery and detection-refutation gaps via reductions from planted clique. In Proceedings of the 36th Conference on Learning Theory (COLT), pages 5850–5889, 2023.arxiv.org/abs/2306.17719
  8. [9]Quentin Berthet and Philippe Rigollet. Complexity theoretic lower bounds for sparse principal component detection. In Proceedings of the 26th Conference on Learning Theory (COLT), pages 1046–1066, 2013.
  9. [10]Dominic W. Berry, Yuan Su, Casper Gyurik, Robbie King, Joao Basso, Alexander Del Toro Barba, Abhishek Rajput, Nathan Wiebe, Vedran Dunjko, and Ryan Babbush. Analyzing prospects for quantum advantage in topological data analysis. PRX Quantum, 5:010319, 2024. arXiv:2209.13581.DOI
  10. [11]Chris Cade and P. Marcos Crichigno. Complexity of supersymmetric systems and the cohomology problem. Quantum, 8, 2024. arXiv:2107.00011.DOI
  11. [12]Chao Chen and Daniel Freedman. Hardness results for homology localization. Discrete & Computational Geometry, 45(3):425–448, 2011.
  12. [13]Marcos Crichigno and Tamara Kohler. Clique homology is QMA₁-hard. Nature Communications, 15, 2024. arXiv:2209.11793.DOI
  13. [14]Yael Dekel, Ori Gurel-Gurevich, and Yuval Peres. Finding hidden cliques in linear time with high probability. Combinatorics, Probability and Computing, 23(1):29–49, 2014.
  14. [15]Luiz Carlos de Jesus, Francisco Fernández-Navarro, and Mariano Carbonero-Ruz. Enhancing financial time series forecasting through topological data analysis. Neural Comput. Appl., 37(9):6527–6545, January 2025.
  15. [16]Yash Deshpande and Andrea Montanari. Finding hidden cliques of size √N/e in nearly linear time. Foundations of Computational Mathematics, 15(4):1069–1128, 2015.
  16. [17]Herbert Edelsbrunner and Salman Parsa. On the computational complexity of betti numbers: Reductions from matrix rank. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 152–160. Society for Industrial and Applied Mathematics, 2014.
  17. [18]Reyad Abed Elrazik, Robert Robere, Assaf Schuster, and Gal Yehuda. Pseudorandom self-reductions for NP-complete problems. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS), pages 65:1–65:12, 2022.DOI
  18. [19]Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. Vempala, and Ying Xiao. Statistical algorithms and a lower bound for detecting planted cliques. Journal of the ACM, 64(2):8:1–8:37, 2017.
  19. [20]Uriel Feige and Robert Krauthgamer. The probable value of the Lovász–Schrijver relaxations for maximum independent set. SIAM Journal on Computing, 32(2):345–370, 2003.DOI
  20. [21]Casper Gyurik, Chris Cade, and Vedran Dunjko. Towards quantum advantage via topological data analysis. Quantum, 6:855, 2022. arXiv:2005.02607.DOI
  21. [22]Sam Gunn and Niels Kornerup. Review of a quantum algorithm for Betti numbers, 2019. arXiv:1906.07673.arxiv.org/abs/1906.07673
  22. [23]Ryu Hayakawa. Quantum algorithm for persistent Betti numbers and topological data analysis. Quantum, 6:873, 2022. arXiv:2111.00433.DOI
  23. [24]Elad Hazan and Robert Krauthgamer. How hard is it to approximate the best Nash equilibrium? SIAM Journal on Computing, 40(1):79–91, 2011.
  24. [25]Shuichi Hirahara and Nobutaka Shimizu. Planted clique conjectures are equivalent. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), pages 358–366, 2024. doi:10.1145/3618260.3649751.DOI
  25. [26]Bruce E. Hajek, Yihong Wu, and Jiaming Xu. Computational lower bounds for community detection on random graphs. In Proceedings of the 28th Conference on Learning Theory (COLT), pages 899–928, 2015.arxiv.org/abs/1406.6625
  26. [27]Mark Jerrum. Large cliques elude the Metropolis process. Random Structures & Algorithms, 3(4):347–360, 1992.DOI
  27. [28]Matthew Kahle. Topology of random clique complexes. Discrete Mathematics, 309(6):1658–1671, 2009.
  28. [29]Matthew Kahle. Sharp vanishing thresholds for cohomology of random flag complexes. Annals of Mathematics, 179(3):1085–1107, 2014.arxiv.org/abs/1207.0149
  29. [30]Robbie King and Tamara Kohler. Gapped clique homology on weighted graphs is QMA₁-hard and contained in QMA, 2023. arXiv:2311.17234.arxiv.org/abs/2311.17234
  30. [31]Luděk Kučera. Expected complexity of graph partitioning problems. Discrete Applied Mathematics, 57(2-3):193–212, 1995.DOI
  31. [32]Dmitriy Kunisky, Alexander S. Wein, and Alfonso S. Bandeira. Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio, 2019. arXiv:1907.11636.arxiv.org/abs/1907.11636
  32. [33]Pascal Koiran and Anastasios Zouzias. Hidden cliques and the certification of the restricted isometry property. IEEE Transactions on Information Theory, 60(8):4999–5006, 2014.
  33. [34]Seth Lloyd, Silvano Garnerone, and Paolo Zanardi. Quantum algorithms for topological and geometric analysis of data. Nature Communications, 7:10138, 2016. arXiv:1408.3106.arxiv.org/abs/1408.3106
  34. [35]Pek Y Lum, Gurjeet Singh, Alan Lehman, Tigran Ishkhanov, Mikael Vejdemo-Johansson, Muthu Alagappan, John Carlsson, and Gunnar Carlsson. Extracting insights from the shape of complex data using topology. Scientific Reports, 3(1):1236, 2013.DOI
  35. [36]Sam McArdle, András Gilvén, and Mario Berta. A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits, 2022. arXiv:2209.12887.DOI
  36. [37]Pasin Manurangsi, Aviad Rubinstein, and Tselil Schramm. The strongish planted clique hypothesis and its consequences. In Proceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS), pages 10:1–10:21, 2021.arxiv.org/abs/2011.05555
  37. [38]Zongming Ma and Yihong Wu. Computational barriers in minimax submatrix detection. The Annals of Statistics, 43(3):1089–1116, 2015.DOI
  38. [39]Monica Nicolau, Arnold J Levine, and Gunnar Carlsson. Topology based data analysis identifies a subgroup of breast cancers with a unique mutational profile and excellent survival. Proceedings of the National Academy of Sciences, 108(17):7265–7270, 2011.
  39. [40]Raúl Rabadán, Yamina Mohamedi, Udi Rubin, Tim Chu, Adam N Alghalith, Oliver Elliott, Luis Arnés, Santiago Cal, Álvaro J Obaya, Arnold J Levine, et al. Identification of relevant genetic alterations in cancer using topological data analysis. Nature Communications, 11(1):3808, 2020.
  40. [41]Benjamin Rossman. On the constant-depth complexity of k-clique. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pages 721–730, 2008.DOI
  41. [42]Bjarke Hammersholt Roune and Eduardo Sáenz-de Cabezón. Complexity and algorithms for Euler characteristic of simplicial complexes. Journal of Symbolic Computation, 50:170–196, 2013.
  42. [43]Yashbir Singh, Colleen M Farrelly, Quincy A Hathaway, Tim Leiner, Jaidip Jagtap, Gunnar E Carlsson, and Bradley J Erickson. Topological data analysis in medical imaging: current state of the art. Insights into Imaging, 14(1):58, 2023.
  43. [44]Alexander Schmidhuber and Seth Lloyd. Complexity-theoretic limitations of quantum algorithms for topological data analysis. PRX Quantum, 4:040349, 2023. arXiv:2209.14286.DOI
  44. [45]Charu Sharma, Deepak Nathani, and Manohar Kaul. Solving partial assignment problems using random clique complexes. In International Conference on Machine Learning, pages 4586–4595. PMLR, 2018.arxiv.org/abs/1907.01739
  45. [46]Fernando A. N. Santos, Ernesto P. Raposo, Maurício D. Coutinho-Filho, Mauro Copelli, Cornelis J. Stam, and Linda Douw. Topological phase transitions in functional brain networks. Phys. Rev. E, 100:032414, Sep 2019.
  46. [47]Tseil Schramm and Alexander S. Wein. Computational barriers to estimation from low-degree polynomials. The Annals of Statistics, 50(3), 2022.DOI
  47. [48]Luca Trevisan. Search vs decision vs certification for planted problems. Blog post, https://lucatrevisan.wordpress.com/2018/05/06/, 2018.
  48. [49]Chad M Topaz, Lori Ziegelmeier, and Tom Halverson. Topological data analysis of biological aggregation models. PloS one, 10(5):e0126383, 2015.DOI
  49. [50]Shashanka Ubaru, Ismail Yunus Akhalwaya, Mark S. Squilllante, Kenneth L. Clark-son, and Lior Horesh. Quantum topological data analysis with linear depth and exponential speedup, 2021. arXiv:2108.02811.arxiv.org/abs/2108.02811

Paper details

vlnc:W_nhu7ftn3
Version
v1 · latest
Published
Added
License
CC BY-SA 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents