Machine learning algorithms perform well on identifying patterns in many different datasets due to their versatility. However, as one increases the size of the data, the computation time for training and using these statistical models grows quickly. Here, we propose and implement on the IBMQ a quantum analogue to K-means clustering, and compare it to a previously developed quantum support vector machine. We find the algorithm's accuracy comparable to the classical K-means algorithm for clustering and classification problems, and find that it becomes less computationally expensive to implement for large datasets as compared to its classical counterpart.
Machine learning algorithms perform well on identifying patterns in many different datasets due to their versatility. However, as one increases the size of the data, the computation time for training and using these statistical models grows quickly. Here, we propose and implement on the IBMQ a quantum analogue to K-means clustering, and compare it to a previously developed quantum support vector machine. We find the algorithm's accuracy comparable to the classical K-means algorithm for clustering and classification problems, and find that it becomes less computationally expensive to implement for large datasets as compared to its classical counterpart.
Quantum machine learning is one of the most promising applications of a full-scale quantum computer. Over the past few years, many quantum machine learning algorithms have been proposed that can potentially offer considerable speedups over the corresponding classical algorithms. In this paper, we introduce q-means, a new quantum algorithm for clustering which is a canonical problem in unsupervised machine learning. The q-means algorithm has convergence and precision guarantees similar to k-means, and it outputs with high probability a good approximation of the k cluster centroids like the classical algorithm. Given a dataset of Nd-dimensional vectors vi (seen as a matrix V∈RN×d) stored in QRAM, the running time of q-means is O(kdδ2ηκ(V)(μ(V)+kδη)+k2δ2η1.5κ(V)μ(V)) per iteration, where κ(V) is the condition number, μ(V) is a parameter that appears in quantum linear algebra procedures and η=maxi∣∣vi∣∣2. For a natural notion of well-clusterable datasets, the running time becomes O(k2dδ3η2.5+k2.5δ3η2) per iteration, which is linear in the number of features d, and polynomial in the rank k, the maximum square norm η and the error parameter δ. Both running times are only polylogarithmic in the number of datapoints N. Our algorithm provides substantial savings compared to the classical k-means algorithm that runs in time O(kdN) per iteration, particularly for the case of large datasets.
This research focuses on the implementation of quantum machine learning with the classical models such as Gradient Boosting and K-means clustering for efficient classification and clustering of most complex datasets in advanced systems. Taking advantage of the large datasets that are handled by the qc, this work examines Quantum Support Vector Machines (QSVM), Quantum Boosting, and Quantum K-means. To compare the efficiency of these hybrid models three datasets - the healthcare, the financial, and the cyber-security datasets - are used. Our findings indicate that quantum optimization algorithms achieve better accuracy in clustering in comparison to the classical counterparts and are computationally faster. This work shows how quantum machine learning can lead to the enhancement of difficult data processing tasks, a major issue in the quantum computing domain, with specific reference to resources and high-dimensional data. The opportunity to integrate quantum and classical models successfully is the best basis for further developments in machine learning.
Quantum algorithms are being extensively researched nowadays, seeing the potential to provide exponential speedup compared to classical algorithm execution. This speedup can play a significant role in machine learning, where training a model is usually prolonged. Training a machine learning model requires compressing large vectors into small computational units, and quantum computers inherently are fast at compressing the large vectors into small computations and tensor products. The present work aims to compare the K-means, a classical machine learning algorithm, and Q-means, a Quantum algorithm. Here in this work, we use q-means, a quantum algorithm for clustering, a canonical problem in unsupervised machine learning. The q-means algorithm has convergence and precision guarantees similar to k-means. [14]It outputs with high probability a good approximation of the k cluster centroids like the classical algorithm. The experimental results are demonstrated, which show a significant difference between k-means and q-means algorithms.
Quantum machine learning is one of the most promising applications of a full-scale quantum computer. Over the past few years, many quantum machine learning algorithms have been proposed that can potentially offer considerable speedups over the corresponding classical algorithms. In this paper, we introduce q-means, a new quantum algorithm for clustering which is a canonical problem in unsupervised machine learning. The q-means algorithm has convergence and precision guarantees similar to k-means, and it outputs with high probability a good approximation of the k cluster centroids like the classical algorithm. Given a dataset of Nd-dimensional vectors vi (seen as a matrix V∈RN×d) stored in QRAM, the running time of q-means is O(kdδ2ηκ(V)(μ(V)+kδη)+k2δ2η1.5κ(V)μ(V)) per iteration, where κ(V) is the condition number, μ(V) is a parameter that appears in quantum linear algebra procedures and η=maxi∣∣vi∣∣2. For a natural notion of well-clusterable datasets, the running time becomes O(k2dδ3η2.5+k2.5δ3η2) per iteration, which is linear in the number of features d, and polynomial in the rank k, the maximum square norm η and the error parameter δ. Both running times are only polylogarithmic in the number of datapoints N. Our algorithm provides substantial savings compared to the classical k-means algorithm that runs in time O(kdN) per iteration, particularly for the case of large datasets.
Supervised machine learning deals with developing complex non-linear models, which can be used later to predict the output for a known input. Clustering is usually treated as an unsupervised machine learning task, but we can formulate a solution to a clustering problem by using a supervised classification algorithm [1]. However, these classification algorithms are highly computationally intensive in nature, so the overall complexity in designing a clustering solution is often very costly from an implementation point of view. The more data we use, the more computational power is required too. Recent advancements in quantum computing show promising advantages in dealing with this kind of computational issues we face while training a complex machine-learning algorithm. In this paper, we do a theoretical investigation on the runtime complexity of algorithms, from classical to randomized, and then to quantum frameworks, when designing a clustering algorithm. The analysis shows significant computational advantages with a quantum framework as compared to the classical and randomized versions of the implementation.
Supervised clustering is the process of grouping unlabeled objects by using some specific objectives and any supervised learning technique. In traditional clustering algorithms, the similarity measure is based on some distance finding formulations. In supervised clustering, this similarity measure is trained with the help of asupervised learning method. In this paper, we have designed a quantum supervised clustering algorithm and analyzed the overall runtime complexity of the algorithm. In our approach, we have trained the similarity measure model with quantum support vector machine. This quantum mechanically trained similarity measure model is used in the quantum K-Means algorithm, instead of the traditional distance-based similarity measure functions, for clustering unlabeled objects. Our analysis demonstrates that the proposed approach exhibits exponential speed up when compared to the classical implementation.