Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 1: Reject
review_content: The authors present and analyze a quantum computing algorithm for learning GMMs.

I think this paper cannot be accepted because it violates formatting guidelines. Also, I think it is not appropriate for ICLR since it assumes knowledge of quantum computing that most people at this conference would not have, and I as a reviewer do not possess, and hence cannot evaluate this paper. For example, I do not know bra-ket notation.

If the ACs disagree, I am happy to revise my review for this paper and try to be more thorough.
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: The authors present a quantum algorithm for expectation maximization on a quantum machine, which is poly-logarithmic in the size of the dataset (and polynomial in other parameters such as the dimension of the feature space, and number of mixture components, condition number of the data and covariance matrices, some precision/error parameters etc) per iteration. So, compared to the . regular EM algorithm, this yields exponential speedup in the number of data points, but is worse in other factors (such as a k^4.5 dependence on the number of mixture components). So, the quantum system could be superior to a conventional computer for some settings of parameters. They run some (simulation) experiments on a dataset (VoxForge) to report accuracies (though there is no comparison of the accuracy of the classical algorithm). Also, there does not seem to be any experimental results to confirm the theoretical analysis of the scaling characteristics (i.e., to show that the scaling is as predicted by the theory).

review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: 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.  
review_title: Official Blind Review #1

Meta-review: The reviewers were unanimous that this submission is not ready for publication at ICLR in its current form. 

Concerns raised include a significant lack of clarity, and the paper not being self-contained.
Decision: Reject