Adversarial Robustness based on Randomized Smoothing in Quantum Machine Learning 
Authors: Aditya Sahdev
Mehul Kumar
Venue: Submitted to ICLR 2023 (2023)
Keywords: Quantum Computing
Adversarial Machine learning
Randomized Smoothing
Quantum Amplitude Estimation

Abstract: We present an end-to-end Quantum Machine Learning algorithm that encodes a classical input into a Quantum Computing state and provides certified radius for a base classifier, with robustness guarantees based on randomized smoothing - current state-of-the-art defense against adversarial attacks. Classically, the number of samples, also the number of queries to the classifier, scale with $O(1/\epsilon^2)$ where $\epsilon$ is the desired error bound in expected value of the probability measure $\rho$ defined over the randomized smoothing neighborhood. Our algorithm is designed to solve the same problem for a Quantum Computing classifier. We prove that number of queries to the classifier scale as $O(1/\epsilon)$ for the same confidence and error bound. We also present the unitary circuit corresponding to the quantum randomized smoothing algorithm, as well as the state preparation methods and circuits for smoothing distributions used to defend against common adversaries - modeled using $l_0$, $l_1$, $l_2$ norms, and other metrics. The results of comparison between the classical and simulation of the quantum algorithm are also discussed.

Under review as a conference paper at ICLR 2023
ADVERSARIAL ROBUSTNESS BASED ON RANDOMIZED SMOOTHING IN QUANTUM MACHINE LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
We present an end-to-end Quantum Machine Learning algorithm for Quantum Ad- versarial Robustness (QuAdRo) that provides a certified radius for base classifier, with robustness guarantees based on randomized smoothing the state-of-the- defense against adversarial attacks. Classically, the number of samples, also the number of queries to the base classifier scale with ((1/e²) where is the desired error bound in the expected value of the probability measure P defined over the randomized smoothing neighborhood around the input. Our algorithm solves the same problem for Quantum Computing classifier. We prove that the number queries to the base classifier is O(1/e) /) for the same confidence and error bound. We also present the unitary circuit for QuAdRo, which includes the state preparation methods and circuits for smoothing distributions used to defend against common adversaries modelled using lo. I, la norms, and other metrics. The results of the comparison between the classical and the simulation of the quantum algorithm are also discussed.
INTRODUCTION
Machine Learning (ML) models have become ubiquitous over the last decade. There has also been massive interest in Quantum Computing (QC) and Quantum Machine Learning (QML) (Aaronson] 2015). with algorithms like Shor's factoring (Shor) 1999), HHL (Harrow et al.) 2009) algorithm for solving linear system of equations, etc providing an exponential speedup over their classical counterparts. There exists another class of QC algorithms with polynomial speedup
Grover's algorithm (Grover 1996) for random database search, Quantum Amplitude Estimation (QAE) (Brassard et al. (2002) for counting problem, Bernstein- Vazirani (Bernstein & Vazirani 1997) algorithm for parity problem, etc.
Shortcomings of classical ML algorithms against malicious actors is widely-studied sub-domain (Goodfellow et al.] 2014 Madry et al., 2017) of ML. Common attack vectors include data poisoning backdoor attacks, and adversarial attacks. Adversarial attacks can easily trick well-trained classifiers
into misclassifying an input perturbed by small, usually imperceptible. noise. QML algorithms are
prone to the same problems (Weber et al. 2021 Liao al. 2021
Guan al. 2020 Lu al. 2020
Ren et al. 2022).
Popular methods for adversarial defense Madry et al. 2017) find challenging to train large, robust
classifiers, which are essential to solving real-world problems at the scale of ImageNet(Deng et al. 2009) or larger. These methods do not offer certifiable guarantees of robustness, even when they work well in practice.
Randomized smoothing is a state-of-the-ar method that offers provable robustness against adversarial attacks without any assumptions about the underlying classifier. The defense works by aggregating a classifier's 's output in a region around the input - henceforth called the smoothing neighborhood and computing the average probability of a class Pe. It is prohibitively expensive to compute the exact value of Pc over the smoothing neighborhood since the number of points is exponential in the input dimension. In practice, Monte Carlo sampling algorithms randomized smoothing for adversarial robustness (Cohen et al.) 2019 Yang et al., 2020 Lee et al. 2019h requires N Nelassicat 10 106 samples from the smoothing neighborhood.
used to estimate Pe. Typically.

---

Under review as a conference paper at ICLR 2023
Contributions In this paper, discuss a purely QC approach to implementing randomized smooth- ing by using an orthogonal representation for the input space and use existing formalism for the Quantum Counting problem (Brassard al., 2002). We create superposition of the smoothing neighborhood of the input image and use our quantum circuit to output the average probability of prediction for class Pe- We also design qubit state encoding and state preparation circuits for lg. 1 and other Ip norm adversaries, and provide results from the simulation of the algorithm in Section 6
Theorem QuAdRo encodes an input x into quantum state (xb) and, for error and confidence 1 6, requires total M O(1/c) queries the base classifier QN to return certified radius for æ. In comparison, any classical implementation of randomized smoothing based certification requires M (()/e) queries for the same guarantees.
Theorem has been proved in See 4 and QuAdRo is presented in Alg
RELATED WORK
2.1 RANDOMIZED SMOOTHING
Randomized smoothing (Cohen al. 2019 Yang et al., 2020) method has achieved provable robustness against adversarial attacks. Given an input, one can define a smoothing neighborhood based on the threat model of the adversary described by l, norm and scale parameter A. Such a robust model outputs the most likely class in the smoothing neighborhood returned by a base classifier, and this output is stable against lp perturbations. Cohen et al. (2019) first proved tight robustness guarantees for l2 norm adversary using Gaussian smoothing. Later, Yang et al. (2020) provided guarantees for a larger set of adversaries and smoothing distributions, except norm, which was provided by Lee et al. (2019).
2.2 QUBIT STATE PREPARATION
Qubits are logical units of information for Quantum Computers, equivalent to bits in classical computers. Any QC device made up of qubits that have the following two properties superposition and entanglement. Superposition refers to a qubit's s ability to exist in multiple states at the same time, while entanglement refers to the ability of multiple qubits to exist in a shared state such that an operation on one qubit also affects the state of another qubit instantancously, without any additional transfer of information. Generally, n qubits encompass 2n dimensional space where if bitstring i = b bu, then state [ ==0 (bz) where by E 1).
There are numerous methods for encoding information into qubit states, often optimized for the target problem. For example, Novel Enhanced Quantum Representation (NEQR) (Zhang et al. (013)) and Flexible Representation of Quantum Images (FRQI) (Le al. 201 used for QC Image algorithms differ from variational heuristics for calculating molecular energies like Unitary Coupled-Cluse Clusser ansatz (Romero et al. 2018). Encoding methods popular in QML applications use the amplitude of a quantum state i) as the representation of input vector element æ[i] to be encoded. This representation is really efficient but has the drawback that quantum search, amplitude estimation, etc., cannot be applied to such qubit states due to lack of orthogonality. Amplitude encoding the same number of gates but a logarithmic number of qubits compared to the basis state encoding.
A number of distributions can be prepared as superposed qubit concave distributions (Grover & Rudolph 2002), Uniform distribution using Quantum Fourier Trans- form (Deutsch] 1985). etc. Distribution parameters can be modified, either during state preparation, or using circuits like QADD (Koch et al. (022)) mid-circuit. QFT and inverse QFT, in particular, are common pair of pre- and post- prot-procsssing circuits that concentrate information from a superposition via a Fourier transform.
& Koczor 2022 Log
2.3 GROVER'S 'S SEARCH ALGORITHM
Given a boolean objective function f defined over unstructured space S of size N such that 3x e S: f() 1 and QC Oracle O operator O (z) lv) |x)) ly ① fx)), Grover's Search algorithm
(Grover 1996) allows searching for x in O(vN) calls O. Using state preparation subroutine U
2

---

Under review as a conference paper at ICLR 2023
such that U [0] 11), the Grover diffusion operator
G= (2 * ( (bb 1)0
(I)
is applied repeatedly concentrate the set of desired outcomes. The result of the measurement of a concentrated state is a value E S such that ((x = 1 with an arbitrarily high probability. The original formulation requires (ı5) to be uniform superposition of all values in the space, but later the same results were extended to arbitrary unitary operations U' (Biron et al. 1999). No QC unstructured search algorithm can perform better than O(vN) (Boyer et al. 1998).
2.4 QUANTUM AMPLITUDE ESTIMATION
An alternate formulation of Grover's search algorithm into a counting problem allows us to use the same number of oracle queries estimate the number of solutions S for f(x) using Quantum Amplitude Estimation (QAE) BBassard et al. 2002 Boyer et al. 1998). Variants of QAE (Grinko al., 202T; Aaronson & Rall 2020; Suzuki al. 2020) tailored for low circuit depth and higher confidence use fewer oracle queries and/or fewer repetitions. The vanilla QAE in Figure [ can be replaced with one of these variants without any loss of generality. detailed comparison of these
QAE variants can be found in Figure in Grinko al. (2021).
2.5 QUANTUM MACHINE LEARNING AND ADVERSARIAL ROBUSTNESS
There are multiple formulations of QML classifiers (Cong et al. 2019 Abohashima et al. 2020). Previous works have shown that QMI. models are prone to adversarial attacks. For example, (Guan et al. 2020) checks the robustness of QML models against noise in the training data using classical methods by modelling the verification problem as a classical SDP. contrast, (Weber et al. 2021) implements new protocols for QML to certify robustness optimally. The threat models and algorithm these papers differ from the algorithm presented here, though QAE-based approach can provide quadratic speedup in the case of (Weber et al. (021) well.
3 QUANTUM ADVERSARIAL ROBUSTNESS
As shown in Figure proposed algorithm for Quantum Adversarial Robustness (QuAdRo) uses state preparation U and Grover Diffusion Operator G. described in subsection and QAE, we can measure Pe an estimate of P. that base classifier answers correctly after smoothing. to high precision with high confidence, discussed in subsection 4 The symbols in the paper defined where they are first used, and a detailed table of notations is available in Appendix
and 3.2 Using
10]
X
10]
01
(0)
G
G:-
G
UPA
UP:A
10)
(0]
0g
10)
10)
QFT
QFT
O...
10)
Om
10)
out
Figure Quantum Estimation Circuit (QEC).

---

Under review as a conference paper at ICLR 2023
00
y:
01:
m1 (Imput)
000
0g
0g:
Sp (Iuput)
0/2
QNN.
UPAA
2 (0) -1
UP.A
03
0x4
06
(a) (Imput) circuit. SP can smooth the input image state to a higher resolution.
(b) Grover Diffusion Operator G. circuit.
Figure 2: Building blocks of QEC.
3.1 QUBIT STATE PREPARATION OPERATOR UP..A
Grover Diffusion Operator can only be used to search when distinct values in the input space are orthogonal. Here onwards, the smoothing neighhorhood represented as a superposition where the square of the amplitude of any perturbed input (ar + ε) represents its probability in the smoothing distribution. Due to the requirements orthogonality between individual inputs and representing the exponentially sized smoothing neighborhood, only an orthogonal basis state encoding can be used. This choice requires the same number qubits as the number classical bits.
Before state preparation, state qubits and ancilla are reset to (0). First, the input loader circuit IL loads the input x from classical bits into qubit state (ı)). For the rest of the discussion, we define d as the size of the input vector æ; and v is the number of qubits needed to represent any 2y. For 28x28 grayscale image, d = 784 and v the resolution of single pixel in the input, i.e. if each pixel belongs range 0-255, i.e. [0, 2 1], then = 8.
Let jth value in input æ be xy = -.bbt--bb i.e. byc: ith classical bit in 4j, then [ = 3 (z,)) =
(2)
To accomplish this, we use Pauli operators o; op 01 to create input loader circuit LL; that loads bys into qubit state Ojutii defined as the tensor product of a; as follows
IL, = 0 Tby
(3)
and by definition IL, 00)" = lay).
Definition Input Loader operator IL can be defined as
IL = ===
(4)
such that
IL 10)* de |agaj02....G.o-1
80=0 (zy)
(5)
Circuit IL comprises of maximum ud I-qubit gates. For any input x. if ||=]]|, k, then LL has exactly & X gates, corresponding to each [1) in (15).
After loading the input, superposition of the smoothing neighborhood of the input & is prepared based on the distribution p0;; A) set to defend against given 1p norm adversary and parameterized by A. Each perturbed value + E another valid input to the base classifier. For detailed discussion about the design and functioning of the qubit encoding scheme, look at Appendix
Definition Smoothing circuit SP with distribution defined by p. X, such that
ST.> 1b) = D6--1 V Vos(ees)) Ex)
(6)
4

---

Under review as a conference paper at ICLR 2023
where 2j + Eg is value in the neighborhood of aj. In our scheme, the complete smoothing operator SPI maps each value zj in the imput vector independently probability- weightte superposition of its neighborhood. For any in the input space, probability weight of in the smoothed qubit state is p(t; A) (1oo)jjoj 1... .... 1i+1)((111111 A). Hence
SP (t) = ST (ay) = 1
A)
In this particular case, all 3 are identical distributions centered around mean 2j. Detailed circuits for each norm are discussed in section 5
Definition 3 Qubit State Preparation Operator UP., (Figure 2 comprises of IL and SP.
UP
8 B 8 S Sp
1L3
(8)
3.2 GROVER DIFFUSION OPERATOR G.
Based on section 2.3 and 2.4 we design a robust QML classifier from any base binary classifier fc for class provided by unitary quantum parallel (Nielsen & Chuang 2002) oracle QN Ne. If output of the QMI. classifier for input æ class e then fa(x) else fa(x)
Definition 4 QMI. classifier oracle QNNc
QNNa (x) (8) (x) y fc(z))
(9)
Setting (u) =1-) J/2 (10) [1)) Deutsch & Jozsa
1992).
QNN. (x) |-) (-1)fole) (x)) 1-)
(10)
When applying QNN. to the smoothed superposition of inputs given by UPAA |0] du from section 3.1. Pe is the expected probability output by our algorithm i.e. input xx + +) in the smoothing neighborhood belongs to class c
Pc = =((
(11)
Definition The Grover Diffusion Operator Ge derives from state preparation circuit UP and QNNe as shown in Figure Db
G. = UT- (0) 1)Untt QNN
(12)
3.3 QUANTUM ESTIMATION CIRCUIT
QEC uses QAE Brassard et al. 2002) to solve the counting problem defined for QNN: using UPA.A and Ge. The ancilla qubits a) in Figure are initialized a uniform superposition in the range
[0, M] via QFT. Here, M is the total number of calls to the oracle in the circuit. Then, we apply
controlled G. gates using (ax) control, which results in
QAE vi) Ja) G |b> (a)
(13)
for all After applying QFT!, measure the ancilla state obtain 0 such that the probability measure Pe is
Pe sin (0/2)
(14)
4 THEORETICAL BOUNDS
As noted earlier, the smoothing distribution o; for each value in the input vector z is independent, as per classical robustness criteria (Cohen et al. 2019 Yang et al. 2020). We claim that the proposed quantum algorithm QuAdRo finds P. with quadratic speedup compared to the best-known classical algorithm with the same error bound. We show that the certified robustness problem can be reduced to counting problem, and for given error in the measurement of Pe for fixed confidence ö, the best known classical algorithm is O ( and QuAdRo OL)). This is also the best speedup possible for counting problem using quantum computer (Brassard et al. 2002).
5

---

Under review as a conference paper at ICLR 2023
Algorithm 1 Quantum Adversarial Robustness (QuAdRo)
procedure QUADRO(Imuut (16), Class e, UPii, Ge M, 5)
Nrep 12 log (g) +
NyFC Nrep for i in Range (Nrep) do
0, = Q (b) U.. Ger N)
Pe [i] sin 6 2
end for
Pe median( Pe lowerConfBound Po Norc
lowerCon Bound 2 then return CortiiccFRadiuseooverCCooBoBoo))
else return -1, ABSTAIN end if
end procedure
4.1 QUANTUM COMPUTING BOUNDS
Given that m ancilla qubits are used for estimation, maximum number of oracle calls can
M >m 2* 2 -1 8 The probability that we measure 0 correctly upto bits is ş.. and the measured probability value Pe such that
(15)
V Po(1 po) l Pell S 60 2m
T²
(16)
M
M
More generally, for a single experiment with no repetitions, the error measurement of Pe with a confidence 1 - (using theorem 12 from Brassard et al. (2002) is
Pa(1 Po)
x²2
n
l Pell S c = 8
(17)
2M
4.²
82
4M²
Solving Eq. 17 for M in terms of 8 gives
poll - Po)
M
0
(18)
de
dc
The success probability in Eq. experiment multiple times and using the median estimate of Pe: (Miyamoto) 2022). As result,
16 can quickly boosted close to 100% by repeating the
M ~ 00- (1=1ogt
(19)
Constants for calculating M in Eq. 19 are small, as shown in Algorithm [1] and Nrep and Nogc are based on Theorem 2 in Miyamoto 2022), also derived from Theorem 12 Brassard al. 2002)
4.2 CLASSICAL COMPUTING BOUNDS
There are numerous intervals and bounds commonly used for statistical guarantees, that result in similar order of magnitude calculating M in terms of for confidence 8. we use Chermoff Bounds
R62
P(IIX - All < 6p) 2 1 2e
(20)
ie for M repetitions of the function classically.
P(Ip- pell S E) 2 1 2e
(21)
For the same setting, using Clopper-Pearsen interval is more popular practice since it provides
tighter bounds upto O(M 3) (Thulin 2014).
M 12 p( p) M-
(22)

---

Under review as a conference paper at ICLR 2023
For confidence 1 6, ignoring for large M,
Pl Pall S M 22g V (((1p)
(23)
Hence
= 2/ - p) M ~ 2
0
(24)
CIRCUITS FOR SMOOTHING DISTRIBUTIONS p, X
Table shows best performing smoothing distributions for each common adversary (Yang al. 2020
Lee et al., 2019). As shown in Yang et al. (2020), the same distribution can be used to counter multplle adversaries. These are subset all possible (ø, (p) pairs, for which we present the state preparation circuits. Please refer to other works (Yang et al. 2020 Lee et al. [2019] Cohen et al.) 2019) for detailed discussion on optimal distributions. Density in
match the probability
distribution obtained from state preparation UPP.A, Appendix discusses this topic in detail.
Table I: Adversary norm parameters and corresponding certified robustness radius.
Adversary 4p
Distribution
Density
Certified Radius
lo
Tight Certificate Uniform L.0
== a A 2 (2"--11
prgmax,p,7
2
0(1 S A) x
2X(pe - 22)
l2
Normal Distribution
e
12
(GoussianCDF=11g00.0
5.1 lo NORM
Theorem The state preparation U in Figure requires only O(v) elementary gates (+e 2v),
where cos(?) = V
X-1 2- to prepare the state (proof in Appendix
2 X
U0 (2z))
V 2
bz)) + EBta, V
18)
(25)
2" 1)
a0
(0)
())
H
IL
0g
(0)
Q3
(0)
(0)
Ry (0)
Figure 3: UnAA circuit for to norm adversary.
U0 smooths state (r,) into quantum state with amplitude for (ır)) and equal superposi- tion the rest of the space. Ugh requires one additional ancilla qubit that cannot be disentangled.
5.2 4 NORM
For I norm adversary, we use a uniform distribution with width X, centred at the pixel value a. To create superposition state in Uniform distribution, if = 2* k E Z, then the Hadamard operator И on k-qubits 0 can be used. The circuit in Figure can also be adapted to prepare a uniform distribution by setting for any A. The prepared uniform distribution can then be shifted to its corresponding mean, resulting in A as shown in Figure
I. MMor generally, QFT(() can prepare the requisite uniform distribution
7

---

Under review as a conference paper at ICLR 2023
5.3 l2 NORM
Creating Gaussian distribution (and any other log-normal distribution) is well-studied problem (Grover & Rudolph 2002). The relevant circuit is described in Figure 2 in the Appendix The same effect can also be achieved using the SHIFT(a, w) operator, as shown in Figure
5.4 OTHER ADVERSARIES
Any log-concave distribution can be created as a qubit state with a quantum circuit (Grover & Rudolph 2002), and the SHIFT operator in Figure [ to shift the distribution
mean value. Yang et al. 2020) uses log-concave distributions for randomized smoothing, for instance, Laplace Uniform distribution for loc norm adversary. Refer to Table A.1 in Yang al. (2020) for comprehensive list of viable distributions and corresponding certified radii.
01
0)
Distribution
SHIFT(a,
0g
oy
0g
0)
Figure UP. circuit for Ip norm.
6 EXPERIMENTS
Due to lack of access to QC hardware at the time of writing, all the presented results are obtained using simulation. For the base classifier, we train 2-layer Deep Neural Network (DNN) model for recognizing handwritten digits using the MNIST dataset from Torch v1.11.0. First, fully connected layer followed by leakyRelu activation, normalization, and scaling to 4-bit integer representation. This discretized classifier has accuracy A 89.8% the MNIST test dataset. We found that Projected Gradient Descent (PGD) adversary (Madry et al. 2017) can successfully attack this classifier, and this attack can be defended against using Randomized Smoothing (Cohen et al.) 2019). Detailed model architecture can be found in Appendix B All training and simulation used an Nvidia RTX 2080 Ti GPU.
To compare QuAdRo with the classical randomized smoothing algorithm, we reduce the problem size simulate the QC circuit efficiently. First, we the feature vector after layer of the classifier as input that the adversary can attack. Second, we use a small layer 2 d 5. Third, we discretize feature vectors 4-bit integer values after training 22 possible inputs, which can be completely simulated classically. Additional 6- 12 ancilla qubits are required for the QEC. Based on preliminary experiments, the simulation cost of QEC- based prediction is high, so classical predictor with N Nprediet = 100 is used in all experiments. Complete MNIST test set is used for experiments in Table while simulation plots in Figure 5 Juse subsamples of size 1000 5a, b and 100 5p.
4. This limits the input space to bits, i.c.
200
50
40
104
Figure 5: Certified accuracy radius for parameters a (left) Adversary À for Normal distribution; (middle) Smoothing distribution truncation parameter w ; e (right) Oracle calls ne Norrtify for classical algorithm; nq Nqæe for QuAdRo:
8

---

Under review as a conference paper at ICLR 2023
The experiments designed around four parameters adversary, Noæe calls the classifier oracle. 1 confidence, and 2 * w + 1 width of the truncated smoothing distribution. It is evident from Figure 55 that increasing À reduces certified accuracy as expected while a smaller À represents a weaker adversary. The effect of change in width wo on Pa in Figure 5) is not very pronounced. We observed that < À cannot model adversary for radius simulation cost, À E [2,4], w E 5] are optimal for our experiments. Table shows the results of our experiments.
d. Since linearly increases
Table 2: Results: Accuracy of robust classifiers for MNIST test dataset abstain (Abs) when pe < 0.5. Acc (IAbs) refers to the accuracy for certified imputs where classifier does not abstain.
Classifier
Acc %
Abs %
Ace (!Abs) %
Pe (y yprea)
Pe (y + ypred)
Base
89.73
Quadro NQEE 12
88.4
22.0
95.2
0.80
0.45
Quadro NQEE : 120
88.4
17.7
94.1
0.83
0.39
Classical Neertify 1000
87.7
17.8
94.0
0.82
0.40
Classical Neertify 10000
88.0
17.8
94.0
0.83
0.40
Based on the theoretical discussion (Thulin 2014
Montanaro 2015), given the number of calls to
the classifier oracle M = Neertify- we can use N Neertify samples for classical certification while
[.(1-pp)) we should see QuAdRo uses Nrep iterations of size NQEc. Given Ey RJ Nona. 2 V Nocrtisy quantum advantage (eg 6c) for
12 log 2/ pe pe)
3 +
NQEC 49
(26)
QuAdRo's os accuracy outpaces the classical algorithm NQ i.e. Neertsfy increases, especially for contentious examples since they have a low certified radius. For median Pr = 0.8 from Table 2 the results for the two algorithms match around NQea 2000 for d 0.001, which is observed in Figure 5. To match the certified radius for Pa 1.0, NQEC must scale by T-pe
The simulations accurately depict the functioning of QuAdRo, except making 2dv calls to the classifier create the superposition state instead of de theoretically needed by the QC equivalent. In addition, floating point errors in the qubit state amplitude have been mitigated through normalization. All the theoretical bounds should remain the same for simulation results well.
7 CONCLUSION
We developed the algorithm QuAdRo that creates a robust classifier and provides certified radius for any base QML classifier. Section establishes S that the QuAdRo offers quadratic speedup over existing classical algorithms for certified adversarial robustness via randomized smoothing. The same guarantees were simulated and tested in Section The results hold for any distribution and classifier that can be implemented on Quantum Computing device, and the QC circuit to prepare popular smoothing distributions as qubit states are presented Section and Appendix C We have not made any additional assumptions on the base classifier; hence any guarantees that hold for prior art (Cohen al., 2019; Yang et al.] 2020) should hold for QuAdRo as well. Based on experiments, QuAdRo abstains less frequently and is more reliable than the robust classical classifier when Neertify is increased.
Broader Impact and Limitations: The robustness guarantees in this paper apply only to the adversarial attacks on a classifier. The robust classifier will also inherit the underlying bias (e.g. training data, mistepresentation of objects/people, etc.) in the base classifier. The algorithm presented here also depends on a functional QC hardware for the speedup, and application to meaningful image inputs will need 1000 qubits.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Scott Aaronson. Read the fine print. Nature Physics, 11(4))2112233, 2015.
Scott Aaronson and Patrick Rall. Quantum approximate counting, simplified. In Symposium on Simplicity Algorithms, pp. 24 32. SIAM, 2020.
Zainab Abohashima, Mohamed Elhosen, Essam Houssein, and Waleed Mohamed. Classification with quantum machine learning: A survey, arXiv preprint arXiv:2006. 0220006.22777 /2270, 2020.
Ville Bergholm, Josh Izaac, Maria Schuld, Christian Gogolin, M Sohaib Alam, Shahnawaz Ahmed, Juan Miguel Arrazola, Carsten Blank, Alain Delgado, Soran Jahangiri, et al. Pennylane: Automatic differentiation of hybrid quantum-classien computations. arXiv preprint arXiv: 1.04968, 2018.
Ethan Bernstein and Umesh Vazirani. Quantum complexity theory. SIAM Journal computing, 26 (5):1411-1473, 1997.
David Biron, Ofer Biham, Eli Biham, Markus Grassl, and Daniel A Lidar. Generalized grover search algorithm for arbitrary initial amplitude distribution. Lecture notes in computer science, pp. 140-147, 1999.
Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. Tight bounds on quantum searching. Fortschritte der Physik: Progress of Physics, 46(4-5):493-500 1998.
Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53-74 74, 2002.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized
smoothing. In International Conference on Machine Learning, pp. 1310-1320. PMLR, 2019.
Iris Cong, Soonwon Choi, and Mikhail D Lukin. Quantum convolutional neural networks. Nature Physics, 15(12)11233-1278 2019.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255. Icve, 2009.
David Deutsch. Quantum theory, the Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 400(1818): 97-117, 1985.
principle and the universal quantum computer.
David Deutsch and Richard Jozsa. Rapid solution of problems by quantum computation. Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences, 439(1907):553-555 1992.
Edward Farhi and Hartmut Neven. Classification with quantum neural networks on near term processors. arXiv preprint arXiv: 06002, 2018.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572, 2014.
Dmitry Grinko, Julien Gacon, Christa Zoufal, and Stefan Woerner. Iterative quantum amplitude estimation. npj Quantum Information, 7(1):1-6, 2021.
Lov Grover and Terry Rudolph. Creating superpositions that correspond to efficiently integrable probability distributions. arXiv preprint quant-ph/0208//111 2002.
Lov K Grover. fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp. 212-219, 1996.
Ji Guan, Wang Fang, and Mingsheng Ying. Robustness verification of quantum machine learning. CoRR, 2020.
Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical review letters, 103(15):150502, 2009.
10

---

Under review as a conference paper at ICLR 2023
Vojtéch Havliček, Antonio D Córcoles, Kristan Temme, Aram W Harrow, Abhinav Kandala, Jerry M Chow, and Jay M Gambetta. Supervised learning with 567(7747):20--111 2019.
feature spaces. Nature,
Daniel Koch, Michael Samodurov, Andrew Projansky, and Paul M Alsing. Gate-based circuit designs for quantum adder-inspired quantum random walks on superconducting qubits. International Journal of Quantum Information. pp. 2150043, 2022.
Phuc Q Le, Fangyan Dong, and Kaoru Hirota. flexible representation quantum images for polynomial preparation, image compression, and processing operations. Quantum Information Processing, 10(1):63 84, 2011.
Guang-He Lee, Yang Yuan, Shiyu Chang, and Tommi Jaakkola. Tight certificates of adversarial robustness for randomly smoothed classifiers. Advances in Neural Information Processing Systems, 32, 2019.
Haoran Liao, Ian Convy, William J Huggins, and K Birgitta Whaley. Robust in practice: Adversarial attacks on quantum machine learning. Physical Review A, 103(4):042477, 2021.
Sirui Lu, Lu-Ming Duan, and Dong-Ling Deng. Quantum adversarial machine learning. Physical Review Research, 2(3):033212, 2020.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint 2017.
Koichi Miyamoto. Bermudan option pricing by quantum amplitude estimation and chebyshev interpolation. EPJ Quantum Technology. 9()::1-27, 2022.
Ashley Montanaro. Quantum speedup of monte carlo methods. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 471(2181):001503) 503001, 2015.
Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002.
Arthur G Rattew and Bálint Koczor. Preparing arbitrary continuous functions in quantum registers with logarithmic complexity. arXiv preprint 1XXiv:2205000112 2022.
Wenhui Ren, Weikang Li, Shibo Xu, Ke Wang, Wenjie Jiang, Feitong Jin, Xuhao Zhu, Jiachen Chen, Zixuan Song, Pengfei Zhang, al. Experimental quantum adversarial learning with programmable superconducting qubits. arXiv preprint arXiv:2204.01738, 2022.
Jonathan Romero, Ryan Babbush, Jarrod R McClean, Cornelius Hempel, Peter J Love, and Alán Aspuru-Guzik. Strategies for quantum computing molecular energies using the unitary coupled cluster ansatz. Quantum Science and Technology. 4(1):014008, 2018.
Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. Advances in Neural Information Processing Systems, 32, 2019.
Maria Schuld and Nathan Killoran. Quantum machine learning in feature hilbert spaces. Physical review letters, 122(4):040504, 2019.
Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac, and Nathan Killoran. Evaluating analytic gradients on quantum hardware. Physical Review A, 99(3))033233, 2019.
Peter W Shor. Polynomial- algorithms for prime factorization and discrete logarithms on quantum computer. SIAM review, 41(2):303-332, 1999.
Yohichi Suzuki, Shumpei Uno, Rudy Raymond, Tomoki Tanaka, Tamiya Onodera, and Naoki Yamamoto. Amplitude estimation without phase estimation. Quantum Information Processing, 19 (2):1-17, 2020.
Mâns Thulin. The cost of using exact confidence intervals for a binomial proportion. Electronic Journal of Statistics, 8(1):1778840, 2014.
11

---

Under review as a conference paper at ICLR 2023
Maurice Weber, Nana Liu, Bo Li, Ce Zhang, and Zhikuan Zhao. Optimal provable robustness of
quantum classification via quantum hypothesis testing. npj Quantum Information, 7(1):1-12, 2021.
Greg Yang, Tony Duan, J Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. In International Conference on Machine Learning, pp. 10693- 10705. PMLR, 2020.
Kaining Zhang, Min-Hsiu Hsieh, Liu Liu, and Dacheng Tao. Toward trainability of quantum neural networks. arXiv preprint arXiv:2011.06258, 2020.
Yi Zhang, Kai Lu, Yinghui Gao, and Mo Wang. Neqr: novel enhanced quantum representation of digital images. Quantum information processing, 1288332333, 2013.
12

---

Under review as a conference paper at ICLR 2023
A
NOTATION AND SCHEMATIC
Table 3: Notation used in the paper
Symbol
Description
2
Input (vector)
byc
7th classical bit jdh element of the input vector Perturbation to the input element
8
C
Class predicted by base classifier
Distance norm that characterizes the adversary Scale parameter for smoothing distribution
Smoothing distribution
Pe
Average probability class in the neighborhood of x:
Pe
Measured probability of class in the neighborhood of x using sampling amplitude estimation
Pc
Median of Pe
M
Total number of calls to the base classifier (oracle)
Error bound on Pc: Confidence bound
8
Number of ancilla qubits in QEC Ground state qubit Bitstring for input encoded into qubits e.g (5) (01101) in 4 dimensional input space hthh qubit wire/state
10)
ag
0
Pauli operators ie. o. = 01 X, x 03
(b)
Qubit state of Input
Image Loader QC operation to load æ into state ())
SpA
QC operation to prepare the superposition of smoothing neighborhood (
UPA
State preparation unitary based on lp and À
QNN.
QML classifier
Ge
Grover diffusion operator for class
QAE
Quantum Ampltitude Estimation
QEC
Quantum Estimation Circuit
QuAdRo
Quantum Adversarial Robustness algorithm
Nrep
Number repetitions QEC in QuAdRo
NQEC
Number of classifier oracle calls in one shot/run of QEC
0
Phase estimated by raw QAE operation s.t. sin (0/2)
Predict
Certify
Quantum Mochine
Impul))
Chassifir
Quantum Enooder
Probability
Distributon ony Perturtetion
Casssccl Computer
Cerified rodiuz
ReN
No
Output C,
Abstain
Figure 6: Flow diagram describing QuAdRo.
13

---

Under review as a conference paper at ICLR 2023
B SIMULATION: DISCUSSION, PLOTs, RESULTS
To be able to simulate QuAdRo on a classical computer, we reduced the problem size by following three changes first, used feature vector after layer I of the model input that adversary can attack. Second, we use a small layer 2. Third, we discretize feature vectors to 4 bit int values after training. This allows to limit the total input space 20 bits, space of 2 possible inputs, which can be completely simulated.
Even for the smaller problem size, show that
The input space is local i.e. the nearby points in a neighborhood are likely to belong to the same class
A non-trivial classical classifier C' can be trained the dataset, achieving se 90% accuracy
An adversary A (PGD) can easily find inputs that are mis-classified by C'
Classifier based on randomized smoothing with lp norm and parameter is effective against A's 's attack.
We created the quantum algorithm simulator numpy, using output the over the complete input space of size 2 to calculate the superposition of states and exact Pe for comparison.
B. MODEL ARCHITECTURE
First, we train 2-layer DNN model trained from scratch layer DNN, Layer of size 784*5, Layer 2 of size 5* 10, using LeakyRelu activation with scaling factor 0.03. Layer inputs normalized, and scaled by 24, Base classifier C' inherits trained Layer2 from model, and inputs are the feature vector output by Layer 1 in the previously trained model, discretized to 4 bit integer representation in range [0, 16). Leaky Relu activation with a scaling factor 0.03 is used after fcl, to make feature vectors partially invertible and can used to visualize images for features outside the train and test datasets.
B.2 SIMULATION SETUP
We simulate QuAdRo for a qubit input, with a total 26-32 simulated qubits, since simulating much larger system is not feasible classical computer. Due to lack of access to quantum computer at the time of writing, the presented results were all simulated.
Given this setup, we implement both the classical and quantum computing algorithms for randomized smoothing to find the certified radius. We simulate Normal Distribution since can defend against 4 l2, and foo adversaries (Yang et al., 2020). We show that for same number of calls to the classifier, QuAdRo error bounds improves and surpasses the classical algorithm for same hyperparameters and input.
The simulator implementation is non-trivial. We recommend reading the code (in supplementary material) and comments in addition to Appendix B Following is a list of noteworthy features of the simulator
Calculates MNIST classifier output for the complete input space. This is used simulate QN N. oracle and calculate the exact value of and corresponding certified radius. Smoothing state v is prepared using discretized Normal Distribution defined by
f (i, mu, sd) = np. exp (i - mu) * 2 (2+sd**2)
for pixel value mu, sd = A.
The QFT operator on ancilla and the following Grover operator applied & have been simplified into an iterative operation on initial state. The iteration has NQEE steps.
B.3 CODE SNIPPETS
We will release the code in supplementary material with its license. The code snippets here are only for reference, and recommend using the code from supplementary material for simulation. The
14

---

Under review as a conference paper at ICLR 2023
following two functions can be used to simulate the Grover's Search operation by first preparing the requisite 3 then repeating the search operation, or using it in a subroutine for amplitude estimation.
def get_psi_npp (vals, low, high sd, v)
p [] psi -
for i, val in enumerate :
= np. zeros cnum_points)
for in range (low, high):
xii] = np.exp (- mu) x* (2*sdx*2))
p.
)x))
if == 0):
psi pli]
else:
psi = kron (psi, p(i])
norm np. np.linalg.... norg.nnomppppp (psi)
psi = psi/norm
return (p, psi)
def grover (classsffeertteeeeeeennn
psi, prev_state):
a np. not (psi, prev_state)
cur_state = 2+axpsi prev_state
cur_ = classifier hta.fier_tenssorcur_ttcct
# Normalize to deal with floating point issues norm np. return cur_state/norm
B.4 OTHER
One major difference in classical randomized smoothing and QuAdRo is the order of sampling and classifier operation. Classically, we sample from the neighborhood first, and then apply base classifier each sample. In QuAdRo, a posteriori. We expect to see a consistently better performance from QuAdRo for large NoEa than suggested by the theoretical discussions.
first apply the base classifier the whole space, and then measure
C STATE PREPARATION CIRCUITS
C.I QUBIT ENCODING CHOICE
Classical data can encoded into a quantum state in numerous ways. Amplitude encoding is one of the most popular methods vector of real/complex values is encoded as the amplitude of the N states a superposition such that the amplitude of [i) corresponds to the ith value the input vector.
Variations of this scheme have been used for different algorithms (Zhang al. 2013 Le et al. 2011).
Oracle output for any input is pixel state dependent and any smoothing operation will destroy that information if pixel state amplitude encoded this is equivalent to running the algorithm for the mean of all images in the smoothing neighborhood for the given distribution.
C.2 lo NORM
The circuit in Figure 7 is optimized for low circuit depth and gate count. General state of this system will be referred to (bb.)) |æ:) Ja), where |az) represents the qubits that will eventually be in superposition state of the smoothing distribution, while (a) is the additional qubit needed the circuit.
Subscript represents nh logical step in the circuit.
Initially, all qubits are set to the ground state (0), hence the state of the system is
(//o)
10)" 10)
(27)
15

---

Under review as a conference paper at ICLR 2023
30
(0]
(0)
H
II.
(0]
(0]
(0)
(0)
Figure 7: UPA circuit for lo norm adversary.
Assuming V elements in the imput space and adversary À such that V X 2 1, the operator Ry (0)
rotates the ancilla state a, where cos( () /
(0) 00 = cos( g -snn 0
2 [1)
(28)
hence
((b1) = cost 10; 10) sinl 100 (1)
0
(29)
Applying u-dimensional Hadamard gate H creates uniform superposition of V 2" states. Here, H@v can be replaced with QFT + 2" for generality. State after the X gate is
(22) = cos( G 10)" [1)
1
sin ( (1)) 10)
(30)
VV
After image loading,
A la) (1) (1b) cos( (00()))1)
sin d
c 10)
(31)
VV
2
After Hadamard H on the ancilla
(bba) (cos( θ ())) VV
1
Poy 5
sinl
sin(
[0) [0) (cos( θ
(
+
1
sin
[1)) (32)
2
VV
Applying QEC on (zb) works for either value of with initial probability
sin
A
P([x) a) = cos2 5
(33)
C.3 ALTERNATE FORMULATION
Alternatively, in situation where repeating measurement of |a) is easier, can use cos(E)
VVX-VV=I-X and repeat the experiment until measurement (a) 1.
(x) (cos())
1 VV VV sin ())
vV sin Exifa li)
(34)
and probability of measuring ancilla
1
0 ?) )sin
P((a) = 1) = 7 + 21
2
(35)
Hence
2
(V 1) A(V +1
P(a = - P(a = 0)
(1
(36)
(V 1)
++1
16

---

Under review as a conference paper at ICLR 2023
Since Pa 1) 2, estimated number of repetitions of the state preparation circuit is less than 2. Please note that state preparation is also a part of Grover's Diffusion Operator, and will concentrate ancilla state [1) after repeated upplications. In general, measuring the output of QEC circuit multiple (<2) times until a = yields the required state. We expect this alternate circuit to be more useful as component in variational circuit.
To get the correct result, we need to perform the experiment multiple times, until ancilla state is measured as [1). The expected number of trials <= 2. addition, ancilla with the discarded state (0) has an error ~ O in the amplitude of (æ) which may be acceptable for some A, V, and M.
C.4 SHIFT OPERATOR
Any prepared qubit state for a distribution can be shifted to a new mean using quantum shift operator. The shift operator circuit SH FTa based on QADD (Koch al. 2022) shown in Figure any superposition as input and shifts each (t) to ii + a). We believe the same can be implemented using other quantum adders/circuits.
8 can take
Po
P1
QFT (w)
QADD
QFT
2
Ps
0g
10)
01
{0)
IL(a )
02
(0)
{0)
Figure 8: (o, w) circuit to shift the input distribution (p) to mean a.
C.5
1/
NORM
Basic Circuit for preparing la norm distribution qubit state is shown in Figure
0n
(0)
(0)
IL
Normal Distribution
022
10)
03
(0)
Figure 9: U (Imput) implementation for l2 norm Grover Rudolph 2002).
The same effect can also achieved using the SHIFT((,, w) operator, as shown in Figure
D QUANTUM MACHINE LEARNING CLASSIFIERS
There are multiple formulations that introduce variational quantum classification (VQC) circuits
Cong al. (2019); Farhi & Neven 2018); Havliček al. (2019); (chuld & Killoran (019)) A
17

---

Under review as a conference paper at ICLR 2023
parameterized quantum classification operation () input (e)) is defined
((n) 1 = En (v) (0:)
(37)
Where V(: is multilayer classifier which can be defined as
V(:)) (22
(38)
The quantum classifiers in these works consist of a sequence of learnable, parameter-deppendnt unitary transformations Vi(:%) followed by measurement operation of selected qubits that outputs the class. is trained so that | corresponds to the probability of input (τ) belonging to class i.
Theoretically, the output of the system on input (v) is given by (vb VtMV 115) where M is the measured observable at the end. For instance, measurement of output qubits in a, basis can be used to estimate the predicted class. Experimentally, because of the probabilistic nature of the measurement,
a high number of repetitions/shots need to be carried out in order to estimate this output distribution and predict the correct class.
Using parameterized VQC as an oracle(2) within QuAdRo is non-trivial. Commonly used methods like Mid-Cireuit Measurement and Reset (MCMR) or any other non-umine non-unitary operation before the end of QEC cannot be used. This restricts our choice to variationally trained classifiers that do not perform MCMR.
inery dless
61
(0)
QFT
QFT
0:
10)
00
01
(0)
VQC-Soft
VQC-G20
VQC-G2
VQC-G22
VQC-Soft
0/2
10)
0g
10)
Z
VQC-Soft!
VQC-Soft
1P
TT-QNN
2/0>< 01-1
Figure 10: Hard classifier derived from TTQNN using nested QAE
implemented one such oracle by training TT-QNNZhame et al. (2020) using pennylane Bergholm et al. 2018) library. We trained both one all and multi-clase classifiers for the reduced MNIST dataset. TT-QNN is a soft classifier by design where the output probability corresponding to class in the output qubit state is mapped to extra ancilla qubits in nested QAE operation within the oracle to convert it to a hard classifier oracle required for randomized smoothing, as shown in Figure 10 This construction increases the eircuit depth and requires more oracle calls. On training. the multi-class classifier reached 74% accuracy for the same input features as used in Sec 6 We found that such a QNN,, oracle is feasible, but simulation using existing libraries and available computational resources is prohibitively expensive. Hence, this oracle is not used in the presented results in this paper. We discuss this further the supplementary material.
In another training approach, Salman Salman et al. (2019) consider a generalization of randomized smoothing to soft classifiers F, which output probability distribution over all classes for a given input, as compared to a hard classifier that outputs single class. The adversarial training objective J in this case is given by(Equation 5 from Salman et al. (2019)).
[xx -10g e)yl
(39)
18

---

Under review as a conference paper at ICLR 2023
The training using adversarial examples of the smoothed soft classifer (SmoothAdv) improves the performance, which makes this another possible candidate for QNNcc
Adversarial training of a VQC has been shown previously in Lu et al. (2020), where they extend classical methods of adversarial training like Projected Gradient DGD to QML. To carry out
adversarial training of a smoothed VQC, the training objective defined above can be optimised using the parameter shift rules as explained Schuld et al. (2019).
19


Reviews:
[{"review_id": "_kqkYzUjlUj", "reviewer": "Reviewer_gbVk", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Classification is one of the most applications in machine learning, and recently, an important research direction along this line is its adversarial robustness. Specifically, one of the state-of-the-art methods for defensing against adversarial attacks was achieved by randomized smoothing. This paper studies how to estimate the probability defined over the randomized smoothing neighborhood. Compared to classical algorithms with query complexity O(1/eps^2), the quantum algorithm has query complexity O(1/eps), which achieved a quadratic quantum speedup. Technically, this is achieved by quantum amplitude amplification and estimation.", "summary_of_the_review": "In all, the problem of adversarial robustness by quantum algorithms is interesting in general, and this paper can be regarded as a first attempt for its quantum computing version. However, from my perspective, its contribution to the state-of-the-art understanding of machine learning is unclear and the technical contribution from the perspective of quantum computing is insignificant.", "strength_and_weaknesses": "From my perspective, the topic of studying quantum speedup of machine learning problems is of general interest. On the other hand, adversarial robustness also has wide applications. It’s nice to see the connection between these two topics and quantum can achieve quadratic speedup. In addition, the authors also conduct numerical experiments to demonstrate their result.\n\nNevertheless, I in general don’t find the contributions made by this paper competitive enough, both from the perspective of adversarial robustness and quantum computing. In current research on adversarial robustness, theoretical results have been obtained for many more scenarios, for instance deep learning (Salman et al. in NeurIPS 2019, https://proceedings.neurips.cc/paper/2019/file/3a24b25a7b092a252166a1641ae953e7-Paper.pdf), feature learning (Ilyas et al. in NeurIPS 2019, https://proceedings.neurips.cc/paper/2019/file/e2c420d928d4bf8ce0ff2ec19b371514-Paper.pdf), etc. This paper studies a primitive case with direct l_0, l_1, or l_2 norm adversarial noise, and the problem simply becomes a Monte Carlo problem of estimating a probability \\rho_c = \\sin^2(\\theta/2) in Eq. (14). I think it would be very helpful if the authors could address why the results in this paper could be applicable to classical state-of-the-art results.\n\nFrom the perspective of quantum computing, I have to say that the technical contribution is insignificant: it is a straightforward use of quantum amplitude amplification and estimation in Brassard et al. There have been many developments about quantum speedups of Monte Carlo methods, by Montanaro https://arxiv.org/abs/1504.06987, Hamoudi https://arxiv.org/pdf/2108.12172.pdf, etc. It would be nice to study whether more advanced quantum Monte Carlo methods could further improve adversarial robustness. \n\nIn addition, as adversarial robustness is in general studied in classification, the paper omits a main line of research on quantum classification algorithms. This is probably initiated by Kapoor, Svore, Wiebe, which studied quantum perceptron models for classification in NIPS 2016: https://proceedings.neurips.cc/paper/2016/hash/d47268e9db2e9aa3827bba3afb7ff94a-Abstract.html. Subsequently, Li, Chakrabarti, and Wu studied sublinear quantum algorithms with quadratic quantum speedup for linear and kernel-based classifications in ICML 2019: http://proceedings.mlr.press/v97/li19b.html, and Li, Wang, Chakrabarti, and Wu further studied  classification with quadratic quantum speedup with different norm schemes in AAAI 2021: https://ojs.aaai.org/index.php/AAAI/article/view/17028. Those results aim at general classification algorithms and do not cover adversarial, but at least a comparison to the current result in this paper and a potential discussion about the adversarial robustness in quantum classification algorithms will be very helpful. In terms of this, the last paragraph in the introduction claims that “Our novel contribution is showing how QC subroutines like Quantum Amplitude Estimation (QAE) can be used in ML” is an overclaim, because all these quantum classification algorithm papers have applied QAE.\n\nMinor comments and suggestions:\n\nPage 4: Between Eq. (7) and (8), there should be a . after “Detailed circuits for each p norm are discussed in section 5”. In addition, section 5 should be Section 5. When referencing theorems/lemmas/sections etc., the English word should be capitalized in general.\n\nPage 5: In Eq. (14), should use math operators, sin -> \\sin (otherwise it means the multiplication s*i*n). Similar corrections shall apply to psi, log, and many other math operators.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "TJNpNbi6fJ", "reviewer": "Reviewer_BnBR", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Adversarial attack is a common issue in traditional ML models against malicious adversary. Randomized smoothing is a sota method to tackle the issue. However, computing exact probability over the smoothing neighborhood is computationally expensive. Instead, sampling is required to estimate the probability. This work focuses on its quantum computing counterpart by applying quantum amplitude estimation with a quadratic speedup compared to existing quantum adversarial robustness. It designs qubit state encoding from classical input to the qubit states, and state preparation circuits for smoothing distributions.", "summary_of_the_review": "This work focuses on adversarial robustness of quantum ML. It mainly develops the area from theoretical perspective. While it is more like an incremental work based on some existing algorithms, we should encourage to have more theoretical works like this in ML community. It is good to come up with solid computational bounds first, which will provide capability of related algorithms and guide more applications later on.", "strength_and_weaknesses": "Strength:\n\n1. This work well introduces preliminaries randomized smoothing and related quantum computing concepts.\n\n2. This work derivates operators of quantum adversarial robustness and its theoretical bounds carefully. It is well explained to make reader from adversarial ML with limited knowledge on quantum computing easier to capture the high-level ideas.\n\n3. This work considers different considers lp norm adversaries.\n\nWeakness:\n\n1. This work is built upon existing quantum computing algorithms to address the adversarial robustness issue in QML, which may look less innovative.\n\n2. Dataset used in this work is quite out-dated in the ML community and NN with 2 layers is also shallow in the practice. If the theoretical work would guide more applications, the dataset and NN should be more complex.\n\n3. Since the experiments of quantum part are reduced to simulation of QC circuits, it would be nice to provide bounds for the simulation as well.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "SR64Q60BY3o", "reviewer": "Reviewer_fJTC", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work considers the problem of designing quantum algorithms to perform adversarial training of classifiers using randomized smoothing.  Using classical method the number of required samples (and therefore queries to the classifier) is roughly $O(1/\\epsilon^2)$, where $\\epsilon$ is the target error parameter for the expectation over the smoothing distribution.  In this work, the authors use quantum computing primitives to design a randomized smoothing algorithm that only requires $O(1/\\epsilon)$ samples, improving over the classical. ", "summary_of_the_review": "This work considers the problem of designing quantum algorithms to perform adversarial training of classifiers using randomized smoothing.  In this work, the authors use quantum computing primitives to design a randomized smoothing algorithm that has improved sample complexity over the corresponding classical approach. Applying QC methods in ML is an interesting direction that has a lot of potential but, in my opinion, this paper in its current state is not ready for publication.  The authors should revise the manuscript and more carefully define notation.  They should also try to present more formally their theoretical results so that their contributions are clear.  I am currently inclined toward rejection but since I am not an expert in this area I am open to discussion with the other reviewers and the authors.", "strength_and_weaknesses": "Strengths \n\n1. This work attempts to show how quantum computing primitives can be used to improve standard machine learning tasks such as adversarial training.\n\n\nWeaknesses\n\n1. I do not think that the paper is well-written. The majority of the ICLR community (myself included) are not experts in quantum computing and therefore a more detailed presentation of the results and contributions as well as the techniques would greatly help this paper. Apart from the presentation, there are various typos and language issues and notation is not properly defined (e.g., the notation in most equations of the main body).\n\n2. It seems that the main contributions of this work are theoretical and yet the main results have no formal statements and seem to follow directly from standard QC results (see the results in Section 4.1). \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "BUQO8T5TFK", "reviewer": "Reviewer_HtzH", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a randomized smoothing method for adversarial robust quantum machine learning. The authors uses superposition of \"random noises\" followed by Grover-based counting in designing quantum circuits. The proposed quantum randomized smoothing need $O(1/\\epsilon)$ queries of the classier compared to the complexity  $O(1/\\epsilon^2)$ of its classical counterpart. Experimental results showed the effectiveness. ", "summary_of_the_review": "Due to the comments in \"Clarity, Quality, Novelty And Reproducibility\", I suggest \"marginally above the acceptance threshold\".\n\n-------------After rebuttal----------------\nI am so sorry for my carelessness of incorrectly choosing \"5 borderline reject\" as the suggested score. \nMany thanks to the authors for their feedback. The revision clearly addressed some of my concerns, and  I would like to choose \"6 borderline accept\".", "strength_and_weaknesses": "Strength:\n\nS1) By using randomized smoothing, a new method is proposed for adversarial robust quantum machine learning.\n\nS2) The proposed quantum randomized smoothing need $O(1/\\epsilon)$ queries of the classier compared to the complexity  $O(1/\\epsilon^2)$ of its classical counterpart.\n\nS3)  Experimental results showed the effectiveness as well as efficiency of proposed method. \n\nWeakness:\n\nW1) The proposed method cannot be applied to real applications due to the bottlenecks in the development physical quantum computers. As discussed in the conclusion, the algorithm presented here is also dependent on a functional QC hardware for the speedup, and application to meaningful image inputs will need >1000 qubits. \n\nW2) This paper has some parts not well written. \n\nThere are some examples:\n\n(W1.2.1) In Figure 1, there are $m$ Grover operators but the authors use 4 ancilla quantum bits $a_0,\\cdots,a_3$. It is suggested to make them consistent. Also, the operator $G_{c}{\\cdots}$ should be in its correct form. \n\n(W1.2.2) In Eq. (7), the (Kronecker) basis $|i\\rangle$ is suggested to be explained for ML audiences who are not familiar with quantum symbols. \n\n(W1.2.3) In Eq. (10), it is suggested to give the explicit form of $|-\\rangle=\\frac{1}{\\sqrt{2}}(|0\\rangle-|1\\rangle)$.\n\n(W1.2.4) In Eq. (13), \"psi\"-->$\\psi$.\n\n(W1.2.5) Why choose parameter $\\frac{7}{N_{QEC}}$ in Algorithm 1?\n\n(W1.2.6) In P12, \"space of size $2^20$\"--> \"space of size $2^{20}$\", \"exact value of $rho_c$\"-->\"exact value of $\\rho_c$\".", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject