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.01432v2
• Date: Mon, 30 Jun 2025 09:08:24 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 show that access to additional topological information enables improved quantum algorithms for estimating Betti numbers.<n>We introduce a new approach based on homology tracking, which avoids computing the kernel of Laplacians.<n>This yields a framework that remains efficient even when Betti numbers are small, offering substantial and sometimes exponential speedups.
• Score: 0.8988769052522807
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The application of quantum computation to topological data analysis (TDA) has received growing attention. While estimating Betti numbers is a central task in TDA, general complexity theoretic limitations restrict the possibility of quantum speedups. To address this, we explore quantum algorithms under a more structured input model. We show that access to additional topological information enables improved quantum algorithms for estimating Betti and persistent Betti numbers. Building on this, we introduce a new approach based on homology tracking, which avoids computing the kernel of combinatorial Laplacians used in prior methods. This yields a framework that remains efficient even when Betti numbers are small, offering substantial and sometimes exponential speedups. Beyond Betti number estimation, we formulate and study the homology property testing problem, and extend our approach to the cohomological setting. We present quantum algorithms for testing triviality and distinguishing homology classes, revealing new avenues for quantum advantage in TDA.

Related papers

• 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)
• 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)

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.