## Discrete Randomized Smoothing Meets Quantum Computing

Tom Wollschl¨ ager ∗‡ , Aman Saxena ∗‡ , Nicola Franco , Jeanette Miriam Lorenz , Stephan G¨ unnemann † † ‡ ‡ School of Computation, Information &amp; Technology, Technical Univ. of Munich, Germany { t.wollschlaeger, a.saxena, s.guennemann } @tum.de † Fraunhofer Institute for Cognitive Systems IKS, Munich, Germany { nicola.franco, jeanette.miriam.lorenz } @iks.fraunhofer.de ∗ denotes equal contribution

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

at exponentially growing input data perturbations, rendering the smooth classifier's exact evaluation computationally intractable. Therefore, in practice, Monte Carlo (MC) based stochastic methods are employed to evaluate the probabilistic approximation of the smooth classifier.

Index Terms -Quantum Machine Learning, Certifiable Robustness, Randomized Smoothing, Quantum Amplitude Estimation.

## I. INTRODUCTION

With machine learning (ML) excelling in various domains such as natural language processing [1]-[3], computer vision [4], [5], and health care [6], [7] the need for reliable models emerged. Many approaches are vulnerable to attacks-noise crafted by an adversary to fool the model. Subsequently, the study of adversarial robustness deals with quantifying the robustness of the models and producing more robust approaches in these domains [8], [9]. One method of quantification is the robustness certificate. There, the so-called certified radius is computed for an input sample in which the classifier's prediction remains unchanged [10]. To this end, one has to provide a provable certificate that no noisy addition of lower magnitude can fool the classifier. Hence, existing certification methods are often computationally intensive. Lately, stochastic certification approaches have been dominating the field of adversarial robustness [11]. A promising method for discrete data certification is discrete randomized smoothing [12], which provides robustness guarantees against adversarial perturbations for black-box classifiers. The certificate is obtained by building a smooth classifier using a sparsity-aware distribution. However, it involves computing the model predictions

Quantum Computing (QC), on the other hand, has shown promise in providing speedups for specific tasks, such as factoring large numbers [13] and unstructured database search [14], making it a compelling approach to explore certifiable robustness. Consequently, research interest has surged at the intersection of QC and adversarial robustness, focusing on two primary categories. The first is to use QC to analyze and improve the adversarial robustness of classical neural networks [15], [16], and the second is to examine the robustness of quantum machine learning models [17]-[20].

This work focuses on stochastic certification and addresses the computational challenges associated with robustness certification for machine learning models on discrete data. We propose a QC-based certification that requires quadratically fewer calls to the base classifier than the classical MC method to achieve similar accuracy in evaluating the smooth classifier. We achieve this by reformulating the estimation of the discrete smooth classifier as counting the weighted solution to a search problem. We frame the search problem as finding the perturbations for which the classifier predicts the desired class, thus relating it to the Quantum Amplitude Estimation (QAE) algorithm [21]. Furthermore, we propose a new threat model for our approach and can certify any data representation against discrete perturbations. Instead of certifying models that operate on binary data, we can work on arbitrary data with discrete perturbations; i.e., attacks can perturb data to finitely many possible states. This enables us to evaluate the utility of our method in certifying machine learning algorithms for natural language processing , image classification , and graph substructure counting against discrete attacks that were previously out of reach for quantum computing certification.

Our core contributions can be summarized as follows: 1

The project/research is supported by the Bavarian Ministry of Economic Affairs, Regional Development and Energy with funds from the Hightech Agenda Bayern.

- · We develop a quantum algorithm to evaluate the smooth classifier for discrete data, requiring quadratically fewer calls to the model.

1 Find our code at: cs.cit.tum.de/daml/quantum-randomized-smoothing.

©2024 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

- · We develop an extension to the sparsity-aware discrete randomized smoothing framework to include a larger class of data representations.
- · We demonstrate the effectiveness of the proposed method both theoretically and empirically, highlighting its potential impact on the robustness of quantum machine learning algorithms.

## II. RELATED WORK

Randomized Smoothing has become one of the most prominent concepts of certifiable robustness in machine learning. Introduced by Cohen et al. [11], originating from differential privacy [22], its applicability to any black-box model and strong certification performance sparked many variants. Examples include the use of confidence scores [23], or localized smoothing improving robustness certificates for multi-output models [24]. Lee et al. [25] introduce discrete smoothing and Bojchevski et al. [12] extend the concept to sparse settings.

QC and Adversarial Robustness Recently, the intersection of QC and adversarial robustness has attracted considerable attention and has become a compelling area of research in the scientific community. To accelerate robustness verification for classic neural networks Franco et al. [15], [16], decompose a mixed-integer program into a quadratic unconstrained optimization problem and use it to determine whether the prediction changes within a given adversarial budget. Other works directly investigate the robustness of QML models [26]-[28]. Specifically, Weber et al. [27] used the quantum hypothesis testing (QHT) framework to derive certification guarantees for QML models. On the other hand, Du et al. [26] developed a framework in which they add quantum noise to show differential privacy and eventually establish robustness guarantees.

QC and Monte Carlo Miyamoto [29] demonstrated the effectiveness of QAE as a quadratically faster alternative to MC estimation and has shown its application in finance. Based on this, Sahdev and Kumar [30] proposed the application of QAE to evaluate the continuous smooth classifier, as defined in Equation (2), and reiterated quadratic speed-up. However, any estimate of the smooth classifier must serve as a guaranteed lower bound to the actual value. In the context of continuous randomized smoothing, estimating the approximation of the actual expectation invariably involves some form of discretization. Although Sahdev and Kumar [30] achieved a lower bound to the approximation, there was no guarantee that it remained a lower bound to the exact value. In addition, the accuracy of the estimate depends on the chosen discretization [31]. Contrary, in this work, we avoid the need to analyze discretization errors by introducing a discrete framework.

## III. BACKGROUND

In this section, we introduce topics from the domain of adversarial robustness and quantum computing that are crucial for our discussion henceforth. We provide only a basic overview of these topics.

## A. Certifiable Robustness

↦

Notation We denote the N dimensional Euclidean space R N as X ( N ) and the binary data space as X ( N ) D , that is, X ( N ) D := { 0 1 , } N . To simplify notation, we omit ( N ) where possible. We express the binary classification task as a twostep process: we first map the input to the logit space using l : X ↦→ [0 , 1] , followed by mapping the logits to the class prediction via η : [0 , 1] →{ 0 1 , } , e.g., η l ( ) := 1 [ l &gt; 0 5] . . The binary classifier f : X ↦→ { 0 1 , } is defined as f := η ◦ l .

Problem Definition The research area of certifiable (provable) robustness aims to establish formal guarantees thatunder all admissible attacks within the budget that does not change the semantic meaning of the data-none will alter the model's prediction. However, the process of examining the semantic similarity of the data is difficult 2 and task-dependent [32]. In the image domain, this difficulty is addressed by assuming that two inputs are semantically similar if they have an L p norm less than ϵ . Therefore, we can write that a model is robust for prediction x and attack budget ϵ if:

$$f ( \tilde { \mathbf x } ) = f ( \mathbf x ) \, \, \forall \tilde { \mathbf x } \in \mathcal { X }, \, \text{s.t.} \, \| \tilde { \mathbf x } - \mathbf x \| _ { p } \leq \epsilon \quad ( 1 )$$

Robustness verification for neural networks can be formulated as a mixed-integer linear program (MILP) based on the neural network's weights [33]. Unfortunately, the verification of properties in neural networks with ReLU activation is shown to be NP complete [10]. To avoid the computational complexity, approximations can be employed [34], which, however, potentially leads to loose guarantees. That is, it might not certify perturbation strengths that do not affect the model predictions. Randomized smoothing [11] has gained significant attention among relaxed certification methods due to its ability to assess robustness without requiring knowledge of the classifier.

## B. Randomized Smoothing

Randomized smoothing as proposed by Cohen et al. [11] constructs a smooth classifier, denoted as g , evaluating the original classifier f in the vicinity of the input:

$$g ( { \mathbf x } ) = \mathbb { E } _ { { \mathbf z } \sim \mathcal { N } ( 0, \sigma ^ { 2 } I ) } [ f ( { \mathbf x } + { \mathbf z } ) ] \, \text{ \quad \ \ } ( 2 )$$

Therefore, instead of the prediction at a data point x , the expected prediction is computed for noisy samples generated by a normal distribution centered at x . The objective is to find L B ( p ( ϵ )) := min δ ∈B p ( ϵ ) g ( x + δ ) and evaluate if L B ( p ( ϵ )) &gt; 1 2 , where B p ( ϵ ) := { δ ∈ X| || δ || p ≤ } ϵ . In other words, we verify if the prediction for all perturbations δ is larger than 0.5, which corresponds to remaining the same. To solve the optimization problem efficiently, one can evaluate the lower bound of L B ( p ( ϵ )) ≥ L F B ( , p ( ϵ )) by finding the minimum value for the worst-case classifier as follows [35]:

$$\i \text{ of } \quad & \mathcal { L } ( \mathcal { F }, \mathcal { B } _ { p } ( \epsilon ) ) \coloneqq \min _ { \substack { \delta \in \mathcal { B } _ { p } ( \epsilon ) \\ h \in \mathcal { F } \\ \text{cru} \\ \text{asic} } } \mathbb { E } _ { \mathbf z \sim \mathcal { N } ( 0, \sigma ^ { 2 } I ) } [ h ( \mathbf x + \delta + \mathbf z ) ]$$

2 Identifying two semantically similar objects is the classification task.

Fig. 1. Example of the worst-case classifier in one dimension; c ∗ = 1 and c other = 0 . In this figure h . ( ) implies h ∗ ( ) . .

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00895v1-figure-f99e8ebe-8069-447b-8346-0e842a359d67.jpg)

Here, F := { f f | : X ↦→ [0 , 1] } is the set of classifiers. Φ denotes the CDF of the standard normal distribution N (0 1) , , and p ∗ x is the lower bound of g ( x ) . We can certify that g is certifiably robust if ϵ &lt; σ Φ -1 ( p ∗ x ) 3 [11], [35]. We show the resulting worst-case classifier, h ∗ ∈ F leading to this guarantee in Figure 1. It is a linear classifier with all the points predicting class 1 clustered behind a linear decision boundary such that E z ∼N (0 ,σ 2 I ) [ h ∗ ( x + z )] = g ( x ) . The worst-case smooth classifier will predict class 1 until its mean h ∗ ( x + ) ϵ is shifted to this boundary at x + σ Φ -1 ( g ( x )) , at which point both classes will be predicted with equal probability. Hence, any lower bound p ∗ x of g ( x ) , ϵ &lt; σ Φ -1 ( p ∗ x ) guarantees robustness.

## C. Discrete Randomized Smoothing

In many fields, we encounter discrete data for which continuous noise is not applicable. To address this challenge, Bojchevski et al. [12] introduced an efficient randomized smoothing-based certification algorithm tailored for all forms of discrete data. They introduced a sparsity-aware smoothing scheme as a means of constructing a smooth classifier, which can then be efficiently certified. For simplicity, we describe the method for binary data, although the concepts can be extended to general discrete data.

For given numbers of additions and deletions, r a , r d , one defines the set of semantically similar graphs as those obtained by adding and deleting less than r a and r d edges respectively. For any binary data, this set is formally defined as:

$$\mathcal { B } _ { r _ { a }, r _ { d } } ( \mathbf x ) \coloneqq \{ \tilde { \mathbf x } \in \mathcal { X } _ { D } \text{ s.t. } \sum _ { \tilde { \mathbf x } _ { i } = \mathbf x _ { i } - 1 } 1 \leq r _ { d } \sum _ { \tilde { \mathbf x } _ { i } = \mathbf x _ { i } + 1 } 1 \leq r _ { a } \} \begin{array} { c } \ln \text{th} \\ \text{our main} \\ \text{for eval} \\ \text{faster. } n \end{array}$$

Notably, the only possible perturbation on the binary data is to flip the bits, and consequentially for smoothing one can model the perturbation on each component as a data-dependent Bernoulli distribution. More precisely, each dimension of the discrete data ˜ x i given the input data x is perturbed as in Equation (5), where each bit is flipped with probability p -if the actual value is 1 and p + otherwise. Formally, this writes:

$$\tilde { x } _ { i } | x \sim \text{Ber} ( p _ { + } \cdot \mathbb { I } ( \mathbf x _ { i } = 0 ) + ( 1 - p _ { - } ) \cdot \mathbb { I } ( \mathbf x _ { i } = 1 ) ). \quad ( 5 ) \quad \text{the sup}$$

We obtain the joint Probability Mass Function (PMF) 4 as:

̸

$$\phi ( \tilde { \mathbf x } | x ; p _ { + }, p _ { - } ) = \prod _ { j = 0 } ^ { n - 1 } ( P _ { F } ^ { ( j ) } ) ^ { \mathbb { I } ( \tilde { \mathbf x } _ { j } \neq \mathbf x _ { j } ) } ( 1 - P _ { F } ^ { ( j ) } ) ^ { \mathbb { I } ( \tilde { \mathbf x } _ { j } = \mathbf x _ { j } ) }. \ ( 6 )$$

Here P ( j ) F := p + · I ( x j = 0)+ p -· I ( x j = 1) is the probability of a bit-flip. Contrary to Gaussian smoothing in the continuous Euclidean domain, we define g : X ↦→ [0 , 1] as:

$$g ( { \mathbf x } ) & = \mathbb { P } [ f ( \tilde { \mathbf x } ) = 1 ] \quad \text{for} \quad \tilde { \mathbf x } \sim \phi (. | { \mathbf x } ) \\ & = \sum _ { f ( \tilde { \mathbf x } ) = 1 } \phi ( \tilde { \mathbf x } | { \mathbf x } ).$$

Although the evaluation of the discrete smooth classifier for binary data is computable, it becomes intractable with increasing dimension of the data space. Therefore, stochastic methods such as the MC method with Clopper-Pearson intervals are employed in practice. Bojchevski et al. [12] propose an efficient algorithm to certify the smooth classifier whose run time varies linearly with the radius of certification and is independent of the size of the data.

## D. Quantum Phase Estimation

Given a unitary operator U , characterized by eigenvalues in the form exp(2 πiθ ) , phase estimation emerges as an important quantum algorithm to efficiently find the phase θ associated with these eigenvalues. This algorithm serves as a fundamental subroutine in various quantum methodologies, including Shor's factoring algorithm [13] and Quantum Amplitude Estimation [21].

The core idea of phase estimation involves the iterative application of controlled operations , typically denoted as CU , to the corresponding eigenstate, progressively doubling the number of applications of the controlled gate with each iteration. If the phase can be accurately represented using t bits, after t iterations of applying the CU gate, we obtain a Quantum Fourier Transform (QFT) of the phase. Subsequently, the Quantum Inverse Fourier Transform (QIFT) is used after applying controlled gates, followed by a measurement operation to recover the phase θ . The circuit for Phase Estimation is shown in Figure 9.

## IV. DISCRETE QUANTUM RANDOMIZED SMOOTHING

In this section, we go into the details of our methods and our main contributions. We present our quantum algorithm for evaluating the discrete smooth classifier that is provably faster, providing a quadratic speed-up over the classical MCbased algorithm. We provide an overview of our approach in Algorithm 1, further laying out the details in this section. From a high-level viewpoint, our algorithm works as follows: (i) we encode all perturbations as quantum superposition | Ψ( x ) ⟩ such that the probability of measuring the perturbed state | Ψ( ˜ x i ) ⟩ is the same as the probability of transition ϕ ( ˜ x x i | ) . (ii) We interpret the smooth classifier as the projection of the superposition | Ψ( x ) ⟩ onto the subspace spanned by all

## Algorithm 1 Smooth Quantum Classifier (SQC)

Input: binary data x , classifier as oracle O f , flip probabil- ities p + , p - , counting qubits n q , confidence 1 - δ .

U = GETDISTRIBUTIONLOADERCIRCUIT().

G = GETGROVEROPERATOR ( U, O f ) .

PEC = GETPHASEESTIMATIONCIRCUIT ( G,n q ) .

BINDPARAMETERS PEC ( , x , p + , p - ) .

$$\text{for } i = 0 \text{ to } \left \lceil 1 7 \log ( \frac { 1 } { \delta } ) \right \rceil \text{ do } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{\ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text$$

PHASE [ i ] = RUNANDMEASURE PEC ( )

end for

SQC = POSTPROCESS PHASE ( )

Return: SQC

the perturbations for which the base classifier f predicts 1 . (iii) Based on this interpretation, we construct an operator whose eigenvalues encode the value of the smooth classifier. (iv) Lastly, we evaluate the eigenvalue of this operator using the QAE.

## A. Discrete smoothing and QAE

The evaluation of the smooth classifier in Equation (7) involves looking at all 2 n perturbed states of the input data point x and adding the transition probabilities ϕ ( ˜ x x | ) for the states ˜ x that belong to class 1 . The dimension of the Hilbert space representing quantum states with n qubits is equal to the number of perturbations in binary data of length n . This allows us to encode all the perturbed states as orthogonal quantum states 5 using n qubits with a basis embedding.

Let ˜ x i be the perturbed data, with i ∈ [0 , 2 n -1 ] being the decimal representation of ˜ x i . The state | ˜ x ⟩ is defined as | i 1 ⟩⊗ | i 2 ⟩ ⊗ ... ⊗ | i n ⟩ , where i 1 , i 2 , ..., i n constitutes the perturbed binary string. We propose a parameterized circuit formally as in Lemma IV.1 to prepare a superposition state which encodes all perturbations | ˜ x i ⟩ of the state | x ⟩ as follows:

$$| \Psi ( x ) \rangle \coloneqq \sum _ { i = 0 } ^ { 2 ^ { n } - 1 } \sqrt { \phi ( \tilde { x } _ { i } | x ) } | \tilde { x } _ { i } \rangle \quad \quad ( 8 ) \begin{array} { c } \begin{array} { c } \begin{array} { c } \end{array} { c } \end{array} \\ \begin{array} { c } \begin{array} { c } \begin{array} { c } \end{array} { c } \end{array} \\ \begin{array} { c } \begin{array} { c } \begin{array} { c } \end{array} \\ \end{array} \\ \begin{array} { c } \begin{array} { c } \begin{array} { c } \end{array} \\ \end{array} \\ \begin{array} { c } \begin{array} { c } \end{array} \\ \end{array}$$

We define the superposition of all good (where f predicts 1 ) states and all bad (where f predicts 0 ) states respectively as:

̸

̸

$$\text{and} \, \text{was} \, \text{p.sures} \, \text{is species} \, \text{y as} \,. \quad \text{Equat} \\ | \text{a} \rangle \coloneqq \frac { \sum _ { f ( \tilde { x } _ { i } ) = 1 } \sqrt { \phi ( \tilde { x } _ { i } | x ) } | \tilde { x } _ { i } \rangle } { \sqrt { \sum _ { f ( \tilde { x } _ { i } ) = 1 } \phi ( \tilde { x } _ { i } | x ) } } } \\ | \text{b} \rangle \coloneqq \frac { \sum _ { f ( \tilde { x } _ { i } ) \neq 1 } \sqrt { \phi ( \tilde { x } _ { i } | x ) } | \tilde { x } _ { i } \rangle } { \sqrt { \sum _ { f ( \tilde { x } _ { i } ) \neq 1 } \phi ( \tilde { x } _ { i } | x ) } }. \quad \text{Given} \\ \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{---} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \,
\text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{-- } \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \tilde{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--}
\text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{\--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{-} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \,\text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{-}" \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \text{--} \, \end{cases}.$$

Note that | a ⟩ and | b ⟩ are orthonormal; therefore, using simple algebra, one can decompose | ψ ( x ) ⟩ into orthogonal subspaces spanned by good and bad perturbation embeddings (Equation (10)). Essentially, given an input data point x ∈ X D and distribution parameters p -and p + , one can use our

5 Any two distinct strings have orthogonal basis encoding, i.e., for a , b ∈ { 0 1 , } n we have ⟨ a b | ⟩ = 1 a [ = b ] .

Lemma IV.1 to efficiently construct a circuit that acts in the ground state | 0 ⟩ as follows:

$$U ( { \mathbf x }, p _ { - }, p _ { + } ) | 0 \rangle = \sqrt { g ( { \mathbf x } ) } | a \rangle + \sqrt { 1 - g ( { \mathbf x } ) } | b \rangle. \quad ( 1 0 )$$

Here g ( x ) := ∑ f ( ˜ x i )=1 ϕ ( ˜ x x i | ) is the evaluation of the smooth classifier; see Equation (7). The task of computing the smooth classifier is reduced to finding the projection of the weighted superposition | ψ ( x ) ⟩ onto the subspace of good perturbations, i.e., g ( x ) from Equation (7) is the amplitude of | a ⟩ in Equation (10). This interpretation allows us to use QAE [21] to evaluate the smooth classifier. We now state the lemma describing a circuit to load all the perturbations as a superposition with the square of the amplitude being the transition probability ϕ ( ˜ x x i | ) , while we defer the proof to Appendix C1.

↦

Lemma IV.1. Let x ∈ { 0 1 , } n represent our binary data, f : x →{ 0 1 , } be the base classifier, and p -, p + ∈ [0 , 1] be the probability of addition and deletion, respectively, as used in Equation (5) . Define,

$$\dot { \theta _ { 0 } } ( p _ { + } ) & \coloneqq 2 \arccos ( \sqrt { 1 - p _ { + } } ) \\ \dot { \theta _ { D } } & \coloneqq - 2 ( \arccos ( \sqrt { 1 - p _ { + } } ) + \arccos ( \sqrt { 1 - p _ { - } } ) ) \quad ( 1 1 ) \\ \text{data} & \quad = - 2 \arccos ( \sqrt { 1 - p _ { + } } \sqrt { 1 - p _ { - } } - \sqrt { p _ { + } } \sqrt { p _ { - } } ),$$

Then the following holds 6 for the operator

$$\text{the} \quad U ( { \mathbf x }, p _ { - }, p _ { + } ) \coloneqq \otimes _ { m = 0 } ^ { n - 1 } R Y ( \theta _ { 0 } + { \mathbf x } _ { m } \theta _ { D } ) \circ R X ( { \mathbf x } _ { m } \pi )$$

and | Ψ( ) x ⟩ as defined in Equation (8) .

$$U ( { \mathbf x }, p _ { - }, p _ { + } ) | 0 \rangle = | \Psi ( x ) \rangle \, \text{ \quad \ \ } ( 1 2 )$$

Furthermore, we can construct an operator whose eigenvalues encode the value of the smooth classifier and employ the QAE algorithm to solve the problem. However, there are alternative algorithms that can replace QAE [36], [37].

## B. Smooth classifier as the phase of a quantum operator

In this subsection, we construct a quantum operation whose eigenvalues encode the value of the smooth classifier. Let R 0 := 2 0 | ⟩⟨ 0 | -I and R ψ x := 2 | ψ ( x ) ⟩⟨ ψ ( x ) | -I represent the reflections about | 0 ⟩ and | ψ ( x ) ⟩ , respectively. Using Equation (12), we can readily deduce that:

$$\mathcal { R } _ { \Psi _ { \mathbf x } } = U ( { \mathbf x }, p _ { - }, p _ { + } ) \mathcal { R } _ { 0 } U ( { \mathbf x }, p _ { - }, p _ { + } ) ^ { H } \quad ( 1 3 )$$

↦

Given an oracle O f that can simulate the action of the classical function f , i.e., it can realize the following operation O f : | x ⟩ → -( 1) f ( x ) | x ⟩ . Its actions on | a ⟩ and | b ⟩ can be described as O f | a ⟩ = -| a ⟩ and O f | b ⟩ = | b ⟩ . As a result, for any quantum state | Φ ⟩ within the span of | a ⟩ and | b ⟩ , the application of O f reflects | Φ ⟩ with respect to | b ⟩ . Defining Grover's operator G := R Ψ x O f , it follows that G rotates any state ϕ ∈ span ( | a ⟩ , | b ⟩ ) by an angle of 2 θ toward | a ⟩ , where θ denotes the angle between | Ψ( x ) ⟩ and | b ⟩ .

6 This is only true up to a global phase but as we discuss in the proof, it will still lead to the desired Grover's operator and therefore for all further discussions we ignore the global phase.

Consequently, within the subspace spanned by | a ⟩ and | b ⟩ , the operator G works as a rotation operation with an angle of 2 θ , resulting in eigenvalues of exp( ± ι 2 ) θ in this plane. Using the representation of | Ψ( x ) ⟩ as specified in Equation (10), along with the orthonormality of | a ⟩ and | b ⟩ , we can express the output of the smooth classifier as follows:

$$g ( { \boldsymbol x } ) = \sum _ { f ( \tilde { \boldsymbol x } _ { \boldsymbol i } ) = 1 } \phi ( \tilde { \boldsymbol x } _ { \boldsymbol i } | { \boldsymbol x } ) = | \langle { \boldsymbol a } | \Psi ( { \boldsymbol x } ) | | \rangle ^ { 2 } = \sin ^ { 2 } ( \theta ) \quad ( 1 4 ) \quad \quad B. \ S m o$$

Therefore, finding the output of the smooth classifier g ( x ) reduces to finding the phase of Grover's operator G corresponding to the eigenvalues in span ( | a , ⟩ | b ⟩ ) . We employ the phase estimation algorithm briefly described in Section III-D to find the phase of the desired Grover operator. Using the results of Brassard et al. [21], one can formally estimate the order of convergence of the quantum algorithm SQC from Algorithm 1 as Lemma IV.2. Finally, we state our main result on quadratic speedup as Theorem IV.3.

Lemma IV.2. Given SQC( O ,p f -, p + , n q , 1 -δ ) as defined in Algorithm 1. To approximate the lower (upper) bound g a ( x ) of g x ( ) , such that | g a ( x ) -g x ( ) | &lt; ϵ with a certainty of 1 -δ , it requires O (ln( 1 δ ) 1 ϵ ) calls to the oracle O f simulating the base classifier f .

Theorem IV.3. [Quadratic Speedup] SQC( O ,p f -, p + , nqc , 1 -δ ) as mentioned in Algorithm 1 needs quadratically fewer calls to the base classifier compared to the classical MonteCarlo method with Clopper-Pearson confidence intervals to obtain an estimate of g x ( ) within the same accuracy.

We outline the proofs in Appendix C while building an intuitive understanding of the convergence result in Appendix B. We elaborate on deriving the guaranteed lower bound of the exact smooth classifier in Appendix B.

## V. DISCRETE PERTURBATIONS ON CONTINUOUS DATA

In the following, we adapt our framework to a new threat model. The data are continuous, but the perturbations of the adversary are discrete. For example, we have an RGB image comprising M × M pixels, where the adversary can corrupt up to N pixels. While the data space expands to R 3 × M M × , the set of perturbations to a fixed image consists of 2 N elementseach pixel can be corrupted or remains unaffected). Each perturbation of an image can be uniquely represented by a binary string of length N . For instance, setting the i th bit to 1 indicates the corruption of the i th pixel in the given image. We demonstrate the application of discrete randomized smoothing in this context to certify robustness against potential binary perturbations.

## A. Threat Model and Smoothing Distribution

In an N dimensional data space, the perturbation model p ( · , · ) allows the adversary to affect the i th feature x i of the input data x as p x , i ( i ) . We define the set of perturbations as:

$$\mathcal { P } _ { \mathbf x } \coloneqq \{ \tilde { \mathbf x } \in \mathcal { X } | \tilde { x } _ { j } \in \{ x _ { j }, p ( x _ { j }, j ) \} \}. \quad ( 1 5 ) \ \text{smoot}$$

Based on the set of perturbations P x we define the threat model as the ball of radius r around x in Equation (16), and the corresponding smoothing distribution as Equation (17).

$$\mathcal { B } _ { r } ( \mathbf x ) \coloneqq \{ \tilde { \mathbf x } \in \mathcal { P } _ { \mathbf x } \text{ s.t.} \sum _ { \tilde { \mathbf x } _ { i } = p ( \mathbf x _ { i }, i ) } 1 \leq r \} \quad \quad ( 1 6 )$$

$$\hat { \phi } ( \tilde { \mathbf x } | \mathbf x ; p ) \coloneqq ( p ) ^ { \sum _ { \mathfrak s _ { i } = p ( \mathbf x _ { i }, i ) } \mathbf 1 } ( 1 - p ) ^ { \sum _ { \mathfrak s _ { i } = \mathbf x _ { i } } \mathbf 1 } \quad ( 1 7 )$$

B. Smooth Classifier and Robustness Certification

Let ˆ : f X ↦→ { 0 1 , } denote the base classifier, we propose to define the smooth classifier as

$$\hat { g } ( { \mathbf x } ) \coloneqq \sum _ { \tilde { \mathbf x } \in \mathcal { P } _ { \mathbf x } \text{ and } \hat { f } ( \tilde { \mathbf x } ) = 1 } \hat { \phi } ( \tilde { \mathbf x } | { \mathbf x } ; p ) \quad \quad ( 1 8 )$$

Further, to certify ˆ( g x ) we establish a bijective mapping η x from P x onto { 0 1 , } N . This mapping ensures that the distribution ˆ ( ϕ ˜ x x | ; p ) coincides with ϕ η ( x ( ˜ x ) | η x ( x ); p + = p, p -= 0) which is defined in Equation (6). Additionally, for a given x , we define a classifier f on { 0 1 , } N based on the base classifier ˆ f on X , as f = ˆ f ◦ η -1 x . By certifying the smooth classifier, we establish analogous guarantees for ˆ g . The formal description of this approach is provided in Appendix A. Furthermore, as discussed in Appendix A, there's no necessity to construct the superposition of all perturbed states. Instead, we generate the superposition of perturbation representations η x ( ˜ x ) utilizing Lemma IV.1, and integrate it with x during oracle evaluation.

## VI. EXPERIMENTS

In this section, we demonstrate the utility of our proposed framework and examine its certification strength in multiple domains, including binary images, graphs, and natural language processing. Within the realm of discrete perturbations framework (Section V and Appendix A), we choose two settings: (i) Image classification on the binary MNIST dataset, (ii) Sentiment analysis on the IMDB reviews. We also evaluate our framework on the discrete data setting: (iii) Graph classification task to find a 4 -clique within the collection graphs with 6 nodes. We present additional results with more details on individual experiments in Appendix D.

We compare the performance of the quantum smooth classifier against the exact smooth classifier, which can be evaluated because of the limited perturbation representation. Moreover, we do not implement the classical models as quantum operations directly; instead, we construct a diagonal unitary that mimics the model giving the same output at all the perturbed data points. All experiments are carried out as a QC simulation on Qiskit with Aer backend [38] on an A100 node with up to 1TB of memory. We use SEML to manage our slurm experiments [39]

## A. Binary-MNIST Classification

We binarise the images of the MNIST handwritten digit dataset [40] and rescale them to 16 × 16 . The certification of the smooth classifier requires computing the output corresponding

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00895v1-figure-b8a22528-3cf8-409f-8d08-d0d5715d5dec.jpg)

Fig. 2. (a) Randomly selected validation image; (b) Window of perturbation, only the highlighted pixels are allowed to be perturbed and the subsequent robustness guarantees are only against attacks within that window; (c) Validation image randomly perturbed within the window.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00895v1-figure-93543082-c1bd-439c-a419-d47d540f281c.jpg)

(a)

(b)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00895v1-figure-b4dbd81c-b4c2-4185-8885-28497ac26aba.jpg)

Fig. 3. Heatmaps showing the percentage of 50 validation images in consideration that are robust against the indicated set of perturbations in the grid corresponding to the quantum smooth classifier( p -= 0 3 . , p + = 0 3 . ) with (a) 5 (b) 6 (c) 7 counting qubits and (d) corresponding to the actual smooth classifier.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00895v1-figure-73b1300d-d44a-401a-87c9-367d4d35478f.jpg)

to each class. Therefore, to simplify the problem computationally, we stick to the binary classification of predicting 4 or ¬ 4 . To construct the smooth classifier, we use p + = p -= 0 3 . as flip probabilities. We define a perturbation window with 17 pixels, as shown in Figure 2(b), and we certify against perturbations within that window. We then randomly select 50 images from the validation split to evaluate our algorithm. Figure 2 shows one of the validation images, the perturbation window, and a random perturbation to the given validation image within the perturbation window.

In Figure 3 we show heatmaps depicting the percentage of certified images for varying perturbations and with 5 , 6 , and 7 counting qubits and the actual smooth classifier. The number of counting qubits represents the binary string corresponding to the phase. When we increase the amount, we see a significant improvement in the certification performance. In Figure 4, we evaluate the proportion of certified images relative to the overall perturbations ( r a + r d ), considering various numbers of counting qubits alongside the exact smooth classifier. We observe that we already achieve a decent approximation using only 7 counting qubits. In Figure 5, we present the empirical comparison between the classical and quantum classifier for

Fig. 4. Certified ratio, exact classifier vs quantum classifiers ( p -= 0 3 . , p + = 0 3 . ) using 4 , 5 , 6 and 7 counting qubits evaluated for randomly selected 50 images.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00895v1-figure-89c71ddc-43f1-4d4e-a540-1ff34b85590b.jpg)

Fig. 5. Convergence of error with number of calls to the oracle. Comparison for Classical vs Quantum algorithm with errors averaged over 50 images from the MNIST testset.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00895v1-figure-68059adf-5f45-4965-a738-9e194254729c.jpg)

the convergence rate of the average error for the number of calls to the oracle . We observe that, although the error is still higher for the quantum approach, the slope of the quantum model is strongly favorable. For increased dimensionality of the data, our curve stays the same while the classic randomized smoothing is likely to get worse. From the slopes in Figure 5, we can calculate that if the quantum algorithm needs N samples, then the classical algorithm takes O N ( 1 92 . ) samples.

## B. Graph Classification

We further investigate discrete quantum randomized smoothing for graph classification. A subfield of machine learning on graphs focuses on detecting subgraph structures within a graph with graph neural networks to determine their expressivity [41]-[43]. Building upon this concept, we develop a dataset specifically tailored for binary classification by generating graphs that either contain a 4-clique or lack one entirely. These graphs are constructed using the Erd˝s-R´ enyi o (ER) model with six nodes. For graphs belonging to class 0, we use a connection probability of 65% , while those in class 1 are assigned a connection probability of 30% . We showcase an example of each class in Figure 6. We trained a PPGN [44] graph neural network on this data as the base classifier. Then we apply the smoothing approach.

Fig. 6. Example images of the graph classification dataset. On the left, we see a graph from class 1. These graphs do not contain a 4-clique. The right graph is an instance of class 2. All of these contain a 4 clique.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00895v1-figure-567c0d47-99e6-4799-a939-239c489f4995.jpg)

Fig. 7. Certified ratio for the exact classifier and quantum classifier with p -= 0 0 . , p + = 0 3 . using four to eight counting qubits evaluated on 170 randomly selected graphs.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00895v1-figure-87b5d7c8-d36c-4b3d-bb47-170f8f900fbe.jpg)

To smooth the data, we use p + = 0 3 . and p -= 0 0 . , since any deletion of an edge has a high probability of destroying a potential 4-clique. Thus, because of the absence of noise for edge deletions, we cannot certify against any adversarial deletion. The line plot in Figure 7 shows the behavior of our simulated quantum approach for 4 -8 counting qubits. We compare it with the actual smooth classifier that acts as a ground-truth result of the classic discrete smoothing approach [12]. We can certify most of the graphs for two additions, while some graphs can even be certified for up to 6 7 . As we increase the number of counting qubits to 8 , our approximation is very close to the ground truth values, see Figure 7. We observe a significant difference between the quantum classifier using 8 counting qubits and the exact smooth classifier arising at radius 7, where our approach is unable to certify. Given that our approach consistently predicts a lower bound, it will never predict 1 for cases where the value is precisely 1. Hence, our certification will hold only for finite perturbations. This limitation explains why we can only certify up to six additions, while the ground truth extends to infinity.

## C. Sentiment Analysis

Sentiment analysis is a subset of text classification in which aims to determine the polarity of sentences toward positive, negative, or neutral. We use a pre-trained model to predict the Positive or Negative tone of the IMDB reviews from Hugging Face and use it to construct a smooth classifier by

7 Graphs of class 0 already containing a 4-clique can have as many edges added as possible.

Fig. 8. Certified ratio for the exact classifier vs quantum classifier with p rem = 0 2 . using five to nine counting qubits evaluated for 600 randomly selected reviews with 8 -10 neutral words.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00895v1-figure-7158427d-7cbb-406f-8b73-ea74d95c3d3c.jpg)

randomly removing neutral words from the input sentences and finally compute certificates for the model's robustness against removal of such neutral words. The certification for a given input gives formal guarantees that the model will not change the prediction upon removal of a certain number of neutral words. We use a list of 29 neutral words and randomly take 600 ( 300 positively labeled and 300 negatively labeled) reviews that have around 8 -10 neutral words from the list. We use p rem = 0 2 . as the probability of removing neutral words. In Figure 8, we plot the percentage of certified sentences showing the strength of the certificate. It shows the increasing certification strengths for varying number of counting qubits.

## VII. CONCLUSION

In this work, we propose a novel framework that combines discrete randomized smoothing with quantum computing for robust classification of discrete data. We demonstrate a quadratic reduction in model evaluations using this framework. Additionally, we extend our approach to certify against threat models where data can be continuous but adversaries affect only restricted parts using discrete attacks. We evaluate the robustness of our approach in three different classification scenarios, showing that with five to seven counting qubits, a satisfactory approximation of the actual smooth classifier is achievable. Despite these improvements, our framework is limited as it handles either discrete data or continuous data with a restricted threat model as described in Section V. Nonetheless, this study highlights the potential of discrete quantum randomized smoothing for certifying neural networks, opening avenues for further exploration and research.

## APPENDIX

## A. Applying randomized smoothing to discrete perturbations

We start by presenting a general framework that extends the idea of RS for discrete data to discrete perturbations and show its utility in verifying the correctness of some of the test cases presented in Section VI. We essentially construct a classifier on discrete data from the actual classifier, whose certification guarantees the certification of the original classifier for discrete

perturbations. This allows us to validate our quantum approach on more realistic datasets.

Assume that the input data lies in some M -dimensional data space C M , where C = { 0 1 , } , { 0 1 , , ..., D } , Z , Q , R or C and the adversary is allowed to affect only N features 8 , indexed as x j i for i = 0 , ..., N -1 . Denote these set of indices as I N := { j i } N -1 i =0 and the remaining M -N indices as I N := { 0 1 , , ..., N -1 } I / N . Additionally, assume that the adversary can leave these features unaffected or apply a datadependent perturbation p x ( j i , j i ) . The perturbation model, denoted as p ( · , · ) takes the i th feature x i to p x , i ( i ) and applying the perturbation model again takes it back to x i . For example, non-corrupted to corrupted ; 0 to 1 or 1 to 0 ; etc. Given x ∈ C M , define the set of all perturbations on x as:

$$\mathcal { P } _ { \mathbf x } \coloneqq \{ \mathbf y \in \mathcal { C } ^ { M } | y _ { j } = \left \{ \begin{array} { c c c } x _ { j } & \text{for } j \in \mathcal { I } _ { N } \\ \in \{ x _ { j }, p ( x _ { j }, j ) \} & \text{for } j \in \overline { \mathcal { I } _ { N } } \\ \end{array} \right \}. \\ \mathfrak { r } \dots \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \end{array} \,.$$

Note that ∀ z ∈ P x , P z = P x . This is because applying the perturbation model p again will take p x , i ( i ) back to x i . To construct a smooth classifier ˜ g , we can sample ˜ x from a distribution ˜ ( ϕ . | x ) defined on P x and evaluate P ( ˜ ( f ˜ x = 1)) as our smooth classifier, where ˜ f is the base classifier. Therefore as before the smooth classifier ˜( g x ) can be obtained as:

$$\tilde { g } ( { \mathbf x } ) \coloneqq \sum _ { \tilde { \mathbf x } \in \mathcal { P } _ { \mathbf x } \text{ and } \tilde { f } ( \tilde { \mathbf x } ) = 1 } \tilde { \phi } ( \tilde { \mathbf x } | { \mathbf x } ) \quad \quad ( 2 0 ) \ \underset { \mathbf a \, \text{fun} } { \text{a fun} }$$

We define ˜ ϕ to allow data-dependent perturbation using two distinct probabilities of perturbation p + and p -. Let q , , . ( ) determine the data-dependent probability, i.e. q x , i ( i ) ∈ { p + , p -} gives the probability of perturbation of the i th feature x i , such that q p x , i ( ( i ) , i ) = p + if q x , i ( i ) = p -and p + otherwise.

Given this setup, we want to argue the following, firstly Equation (20) can be certified using the framework of [12] Secondly, it can be computed using our quantum algorithm without the need to construct a superposition of perturbed states ˜ x ∈ P x . We just need to construct the superposition in Lemma IV.1 and we can make data representation as part of the Oracle construction.

↦

Clearly, |P x | = 2 N , therefore we can find a bijection η x : P x →{ 0 1 , } N . Define η x as follows:

$$\eta _ { \mathbf x } ( \tilde { \mathbf x } ) _ { j } = \left \{ \begin{array} { c c } 1 & \text{if $q(x_{j},j)=p_{-}$} \\ 0 & \text{if $q(x_{j},j)=p_{+}$} \end{array} \right \} \quad \begin{array} { c } \text{pertur} \\ \text{(21)} & \text{that if} \\ \text{experi} \end{array}$$

↦

It is easy to verify that Equation (21) is a bijection which allows us to define f : { 0 1 , } N →{ 0 1 , } as a binary classifier on binary data such that f ( b ) := ˜ ( f η -1 x ( b )) . The construction of η x also ensures that ∀ y z , ∈ P x , ˜ ( ϕ y z | ) = ϕ η ( x ( y ) | η x ( z )) , where ϕ is as defined in Equation (6). Using the framework of Bojchevski et al. [12], the smooth classifier defined as:

$$g ( b ) \coloneqq \sum _ { f ( \tilde { b } ) = 1 } \phi ( \tilde { b } | b ) \quad \quad ( 2 2 ) \, \stackrel { \text{accu} } { \text{of th} } \\ \text{depic}$$

8 In the windowed MNIST experiment we allowed the adversary to perturb only a subset of the whole image. Therefore this framework can be used to verify its correctness.

Fig. 9. A typical Phase Estimation Circuit, taken from [38].

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00895v1-figure-b28c1c7d-acf3-44f6-a2ed-449182423214.jpg)

can be certified. Since, Equation (22) can be written as:

$$\Big \{ \begin{matrix} & & g ( b ) = & \sum _ { \eta _ { x } ^ { - 1 } ( \tilde { b } ) \in \mathcal { P } _ { x }, \tilde { f } ( \eta _ { x } ^ { - 1 } \tilde { b } ) = 1 } \\ ( 1 9 ) & & \tilde { b } \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and} \text{and}. \end{matrix}$$

If changing b to ˜ b does not change the prediction of g it can be inferred that changing η -1 x b to η -1 x ˜ b will not change the prediction of ˜ g . Therefore, any guarantees for g will also hold correspondingly for ˜ g .

↦

↦

a) Implementing smooth classifier for binary perturbations on QC: Assume we are given a classical neural machine learning model ˜ f . For a given x , we can implement a function η -1 x , and composing it with ˜ f we can implement f x := ˜ f ◦ η -1 x . Employing the classical circuit that implements the base classifier f x , for the perturbation representation, we can construct the reversible circuit performing the following transformation: ( b , y ) → ( b , y ⊕ f x ( b )) , as described in [45]. These reversible computations can then be simulated using quantum gates to obtain the corresponding quantum neural network oracle O f capable of realizing the following map: | b ⟩|-⟩ ↦→ ( -1) f x ( b ) | b ⟩|-⟩ . In principle, given any classical base classifier ˜ f , we can construct a quantum oracle O f : | x ⟩ → -( 1) f ( x ) | x ⟩ with a comparable compute time. That is, we assume the compute time of the classical operation ˜ ( f x ) is similar to that of the corresponding quantum operation O f | b ⟩ . This assumption allows us to expect that any asymptotic improvement in the number of calls to the oracle (or base classifier) will also be reflected in the actual runtime. Therefore we just need to prepare a superposition of all the perturbations as we can construct a data-dependent oracle that implicitly implements the base classifier on the data. For experiments, we have constructed a data-dependent diagonal unitary that given the perturbation representation gives the desired output.

## B. Phase estimation circuit and obtaining the lower bound

By denoting the eigenvalues of the unitary operator G as exp( ± 2 πιϕ ) , we can apply the phase estimation algorithm to accurately estimate ϕ up to t bits. Consequently, the value of the smooth classifier can be determined using the circuit depicted in Figure 9.

As discussed by Bojchevski et al. [12], obtaining a lower bound (or an upper bound when the output is below 0.5) on the probability that the smooth classifier predicts class 1 is

crucial for ensuring the certified robustness guarantees hold, irrespective of the base classifier selected. Brassard et al. [21] previously analyzed to estimate the bounds for the absolute difference between the actual and predicted amplitudes, specifically, | sin 2 ( πϕ actual ) -sin 2 ( πϕ approx ) | . In principle, the aforementioned error bound can be employed by subtracting it from the approximated value to acquire the lower bound. Nonetheless, utilizing this uniform error bound (independent of the actual value) might prove excessively conservative, particularly when working with a smaller number of qubits. As seen in our experiments(Section VI), such deviations from the actual value could lead the algorithm to disregard potential robustness.

Essentially, the phase estimation algorithm, contingent upon the number of counting qubits, can yield a finite set of distinct output values ( sin 2 ( θ/ 2) ). These values partition the interval [0 , 1] into a series of subintervals, denoted by { [ a , a j j +1 ] } j =1 ,..., 2 n -1 . Given that the second register in Figure 9 is initialized with | ψ ( x ) ⟩ , representing an equal superposition of the eigenstates of the operator G , for every observed phase ω , a similar number of observations is expected for 1 -ω (except when both the eigenstates coincide). Nevertheless, it is crucial to acknowledge that both values produce identical outputs. As illustrated in [21], with a probability of at least 8 π 2 , boundary values of the interval [ a j ∗ , a j ∗ +1 ] is obtained, such that g ( x ) ∈ [ a j ∗ , a j ∗ +1 ] . Consequently, if a state corresponding to a i is observed, a i -1 is a highprobability guaranteed lower bound. This probability is further enhanced by repeating the experiment multiple times.

Intutive understanding of Lemma IV.2: From our discussion above we notice that the error in estimating the precise value may diminish exponentially as the number of qubits increases, due to the exponential growth in the number of intervals. Nonetheless, the number of calls to the oracle (through Grover's operator G) also experiences exponential growth. As a result, a linear decrease in the error can be anticipated with the number of calls to the oracle.

## C. Proofs

## 1) Parameterized distribution loader circuit:

Proof of Lemma IV.1. Here we that U x,p ( -, p + ) creates the desired superposition state upto a global phase, and the global phase introduced in the process does not change the resulting Grover's operator.

Starting with the first part, decompose U x,p ( -, p + ) as two operators DL x p ( ; -, p + ) := ⊗ n -1 m =0 RY θ ( 0 + x m D θ ) and D x ( ) := ⊗ n -1 m =0 RX x ( m π ) . D x ( ) loads the data point | x ⟩ using basis encoding and DL x p ( ; -, p + ) further creates the desired superposition from | x ⟩ based on the distribution µ x as shown below, D x ( ) applies RX (0) = I to the i th qubit if x i = 0 else apply RX π ( ) = -ιX if x i = 1 , therefore, D x ( ) 0 | ⟩ = ( -ι ) ∑ n -1 j =0 x j | x ⟩ . Denote, DL M ( x M ; p -, p + ) :=

RY θ ( 0 + x M D θ ) and note that,

$$\begin{array} { c } \dot { \cdot } \, \quad \\ \ D L _ { M } ( 0 ; p _ { - }, p _ { + } ) | 0 \rangle & = R Y ( \theta _ { 0 } ) | 0 \rangle \\ f _ { - } & = \sqrt { 1 - p _ { + } } | 0 \rangle + \sqrt { p _ { + } } | 1 \rangle \\ \intertext { e } \ D L _ { M } ( 1 ; p _ { - }, p _ { + } ) | 1 \rangle & = R Y ( \theta _ { 0 } + \theta _ { D } ) | 1 \rangle \\ \intertext { e } \ D L _ { M } \dots c.. \end{array}$$

Therefore,

$$\text{retrive}, \quad D L _ { M } ( x _ { M } ; p _ { - }, p _ { + } ) | x _ { M } \rangle = ( \sqrt { P _ { F } ^ { ( M ) } } | \bar { x } _ { M } \rangle + \sqrt { 1 - P _ { F } ^ { ( M ) } } | x _ { M } \rangle ) \\ \text{ns from} \quad.$$

̸

where, as discussed before P ( m ) F := ( p + ) 1 -x m ( p -) x m . Using Equation 25 and the fact that P i x ( | m ) = ( √ P ( m ) F I ( = i x m ) √ 1 -P ( m ) F I ( = i x m ) ) ,

$$\det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det\det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \dotdet \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det
\det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \det \delta \det ( 2 6 ), \text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text	$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text
$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text<$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text}$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text#$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text`$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text1$$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\test$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text'$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text"$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text $\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$\text{$$$

Therefore, as desired DL x p ( ; -, p + ) | x ⟩ = | ψ x ( ) ⟩ := ∑ 2 n -1 i =0 √ µ x ( ) i | i ⟩ and U x,p ( -, p + ) 0 | ⟩ = ( -ι ) ∑ n -1 j =0 x j | ψ x ( ) ⟩ . Moreover, consider G = ( -ιι ) ∑ n -1 j =0 x j (2 | ψ x ( ) ⟩⟨ ψ x ( ) | -I 2 n ) O = R | ψ ⟩ x O f . Hence, the global phase does not change the final Grover's operator.

## 2) Asymptotic analysis and Quadratic speedup:

Proof of Lemma IV.2. Let a denote the output of the exact smooth classifier and ˜ a be the output of SQC(...). From the analysis of Quantum Amplitude Estimation by [21] we know the following results, for t counting qubits and T := 2 t ,

$$| \tilde { a } - a | \leq \frac { 2 \pi \sqrt { a ( 1 - a ) } } { T } + \frac { \pi ^ { 2 } } { T ^ { 2 } } \leq \frac { \pi } { T } + \frac { \pi ^ { 2 } } { T ^ { 2 } } \quad ( 2 7 )$$

with probability p 0 ≥ 8 π 2 . Number of calls to the oracle is also T ; T -1 calls in the controlled Grover's operation and 1 in eigenstate preparation. Therefore if π T + π 2 T 2 &lt; ϵ = ⇒ | a -˜ a | &lt; ϵ . Hence T = O ( 1 ϵ ) calls are required to get the correct estimate upto a bound of ϵ with a probability of 8 π 2 .

## Using median estimate to boost the success probability:

The motivation behind using the median estimate is that in order for the median to fail the experiment must fail more than half of the times therefore as the number of samples increase the probability of failure decreases exponentially.

Let X denote the random variable corresponding to the success of the event that upon using T evaluations of the base

classifier in the phase estimation algorithm the error bound in Equation 27 is achieved. Clearly X is Bernoulli with p 0 (i.e. X ∼ B p ( 0 ) ). Let Y = ∑ N i =1 X i , i.e. Y ∼ Binomial N,p ( 0 ) then the probability that that the median fails to satisfy the bound is given by:

$$P [ | \tilde { a } - a | > \frac { \pi } { T } + \frac { \pi ^ { 2 } } { T ^ { 2 } } ] \leq P [ Y \leq \frac { N } { 2 } ] \quad \quad ( 2 8 )$$

Using the Chernoff's bound for binomial,

$$P [ Y \leq ( 1 - \delta ) \mu ] \leq e ^ { - \frac { \delta ^ { 2 } \mu } { 2 } },$$

choose δ = 1 -1 2 p 0 to get a bound for Equation 28:

$$P & [ | \tilde { a } - a | > \frac { \pi } { T } + \frac { \pi ^ { 2 } } { T ^ { 2 } } ] \leq P [ Y \leq \frac { N } { 2 } ] \leq \exp ( - \frac { ( 1 - \frac { \pi ^ { 2 } } { 1 6 } ) ^ { 2 } N ( \frac { 8 } { \pi ^ { 2 } } ) ) } { 2 } ) & \text{for Classic} \\ & \tau \dots c \dots \cdots \cdots \cdots \cdots \cdots \cdots \cdots c$$

Therefore, choose N = ⌈ 17 ln( 1 δ ) ⌉ to have a certainty of 1 -δ by which the median estimate is within the desired bounds. Overall, to find the estimate of a within the tolerance of ϵ with a probability of 1 -α , the quantum phase estimation algorithm requires O ( 1 ϵ ln( 1 α )) calls to the base classifier.

Proof of Theorem IV.3. For quadratic speedup, we just need to show that the classical method requires O (ln( 1 δ ) 1 ϵ 2 ) calls to the oracle to get an estimate within a bound of ϵ with probability 1 -δ . This can be done using Theorem 2 of [46]. For N number of evaluations of the base classifier the expected length of the Clopper-Pearson interval with probability 1 -δ can be written as

$$\epsilon & = \mathbb { E } [ L _ { c p } ] = 2 z _ { \delta / 2 } N ^ { - 1 / 2 } ( p ( 1 - p ) ^ { 1 / 2 } ) + O ( N ^ { - 1 } ) \quad \text{ as show} \\ & = \Omega ( \sqrt { \ln ( \frac { 1 } { \delta } ) } N ^ { - 1 / 2 } ) \quad \text{ (31)} \quad \text{ $3\ T\epsilon$} \\. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &.. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &.$$

where z α/ 2 is the upper α/ 2 quantile of the normal distribution and the for the last asymptotic equality we use the asymptotic behaviour of the tail of the Gaussian. Therefore to obtain with a probability 1 -δ , an estimate ˜( g x ) of the smooth classifier g x ( ) such that | ˜( g x ) -g x ( ) | &lt; ϵ we need O (ln( 1 δ ) 1 ϵ 2 ) calls to the classifier.

## D. Further details on experiments

1) Binary-MNIST Classification: To get the base classifier we train a convolution neural network [47] coupled with adversarial training to solve the multi-class classification task by minimizing the cross-entropy loss. For adversarial training, we sample 128 perturbed images [12] and take the empirical mean of all the perturbed predictions as an estimate of the smooth classifier from Equation 7. We choose the smoothing defined by p + = p -= 0 2 . for training the network. Note that, although the certification works for any model, we still use adversarial training to ensure that the resulting smooth classifier performs well. It is not essential to use the same smoothing parameters to construct the smooth classifier. The data space is represented as X := { 0 1 , } 16 × 16 , and the window of perturbation is Π : { 0 1 , , ..., 16 } ↦→ { 0 1 , , ..., 15 } × { 0 1 , , ..., 15 } ,

)

Fig. 10. Convergence of error with number of calls to the oracle. Comparison for Classical vs Quantum algorithm with errors averaged over 170 graphs from the Graph classification test case.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00895v1-figure-a3344a93-b961-49fb-9231-bd4b94afa89b.jpg)

i.e., Π( ) i gives the index of the i th pixel of the window. The set Π here corresponds to the set I N in Appendix A. We define the perturbation model p x , i ( i ) as p x , i ( i ) := x i . i.e. independent of the location of the pixel 1 can be perturbed to 0 and vice-versa. This allows us to define the perturbation space with 2 17 perturbations. Further, we define the data-dependent probability q x , i ( i ) := p + 1 [ x i = 0] + p -1 [ x i = 1] . The characterization of p x , i ( i ) and q x , i ( i ) allows us to map this problem to the framework of Appendix A.

- 2) Graphs Classification: Here, we compare the convergence rates of classical and quantum smooth classifiers. For the graph classification task, if the quantum algorithm requires N samples, the classical algorithm requires O ( N . 1 78) samples, as shown in Figure 10.
- 3) Text Classification: Let x denote the list of input tokens, and Φ the removal of a token. Further, I denotes the indices of the tokens corresponding to stop words. For i ∈ I , define, p x , i ( i ) = Φ and q x , i ( i ) = 0 if x i = Φ , q x , i ( i ) = p rem otherwise. Essentially, given x , we map it to the binary vector of length |I| with all 0 's and change 0 to 1 whenever a stop word is removed. For the smoothing distribution we allow 0 to change to 1 with p + = p rem and 1 to 0 with p -= 0 . We show the certified ratio for the exact and the quantum classifier with p rem = 0 5 . in Figure 11.

Fig. 11. Certified ratio, exact classifier vs quantum classifier ( p rem = 0 5 . ) using 5 6 7 8 9 , , , , counting qubits evaluated for 600 ( 300 for each polarity) randomly selected reviews with 8 -10 neutral words.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00895v1-figure-1afaeaee-cba6-4a9e-acd7-4145b6207b49.jpg)

## REFERENCES

- [1] T. Brown, B. Mann, N. Ryder, et al. , 'Language models are few-shot learners,' Advances in neural information processing systems , vol. 33, pp. 1877-1901, 2020.
- [2] R. Thoppilan, D. De Freitas, J. Hall, et al. , 'Lamda: Language models for dialog applications,' arXiv preprint arXiv:2201.08239 , 2022.
- [3] OpenAI, Gpt-4 technical report , 2023. arXiv: 2303 . 08774 [cs.CL] .
- [4] K. Han, Y. Wang, H. Chen, et al. , 'A survey on vision transformer,' IEEE transactions on pattern analysis and machine intelligence , vol. 45, no. 1, pp. 87-110, 2022.
- [5] P. Dhariwal and A. Nichol, 'Diffusion models beat gans on image synthesis,' Advances in Neural Information Processing Systems , vol. 34, pp. 8780-8794, 2021.
- [6] A. Rajkomar, J. Dean, and I. Kohane, 'Machine learning in medicine,' New England Journal of Medicine , 2018.
- [7] A. Esteva, A. Robicquet, B. Ramsundar, et al. , 'A guide to deep learning in healthcare,' Nature medicine , vol. 25, no. 1, pp. 24-29, 2019.
- [8] A. Gnanasambandam, A. M. Sherman, and S. H. Chan, Optical adversarial attack , 2021. arXiv: 2108.06247 [cs.AI] .
- [9] S. Geisler, T. Wollschl¨ ager, M. H. I. Abdalla, J. Gasteiger, and S. G¨nnemann, u Attacking large language models with projected gradient descent , 2024. arXiv: 2402.09154 [cs.LG] .
- [10] G. Katz, C. Barrett, D. Dill, K. Julian, and M. Kochenderfer, Reluplex: An efficient smt solver for verifying deep neural networks , 2017. arXiv: 1702 . 01135 [cs.AI] .
- [11] J. Cohen, E. Rosenfeld, and Z. Kolter, 'Certified adversarial robustness via randomized smoothing,' in international conference on machine learning , PMLR, 2019, pp. 1310-1320.
- [12] A. Bojchevski, J. Gasteiger, and S. G¨ unnemann, Efficient robustness certificates for discrete data: Sparsityaware randomized smoothing for graphs, images and more , 2023. arXiv: 2008.12952 [cs.LG] .
- [13] P. W. Shor, 'Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,' SIAM Journal on Computing , vol. 26, no. 5, pp. 1484-1509, Oct. 1997, ISSN: 1095-7111. DOI: 10. 1137/s0097539795293172. [Online]. Available: http:// dx.doi.org/10.1137/S0097539795293172.
- [14] L. K. Grover, A fast quantum mechanical algorithm for database search , 1996. arXiv: quant- ph/9605043 [quant-ph] .
- [15] N. Franco, T. Wollschl¨ ager, N. Gao, J. Lorenz, and S. Guennemann, 'Quantum robustness verification: A hybrid quantum-classical neural network certification algorithm,' 2022 IEEE International Conference on Quantum Computing and Engineering (QCE) , pp. 142153, 2022.
- [16] N. Franco, T. Wollschl¨ ager, B. Poggel, S. G¨nnemann, u and J. M. Lorenz, 'Efficient milp decomposition in quantum computing for relu network robustness,' in 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) , vol. 01, 2023, pp. 524534. DOI: 10.1109/QCE57702.2023.00066.
- [17] Y. Du, M.-H. Hsieh, T. Liu, D. Tao, and N. Liu, 'Quantum noise protects quantum classifiers against adversaries,' Physical Review Research , vol. 3, no. 2, p. 023 153, 2021.
- [18] W. Gong, D. Yuan, W. Li, and D.-L. Deng, Enhancing quantum adversarial robustness by randomized encodings , 2022. arXiv: 2212.02531 [quant-ph] .
- [19] A. Saxena, T. Wollschl¨ ager, N. Franco, J. M. Lorenz, and S. G¨ unnemann, 'Certifiably robust encoding schemes,' 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) , 2024.
- [20] J.-C. Huang, Y.-L. Tsai, C.-H. H. Yang, C.-F. Su, C.-M. Yu, P.-Y. Chen, and S.-Y. Kuo, 'Certified robustness of quantum classifiers against adversarial examples through quantum noise,' in ICASSP 2023 - 2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) , 2023, pp. 1-5. DOI: 10.1109/ ICASSP49357.2023.10095030.
- [21] G. Brassard, P. Høyer, M. Mosca, A. Montreal, B. U. of Aarhus, and C. U. of Waterloo, 'Quantum amplitude amplification and estimation,' arXiv: Quantum Physics , 2000.
- [22] M. Yang, T. Guo, T. Zhu, I. Tjuawinata, J. Zhao, and K.-Y. Lam, 'Local differential privacy and its applications: A comprehensive survey,' Computer Standards &amp; Interfaces , vol. 89, p. 103 827, 2024, ISSN: 09205489. DOI: https://doi.org/10.1016/j.csi.2023.103827. [Online]. Available: https : / / www. sciencedirect . com / science/article/pii/S0920548923001083.
- [23] A. Kumar, A. Levine, S. Feizi, and T. Goldstein, Certifying confidence via randomized smoothing , 2020. arXiv: 2009.08061 [cs.LG] .
- [24] J. Schuchardt, T. Wollschl¨ ager, A. Bojchevski, and S. G¨ unnemann, Localized randomized smoothing for collective robustness certification , 2023. arXiv: 2210. 16140 [cs.LG] .
- [25] G.-H. Lee, Y. Yuan, S. Chang, and T. S. Jaakkola, Tight certificates of adversarial robustness for randomly smoothed classifiers , 2020. arXiv: 1906.04948 [cs.LG] .
- [26] Y. Du, M.-H. Hsieh, T. Liu, D. Tao, and N. Liu, 'Quantum noise protects quantum classifiers against adversaries,' Phys. Rev. Res. , vol. 3, p. 023 153, 2 May 2021. DOI: 10.1103/PhysRevResearch.3.023153. [Online]. Available: https://link.aps.org/doi/10.1103/ PhysRevResearch.3.023153.
- [27] M. Weber, N. Liu, B. Li, C. Zhang, and Z. Zhao, 'Optimal provable robustness of quantum classification via quantum hypothesis testing,' npj Quantum Information , vol. 7, no. 1, May 2021. DOI: 10.1038/s41534-021-

00410-5. [Online]. Available: https://doi.org/10.1038% 2Fs41534-021-00410-5.

- [28] W. Gong, D. Yuan, W. Li, and D.-L. Deng, Enhancing quantum adversarial robustness by randomized encodings , 2022. arXiv: 2212.02531 [quant-ph] .
- [29] K. Miyamoto, Bermudan option pricing by quantum amplitude estimation and chebyshev interpolation , 2021. arXiv: 2108.09014 [quant-ph] .
- [30] A. Sahdev and M. Kumar, 'Adversarial robustness based on randomized smoothing in quantum machine learning,' [Online]. Available: https://openreview.net/ forum?id=o-Yxq5iicIp.
- [31] N. Franco, M. Kempkes, J. Spiegelberg, and J. M. Lorenz, 'Quadratic advantage with quantum randomized smoothing applied to time-series analysis,' arXiv preprint arXiv:2407.18021 , 2024.
- [32] L. Gosch, D. Sturm, S. Geisler, and S. G¨ unnemann, Revisiting robustness in graph machine learning , 2023. arXiv: 2305.00851 [cs.LG] .
- [33] V. Tjeng, K. Xiao, and R. Tedrake, Evaluating robustness of neural networks with mixed integer programming , 2019. arXiv: 1711.07356 [cs.LG] .
- [34] S. Gowal, K. Dvijotham, R. Stanforth, R. Bunel, C. Qin, J. Uesato, R. Arandjelovic, T. Mann, and P. Kohli, On the effectiveness of interval bound propagation for training verifiably robust models , 2019. arXiv: 1810. 12715 [cs.LG] .
- [35] D. Zhang, M. Ye, C. Gong, Z. Zhu, and Q. Liu, 'Black-box certification with randomized smoothing: A functional optimization based framework,' ArXiv , vol. abs/2002.09169, 2020. [Online]. Available: https: //api.semanticscholar.org/CorpusID:211252440.
- [36] S. Aaronson and P. Rall, 'Quantum approximate counting, simplified,' in Symposium on Simplicity in Algorithms , Society for Industrial and Applied Mathematics, Jan. 2020, pp. 24-32. DOI: 10.1137/1.9781611976014. 5. [Online]. Available: https://doi.org/10.1137%5C% 2F1.9781611976014.5.
- [37] D. Grinko, J. Gacon, C. Zoufal, and S. Woerner, 'Iterative quantum amplitude estimation,' npj Quantum Information , vol. 7, no. 1, Mar. 2021. DOI: 10.1038/ s41534-021-00379-1. [Online]. Available: https://doi. org/10.1038%5C%2Fs41534-021-00379-1.
- [38] Qiskit contributors, Qiskit: An open-source framework for quantum computing , 2023. DOI: 10.5281/zenodo. 2573505.
- [39] D. Z¨ ugner, J. Gasteiger, and N. Gao, SEML: Slurm Experiment Management Library , version 0.3.7, 2022. [Online]. Available: https://github.com/TUM-DAML/ seml.
- [40] L. Deng, 'The mnist database of handwritten digit images for machine learning research,' IEEE Signal Processing Magazine , vol. 29, no. 6, pp. 141-142, 2012.
- [41] Z. Chen, L. Chen, S. Villar, and J. Bruna, Can graph neural networks count substructures? 2020. arXiv: 2002.04025 [cs.LG] .
- [42] G. Bouritsas, F. Frasca, S. Zafeiriou, and M. M. Bronstein, 'Improving graph neural network expressivity via subgraph isomorphism counting,' IEEE Transactions on Pattern Analysis and Machine Intelligence , vol. 45, pp. 657-668, 2020.
- [43] F. Campi, L. Gosch, T. Wollschl¨ ager, Y. Scholten, and S. G¨ unnemann, Expressivity of graph neural networks through the lens of adversarial robustness , 2023. arXiv: 2308.08173 [cs.LG] .
- [44] H. Maron, H. Ben-Hamu, H. Serviansky, and Y. Lipman, Provably powerful graph networks , 2020. arXiv: 1905.11136 [cs.LG] .
- [45] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information . Cambridge University Press, 2000.
- [46] M. Thulin, 'The cost of using exact confidence intervals for a binomial proportion,' Electronic Journal of Statistics , vol. 8, no. 1, pp. 817-840, 2014. DOI: 10.1214/14EJS909. [Online]. Available: https://doi.org/10.1214/14EJS909.
- [47] Y. LeCun, B. Boser, J. S. Denker, D. Henderson, R. E. Howard, W. Hubbard, and L. D. Jackel, 'Backpropagation applied to handwritten zip code recognition,' Neural Computation , vol. 1, no. 4, pp. 541-551, 1989. DOI: 10.1162/neco.1989.1.4.541.
Tom Wollschläger Aman Saxena Nicola Franco Jeanette Miriam Lorenz Stephan Günnemann
Discrete Randomized Smoothing Meets Quantum Computing
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.