On Quantum Perceptron Learning via Quantum Search

Abstract

With the growing interest in quantum machine learning, the perceptron -- a fundamental building block in traditional machine learning -- has emerged as a valuable model for exploring quantum advantages. Two quantum perceptron algorithms based on Grover's search, were developed in arXiv:1602.04799 to accelerate training and improve statistical efficiency in perceptron learning. This paper points out and corrects a mistake in the proof of Theorem 2 in arXiv:1602.04799. Specifically, we show that the probability of sampling from a normal distribution for a D-dimensional hyperplane that perfectly classifies the data scales as (^D) instead of (), where is the margin. We then revisit two well-established linear programming algorithms -- the ellipsoid method and the cutting plane random walk algorithm -- in the context of perceptron learning, and show how quantum search algorithms can be leveraged to enhance the overall complexity. Specifically, both algorithms gain a sub-linear speed-up O(N) in the number of data points N as a result of Grover's algorithm and an additional O(D^1.5) speed-up is possible for cutting plane random walk algorithm employing quantum walk search.

Tasks

Reproductions