Quantum Distance Approximation for Persistence Diagrams

• URL: http://arxiv.org/abs/2402.17295v2
• Date: Fri, 30 Aug 2024 17:36:49 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.0062127381149395
• 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

• A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
  The proposed method introduces a Quantum Genetic Algorithm (QGA) using a Grover-based evolutionary framework and divide-and-conquer principles. On complete graphs, the proposed method consistently achieves the true optimal MaxCut values, outperforming the Semidefinite Programming (SDP) approach. On ErdHos-R'enyi random graphs, the QGA demonstrates competitive performance, achieving median solutions within 92-96% of the SDP results.
  arXiv  Detail & Related papers  (2025-01-02T05:06:16Z)
• GSSF: Generalized Structural Sparse Function for Deep Cross-modal Metric Learning [51.677086019209554]
  We propose a Generalized Structural Sparse to capture powerful relationships across modalities for pair-wise similarity learning. The distance metric delicately encapsulates two formats of diagonal and block-diagonal terms. Experiments on cross-modal and two extra uni-modal retrieval tasks have validated its superiority and flexibility.
  arXiv  Detail & Related papers  (2024-10-20T03:45:50Z)
• Approximation Theory, Computing, and Deep Learning on the Wasserstein Space [0.5735035463793009]
  We address the challenge of approximating functions in infinite-dimensional spaces from finite samples. Our focus is on the Wasserstein distance function, which serves as a relevant example. We adopt three machine learning-based approaches to define functional approximants.
  arXiv  Detail & Related papers  (2023-10-30T13:59:47Z)
• 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)

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.