Quantum Distance Approximation for Persistence Diagrams
- URL: http://arxiv.org/abs/2402.17295v1
- Date: Tue, 27 Feb 2024 08:16:17 GMT
- Title: Quantum Distance Approximation for Persistence Diagrams
- Authors: Bernardo Ameneyro, Rebekah Herrman, George Siopsis, Vasileios Maroulas
- Abstract summary: We explore the potential of quantum computers to estimate the distance between persistence diagrams.
We propose variational quantum algorithms for the Wasserstein distance as well as the $dc_p$ distance.
- Score: 1.0992151305603266
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Topological Data Analysis methods can be useful for classification and
clustering tasks in many different fields as they can provide two dimensional
persistence diagrams that summarize important information about the shape of
potentially complex and high dimensional data sets. The space of persistence
diagrams can be endowed with various metrics such as the Wasserstein distance
which admit a statistical structure and allow to use these summaries for
machine learning algorithms. However, computing the distance between two
persistence diagrams involves finding an optimal way to match the points of the
two diagrams and may not always be an easy task for classical computers. In
this work we explore the potential of quantum computers to estimate the
distance between persistence diagrams, in particular we propose variational
quantum algorithms for the Wasserstein distance as well as the $d^{c}_{p}$
distance. Our implementation is a weighted version of the Quantum Approximate
Optimization Algorithm that relies on control clauses to encode the constraints
of the optimization problem.
Related papers
- Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing [93.83016310295804]
AQCs allow to implement problems of research interest, which has sparked the development of quantum representations for computer vision tasks.
In this work, we explore the potential of using this information for probabilistic balanced k-means clustering.
Instead of discarding non-optimal solutions, we propose to use them to compute calibrated posterior probabilities with little additional compute cost.
This allows us to identify ambiguous solutions and data points, which we demonstrate on a D-Wave AQC on synthetic tasks and real visual data.
arXiv Detail & Related papers (2023-10-18T17:59:45Z) - Quantum Algorithm for Computing Distances Between Subspaces [0.0]
We provide a quantum algorithm for estimating two kinds of distance: Grassmann distance and ellipsoid distance.
Some extensions regarding estimating different kinds of distance are then discussed as a corollary of our main quantum algorithmic method.
arXiv Detail & Related papers (2023-08-29T16:46:20Z) - A Topological Distance Measure between Multi-Fields for Classification
and Analysis of Shapes and Data [0.0]
We propose an improved distance measure between two multi-fields by computing a multi-dimensional Reeb graph (MDRG)
A hierarchy of persistence diagrams is then constructed by computing a persistence diagram corresponding to each Reeb graph of the MDRG.
We show that the proposed measure satisfies the pseudo-metric and stability properties.
arXiv Detail & Related papers (2023-03-06T05:38:13Z) - Linearized Wasserstein dimensionality reduction with approximation
guarantees [65.16758672591365]
LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space.
We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size.
We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
arXiv Detail & Related papers (2023-02-14T22:12:16Z) - End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
We provide a complete quantum circuit-level description of the algorithm from problem input to problem output.
We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
arXiv Detail & Related papers (2022-11-22T18:54:48Z) - Benchmarking Small-Scale Quantum Devices on Computing Graph Edit
Distance [52.77024349608834]
Graph Edit Distance (GED) measures the degree of (dis)similarity between two graphs in terms of the operations needed to make them identical.
In this paper we present a comparative study of two quantum approaches to computing GED.
arXiv Detail & Related papers (2021-11-19T12:35:26Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$.
This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
arXiv Detail & Related papers (2021-06-11T09:43:09Z) - A Domain-Oblivious Approach for Learning Concise Representations of
Filtered Topological Spaces [7.717214217542406]
We propose a persistence diagram hashing framework that learns a binary code representation of persistence diagrams.
This framework is built upon a generative adversarial network (GAN) with a diagram distance loss function to steer the learning process.
Our proposed method is directly applicable to various datasets without the need of retraining the model.
arXiv Detail & Related papers (2021-05-25T20:44:28Z) - Quantum Algorithms for Data Representation and Analysis [68.754953879193]
We provide quantum procedures that speed-up the solution of eigenproblems for data representation in machine learning.
The power and practical use of these subroutines is shown through new quantum algorithms, sublinear in the input matrix's size, for principal component analysis, correspondence analysis, and latent semantic analysis.
Results show that the run-time parameters that do not depend on the input's size are reasonable and that the error on the computed model is small, allowing for competitive classification performances.
arXiv Detail & Related papers (2021-04-19T00:41:43Z) - Quantum Robust Fitting [43.28199403216451]
Many computer vision applications need to recover structure from imperfect measurements of the real world.
The task is often solved by robustly fitting a geometric model onto noisy and outlier-contaminated data.
In this paper, we explore the usage of quantum computers for robust fitting.
arXiv Detail & Related papers (2020-06-12T08:00:55Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.