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) and Maximum A Posteriori 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 by fitting any mixture model of base distributions in the exponential family. We discuss the performance of the algorithm on datasets that are expected to be classified successfully by those algorithms, arguing that on those cases we can give strong guarantees on the runtime.
Quantum machine learning is a hot topic, recently. There are several "schools of thought": 
-- quantum kernel embeddings, which work per-observation, and allow for application on noisy intermediate-scale devices,
-- work based on quantum optimization solvers, which try to claim one could apply quantum eigensolvers to various training problems, but which does not seem to be applicable on intermediate-scale devices, given the scale of the requisite input,
--  novel quantum algorithms. 
In principle, the novel quantum algorithms hold the promise of an exponential speed-up. 
The authors propose a novel variant of expectation minimisation for parameter estimation of a gaussian mixture model with uniform mixing coefficients, targeting an ill-defined model of quantum computing of their own coinage.  Unfortunately, the paper is very sloppy. 
The sloppiness starts with the model of quantum computing, which seems to assume anything the authors needed:
-- Definition 1: one can perform |k|d arithmetic operations in time polylog(d)
-- sentence above Lemma 3.4: post-selection (which makes it possible to solve at least all of PP, cf. https://arxiv.org/abs/quant-ph/0412187)
-- sentence below Lemma 3.6: "quantum linear algebra subroutines and tomography" in no time at all (?), wherein there are information-theoretic limits \Omega(exp(kd)) on the state tomography.
In terms of statistics and learning theory, the authors:
-- do not consider the separation of the Gaussians as a parameter. It is well-known that with o(1) separation, exponentially many samples are required, and with sqrt(log(k)) separation, polynomially many samples suggest (http://ieee-focs.org/FOCS-2017-Papers/3464a085.pdf). Unless Definition 1 of the authors "subsumes" processing of exponentially large numbers of samples in polylog(d) time, the authors may need to add an assumption on the separation.
-- the authors explain that their approach works only for the gaussian mixture model with uniform mixing coefficients only at the top of page 4, in a completely obscure notation of their own, and do not reference it as an assumption in the theorems later. 
The sloppiness continues with the description of the Experiments in Section 4. Authors present a table of some results, but do not mention whether these have been obtained on quantum-computing hardware, a simulator thereof (what simulator? with noise?), or whether this is some fully-classical variant of the algorithm being tested. This clearly violates any "reproducibility checklist".
Within the "minor comments" category:
-- the introduction of the EM algorithms for GMM is sloppy. It is well known that EM for GMM is super-sensitive to noise and balance of the mixing coefficients (https://ieeexplore.ieee.org/document/8635825) and can get stuck in arbitrarily bad local optima, which is not mentioned once. 
-- the references to other algorithms for GMM mention only Dasgupta 1999, rather than the subsequent 20 years of research, e.g., of Ankur Moitra at MIT (https://math.mit.edu/directory/profile.php?pid=1502). 
-- on the other hand, there are plentiful references to arxiv pre-prints of Kerenidis et al, at least some of which have been shown to be vacuous, e.g., https://arxiv.org/abs/1808.09266 with an infinite upper bound on the run-time and no relation to the present paper? 
-- there are some formulae missing or ending half-way through, e.g. Page 3 before "alas", Page 3 after "GMM would be". 
-- there are a number of language issues: "we can thresholding", "some other real-world dataset".
-- the discussion starting with "Let's have a first high-level comparison" is completely wrong. Especially the condition number estimates of 5 seem to have no justification what so ever. 
-- authors say that "polynomial dependence on the rank, the error, and the condition number, make these algorithms impractical on interesting datasets" -- but it is not clear whether they mean that their algorithm is also impractical?
Overall, while I like the idea of parameter estimation on a quantum computer, I could not recommend accepting the paper in its current form.