Quantum Perceptron Models
We demonstrate how quantum computation can provide non-trivial improvements in the computational and statistical complexity of the perceptron model. We develop two quantum algorithms for perceptron learning. The first algorithm exploits quantum information processing to determine a separating hyperplane using a number of steps sublinear in the number of data points N , namely O( √ N ). The second algorithm illustrates how the classical mistake bound of O( 1 γ 2 ) can be further improved to O( 1 √ γ ) through quantum means, where γ denotes the margin. Such improvements are achieved through the application of quantum amplitude amplification to the version space interpretation of the perceptron model.
The authors present two ways of training the classical perceptron algorithm on a quantum computer based on Grover's search algorithm.   The key idea behind their algorithms is the mapping of the training procedure to a search for misclassified datapoints or separating hyperplanes (in the version space) from a uniform distribution over the data and a defined number of sampled hyperplanes, respectively. This mapping is explained in detail.  The authors formally show that their algorithms yield a quadratic speedup in the number of necessary training data points and the margin between the two classes, respectively.
In my opinion, this paper deserves the attention of the NIPS audience at least on poster level for sound investigation of an highly interdisciplinary and fundamental question whose answer might eventually have a strong impact on ML.  To the best of my knowledge, the proofs and arguments presented are correct. While an experimental evaluation would of course have been very good to back up the theoretical claims, the absence of a device capable of executing the algorithm excuses the authors from my point of view. As far as quantum algorithms go, the results are hence well presented and analyzed.  It is clear that this paper stands out in terms of originality and novelty (at least for the NIPS audience). While Grover's search is not a new algorithm, this application of it and the corresponding interdisciplinary insight certainly are novel by NIPS standards.  The impact is perhaps the most critical point as, for the reason stated above, this work is of purely theoretical nature and also far away from what most machine learning researches probably work on. However, it certainly does bridge multiple disciplines and should a quantum computer be built in the future, this work will surely have a strong impact and spawn much future work. Even if the immediate impact might not be high, researchers should be interested in important future developments in their field for which this work poses an example.  From my perspective, the authors (apart from some superfluous words that should be deleted and referring to Algorithm 2 in the proof of Lemma 2 when it should be Algorithm 1) try to express their ideas in a language understandable for the NIPS audience and rely on as little previous knowledge about quantum mechanics as possible. The explanations and proofs are also almost exclusively based on purely mathematical arguments, so that they should be understandable. However, some concepts  such as 'superposition' and resulting speedups might have deserved more explanation. The lack of knowledge of basic principle in QM might hinder the understanding of some readers. However, given the page limit I find that the authors did reasonably well in introducing the most important concepts from quantum mechanics.