Clustering using Quantum Persistent Homology

R.H.A.J. Meijer

Published Jan 1, 2019• 2 citations

Abstract

Persistent homology is a way to analyse the shape of a dataset rather than its semantics. This is done by assigning the dataset holes in different dimensions, borrowing this theory from the mathematical area of topology. The dataset is treated as being sampled from a topological space, which is in turn approximated at different resolutions. The persistent Betti numbers then count the number of holes in these spaces, registering for how long the holes persist as the resolution increases. Computing such features classically may prove costly, with some steps possibly requiring exponential time. In a 2016 paper, a polynomial time quantum algorithm for the approximation of persistent homology is promised. In this thesis it is shown these methods are generally incapable of uniquely determining the persistent Betti numbers in arbitrary dimensions. The algorithm does succeed in the zeroth dimension. After treating the prerequisites, the methods from this paper are explained, the above statements are proven, and finally the quantum algorithm is related to agglomerative hierarchical clustering and spectral clustering.

Related papers

Quantum algorithms for topological and geometric analysis of data

Seth Lloyd, Silvano Garnerone, Paolo Zanardi A

Extracting useful information from large data sets can be a daunting task. Topological methods for analysing data sets provide a powerful technique for extracting such information. Persistent homology is a sophisticated tool for identifying topological features and for determining how such features persist as the data is viewed at different scales. Here we present quantum machine learning algorithms for calculating Betti numbers--the numbers of connected components, holes and voids--in persistent homology, and for finding eigenvectors and eigenvalues of the combinatorial Laplacian. The algorithms provide an exponential speed-up over the best currently known classical algorithms for topological data analysis.

Nature CommunicationsJan 25, 2016241 citations

Quantum algorithms for topological and geometric analysis of big data

Seth Lloyd, Silvano Garnerone, Paolo Zanardi A

Extracting useful information from large data sets can be a daunting task. Topological methods for analyzing data sets provide a powerful technique for extracting such information. Persistent homology is a sophisticated tool for identifying such topological features -- connected components, holes, or voids -- and for determining how such features persist as the data is viewed at different scales. This paper provides quantum algorithms for calculating Betti numbers in persistent homology, and for finding eigenvectors and eigenvalues of the combinatorial Laplacian. The algorithms provide an exponential speedup over classical algorithms for topological data analysis.

arXiv:1408.3106Aug 13, 201411 citations

Limitations of Clustering Using Quantum Persistent Homology

Niels M. P. Neumann, Sterre den Breeijen

Different algorithms can be used for clustering purposes with data sets. On of these algorithms, uses topological features extracted from the data set to base the clusters on. The complexity of this algorithm is however exponential in the number of data points. Recently a quantum algorithm was proposed by Lloyd Garnerone and Zanardi with claimed polynomial complexity, hence an exponential improved over classical algorithms. However, we show that this algorithm in general cannot be used to compute these topological features in any dimension but the zeroth. We also give pointers on how to still use the algorithm for clustering purposes.

arXiv:1911.10781Nov 25, 20193 citations

Quantum algorithm for persistent Betti numbers and topological data analysis

Ryu Hayakawa

Topological data analysis (TDA) is an emergent field of data analysis. The critical step of TDA is computing the persistent Betti numbers. Existing classical algorithms for TDA are limited if we want to learn from high-dimensional topological features because the number of high-dimensional simplices grows exponentially in the size of the data. In the context of quantum computation, it has been previously shown that there exists an efficient quantum algorithm for estimating the Betti numbers even in high dimensions. However, the Betti numbers are less general than the persistent Betti numbers, and there have been no quantum algorithms that can estimate the persistent Betti numbers of arbitrary dimensions. This paper shows the first quantum algorithm that can estimate the (normalized) 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:2111.00433QuantumDec 7, 202240 citations

Quantum Persistent Homology for Time Series

Bernardo Ameneyro, George Siopsis, Vasileios Maroulas

Persistent homology, a powerful mathematical tool for data analysis, summarizes the shape of data through tracking topological features across changes in different scales. Classical algorithms for persistent homol-ogy are often constrained by running times and mem-ory requirements that grow exponentially on the number of data points. To surpass this problem, two quantum algorithms of persistent homology have been developed based on two different approaches. However, both of these quantum algorithms consider a data set in the form of a point cloud, which can be restrictive considering that many data sets come in the form of time series. In this paper, we alleviate this issue by establishing a quantum Takens's delay embedding algorithm, which turns a time series into a point cloud by considering a pertinent embedding into a higher dimensional space. Having this quantum transformation of time series to point clouds, then one may use a quantum persistent homology algorithm to extract the topological features from the point cloud associated with the original times series.

arXiv:2211.04465IEEE/ACM Symposium on Edge Computing (SEC)Dec 1, 202211 citations

From Betti Numbers to Persistence Diagrams: A Hybrid Quantum Algorithm for Topological Data Analysis

Dong Liu

Persistence diagrams serve as a core tool in topological data analysis, playing a crucial role in pathological monitoring, drug discovery, and materials design. However, existing quantum topological algorithms, such as the LGZ algorithm, can only efficiently compute summary statistics like Betti numbers, failing to provide persistence diagram information that tracks the lifecycle of individual topological features, severely limiting their practical value. This paper proposes a novel quantum-classical hybrid algorithm that achieves, for the first time, the leap from "quantum computation of Betti numbers" to "quantum acquisition of practical persistence diagrams." The algorithm leverages the LGZ quantum algorithm as an efficient feature extractor, mining the harmonic form eigenvectors of the combinatorial Laplacian as well as Betti numbers, constructing specialized topological kernel functions to train a quantum support vector machine (QSVM), and learning the mapping from quantum topological features to persistence diagrams. The core contributions of this algorithm are: (1) elevating quantum topological computation from statistical summaries to pattern recognition, greatly expanding its application value; (2) obtaining more practical topological information in the form of persistence diagrams for real-world applications while maintaining the exponential speedup advantage of quantum computation; (3) proposing a novel hybrid paradigm of "classical precision guiding quantum efficiency." This method provides a feasible pathway for the practical implementation of quantum topological data analysis.

quant-pharXiv:2512.02081Dec 2, 20250 citations