Computing Wasserstein Distance for Persistence Diagrams on a Quantum Computer
arXiv:1809.06433
Abstract
Persistence diagrams are a useful tool from topological data analysis which can be used to provide a concise description of a filtered topological space. What makes them even more useful in practice is that they come with a notion of a metric, the Wasserstein distance (closely related to but not the same as the homonymous metric from probability theory). Further, this metric provides a notion of stability; that is, small noise in the input causes at worst small differences in the output. In this paper, we show that the Wasserstein distance for persistence diagrams can be computed through quantum annealing. We provide a formulation of the problem as a Quadratic Unconstrained Binary Optimization problem, or QUBO, and prove correctness. Finally, we test our algorithm, exploring parameter choices and problem size capabilities, using a D-Wave 2000Q quantum annealing computer.
References in corpus (13)
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- A roadmap for the computation of persistent homology
- Clique topology reveals intrinsic geometric structure in neural correlations
- A practical heuristic for finding graph minors
- The Theory of the Interleaving Distance on Multidimensional Persistence Modules
- Inference of Ancestral Recombination Graphs through Topological Data Analysis
- Parametric Inference using Persistence Diagrams: A Case Study in Population Genetics
- Homology Computation of Large Point Clouds using Quantum Annealing
- Geometry Helps to Compare Persistence Diagrams
- Quantum topological data analysis with continuous variables
- Dynamics of silo deformation under granular discharge
Cited by in corpus (5)
- A Tutorial on Formulating and Using QUBO Models
- Quantum annealing with twisted fields
- Topological Data Analysis in Text Classification: Extracting Features with Additive Information
- Topological Machine Learning for Mixed Numeric and Categorical Data
- Topological Machine Learning for Multivariate Time Series