New aspects of quantum topological data analysis: Betti number estimation, and testing and tracking of homology and cohomology classes

• URL: http://arxiv.org/abs/2506.01432v3
• Date: Wed, 05 Nov 2025 07:25:53 GMT
• Title: New aspects of quantum topological data analysis: Betti number estimation, and testing and tracking of homology and cohomology classes
• Authors: Junseo Lee, Nhat A. Nghiem,
• Abstract summary: 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.
• Score: 3.2268950104324965
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present new quantum algorithms for estimating homological invariants, specifically Betti and persistent Betti numbers, of a simplicial complex given through structured classical data. Our approach efficiently constructs block-encodings of (persistent) Laplacians, enabling estimation via stochastic rank methods with complexity polylogarithmic in the number of simplices across both sparse and dense regimes. Unlike prior spectral algorithms that suffer when Betti numbers are small, we introduce homology tracking and property testing techniques achieving exponential speedups under natural sparsity and structure assumptions. We also formulate homology triviality and equivalence testing as property testing problems, giving nearly linear-time quantum algorithms when the boundary rank is large. A cohomological formulation further yields rank-independent testing and polylog-time manipulation of $r$-cocycles via block-encoded projections. These results open a new direction in quantum topological data analysis and demonstrate provable quantum advantages in computing topological invariants.

Related papers

• 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)
• Towards quantum topological data analysis: torsion detection [0.0]
  We introduce a quantum algorithm for torsion detection, that is, determining whether a given simplicial complex contains torsion.<n>Our algorithm, assisted by a low complexity classical procedure, can succeed with high probability and potentially offer exponential speedup.
  arXiv  Detail & Related papers  (2025-08-27T14:59:44Z)
• Hybrid quantum-classical framework for Betti number estimation with applications to topological data analysis [0.7997838571956237]
  Topological data analysis (TDA) is a rapidly growing area that applies techniques from algebraic topology to extract robust features from large-scale data.<n>A key task in TDA is the estimation of (normalized) Betti numbers, which capture essential topological invariants.<n>We explore an alternative direction: combining classical and quantum resources to estimate the Betti numbers of a simplicial complex more efficiently.
  arXiv  Detail & Related papers  (2025-08-02T23:19:11Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Alternative Method for Estimating Betti Numbers [0.0]
  We provide an alternative method for estimating Betti numbers and normalized Betti numbers of given simplicial complex. Our method can be faster than the best-known classical method for finding Betti numbers. Our method could match the running time of best-known quantum method in the case of dense simplices.
  arXiv  Detail & Related papers  (2024-03-07T17:32:42Z)
• A Quantum-Classical Collaborative Training Architecture Based on Quantum State Fidelity [50.387179833629254]
  We introduce a collaborative classical-quantum architecture called co-TenQu. Co-TenQu enhances a classical deep neural network by up to 41.72% in a fair setting. It outperforms other quantum-based methods by up to 1.9 times and achieves similar accuracy while utilizing 70.59% fewer qubits.
  arXiv  Detail & Related papers  (2024-02-23T14:09:41Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• Higher-order topological kernels via quantum computation [68.8204255655161]
  Topological data analysis (TDA) has emerged as a powerful tool for extracting meaningful insights from complex data. We propose a quantum approach to defining Betti kernels, which is based on constructing Betti curves with increasing order.
  arXiv  Detail & Related papers  (2023-07-14T14:48:52Z)
• Quantum-Enhanced Topological Data Analysis: A Peep from an Implementation Perspective [22.137388773023854]
  This paper presents an implementation of one such algorithm for calculating Betti numbers. The step-by-step instructions for the chosen quantum algorithm and the aspects of how it can be used for machine learning tasks are provided. We provide encouraging results on using Betti numbers for classification and give a preliminary analysis of the effect of the number of shots and precision qubits on the outcome of the quantum algorithm.
  arXiv  Detail & Related papers  (2023-02-19T12:18:13Z)
• QuanGCN: Noise-Adaptive Training for Robust Quantum Graph Convolutional Networks [124.7972093110732]
  We propose quantum graph convolutional networks (QuanGCN), which learns the local message passing among nodes with the sequence of crossing-gate quantum operations. To mitigate the inherent noises from modern quantum devices, we apply sparse constraint to sparsify the nodes' connections. Our QuanGCN is functionally comparable or even superior than the classical algorithms on several benchmark graph datasets.
  arXiv  Detail & Related papers  (2022-11-09T21:43:16Z)
• 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)
• A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits [5.478764356647437]
  We present an improved quantum algorithm for computing persistent Betti numbers. We discuss whether quantum algorithms can achieve an exponential speedup for tasks of practical interest.
  arXiv  Detail & Related papers  (2022-09-26T17:56:11Z)
• Understanding the Mapping of Encode Data Through An Implementation of Quantum Topological Analysis [0.7106986689736827]
  We show the difference in encoding techniques can be visualized by investigating the topology of the data embedded in complex Hilbert space. Our results suggest the encoding method needs to be considered carefully within different quantum machine learning models.
  arXiv  Detail & Related papers  (2022-09-21T18:46:08Z)
• Quantum algorithm for persistent Betti numbers and topological data analysis [0.0]
  This paper shows the first quantum algorithm that can estimate the persistent Betti numbers of arbitrary dimensions. Our algorithm is efficient for simplicial complexes such as the Vietoris-Rips complex and demonstrates exponential speedup over the known classical algorithms.
  arXiv  Detail & Related papers  (2021-10-31T09:02:01Z)
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
  We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression. We argue that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise.
  arXiv  Detail & Related papers  (2020-11-09T01:13:07Z)
• A Constraint-Based Algorithm for the Structural Learning of Continuous-Time Bayesian Networks [70.88503833248159]
  We propose the first constraint-based algorithm for learning the structure of continuous-time Bayesian networks. We discuss the different statistical tests and the underlying hypotheses used by our proposal to establish conditional independence.
  arXiv  Detail & Related papers  (2020-07-07T07:34:09Z)

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.