Quantum density peak clustering

• URL: http://arxiv.org/abs/2207.10559v1
• Date: Thu, 21 Jul 2022 15:58:40 GMT
• Title: Quantum density peak clustering
• Authors: Duarte Magano, Lorenzo Buffoni, Yasser Omar
• Abstract summary: We introduce a quantum version of the density peak clustering algorithm, built upon a quantum routine for minimum finding. We prove a quantum speedup for a decision version of density peak clustering depending on the structure of the dataset.
• Score: 5.8010446129208155
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Clustering algorithms are of fundamental importance when dealing with large unstructured datasets and discovering new patterns and correlations therein, with applications ranging from scientific research to medical imaging and marketing analysis. In this work, we introduce a quantum version of the density peak clustering algorithm, built upon a quantum routine for minimum finding. We prove a quantum speedup for a decision version of density peak clustering depending on the structure of the dataset. Specifically, the speedup is dependent on the heights of the trees of the induced graph of nearest-highers, i.e., the graph of connections to the nearest elements with higher density. We discuss this condition, showing that our algorithm is particularly suitable for high-dimensional datasets. Finally, we benchmark our proposal with a toy problem on a real quantum device.

Related papers

• qLUE: A Quantum Clustering Algorithm for Multi- Dimensional Datasets [0.6597195879147555]
  qLUE is a quantum clustering algorithm that scales linearly in both the number of points and their density. We show that qLUE is a promising route to handle complex data analysis tasks.
  arXiv  Detail & Related papers  (2024-06-29T08:10:09Z)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
  arXiv  Detail & Related papers  (2024-06-11T04:40:05Z)
• Quantization of Large Language Models with an Overdetermined Basis [73.79368761182998]
  We introduce an algorithm for data quantization based on the principles of Kashin representation. Our findings demonstrate that Kashin Quantization achieves competitive or superior quality in model performance.
  arXiv  Detail & Related papers  (2024-04-15T12:38:46Z)
• Quantum topological data analysis via the estimation of the density of states [17.857341127079305]
  We develop a quantum topological data analysis protocol based on the estimation of the density of states (DOS) of the Laplacian. We test our protocol on noiseless and noisy quantum simulators and run examples on IBM quantum processors.
  arXiv  Detail & Related papers  (2023-12-12T09:43:04Z)
• NISQ-friendly measurement-based quantum clustering algorithms [0.7373617024876725]
  Two novel measurement-based, quantum clustering algorithms are proposed. The first algorithm follows a divisive approach, the second is based on unsharp measurements. Both algorithms are simplistic in nature, easy to implement, and well suited for noisy intermediate scale quantum computers.
  arXiv  Detail & Related papers  (2023-02-01T16:38:27Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• QuanGCN: Noise-Adaptive Training for Robust Quantum Graph Convolutional Networks [124.7972093110732]
  We propose quantum graph convolutional networks (QuanGCN), which learns the local message passing among nodes with the sequence of crossing-gate quantum operations. To mitigate the inherent noises from modern quantum devices, we apply sparse constraint to sparsify the nodes' connections. Our QuanGCN is functionally comparable or even superior than the classical algorithms on several benchmark graph datasets.
  arXiv  Detail & Related papers  (2022-11-09T21:43:16Z)
• Density-Based Clustering with Kernel Diffusion [59.4179549482505]
  A naive density corresponding to the indicator function of a unit $d$-dimensional Euclidean ball is commonly used in density-based clustering algorithms. We propose a new kernel diffusion density function, which is adaptive to data of varying local distributional characteristics and smoothness.
  arXiv  Detail & Related papers  (2021-10-11T09:00:33Z)
• Quantum information spreading in a disordered quantum walk [50.591267188664666]
  We design a quantum probing protocol using Quantum Walks to investigate the Quantum Information spreading pattern. We focus on the coherent static and dynamic disorder to investigate anomalous and classical transport. Our results show that a Quantum Walk can be considered as a readout device of information about defects and perturbations occurring in complex networks.
  arXiv  Detail & Related papers  (2020-10-20T20:03:19Z)
• A Quantum Graph Neural Network Approach to Particle Track Reconstruction [1.087475836765689]
  We present an improved model with an iterative approach to overcome the low accuracy of the initial oversimplified Tree Network (TTN) model. We aim to leverage the capability of quantum computing to evaluate a very large number of states simultaneously and thus to effectively search a large parameter space.
  arXiv  Detail & Related papers  (2020-07-14T07:25:24Z)
• High-Dimensional Similarity Search with Quantum-Assisted Variational Autoencoder [3.6704555687356644]
  Quantum machine learning is touted as a potential approach to demonstrate quantum advantage. We show how to construct a space-efficient search index based on the latent space representation of a QVAE. We find real-world speedups compared to linear search and demonstrate memory-efficient scaling to half a billion data points.
  arXiv  Detail & Related papers  (2020-06-13T16:55:23Z)

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.