There is heightened interest in quantum algorithms for Topological Data Analysis (TDA) as it is a powerful tool for data analysis, but it can get highly computationally expensive. Even though there are different propositions and observations for Quantum Topological Data Analysis (QTDA), the necessary details to implement them on software platforms are lacking. Towards closing this gap, the present 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.
There is heightened interest in quantum algorithms for Topological Data Analysis (TDA) as it is a powerful tool for data analysis, but it can get highly computationally expensive. Even though there are different propositions and observations for Quantum Topological Data Analysis (QTDA), the necessary details to implement them on software platforms are lacking. Towards closing this gap, the present 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.
Topological data analysis (TDA) has emerged as a powerful tool for extracting meaningful insights from complex data. TDA enhances the analysis of objects by embedding them into a simplicial complex and extracting useful global properties such as the Betti numbers, i.e. the number of multidimensional holes, which can be used to define kernel methods that are easily integrated with existing machine-learning algorithms. These kernel methods have found broad applications, as they rely on powerful mathematical frameworks which provide theoretical guarantees on their performance. However, the computation of higher-dimensional Betti numbers can be prohibitively expensive on classical hardware, while quantum algorithms can approximate them in polynomial time in the instance size. In this work, we propose a quantum approach to defining topological kernels, which is based on constructing Betti curves, i.e. topological fingerprint of filtrations with increasing order. We exhibit a working prototype of our approach implemented on a noiseless simulator and show its robustness by means of some empirical results suggesting that topological approaches may offer an advantage in quantum machine learning.
Topological Data Analysis (TDA) is a powerful but computationally expensive tool for data analysis. Quantum Topological Data Analysis (QTDA) promises to reduce this cost while giving comparable results. This paper explores using QTDA for quantum machine learning (QML) and provides a pipeline for QML where QTDA's quantum state output is fed to the QML module. We also show how reduced Hamiltonians can be used to recover most of the performance for machine learning while using much fewer resources in terms of the number of qubits, depth, and gate counts.
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.
Abstract Topological Data Analysis (TDA) is a well-established field derived to give insight into the geometric structure of real-world data. However, many methods in TDA are computationally intensive. The method that computes the respective Betti number has been shown to obtain a speed-up from translating the algorithm into a quantum circuit. The quantum circuit to calculate a particular Betti number requires a significant number of gates and, without a small record of data, is currently unable to be implemented on a NISQ-era processor. Given this NISQ-era restriction, a hybrid-method is proposed that calculates the Euclidean distance of the encoded data and computes the desired Betti number. This method is applied to a toy data set with different encoding techniques. The empirical results show the noise within the data is intensified with each encoding method as there is a clear change in the geometric structure of the original data, exhibiting information loss.
Topological data analysis (TDA) provides a powerful framework for extracting information about the shape of complex, unstructured data, but the classical cost of computing high dimensional topological features limits its application. Quantum algorithms for TDA offer a route around this bottleneck, yet existing approaches typically focus on exact or high precision Betti number estimation, making the regime for practical quantum advantage appear narrow. Here, we instead frame quantum TDA as a feature-extraction method for downstream data analysis by extracting low-order spectral information from the combinatorial Laplacian as a proxy for high-dimensional topology.
We support this perspective from both the application and algorithmic sides. First, we show that higher-order TDA features improve predictive performance in two time-series applications: functional MRI analysis for neurodegenerative disease classification and financial time-series analysis for identifying market instability. Second, we develop a moment-based quantum algorithm and show that low-order moments, including the relative trace, are strongly correlated with high-dimensional Betti information, even when the relative Betti number is small. Finally, we present circuit constructions, resource estimates, quantum-classical crossover projections, and experimental results from a Barium development system similar to the forthcoming IonQ Tempo line, extracting Laplacian-derived observables from graph instances and quantitatively comparing them with exact Betti information.
Together, these results establish quantum TDA as a practical approach for extracting topological features from classically challenging data
Quantum computing offers the potential of exponential speedups for certain classical computations. Over the last decade, many quantum machine learning (QML) algorithms have been proposed as candidates for such exponential improvements. However, two issues unravel the hope of exponential speedup for some of these QML algorithms: the data-loading problem and, more recently, the stunning dequantization results of Tang et al. A third issue, namely the fault-tolerance requirements of most QML algorithms, has further hindered their practical realization. The quantum topological data analysis (QTDA) algorithm of Lloyd, Garnerone and Zanardi was one of the first QML algorithms that convincingly offered an expected exponential speedup. From the outset, it did not suffer from the data-loading problem. A recent result has also shown that the generalized problem solved by this algorithm is likely classically intractable, and would therefore be immune to any dequantization efforts. However, the QTDA algorithm of Lloyd et~al. has a time complexity of O(n4/(ε2δ)) (where n is the number of data points, ε is the error tolerance, and δ is the smallest nonzero eigenvalue of the restricted Laplacian) and requires fault-tolerant quantum computing, which has not yet been achieved. In this paper, we completely overhaul the QTDA algorithm to achieve an improved exponential speedup and depth complexity of O(nlog(1/(δε))). Our approach includes three key innovations: (a) an efficient realization of the combinatorial Laplacian as a sum of Pauli operators; (b) a quantum rejection sampling approach to restrict the superposition to the simplices in the complex; and (c) a stochastic rank estimation method to estimate the Betti numbers. We present a theoretical error analysis, and the circuit and computational time and depth complexities for Betti number estimation.