Clustering algorithms are a cornerstone of machine learning applications. Recently, a quantum algorithm for clustering based on the $k$-means algorithm has been proposed by Kerenidis, Landman, Luongo, and Prakash. Based on their work, we propose a quantum expectation-maximization algorithm for Gaussian mixture models (GMMs). The robustness and quantum speedup of the algorithm are shown. We also show numerically the advantage of GMM over $k$-means algorithm for nontrivial cluster data.
Clustering algorithms are a cornerstone of machine learning applications. Recently, a quantum algorithm for clustering based on the k-means algorithm has been proposed by Kerenidis, Landman, Luongo, and Prakash. Based on their work, we propose a quantum expectation-maximization algorithm for Gaussian mixture models (GMMs). The robustness and quantum speedup of the algorithm are shown. We also show numerically the advantage of GMM over k-means algorithm for nontrivial cluster data.
The Expectation-Maximization (EM) algorithm is a fundamental tool in unsupervised machine learning. It is often used as an efficient way to solve Maximum Likelihood (ML) estimation problems, especially for models with latent variables. It is also the algorithm of choice to fit mixture models: generative models that represent unlabelled points originating from k different processes, as samples from k multivariate distributions. In this work we define and use a quantum version of EM to fit a Gaussian Mixture Model. Given quantum access to a dataset of n vectors of dimension d, our algorithm has convergence and precision guarantees similar to the classical algorithm, but the runtime is only polylogarithmic in the number of elements in the training set, and is polynomial in other parameters - as the dimension of the feature space, and the number of components in the mixture. We generalize further the algorithm in two directions. First, we show how to fit any mixture model of probability distributions in the exponential family. Then, we show how to use this algorithm to compute the Maximum a Posteriori (MAP) estimate of a mixture model: the Bayesian approach to likelihood estimation problems. We discuss the performance of the algorithm on a dataset that is expected to be classified successfully by this algorithm, arguing that on those cases we can give strong guarantees on the runtime.
Quantum communication systems are essential for secure information transmission, but their performance is significantly impeded by complex hybrid quantum noise (HQN) in Gaussian quantum channels. Accurately modeling this noise is crucial for optimizing channel achievable rates, a problem compounded by the complex nature of hybrid noise, which combines quantum shot noise and classical additive-white-Gaussian noise (AWGN) and is typically represented as an infinite mixture of Gaussian distributions. This work focuses on optimizing the HQN model to improve the achievable rate of Gaussian quantum channels using Machine Learning (ML) optimized clusters. The work specifically leverages Gaussian mixture model (GMM) and the Expectation-Maximization (EM) algorithm to model the complex noise characteristics of quantum channels. The study proposes modeling of hybrid noise as an infinite mixture of Gaussian distributions weighted by Poissonian parameters, with a novel cluster reduction technique that minimizes the number of Gaussian components while maintaining accuracy within acceptable error tolerances. Simulation results demonstrate that the GMM-EM enhanced clustering method significantly improves channel achievable rates in general quantum communication and satellite-based quantum communication systems. The GMMEM method substantially outperforms conventional clustering techniques, including K-means and Density-Based Spatial Clustering of Applications with Noise (DBSCAN) algorithms, in terms of maximizing achievable rates and characterizing noise accuracy. This advancement provides a practical and efficient solution for real-time quantum noise modeling, representing a significant improvement over existing state-of-the-art approaches in quantum communication network optimization
Spectral clustering is one of the most robust methods of an unsupervised machine learning field. Compared with the well-known k-means, spectral clustering uses the spectral properties of the Laplacian matrix to project data to a low-dimensional clustering with higher efficiency. However, for a sparse network with a substantial degree of heterogeneity, standard spectral clustering often overfits noise in the periphery of a sparse and stochastic graph. In our work, we combined the quantum version of the k-means algorithm with regularized spectral clustering and proposed a new quantum machine learning algorithm. It is more like a combination of classical and quantum algorithms. Compared with the established quantum k-means algorithm, our method has obvious computational advantages in non-convex or nested structures. At this stage, the research of quantum algorithms mainly stays in the simulation of classical computers. Our method does not need to expend a lot of effort to preprocess the data at the initial quantum state stage. Under the assumption of quantum data encoding, we theoretically demonstrate the feasibility of the quantum regularized spectral clustering algorithm. Then combine Q-means algorithm complexity advantages to complete the clustering task. This work aims to pave the path and help realize quantum spectral clustering algorithms on real quantum computers in the future and help create other versions of quantum machine learning algorithms. We provide simulations and data examples to illustrate these results.
Provably faster randomized and quantum algorithms for k-means clustering via uniform sampling
The k-means algorithm (Lloyd's algorithm) is a widely used method for clustering unlabeled data. A key bottleneck of the k-means algorithm is that each iteration requires time linear in the number of data points, which can be expensive in big data applications. This was improved in recent works proposing quantum and quantum-inspired classical algorithms to approximate the k-means algorithm locally, in time depending only logarithmically on the number of data points (along with data dependent parameters) [q-means: A quantum algorithm for unsupervised machine learning, Kerenidis, Landman, Luongo, and Prakash, NeurIPS 2019; Do you know what q-means?, Cornelissen, Doriguello, Luongo, Tang, QTML 2025]. In this work, we describe a simple randomized mini-batch k-means algorithm and a quantum algorithm inspired by the classical algorithm. We demonstrate that the worst case guarantees of these algorithms can significantly improve upon the bounds for algorithms in prior work. Our improvements are due to a careful use of uniform sampling, which preserves certain symmetries of the k-means problem that are not preserved in previous algorithms that use data norm-based sampling.
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.
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.