Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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. 
strength_and_weaknesses: Strengths 

1. This work attempts to show how quantum computing primitives can be used to improve standard machine learning tasks such as adversarial training.


Weaknesses

1. 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).

2. 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). 


clarity,_quality,_novelty_and_reproducibility: I think the paper would benefit a lot from careful proofreading to fix typos, language, and notation issues.  I am not an expert in Quantum Computing and Quantum ML however, I think that the results presented in this work are not particularly novel and original.
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 
strength_and_weaknesses: Strength:

S1) By using randomized smoothing, a new method is proposed for adversarial robust quantum machine learning.

S2) 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.

S3)  Experimental results showed the effectiveness as well as efficiency of proposed method. 

Weakness:

W1) 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. 

W2) This paper has some parts not well written. 

There are some examples:

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

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

(W1.2.3) In Eq. (10), it is suggested to give the explicit form of $|-\rangle=\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$.

(W1.2.4) In Eq. (13), "psi"-->$\psi$.

(W1.2.5) Why choose parameter $\frac{7}{N_{QEC}}$ in Algorithm 1?

(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$".
clarity,_quality,_novelty_and_reproducibility: Clarity score 4/10: This paper is in general not clearly written. See the Weakness for example. 
I also have the following suggestions:

C1.1) It is also suggested to give a list of notations before introducing how to design the quantum algorithm. 

C1.2) Another suggestion is to tell the reader the dimensionality of a vector or matrix in Eqs. (2)-(13). 

Quality score 5/10: The derivation of query complexity seems correct. It is suggested to add references to support Eq. (16). 

Novelty score 5/10: The proposed quantum randomized smoothing is moderately new, because techniques like randomized smoothing in classical ML, Grover-like operators, quantum preparation of distributions, etc. have already been well developed.

Reproductivity 8/10: I run the shared code and it works. 
summary_of_the_review: Due to the comments in "Clarity, Quality, Novelty And Reproducibility", I suggest "marginally above the acceptance threshold".

-------------After rebuttal----------------
I am so sorry for my carelessness of incorrectly choosing "5 borderline reject" as the suggested score. 
Many thanks to the authors for their feedback. The revision clearly addressed some of my concerns, and  I would like to choose "6 borderline accept".
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
strength_and_weaknesses: Strength:

1. This work well introduces preliminaries randomized smoothing and related quantum computing concepts.

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

3. This work considers different considers lp norm adversaries.

Weakness:

1. This work is built upon existing quantum computing algorithms to address the adversarial robustness issue in QML, which may look less innovative.

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

3. 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.
clarity,_quality,_novelty_and_reproducibility: Clarity: This work goes through the proof smoothly from preliminaries to the point it focuses.

Quality: Since this work mainly works on derivation of bounds, it looks good to me.

Novelty: This work is an incremental work on quantum amplitude estimation and quantum adversarial robustness, so I would say it is less novel while it provides experimental comparison.
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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
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.

Nevertheless, 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.

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

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

Minor comments and suggestions:

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

Page 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.
clarity,_quality,_novelty_and_reproducibility: As I mentioned above, the clarity, quality, and novelty has space to improve both in terms of comparison to classical adversarial robustness literature, quantum Monte Carlo method, and quantum classification algorithm literature. In terms of reproducibility, the paper did a decent job by conducting detailed numerical experiments. In addition, the model architecture and simulation setup are explained in Appendix A. 
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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The reviewers generally felt the paper was a bit below the bar for ICLR in terms of novelty, both from a quantum and an adversarial robustness perspective. Some of the theory results were thought to be incremental, and there were also concerns about experiments and practicality, as well as presentation. The author response helped a little bit, but the concerns were not completely removed. 
justification_for_why_not_higher_score: see summary above
Decision: Reject