  Breakthroughs in machine learning (ML) and advances in quantum computing (QC)
drive the interdisciplinary field of quantum machine learning to new levels.
However, due to the susceptibility of ML models to adversarial attacks,
practical use raises safety-critical concerns. Existing Randomized Smoothing
(RS) certification methods for classical machine learning models are
computationally intensive. In this paper, we propose the combination of QC and
the concept of discrete randomized smoothing to speed up the stochastic
certification of ML models for discrete data. We show how to encode all the
perturbations of the input binary data in superposition and use Quantum
Amplitude Estimation (QAE) to obtain a quadratic reduction in the number of
calls to the model that are required compared to traditional randomized
smoothing techniques. In addition, we propose a new binary threat model to
allow for an extensive evaluation of our approach on images, graphs, and text.
