Average-case hardness of Betti number estimation

• URL: http://arxiv.org/abs/2609.12777v1
• Date: Fri, 11 Sep 2026 12:30:30 GMT
• Title: Average-case hardness of Betti number estimation
• Abstract summary: We establish the average-case hardness of Betti number estimation on random clique complexes via a reduction from the planted clique problem.<n>We show that our reduction implies a series of hardness results for many problems in both classical and quantum Topological Data Analysis.
• Score: 1.6312989763677892
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We establish the average-case hardness of Betti number estimation on random clique complexes via a reduction from the planted clique problem. We further show that our reduction implies a series of hardness results for many problems in both classical and quantum Topological Data Analysis (qTDA). Under the classical planted clique conjecture, no randomized polynomial-time Betti number estimator achieves additive error below $\tfrac12$ with constant advantage. Under a new quantum planted clique conjecture that we introduce, the same conclusion holds for quantum polynomial-time algorithms. We also obtain related conditional hardness results for homology vanishing, additive approximations with larger error tolerances, preparation of simplex and harmonic states, cycle recovery, and counting eigenvalues at low energy. Our reduction clarifies the structural requirements for quantum advantage in TDA and provides a new lens to investigate the classical and quantum complexity of related problems.

Related papers

• A rigorous quasipolynomial-time classical algorithm for SYK thermal expectations [51.660331450043806]
  Estimating local observables in Gibbs states is a central problem in quantum simulation.<n>We give a proof of a quasipolynomial-time classical algorithm that estimates SYK local thermal expectations at sufficiently high constant temperature.<n>Our result introduces a new Wick-pair expansion that we expect to be broadly useful for quantum many-body systems.
  arXiv  Detail & Related papers  (2026-04-22T21:14:04Z)
• Quartic quantum speedups for community detection [84.14713515477784]
  We develop a quantum algorithm for hypergraph community detection that achieves a quartic quantum speedup.<n>Our algorithm is based on the Kikuchi method, which we extend beyond previously considered problems such as PCA and $p$XORSAT.
  arXiv  Detail & Related papers  (2025-10-09T17:35:17Z)
• New aspects of quantum topological data analysis: Betti number estimation, and testing and tracking of homology and cohomology classes [3.2268950104324965]
  We present new quantum algorithms for estimating homological invariants, specifically Betti and persistent Betti numbers.<n>Our approach efficiently block-encodings of constructs (persistent) Laplacians, enabling estimation via exponential rank methods.<n>These results open a new direction in quantum topological data analysis and demonstrate provable quantum advantages in computing topological invariants.
  arXiv  Detail & Related papers  (2025-06-02T08:43:58Z)
• Reducing the sampling complexity of energy estimation in quantum many-body systems using empirical variance information [45.18582668677648]
  We consider the problem of estimating the energy of a quantum state preparation for a given Hamiltonian in Pauli decomposition.<n>We construct an adaptive estimator using the state's actual variance.
  arXiv  Detail & Related papers  (2025-02-03T19:00:01Z)
• Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios [0.0]
  We provide some of the first lower coefficients for the number of rounds (the dominant component of QAOA runtimes) required for the QAOA.<n>For the conventional transverse-field mixer, (iv) our framework gives a trivial lower bound to all bounded-occurrence local cost problems.<n>For all strictly $k$-local cost Hamiltonians matching known results that constant approximation ratio is obtainable with a constant-round QAOA.
  arXiv  Detail & Related papers  (2023-08-29T17:10:20Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Experimental violations of Leggett-Garg's inequalities on a quantum computer [77.34726150561087]
  We experimentally observe the violations of Leggett-Garg-Bell's inequalities on single and multi-qubit systems. Our analysis highlights the limits of nowadays quantum platforms, showing that the above-mentioned correlation functions deviate from theoretical prediction as the number of qubits and the depth of the circuit grow.
  arXiv  Detail & Related papers  (2021-09-06T14:35:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.