Quantum Topological Data Analysis for Anomaly Detection

Author / Creator

Quantum 2020 (2020)

Conferences

Quantum 2020 P6: Quantum technology in industry (2020)

Available as

Online

Summary

The initial research undertaken was aimed at examining the feasibility of adapting and implementing Topological Data Analysis (TDA) methods using Persistent Homology to meet requirements in the tel...

The initial research undertaken was aimed at examining the feasibility of adapting and implementing Topological Data Analysis (TDA) methods using Persistent Homology to meet requirements in the telecom domain. Persistent Homology based methods are especially useful in detecting anomalies in time series data and show good prospects of being useful in telecom network alarm data. Here, the special interest to this technique is a metric called the Wasserstein Distance, which shows how much two persistence diagrams correspondingly differ from one another. Calculating this metric is a minimum weight maximum matching problem on a bipartite graph. Existing classical methods of calculating the Wasserstein distance show polynomial time complexity O(n power 3). We carried out a quantum study which involved converting this Wasserstein matching problem into a Quadratic Unconstrained Binary Optimization problem and minimizing it using a Quantum Annealer approach. Our final focus on the TDA Wasserstein distance problem is the implementation of an alternate Combinatorial Optimization Quantum Algorithm which should theoretically be faster than existing classical methods, potentially yielding a quantum speedup in detecting anomalies in the future.

Show More