Quantum spectral clustering algorithm for unsupervised learning
- URL: http://arxiv.org/abs/2203.03132v2
- Date: Fri, 10 Jun 2022 09:41:53 GMT
- Title: Quantum spectral clustering algorithm for unsupervised learning
- Authors: Qingyu Li, Yuhan Huang, Shan Jin, Xiaokai Hou, Xiaoting Wang
- Abstract summary: 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.
- Score: 0.8399688944263843
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Clustering is one of the most crucial problems in unsupervised learning, and
the well-known $k$-means clustering algorithm has been shown to be
implementable on a quantum computer with a significant speedup. However, many
clustering problems cannot be solved by $k$-means, and a powerful method called
spectral clustering is introduced to solve these problems. In this work, we
propose a circuit design to implement spectral clustering on a quantum
processor with a substantial speedup, by initializing the processor into a
maximally entangled state and encoding the data information into an
efficiently-simulatable Hamiltonian. Compared with the established quantum
$k$-means algorithms, our method does not require a quantum random access
memory or a quantum adiabatic process. It relies on an appropriate embedding of
quantum phase estimation into Grover's search to gain the quantum speedup.
Simulations demonstrate that our method is effective in solving clustering
problems and will serve as an important supplement to quantum $k$-means for
unsupervised learning.
Related papers
- 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) - 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) - 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) - Efficient algorithms for quantum information bottleneck [64.67104066707309]
We propose a new and general algorithm for the quantum generalisation of information bottleneck.
Our algorithm excels in the speed and the definiteness of convergence compared with prior results.
Notably, we discover that a quantum system can achieve strictly better performance than a classical system of the same size regarding quantum information bottleneck.
arXiv Detail & Related papers (2022-08-22T14:20:05Z) - 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) - Quantum circuit debugging and sensitivity analysis via local inversions [62.997667081978825]
We present a technique that pinpoints the sections of a quantum circuit that affect the circuit output the most.
We demonstrate the practicality and efficacy of the proposed technique by applying it to example algorithmic circuits implemented on IBM quantum machines.
arXiv Detail & Related papers (2022-04-12T19:39:31Z) - Quantum Federated Learning with Quantum Data [87.49715898878858]
Quantum machine learning (QML) has emerged as a promising field that leans on the developments in quantum computing to explore large complex machine learning problems.
This paper proposes the first fully quantum federated learning framework that can operate over quantum data and, thus, share the learning of quantum circuit parameters in a decentralized manner.
arXiv Detail & Related papers (2021-05-30T12:19:27Z) - Quantum K-medians Algorithm Using Parallel Euclidean Distance Estimator [0.0]
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.
arXiv Detail & Related papers (2020-12-21T06:38:20Z) - Robustness Verification of Quantum Classifiers [1.3534683694551501]
We define a formal framework for the verification and analysis of quantum machine learning algorithms against noises.
A robust bound is derived and an algorithm is developed to check whether or not a quantum machine learning algorithm is robust with respect to quantum training data.
Our approach is implemented on Google's Quantum classifier and can verify the robustness of quantum machine learning algorithms with respect to a small disturbance of noises.
arXiv Detail & Related papers (2020-08-17T11:56: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.