Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 1: strong reject
review_content: summary_of_the_paper: This paper tries to identify a condition that makes quantum-based kernel methods superior to standard ones.
main_review: Although the question raised by this paper is interesting, I am not convinced enough by the proposed answer to warrant acceptance. In particular,

**There are many writing flaws**:
- last sentence of 2nd paragraph in unclear
- 1st sentence of 3rd paragraph in unclear: *kernel methods* (and not *the kernel method*) are a family of algorithms
- kernel methods bec*o*me (last word of p.1)
- We *conjecture* (1st contribution bullet point)
- please cite the SVM paper when introducing them (1st par. of sec. 2)
- kernel *trick* (2nd par. sec. 2)
- SVM paragraph: remove *kind of*
- Eq. (4), a $\top$ is missing between the $\phi$ (also support vectors are never defined)
- top of page 4: there is a very clear theoretical answer about what kernel is a valid or not. The good performances of the sigmoid kernel (reference needed here) does not change anything
- I cannot understand what authors mean by *that expands the family of kernel functions*
- Fig.2 seems to imply that tree and graph kernels do not satisfy Mercer's conditions: why such a separation? Also, the ... boxes are not relevant, and "Don't satisfy..." would be a better legend
- the Mersenne Twister distribution could be introduced and commented before the theorem statement
- Eq. (5): I assume $N_l$, $N_m$ instead of $N_1$, $N_2$
- the "number of observations belonging to class X" would be more clear than the *size*
- the $\rightarrow$ vector notation is introduced once and is not consistent with the rest of the paper
- expliciting the formulas in eq. (7) is not necessary

**The exposition of classical and quantum kernels is particularly messy**, which is very harmful as it is a key point in the paper:
- weird $x$ notation
- $f_c$ is mapping $x$ to $\phi(x)$ ?! 
- the dot product denoted with both $^T$ and $\cdot$
- note also that to compute a distance, one would use $|| \phi(x) - \phi(y)||$ rather that $<\phi(x), \phi(y)>$ as claimed by the authors
- in the quantum paragraph, I assume $F_q$ means $f_q$
- it seems to me that the definition of $f_q$ from $\mathcal{O}$ to $\mathcal{F}_q$ is repeated. Furthermore, I cannot see any difference from the standard kernel definition
- $f_q$ is mapping $x_i$ to a quantity that depends on $x_j$ ?!
- the $|\cdot >$ notation is very confusing for people used to kernel dot products. Even if it is the standard notation in the quantum literature, why don't we have two $|$ in the definition of $f_q$?
- the circuit $U$ is never defined

In the same vein, **the maths seem not rigorous to me**:
- how can the proof of Theorem 3.1 begin by "we assume" ?! If you have an extra assumption, just put it in the theorem statement
- the same goes for the proof of Theorem 3.2
- the exact statement of Theorem 3.2 should be "there exists $\delta_0$ such that..."
- the CLT does not imply the existence of a $R$ such that the distribution is the standard Gaussian (what if the empirical mean is $1/n$ for instance?)
- what are the "measurements" referring to?
- where do $\sigma$ and $\mu$ play a role?
- please prove "it is easy for a deterministic kernel [...] with small error"

And **the contribution is at best incomplete**, if not erroneous (see comments about the proofs above):
- Theorem 3.1 only states that quantum kernels are superior than standard kernels on this example because the latter cannot learn anything. Can we prove that quantum **can** learn something in this case, i.e., are strictly better. Otherwise the statement is pretty vacuous.
- the definition of $\delta$ is based on empirical quantities, is it suitable? Shouldn't a quantity in expectation make more sense?
- what happens for kernels defined on non-vectorial inputs? Do they have a quantum analog? It should be discussed
- can we use another distance than the Euclidean one?
- if we add an offset to the distance, it seems that the 0.6 threshold exhibited changes, making me dubious about such an absolute value
- Theorem 3.2 actually only shows that quantum kernels are worse than standard ones in a precise regime, not that they are better in the opposite scenario

More generally, the general idea I retain from this paper is that computing quantum kernels requires some randomness, and that if this randomness is greater than the "task randomness/difficulty", it is vain to use quantum kernels. If this message is the right one, I would suggest the authors to be more clear on this, and to drop the $\delta$ criterion, which seems to be a proxy for the task difficulty.
summary_of_the_review: Although the question raised by this paper is interesting, the proposed answer is not clearly exposed, not rigorous enough on the math side, and not enough significant to warrant acceptance.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This article studies the superiority of quantum kernel methods over classical kernel methods. The authors relate the quantum advantages for classification tasks to the separation between the classes.  Several numerical simulations were conducted to support the theoretical findings.

main_review: The introduction of the article is well-written and reflects a good knowledge of the literature. However, the authors restrict the comparison between quantum kernel methods and classical kernel methods to the case of binary classification. Moreover, the theoretical results are presented informally. 
summary_of_the_review: Unfortunately, I have to recommend that the paper would be rejected for the following reasons:

1.  the analysis concerns binary classification, which is one among many learning tasks to study. It is not clear how to deal with other learning tasks. 
2. The presentation of the theoretical results (Theorem 3.1 and Theorem 3.2) is poor and informal, and the proofs lack rigor. For example, the threshold 0.6 in Theorem 3.2 Is mysterious and does not seem to stem from any grounded argument.
review_title: null

final_score: rating: 1: strong reject
review_content: summary_of_the_paper: This paper studies quantum kernel methods for classification problems. It compares the differences between quantum kernel functions and classical kernel functions. A degree of integration and two theorems are proposed. Some empirical experiments are done on the datasets from Qiskit and Kaggle.
main_review: 1. The writing quality of the paper is not ideal. Sections 2 and 3 are long but not informative. The figures in experiments are hard to understand. The paper has a lot of grammar errors.

2. The paper seems to focus on the classification problems. Quantum kernels can be applied to a much wider range of problems. The terminology ``quantum kernel methods" in the title may need to be changed to quantum kernel based classification methods.

3. The proof of theorem 3.1 is just a summary of statements in the literature. The proof of theorem 3.2 is just an application of CLT (and with some errors). For example, the first sentence in the proof of Theorem 3.2. ``Suppose our measurement independent identical distribution ... where M is the random variable, R is the
number of measurement shots." is not correct in both English and mathematics. Also, I am not sure if the proof really did the job to prove the statements in Theorem 3.2.

4. The experiments are not convincing. Many implementation details are missing. The results, figures, and explanations are hard to understand. No replication codes are provided. My guess is the experiments are done by simulations run on the classical computer rather than real quantum computers? 
summary_of_the_review: Correctness: 
This paper only considered limited scenarios in classification problems. Therefore, the title and the statements in the paper may be exaggerated by saying quantum kernel methods instead of quantum kernel based classification methods. The proofs of the major theorems are not convincing to me. The experiments are not strong enough to support the claims made in the paper.

Technical Novelty And Significance:
The theoretical contributions of the paper are limited if there are some at all. 

Empirical Novelty And Significance:
I am not sure if the authors have proposed any new quantum methods for the experiments. The results are hard to understand.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper investigates the circumstances under which quantum kernel methods will be superior to classical kernel methods.  The criteria is based on a threshold of the ratio of the inter- and intra-class distances of the (binary) training data.  Validation of the proposed criteria is carried out on a range of toy and real datasets.
main_review: The background section was clear and thorough.

I have some difficulties with section 3:

- proof of theorem 3.1.  The proof hinges on an assumption - "the Z-ZZ feature map can effectively simulate the efficacy of the feature map proposed by Liu et al. (2021)" - but I don't see any proof of this conjecture, at least in the mathematical sense.  If this is axiomatic to the theorem then it should be presented as such in the theorem: otherwise the proof doesn't work afaict.  Have I missed something here?

- theorem 3.2: why is $\delta_0$ usually taken as 0.6?  Is this based on the experimental results alone, or is there some intuition as to why this particular threshold is important?

However the experimental section is very thorough and quite convincing, so I am willing to overlook my misgivings regarding the theorems.

Minor point:

- in the paragraph before equation (1), is the definition of the feature map $f_q : x_i \to < \phi (x_i) | \phi  (x_j) >$ correct?  And if so, how does $x_j$ fit here?


-- EDIT AFTER FURTHER CONSIDERATION --

After further consideration and reading other comments I am persuaded that the informality of proofs is a more serious problem than I initially thought and adjusted my recommendation accordingly.
summary_of_the_review: - Overall a well-written paper.
- I have some problems with the proof of theorem 3.1.
- I am also curious how the threshold value 0.6 is arrived at, and whether this is purely experimental or if there is some alternative intuition.
- The experimental section is very thorough and quite convincing.


-- EDIT AFTER FURTHER CONSIDERATION --

After further consideration and reading other comments I am persuaded that the informality of proofs is a more serious problem than I initially thought and adjusted my recommendation accordingly.
review_title: null

Meta-review: There was consensus that though  the paper introduces an interesting question, but not enough exploration has been made. The reviews point out several mathematical in-accuracies, and points out  several issues including that the delta criterion needs to be examined.
Decision: Reject