On Quantum Perceptron Learning via Quantum Search

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. In this work, we make two principal contributions. First, we revisit the \emph{quantum version space perceptron} algorithm proposed by \cite{kapoor2016quantum}, identifying and correcting a flawed complexity assumption. We prove that the complexity of the algorithm is dimension-dependent, which has significant implications for the feasibility of the sampling-based quantum perceptron algorithm in high-dimensional regimes. Second, we propose and analyse two \emph{quantum-enhanced} cutting-plane algorithms for perceptron learning. Specifically, we leverage established quantum tools like \emph{Grover's search} and \emph{quantum walk search} in these algorithms. We provide detailed algorithmic constructions, complexity analysis and comparison to their classical counterparts. Our results demonstrate how quantum resources can yield provable improvements in query complexity and arithmetic operations, providing constructive insights into the statistical efficiency of different perceptron models and offering new perspectives on quantum perceptron learning.