Provable Adversarial Robustness in the Quantum Model
  Modern machine learning systems have been applied successfully to a variety
of tasks in recent years but making such systems robust against adversarially
chosen modifications of input instances seems to be a much harder problem. It
is probably fair to say that no fully satisfying solution has been found up to
date and it is not clear if the standard formulation even allows for a
principled solution. Hence, rather than following the classical path of bounded
perturbations, we consider a model similar to the quantum PAC-learning model
introduced by Bshouty and Jackson [1995]. Our first key contribution shows that
in this model we can reduce adversarial robustness to the conjunction of two
classical learning theory problems, namely (Problem 1) the problem of finding
generative models and (Problem 2) the problem of devising classifiers that are
robust with respect to distributional shifts. Our second key contribution is
that the considered framework does not rely on specific (and hence also
somewhat arbitrary) threat models like $\ell_p$ bounded perturbations. Instead,
our reduction guarantees that in order to solve the adversarial robustness
problem in our model it suffices to consider a single distance notion, i.e. the
Hellinger distance. From the technical perspective our protocols are heavily
based on the recent advances on delegation of quantum computation, e.g. Mahadev
[2018].
  Although the considered model is quantum and therefore not immediately
applicable to ``real-world'' situations, one might hope that in the future
either one can find a way to embed ``real-world'' problems into a quantum
framework or that classical algorithms can be found that are capable of
mimicking their powerful quantum counterparts.
