Quantum Perceptron Revisited: Computational-Statistical Tradeoffs
  Quantum machine learning algorithms could provide significant speed-ups over
their classical counterparts; however, whether they could also achieve good
generalization remains unclear. Recently, two quantum perceptron models which
give a quadratic improvement over the classical perceptron algorithm using
Grover's search have been proposed by Wiebe et al. arXiv:1602.04799 . While the
first model reduces the complexity with respect to the size of the training
set, the second one improves the bound on the number of mistakes made by the
perceptron. In this paper, we introduce a hybrid quantum-classical perceptron
algorithm with lower complexity and better generalization ability than the
classical perceptron. We show a quadratic improvement over the classical
perceptron in both the number of samples and the margin of the data. We derive
a bound on the expected error of the hypothesis returned by our algorithm,
which compares favorably to the one obtained with the classical online
perceptron. We use numerical experiments to illustrate the trade-off between
computational complexity and statistical accuracy in quantum perceptron
learning and discuss some of the key practical issues surrounding the
implementation of quantum perceptron models into near-term quantum devices,
whose practical implementation represents a serious challenge due to inherent
noise. However, the potential benefits make correcting this worthwhile.
