# Provable Adversarial Robustness in the Quantum Model

arXiv: https://arxiv.org/abs/2112.09625 · HTML: https://mlsanity.com/paper/2112.09625/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 33 references that are in the map.
- First posted on arXiv 17 Dec 2021.

## Builds on (most cited first, 16 of 16)

- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Do ImageNet Classifiers Generalize to ImageNet?](https://mlsanity.com/paper/1902.10811/) (2019)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [Deep Neural Networks are Easily Fooled: High Confidence Predictions for Unrecognizable Images](https://mlsanity.com/paper/1412.1897/) (2014)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Measuring Robustness to Natural Distribution Shifts in Image Classification](https://mlsanity.com/paper/2007.00644/) (2020)
- [Certified Defenses against Adversarial Examples](https://mlsanity.com/paper/1801.09344/) (2018)
- [Adversarial Training and Robustness for Multiple Perturbations](https://mlsanity.com/paper/1904.13000/) (2019)
- [Exploring the Landscape of Spatial Robustness](https://mlsanity.com/paper/1712.02779/) (2017)
- [Adversarial examples from computational constraints](https://mlsanity.com/paper/1805.10204/) (2018)
- [Out of Distribution Generalization in Machine Learning](https://mlsanity.com/paper/2103.02667/) (2021)
- [Beyond Perturbations: Learning Guarantees with Arbitrary Adversarial Test Examples](https://mlsanity.com/paper/2007.05145/) (2020)
- [Adversarially Robust Learning with Unknown Perturbation Sets](https://mlsanity.com/paper/2102.02145/) (2021)
- [Adversarial Examples from Cryptographic Pseudo-Random Generators](https://mlsanity.com/paper/1811.06418/) (2018)
- [Query complexity of adversarial attacks](https://mlsanity.com/paper/2010.01039/) (2020)
- [Adversarial Robustness: What fools you makes you stronger](https://mlsanity.com/paper/2102.05475/) (2021)

## Built on by (most cited first, 1 of 1)

- [SoK: Critical Evaluation of Quantum Machine Learning for Adversarial Robustness](https://mlsanity.com/paper/2511.14989/) (2025)

## Abstract (arXiv)

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 ℓ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.