Abstract

The Expectation-Maximization (EM) algorithm is a fundamentaltool in unsupervised machine learning. It is often used as an efficientway to solve Maximum Likelihood (ML) and Maximum A Posteriori (MAP)estimation problems, especially for models with latent variables. It isalso the algorithm of choice to fit mixture models.  In this talk wedefine and use a quantum version of EM to fit a Gaussian MixtureMode (GMM). We start by introducing in great detail all the tools usedin quantum machine learning (QRAM, distance estimation procedures,quantum linear algebra, etc.). Then we present q-means: a quantumalgorithm for k-means. We generalize q-means algorithm to fit a GMM . Ouralgorithms are only polylogarithmic in the number of elements in thetraining set, but are polynomial in other parameters – as the dimensionof the feature space and the number of components in the mixture. We’lldiscuss some experiments concerning the runtime of these algorithms onreal datasets. We conclude by analyzing prospect relations betweenquantum iterative algorithms and the Information Bottleneck Method.