  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(\sqrt{N})$. The second algorithm illustrates how the classical mistake bound
of $O(\frac{1}{\gamma^2})$ can be further improved to
$O(\frac{1}{\sqrt{\gamma}})$ through quantum means, where $\gamma$ denotes the
margin. Such improvements are achieved through the application of quantum
amplitude amplification to the version space interpretation of the perceptron
model.
