Quantum K-medians Algorithm Using Parallel Euclidean Distance Estimator

• URL: http://arxiv.org/abs/2012.11139v1
• Date: Mon, 21 Dec 2020 06:38:20 GMT
• Title: Quantum K-medians Algorithm Using Parallel Euclidean Distance Estimator
• Authors: Amanuel Tamirat Getachew
• Abstract summary: This paper proposes an efficient quantum k-medians clustering algorithm using the powerful quantum Euclidean estimator algorithm. The proposed quantum k-medians algorithm has provided an exponential speed up as compared to the classical version of it.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum machine learning, though in its initial stage, has demonstrated its potential to speed up some of the costly machine learning calculations when compared to the existing classical approaches. Among the challenging subroutines, computing distance between with the large and high-dimensional data sets by the classical k-medians clustering algorithm is one of them. To tackle this challenge, this paper proposes an efficient quantum k-medians clustering algorithm using the powerful quantum Euclidean estimator algorithm. The proposed quantum k-medians algorithm has provided an exponential speed up as compared to the classical version of it. If and only if we allow the input and the output vectors to be quantum states. The proposed algorithm implementation handled in python with the help of third-party module known as QISKit. The implemented quantum algorithm was executed on the IBM Quantum simulators through cloud. The results from the experiment and simulation suggest that quantum distance estimator algorithms could give benefits for other distance-based machine learning algorithms like k-nearest neighbor classification, support vector machine, hierarchical clustering and k-means clustering. This work sheds light on the bright future of the age of big data making use of exponential speed up provided by quantum theory.

Related papers

• A quantum implementation of high-order power method for estimating geometric entanglement of pure states [39.58317527488534]
  This work presents a quantum adaptation of the iterative higher-order power method for estimating the geometric measure of entanglement of multi-qubit pure states. It is executable on current (hybrid) quantum hardware and does not depend on quantum memory. We study the effect of noise on the algorithm using a simple theoretical model based on the standard depolarising channel.
  arXiv  Detail & Related papers  (2024-05-29T14:40:24Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• 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)
• Quantum jet clustering with LHC simulated data [0.0]
  Two new quantum algorithms might speed up classical jet clustering algorithms. In the first two algorithms, an exponential speed up in dimensionality and data length can be achieved. In the $k_T$ algorithm, a quantum version of the same order as FastJet is achieved.
  arXiv  Detail & Related papers  (2022-09-19T10:51:13Z)
• Variational Quantum and Quantum-Inspired Clustering [0.0]
  We present a quantum algorithm for clustering data based on a variational quantum circuit. The algorithm allows to classify data into many clusters, and can easily be implemented in few-qubit Noisy Intermediate-Scale Quantum (NISQ) devices.
  arXiv  Detail & Related papers  (2022-06-20T17:02:19Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Quantum clustering and jet reconstruction at the LHC [0.0]
  Jet clustering at the CERN's Large Hadron Collider is computationally expensive. We consider two novel quantum algorithms which may speed up the classical jet clustering algorithms.
  arXiv  Detail & Related papers  (2022-04-13T16:27:04Z)
• 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)
• QEML (Quantum Enhanced Machine Learning): Using Quantum Computing to Enhance ML Classifiers and Feature Spaces [0.49841205356595936]
  Machine learning and quantum computing are causing a paradigm shift in the performance and behavior of certain algorithms. This paper first understands the mathematical intuition for the implementation of quantum feature space. We build a noisy variational quantum circuit KNN which mimics the classification methods of a traditional KNN.
  arXiv  Detail & Related papers  (2020-02-22T04:14:32Z)

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.