Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1908.06657

Quantum Expectation-Maximization for Gaussian Mixture Models

Iordanis Kerenidis, Alessandro Luongo, Anupam Prakash

Published Aug 19, 2019• 19 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1908.06657

Related papers

q-means: A quantum algorithm for unsupervised machine learning

Iordanis Kerenidis, Jonas Landman, Alessandro Luongo +1 more

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 $N$ $d$-dimensional vectors $v_i$ (seen as a matrix $V \in \mathbb{R}^{N \times d})$ stored in QRAM, the running time of q-means is $\widetilde{O}\left( k d \fracη{δ^2}κ(V)(μ(V) + k \fracηδ) + k^2 \frac{η^{1.5}}{δ^2} κ(V)μ(V) \right)$ per iteration, where $κ(V)$ is the condition number, $μ(V)$ is a parameter that appears in quantum linear algebra procedures and $η= \max_{i} ||v_{i}||^{2}$. For a natural notion of well-clusterable datasets, the running time becomes $\widetilde{O}\left( k^2 d \frac{η^{2.5}}{δ^3} + k^{2.5} \frac{η^2}{δ^3} \right)$ 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.

arXiv:1812.03584•Dec 10, 2018•119 citations

Relaxation of the EM algorithm via quantum annealing for Gaussian mixture models

Hideyuki Miyahara, Koji Tsumura, Yuki Sughiyama

We propose a modified expectation-maximization algorithm by introducing the concept of quantum annealing, which we call the deterministic quantum annealing expectation-maximization algorithm (DQAEM). The expectation-maximization algorithm (EM) is an established algorithm to compute maximum likelihood estimates and applied to many practical applications. However, it is known that EM heavily depends on initial values and its estimates are sometimes trapped by local optima. To solve such a problem, quantum annealing (QA) was proposed as a novel optimization approach motivated by quantum mechanics. By employing QA, we then formulate DQAEM and present a theorem that supports its stability. Finally, we demonstrate numerical simulations to confirm its efficiency.

arXiv:1701.03268•IEEE Conference on Decision and Control (CDC)•Dec 1, 2016•2 citations

q-means: A quantum algorithm for unsupervised machine learning

Iordanis Kerenidis, Jonas Landman, Alessandro Luongo +1 more

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 $N$ $d$-dimensional vectors $v_i$ (seen as a matrix $V \in \mathbb{R}^{N \times d})$ stored in QRAM, the running time of q-means is $\widetilde{O}\left( k d \frac{\eta}{\delta^2}\kappa(V)(\mu(V) + k \frac{\eta}{\delta}) + k^2 \frac{\eta^{1.5}}{\delta^2} \kappa(V)\mu(V) \right)$ per iteration, where $\kappa(V)$ is the condition number, $\mu(V)$ is a parameter that appears in quantum linear algebra procedures and $\eta = \max_{i} ||v_{i}||^{2}$. For a natural notion of well-clusterable datasets, the running time becomes $\widetilde{O}\left( k^2 d \frac{\eta^{2.5}}{\delta^3} + k^{2.5} \frac{\eta^2}{\delta^3} \right)$ per iteration, which is linear in the number of features $d$, and polynomial in the rank $k$, the maximum square norm $\eta$ and the error parameter $\delta$. 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.

•Jan 1, 2019•15 citations

Density Operator Expectation Maximization

Adit Vishnu, Shastry, Abhay, Dhruva Kashyap +1 more

Machine learning with density operators, the mathematical foundation of quantum mechanics, is gaining prominence with rapid advances in quantum computing. Generative models based on density operators cannot yet handle tasks that are routinely handled by probabilistic models. The progress of latent variable models, a broad and influential class of probabilistic unsupervised models, was driven by the Expectation-Maximization framework. Deriving such a framework for density operators is challenging due to the non-commutativity of operators. To tackle this challenge, an inequality arising from the monotonicity of relative entropy is demonstrated to serve as an evidence lower bound for density operators. A minorant-maximization perspective on this bound leads to Density Operator Expectation Maximization (DO-EM), a general framework for training latent variable models defined through density operators. Through an information-geometric argument, the Expectation step in DO-EM is shown to be the Petz recovery map. The DO-EM algorithm is applied to Quantum Restricted Boltzmann Machines, adapting Contrastive Divergence to approximate the Maximization step gradient. Quantum interleaved Deep Boltzmann Machines and Quantum Gaussian-Bernoulli Restricted Boltzmann Machines, new models introduced in this work, outperform their probabilistic counterparts on generative tasks when trained with similar computational resources and identical hyperparameters.

arXiv:2507.22786•Jul 30, 2025•0 citations

Quantum Maximum Likelihood Prediction via Hilbert Space Embeddings

Sreejith Sreekumar, Nir Weinberger

Maximum likelihood prediction (MLP) is a core task at the heart of modern large language models. Here, we study a quantum version of this task for a simplified data model consisting of independent and identically distributed samples, as a first step. The quantum maximum likelihood predictor (QMLP) is obtained by embedding of empirical probability distributions into quantum states and performing a minimization of quantum relative entropy over a given class of states. We derive non-asymptotic performance guarantees for QMLP in terms of convergence rates and concentration inequalities, both in trace norm and quantum relative entropy. Our approach provides a unified framework to handle MLP within both classical and quantum LLMs. We also consider the related problem of quantum information projection and generalize the quantum Pythagorean theorem to mixture families specified by possibly non-self-adjoint linear constraints. We further show that the Pythagorean inequality continues to hold in the infinite-dimensional setting whenever the convex information-projection problem attains a finite minimum.

cs.ITCross-listedarXiv:2602.18364•Feb 23, 2026•0 citations

An efficient quantum algorithm for generative machine learning

Xun Gao, Zhengyu Zhang, Luming Duan

A central task in the field of quantum computing is to find applications where quantum computer could provide exponential speedup over any classical computer. Machine learning represents an important field with broad applications where quantum computer may offer significant speedup. Several quantum algorithms for discriminative machine learning have been found based on efficient solving of linear algebraic problems, with potential exponential speedup in runtime under the assumption of effective input from a quantum random access memory. In machine learning, generative models represent another large class which is widely used for both supervised and unsupervised learning. Here, we propose an efficient quantum algorithm for machine learning based on a quantum generative model. We prove that our proposed model is exponentially more powerful to represent probability distributions compared with classical generative models and has exponential speedup in training and inference at least for some instances under a reasonable assumption in computational complexity theory. Our result opens a new direction for quantum machine learning and offers a remarkable example in which a quantum algorithm shows exponential improvement over any classical algorithm in an important application field.

arXiv:1711.02038•Nov 6, 2017•17 citations
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 kkk different processes, as samples from kkk 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 nnn vectors of dimension ddd, 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 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 qqq-means algorithm has convergence and precision guarantees similar to kkk-means, and it outputs with high probability a good approximation of the kkk cluster centroids like the classical algorithm. Given a dataset of NNN ddd-dimensional vectors viv_ivi​ (seen as a matrix V∈RN×d)V \in \mathbb{R}^{N \times d})V∈RN×d) stored in QRAM, the running time of q-means is O~(kdηδ2κ(V)(μ(V)+kηδ)+k2η1.5δ2κ(V)μ(V))\widetilde{O}\left( k d \fracη{δ^2}κ(V)(μ(V) + k \fracηδ) + k^2 \frac{η^{1.5}}{δ^2} κ(V)μ(V) \right)O(kdδ2η​κ(V)(μ(V)+kδη​)+k2δ2η1.5​κ(V)μ(V)) per iteration, where κ(V)κ(V)κ(V) is the condition number, μ(V)μ(V)μ(V) is a parameter that appears in quantum linear algebra procedures and η=max⁡i∣∣vi∣∣2η= \max_{i} ||v_{i}||^{2}η=maxi​∣∣vi​∣∣2. For a natural notion of well-clusterable datasets, the running time becomes O~(k2dη2.5δ3+k2.5η2δ3)\widetilde{O}\left( k^2 d \frac{η^{2.5}}{δ^3} + k^{2.5} \frac{η^2}{δ^3} \right)O(k2dδ3η2.5​+k2.5δ3η2​) per iteration, which is linear in the number of features ddd, and polynomial in the rank kkk, the maximum square norm ηηη and the error parameter δδδ. Both running times are only polylogarithmic in the number of datapoints NNN. Our algorithm provides substantial savings compared to the classical kkk-means algorithm that runs in time O(kdN)O(kdN)O(kdN) per iteration, particularly for the case of large datasets.
We propose a modified expectation-maximization algorithm by introducing the concept of quantum annealing, which we call the deterministic quantum annealing expectation-maximization algorithm (DQAEM). The expectation-maximization algorithm (EM) is an established algorithm to compute maximum likelihood estimates and applied to many practical applications. However, it is known that EM heavily depends on initial values and its estimates are sometimes trapped by local optima. To solve such a problem, quantum annealing (QA) was proposed as a novel optimization approach motivated by quantum mechanics. By employing QA, we then formulate DQAEM and present a theorem that supports its stability. Finally, we demonstrate numerical simulations to confirm its efficiency.
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 qqq-means algorithm has convergence and precision guarantees similar to kkk-means, and it outputs with high probability a good approximation of the kkk cluster centroids like the classical algorithm. Given a dataset of NNN ddd-dimensional vectors viv_ivi​ (seen as a matrix V∈RN×d)V \in \mathbb{R}^{N \times d})V∈RN×d) stored in QRAM, the running time of q-means is O~(kdηδ2κ(V)(μ(V)+kηδ)+k2η1.5δ2κ(V)μ(V))\widetilde{O}\left( k d \frac{\eta}{\delta^2}\kappa(V)(\mu(V) + k \frac{\eta}{\delta}) + k^2 \frac{\eta^{1.5}}{\delta^2} \kappa(V)\mu(V) \right)O(kdδ2η​κ(V)(μ(V)+kδη​)+k2δ2η1.5​κ(V)μ(V)) per iteration, where κ(V)\kappa(V)κ(V) is the condition number, μ(V)\mu(V)μ(V) is a parameter that appears in quantum linear algebra procedures and η=max⁡i∣∣vi∣∣2\eta = \max_{i} ||v_{i}||^{2}η=maxi​∣∣vi​∣∣2. For a natural notion of well-clusterable datasets, the running time becomes O~(k2dη2.5δ3+k2.5η2δ3)\widetilde{O}\left( k^2 d \frac{\eta^{2.5}}{\delta^3} + k^{2.5} \frac{\eta^2}{\delta^3} \right)O(k2dδ3η2.5​+k2.5δ3η2​) per iteration, which is linear in the number of features ddd, and polynomial in the rank kkk, the maximum square norm η\etaη and the error parameter δ\deltaδ. Both running times are only polylogarithmic in the number of datapoints NNN. Our algorithm provides substantial savings compared to the classical kkk-means algorithm that runs in time O(kdN)O(kdN)O(kdN) per iteration, particularly for the case of large datasets.
Machine learning with density operators, the mathematical foundation of quantum mechanics, is gaining prominence with rapid advances in quantum computing. Generative models based on density operators cannot yet handle tasks that are routinely handled by probabilistic models. The progress of latent variable models, a broad and influential class of probabilistic unsupervised models, was driven by the Expectation-Maximization framework. Deriving such a framework for density operators is challenging due to the non-commutativity of operators. To tackle this challenge, an inequality arising from the monotonicity of relative entropy is demonstrated to serve as an evidence lower bound for density operators. A minorant-maximization perspective on this bound leads to Density Operator Expectation Maximization (DO-EM), a general framework for training latent variable models defined through density operators. Through an information-geometric argument, the Expectation step in DO-EM is shown to be the Petz recovery map. The DO-EM algorithm is applied to Quantum Restricted Boltzmann Machines, adapting Contrastive Divergence to approximate the Maximization step gradient. Quantum interleaved Deep Boltzmann Machines and Quantum Gaussian-Bernoulli Restricted Boltzmann Machines, new models introduced in this work, outperform their probabilistic counterparts on generative tasks when trained with similar computational resources and identical hyperparameters.
Maximum likelihood prediction (MLP) is a core task at the heart of modern large language models. Here, we study a quantum version of this task for a simplified data model consisting of independent and identically distributed samples, as a first step. The quantum maximum likelihood predictor (QMLP) is obtained by embedding of empirical probability distributions into quantum states and performing a minimization of quantum relative entropy over a given class of states. We derive non-asymptotic performance guarantees for QMLP in terms of convergence rates and concentration inequalities, both in trace norm and quantum relative entropy. Our approach provides a unified framework to handle MLP within both classical and quantum LLMs. We also consider the related problem of quantum information projection and generalize the quantum Pythagorean theorem to mixture families specified by possibly non-self-adjoint linear constraints. We further show that the Pythagorean inequality continues to hold in the infinite-dimensional setting whenever the convex information-projection problem attains a finite minimum.
A central task in the field of quantum computing is to find applications where quantum computer could provide exponential speedup over any classical computer. Machine learning represents an important field with broad applications where quantum computer may offer significant speedup. Several quantum algorithms for discriminative machine learning have been found based on efficient solving of linear algebraic problems, with potential exponential speedup in runtime under the assumption of effective input from a quantum random access memory. In machine learning, generative models represent another large class which is widely used for both supervised and unsupervised learning. Here, we propose an efficient quantum algorithm for machine learning based on a quantum generative model. We prove that our proposed model is exponentially more powerful to represent probability distributions compared with classical generative models and has exponential speedup in training and inference at least for some instances under a reasonable assumption in computational complexity theory. Our result opens a new direction for quantum machine learning and offers a remarkable example in which a quantum algorithm shows exponential improvement over any classical algorithm in an important application field.