Quantum Expectation-Maximization Algorithm

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 (EM) algorithm for Gaussian mixture models (GMMs). The robustness and quantum speedup of the algorithm is demonstrated. We also show numerically the advantage of GMM over k-means for nontrivial cluster data. I. INTRODUCTION Quantum computing has attracted much attention since the discovery of Shor's algorithm [1, 2]. Recently, with the rapid developments in machine learning, physicists have started to consider utilizing quantum computers for machine learning applications [3-8]. As a result, quantum machine learning has emerged as an interdisciplinary field between quantum computing and machine learning. Furthermore, a quantum algorithm for the k - means algorithm [9, 10] with proven quantum speedup was proposed [11]. The k -means algorithm is an essential tool in many machine learning applications [9, 10].