Performance analysis of coreset selection for quantum implementation of K-Means clustering algorithm

• URL: http://arxiv.org/abs/2206.07852v1
• Date: Thu, 16 Jun 2022 00:01:48 GMT
• Title: Performance analysis of coreset selection for quantum implementation of K-Means clustering algorithm
• Authors: Fanzhe Qu, Sarah M. Erfani, Muhammad Usman
• Abstract summary: Coreset selection aims to reduce the size of input data without compromising the accuracy. Recent work has shown that coreset selection can help to implement quantum K-Means clustering problem. We compare the relative performance of two coreset techniques, and the size of coreset construction in each case, with respect to a variety of data sets. We also investigated the effect of depolarisation quantum noise and bit-flip error, and implemented the Quantum AutoEncoder technique for surpassing the noise effect.
• Score: 15.84585517821099
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum computing is anticipated to offer immense computational capabilities which could provide efficient solutions to many data science problems. However, the current generation of quantum devices are small and noisy, which makes it difficult to process large data sets relevant for practical problems. Coreset selection aims to circumvent this problem by reducing the size of input data without compromising the accuracy. Recent work has shown that coreset selection can help to implement quantum K-Means clustering problem. However, the impact of coreset selection on the performance of quantum K-Means clustering has not been explored. In this work, we compare the relative performance of two coreset techniques (BFL16 and ONESHOT), and the size of coreset construction in each case, with respect to a variety of data sets and layout the advantages and limitations of coreset selection in implementing quantum algorithms. We also investigated the effect of depolarisation quantum noise and bit-flip error, and implemented the Quantum AutoEncoder technique for surpassing the noise effect. Our work provides useful insights for future implementation of data science algorithms on near-term quantum devices where problem size has been reduced by coreset selection.

Related papers

• Hybrid quantum-classical approach for combinatorial problems at hadron colliders [7.2572969510173655]
  We explore the potential of quantum algorithms to resolve the problems in particle physics experiments. We consider top quark pair production in the fully hadronic channel at the Large Hadron Collider. We show that the efficiency for selecting the correct pairing is greatly improved by utilizing quantum algorithms.
  arXiv  Detail & Related papers  (2024-10-29T18:00:07Z)
• The curse of random quantum data [62.24825255497622]
  We quantify the performances of quantum machine learning in the landscape of quantum data. We find that the training efficiency and generalization capabilities in quantum machine learning will be exponentially suppressed with the increase in qubits. Our findings apply to both the quantum kernel method and the large-width limit of quantum neural networks.
  arXiv  Detail & Related papers  (2024-08-19T12:18:07Z)
• Big data applications on small quantum computers [0.0]
  Coresets allow for a succinct description of large datasets and their solution in a computational task is competitive with the solution on the original dataset. We apply the coreset method in three different well-studied classical machine learning problems, namely Divisive Clustering, 3-means Clustering, and Gaussian Model Clustering. We show that our approach provides comparable performance to classical solvers.
  arXiv  Detail & Related papers  (2024-02-02T16:15:55Z)
• Power Characterization of Noisy Quantum Kernels [52.47151453259434]
  We show that noise may make quantum kernel methods to only have poor prediction capability, even when the generalization error is small. We provide a crucial warning to employ noisy quantum kernel methods for quantum computation.
  arXiv  Detail & Related papers  (2024-01-31T01:02:16Z)
• Neural auto-designer for enhanced quantum kernels [59.616404192966016]
  We present a data-driven approach that automates the design of problem-specific quantum feature maps. Our work highlights the substantial role of deep learning in advancing quantum machine learning.
  arXiv  Detail & Related papers  (2024-01-20T03:11:59Z)
• Clustering by Contour coreset and variational quantum eigensolver [0.8544206632559302]
  We propose solving the k-means clustering problem with the variational quantum eigensolver (VQE) and a customised coreset method, the Contour coreset. Our work has shown that quantum tailored coreset techniques has the potential to significantly boost the performance of quantum algorithms.
  arXiv  Detail & Related papers  (2023-12-06T14:21:17Z)
• 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)
• Iterative Qubits Management for Quantum Index Searching in a Hybrid System [56.39703478198019]
  IQuCS aims at index searching and counting in a quantum-classical hybrid system. We implement IQuCS with Qiskit and conduct intensive experiments. Results demonstrate that it reduces qubits consumption by up to 66.2%.
  arXiv  Detail & Related papers  (2022-09-22T21:54:28Z)
• Quantum spectral clustering algorithm for unsupervised learning [0.8399688944263843]
  We propose a circuit design to implement spectral clustering on a quantum processor with a substantial speedup. Compared with the established quantum $k$-means algorithms, our method does not require a quantum random access memory or a quantum adiabatic process.
  arXiv  Detail & Related papers  (2022-03-07T05:06:47Z)
• Quantum circuit architecture search for variational quantum algorithms [88.71725630554758]
  We propose a resource and runtime efficient scheme termed quantum architecture search (QAS) QAS automatically seeks a near-optimal ansatz to balance benefits and side-effects brought by adding more noisy quantum gates. We implement QAS on both the numerical simulator and real quantum hardware, via the IBM cloud, to accomplish data classification and quantum chemistry tasks.
  arXiv  Detail & Related papers  (2020-10-20T12:06:27Z)
• Coreset Clustering on Small Quantum Computers [3.4075213885825377]
  Recent work by Harrow introduces a new paradigm in hybrid quantum-classical computing. We investigate using this paradigm to perform $k$-means clustering on near-term quantum computers. We find data sets where both coresets and QAOA work well--which is necessary for a quantum advantage over $k$-means on the entire data set--appears to be challenging.
  arXiv  Detail & Related papers  (2020-04-30T17:19:19Z)

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.