Hybrid quantum-classical framework for Betti number estimation with applications to topological data analysis

Nhat A. Nghiem, Junseo Lee, Tzu-Chieh Wei · 2025

Read Hybrid quantum-classical framework for Betti number estimation with applications to topological data analysis by Nhat A. Nghiem, Junseo Lee, Tzu-Chieh Wei (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-01516.txt.

Introduction

Nghiem and co-authors blend classical and quantum computing to measure the shape of data. Their target is Betti numbers, counts that describe holes and voids in a shape built from data points. Such counts help analysts find sturdy patterns in large data sets, a field called topological data analysis.

In their scheme, a normal computer first lists all the building blocks of the shape. A quantum routine then estimates the Betti numbers from that list. The team analyzes when this split beats purely quantum methods, finding speed gains from polynomial to exponential in some regimes. The cost is extra helper qubits. They close by showing uses for the normalized counts in real analysis tasks.

Catalog record

CREATORNhat A. Nghiem, Junseo Lee, Tzu-Chieh Wei
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE53 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-01516

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Hybrid quantum-classical framework for Betti number estimation with applications to topological data analysis Nhat A. Nghiem, Junseo Lee, Tzu-Chieh Wei Abstract Topological data analysis (TDA) is a rapidly growing area that applies techniques from algebraic topology to extract robust features from large-scale data. A key task in TDA is the estimation of (normalized) Betti numbers, which capture essential topological invariants. While recent work has led to quantum algorithms for this problem, we explore an alternative direction: combining classical and quantum resources to estimate the Betti numbers of a simplicial complex more efficiently. Assuming the classical description of a simplicial complex—namely, its set of vertices and edges—we propose a hybrid quantum-classical algorithm. The classical component enumerates all simplices, and this combinatorial structure is subsequently processed by a quantum algorithm to estimate the Betti numbers. We analyze the performance of our approach and identify regimes where it potentially achieves polynomial to exponential speedups over existing quantum methods, at the trade-off of using more ancilla qubits. We further demonstrate the utility of normalized Betti numbers in concrete applications, highlighting the broader potential of hybrid quantum algorithms in topological data analysis. I Introduction Recently, there has been a surge of interest in applying quantum computation to topological data analysis (TDA) , a field now often referred to as quantum TDA . TDA offers a mathematically principled framework, rooted in algebraic topology, for extracting robust and interpretable features from complex datasets wasserman2016topological . It typically begins with data represented as point clouds or graphs, from which higher-order simplices are formed based on pairwise relationships. By identifying cliques (i.e., fully connected subgraphs) with simplices, one obtains a combinatorial object known as a simplicial complex . The topological structure of such a complex can then be analyzed through Betti numbers , computed via homology theory. Despite the conceptual elegance of this framework, TDA often suffers from severe computational overhead, particularly in large-scale settings. In a seminal work, Lloyd, Garnerone, and Zanardi lloyd2016quantum introduced a quantum algorithm for estimating Betti numbers, now commonly referred to as the LGZ algorithm. Their approach incorporates several foundational quantum subroutines, including Grover’s search grover1996fast , quantum phase estimation kitaev1995quantum , and Hamiltonian simulation berry2007efficient ; berry2012black . This work initiated a line of research investigating quantum advantages in topological inference. Subsequent studies have extended and refined the LGZ framework, both algorithmically and structurally ubaru2021quantum ; berry2024analyzing ; hayakawa2022quantum ; mcardle2022streamlined . Despite the promise of these developments, recent complexity-theoretic results suggest significant limitations. It was shown in schmidhuber2022complexity that estimating Betti numbers is NP-hard, and that computing them exactly is #P-hard. Consequently, any efficient classical or quantum algorithm that estimates Betti numbers from a simplicial complex specified by vertices and edges would imply a polynomial-time solution to an NP-hard problem. This outcome is widely considered implausible under standard complexity assumptions. Furthermore, it was previously established in crichigno2024clique that computing Betti numbers is QMA-hard, further reinforcing the theoretical intractability of the task. In addition, the work mcardle2022streamlined provides a comprehensive practical evaluation, concluding that exponential quantum speedups for this problem are unlikely for generic input instances. These insights motivate a re-examination of the quantum TDA landscape. In this work, we propose an alternative perspective in which quantum and classical resources are integrated, each contributing their respective strengths toward solving topological inference problems. Our framework is based on the following key observations: • Existing quantum algorithms for estimating Betti numbers lloyd2016quantum ; berry2024analyzing ; mcardle2022streamlined ; hayakawa2022quantum ; nghiem2023quantum ; lee2025new rely on input models such as quantum oracles, quantum RAM (as suggested in lloyd2016quantum ), or structured data matrices encoding the simplicial complex. However, the feasibility and practical relevance of these models remain unclear in many applications. • The efficiency of LGZ-type algorithms lloyd2016quantum ; berry2024analyzing ; mcardle2022streamlined ; hayakawa2022quantum generally improves in simplex-dense regimes, where the number of simplices is large. In contrast, real-world datasets often give rise to sparse complexes, where these algorithms exhibit poor scalability and may incur polynomial or exponential runtimes. • If estimating Betti numbers from the graph-level description of a complex (i.e., vertex and edge lists) offers no quantum advantage, then it is natural to investigate whether quantum speedups may emerge in an earlier stage, such as the acquisition or construction of the complex itself. Guided by these considerations, we adopt the setting in which the input is given as classical graph data , namely, a list of vertices and edges describing the 1-skeleton of the simplicial complex. With respect to the second observation, we introduce a hybrid classical-quantum algorithm that achieves improved performance in the clique-sparse regime. In support of the third point, we identify concrete instances from olsthoorn2023persistent ; hamilton2024probing where quantum algorithms allow for exponential improvements in constructing the underlying graph structure. These cases fall within the domain of applicability of our proposed method. Organization. The remainder of this paper is organized as follows. In Section II , we present our main result: a hybrid classical-quantum algorithm for estimating Betti numbers. Section II.1 describes the input model and the underlying assumptions. Section II.2 outlines the classical subroutine used to generate a simplicial complex from graph data. In Section II.3 , we describe the quantum subroutine for estimating Betti numbers. This section includes a formal description of our method in Algorithm 1 , along with a statement of the main result in Theorem 1 . Section III offers a detailed comparison between our hybrid algorithm and previous quantum approaches, emphasizing the scenarios in which our method provides a computational advantage. Section IV presents several concrete applications where the hybrid algorithm can be effectively employed. Appendix A contains a summary of the quantum techniques used in our algorithm. Appendix B provides a self-contained overview of relevant concepts from algebraic topology, intended for readers unfamiliar with the mathematical background. II Hybrid algorithm for estimating Betti numbers for sparse complex II.1 Input model We consider a classical input model in which the simplicial complex of interest is specified by the underlying graph that encodes its pairwise adjacency. Formally, we are given a finite set of vertices (0-simplices), along with classical information describing which unordered pairs of vertices form edges (1-simplices). This graph representation corresponds to the so-called 1-skeleton of the simplicial complex, which consists solely of its vertices and edges, excluding any higher-dimensional simplices such as triangles (2-simplices) or tetrahedra (3-simplices). Our setting is similar in spirit to that of the LGZ algorithm and related approaches. However, a key distinction lies in the input access model: we do not assume a quantum oracle that encodes pairwise connectivity. Instead, the entire 1-skeleton is provided explicitly as classical data. II.2 Classical algorithm for specifying the complex Given the pairwise adjacency information from the input graph, we can efficiently identify higher-dimensional simplices by enumerating cliques of specified sizes. The following result is central to this procedure: Lemma 1 (Clique enumeration via arboricity chiba1985arboricity ) . Let \mathcal{G}=(V,E) be an undirected graph, where V denotes the set of vertices and E the set of edges. Then there exists a classical algorithm that enumerates all (r{+}1) -cliques in \mathcal{G} with running time \mathcal{O}\left(|E|\cdot\alpha(\mathcal{G})^{r-1}\right) , where \alpha(\mathcal{G}) is the arboricity of the graph, defined as the minimum number of forests into which the edge

Read the complete text