Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This article studies the learnability of functions using quantum kernels. More precisely, it investigates the potential advantages in learning that quantum kernels may offer compared to classical ones. The focus was put on ridge kernel regression as a running example of a learning task. In this case, the analysis boils down to two ingredients: 1) the spectral properties of the corresponding integration operator 2) the alignment of the function to learn with the first eigenfunctions of the integration operator. The contribution of this work is to highlight the fact that, under some assumptions, the class of functions for which quantum kernels would have an advantage over classical ones is very restricted: the functions that belong to RKHSs associated with the so-called biased kernels.
main_review: 
Overall the article is well-written and tackles a crucial question in quantum learning theory. However, I believe that the conclusion is probably hasty since the analysis given in this work assumes that the kernel is separable:
$k(x,y) = \prod_{i \in [d]} k_i(x_i,y_i)$. For this class of kernels, the eigenvalues are the product of the eigenvalues of the respective uni-dimensional kernels: the eigenvalues of the corresponding integration operator are arranged by “plateaus”. It seems that this arrangement of the eigenvalues is crucial in the argument of this work (Section C.2. from line 629 to line 635 in the appendix). It would be interesting to study the case of a non-separable quantum kernel (Matérn kernels constitute a family of classic kernels that are non-separable without being pathological).



Minor observations: 
- In line 266, the letter k is already used for the kernel k. 
- In lines 717 and 718, I am not sure of the order in the inequalities since we assume that $n \leq d^{k}$.

limitations_and_societal_impact: No.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper gives a general investigation of quantum kernel learning, where quantum computers are used to compute the kernel functions used in standard kernel learning problems. Several results are given characterizing the general behavior of quantum kernels, which together give useful guidance towards the design of effective kernels for specific problems.
main_review: Given the recent interest in quantum machine learning, with quantum kernel learning being an important special case of this, the (mostly negative) results given here are useful for researchers in the field to identify promising areas for further investigation. The results themselves are a bit scattered, but they are applicable to general quantum kernel learning problems. These results mostly come from a spectral analysis of the quantum kernel, which is usefully related to properties of the underlying embedding of data into quantum density operators, and are clearly and thoroughly explained in the paper. All theoretical results are proved in full detail in the supplemental material.

A small collection of experiments are given which emphasize the utility of quantum kernels which are strongly biased towards specific problems, a fact which is justified by the theoretical results. The authors finally give a careful discussion about the impact of their results for further research in this area, which should be of interest to quantum ML researchers.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper presents the inductive bias of quantum kernels by analyzing their spectral properties. Specifically, their main theoretical results are that quantum kernels with too expressive RKHS will fail to generalize, and projected quantum kernels are a promising way to construct inductive biases that are hard to create classically.
main_review: Strengths:
This paper is well written. It provides a clear perspective to present some problems faced by quantum kernel methods through the lens of the inductive bias by analyzing the spectral of the corresponding integral operator. 

Weakness:
My concerns lie in the following aspects about the two core theorems (Theorem 1 and 2):
-I am very confused about condition   $n \leq d^k$  in Theorem 1. First, I cannot find any clear definition of the notation "$k$". Is this a constant or a "kernel"? Second, in your proof, the usage of this condition seems to be unreasonable and even wrong. In particular, to ensure that the inequality in the bracket in the last row of the proof, the inequality "$\delta^{d/2} < \epsilon n^{-4}/2$" seems sufficient. Besides, the condition used in your proof is actually "$n>d^k$" instead of "`$n<d^k$" employed in Theorem 1.

-In the proof of Theorem 3 (the first line of page 23), it is unclear why $\lambda$ can be omitted in the derivation of inequality $\|\alpha\|^2 \le 2\|y\|^2$, as $K^{-1} \le 2I_{n}$ cannot deduce $(K+\lambda I_n)^{-1} \le K^{-1}$ when $\lambda$ can take any value. In the same place, the claim `for any $\epsilon > 0 $ with probability $1-\epsilon$ we have $\|y\|^2 \le \frac{n}{\epsilon}\|f\|_2^2$’ is not obvious.
 
-The conclusions and implications of Theorem 2 are arguable. Note that when $d$ grows, although the eigenfunctions are exponentially hard to compute classically, the eigenvalues and the projected kernel also exponentially tend to be a constant. Such a result can offset the quantum advantage brought by the eigenfunctions. 

-In addition, there should be some specific explanations or appropriate references in the analysis of Theorem 2. For example, there should be an appropriate reference for the statement “However, …, but a proof would require the evaluation of 8-th order polynomials over the unitary group”.    

Minor issues:

-the notation of kernel matrix and integral operator is the same.

-there is no necessary label of the y-axis in Figure 2 and Figure 3.

-the definition of $\| \cdot \|_{HS}$ is not clearly given.

-the subscript of $V_{\alpha, \alpha, j_1}$ in Eqn. (56) is confusing.

-the subscript of $T_{\alpha \beta, \gamma \delta}$ in Eqn. (62) is confusing.

-It should be $q_m^V(x, x’)=Tr[\widetilde{\rho}_m^V(x)  \widetilde{\rho}_m^V(x’)]$ in the introduction of `Biased kernels' in Page 8.

-It should be $\alpha=(K(X,X)+\lambda id_{n \times n})^{-1} y $ in the first line of page 23.

limitations_and_societal_impact: The results discussed in the submission can not be directly employed to solve practical learning tasks with provable quantum advantages.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper investigates quantum kernels and learning with them, and whether it can be advantageous over using classical computations. A lemma is proposed which bounds the eigenvalues of the integral operator of a quantum kernel, and a theorem which shows how the empirical risk of the KRR solution with certain kinds of quantum kernels is bounded from below. Further, a biased quantum kernel is introduced for which the integral operators are also investigated. From these results (and experimentally verifying the last of them) the authors conclude that the advantage of learning with quantum kernels is restricted to very particular functions.
main_review: The paper introduces relevant analysis for the quantum machine learning community, showcasing that the very popular idea of quantum advantage in reality is not easy to achieve. This is very significant, and in this sense I would like to see this paper accepted.

While for the most part the authors have made admirable effort to as simply as possible communicate the complicated contributions (e.g. introduced theorems and concepts are thoroughly discussed), this is not fully successful. Some details in the paper remain unclear to me (at the level of mainly focusing on the main paper but also taking quick looks to appendix trying to see if it would clear things up), but I would assume mostly due to undefined notation. However not being able to understand the theorem statements etc fully hinders the full understanding the paper, and as it is difficult to fully understand I'm slightly reserved in my acceptance recommendation.


While I'm somewhat familiar with the concepts of quantum computation in machine learning, I am not very familiar with most of the literature there. Thus I cannot too accurately judge the novelty of the work and its relation to other quantum machine learning papers.


Comments and questions:

- You at the beginning of your paper introduce the two measures to assess the quality of a kernel to learn a function. I was expecting to see them in your theoretical analysis, but it seems that instead they are only used in the experimental validation? 
- A comment about the measures to judge the quality of a kernel:  while having a high value on kernel target alignment to ideal kernel certainly indicates the good quality to learn f, it is very much possible that other kinds of kernels could be also reasonably good at the task even if they don't have a high alignment. On some easy learning problem RBF kernel can produce great results even if doesn't look like the ideal kernel. Could you comment if this has any impact on your analysis and conclusions? 

- Line 228, what is \varphi? It has not been formally defined previously as far as I can see.

- Line between 251&252 Tr_1 has not yet been defined - is this partial or block trace? Does the last equality follow from some property detailed e.g. in [1]? 

- Biased kernels: V just starts to appear (line 280) in superscript of \rho without any further introduction; only later it is said that it is a Haar-distributed random unitary matrix but it doesn't really explain why they are used with \rho. Nor does section 3 introduce such notation. Paragraph starting from line 227 introduces unitary tranformation V for the embeddings, but the notation in superscript is not used there either. Note: also Figure 1 uses this notation. 

- Theorem 1: 
  * line 266: what is k here? k has been the kernel function throughout the paper, now it's in the exponent. 
  * for all d >= d0 no function can be learned with KRR and d-qubit kernel. What if d is smaller than d0, what happens then? 
    -> it seems that you do not illustrate this theorem experimentally. While I realise that theorem 2 is more relevant to be illustrated mainly due to it not having a fixed V, it could be very illuminating to the reader to illustrate also this theorem. 
  * what is the formula for d_0? I did not see this laid out in appendix (and the proof is overall difficult to grasp quickly as the parts introduced in theorem statement were not explicitly used there; to me it seems that the reader has to fill many gaps.)
  * Reading the theorem I can't help but think of deep neural networks, and other models with high number of parameters. Can we interpret that if d>=d0 then there are too many parameters for the restricted number of samples n for the function to be learned effectively? Or is my comparison completely faulty? 

- Figure 2: gamma0 is stated on line 311 to be 0.5+O(2^-d); why is this constant in the figure when the x-axis displays d? Is it derived from your choice of keeping variances fixed?

- Abstract: "we show that finding suitable quantum kernels is not easy because the kernel evaluation might require exponentially many measurements" where is this shown? Something like this is discussed in paragraph "barren plateaus", but there it seems like kernel evaluation being costly is general knowledge. Or have I missed the assumption of requiring the measurements in some of the theorems?

- Might I suggest that for a reader not too familiar with quantum kernels but very familiar with kernel methods otherwise a table in which all the relevant things about quantum kernels (i.e. RKHS, kernel function, feature mapping...) are thoroughly detailed. (I realise space constraints probably won't allow this to be added to the main part of the paper.)




Minor comments (clear typos etc):
- Is "joint probability law" and "marignal law" (i.e. with the term law) standard language in this setting? Line 81 & 82. To me at least it would be more natural to use "distribution" rather than "law". 
- First in line 95 K is used for kernel matrix; then in 101 and after that it is integral operator.
- typo on line 235: bet->be
- typo line 247 "consists of all functionS"
- "id" as identity matrix should be introduced as notation. Why not use I?
- Figures 2 & 3: left plot missing label for y-axis, Figure 2 left: it is not clear if the legend lists "gamma" or "y" (even if it can be deduced). Figure 2 right: are qw train and test on top of each other?
- Line 341, here "with high probability" is probably not an exact mathematical statement (but these words can be used as such in some settings).
- Line 346 "have to little bias" -> too little?
- Line 377 "Here" no need for capital H


[1] Filipiak et al, "THE PROPERTIES OF PARTIAL TRACE AND BLOCK TRACE OPERATORS OF PARTITIONED MATRICES", Electronic Journal of Linear Algebra, Volume 33, pp. 3-15
limitations_and_societal_impact: Limitations of this work: according to authors end of section 4 and section 6. However to me especially section 6 sounds more like limitations of quantum machine learning based on the results obtained. In any case I find it very good that authors mention and highlight that in practice the kernel would need to be determined via measurements, which is not something they consider in their analysis or experiments.
review_title: null

Meta-review: There is a consensus among the reviewers that this is a very strong theoretical analysis for the learnability of functions using quantum kernels. The results discovered poor learnability of quantum kernels which is similar to the “barren plateau” phenomenon in quantum neural networks and provided useful guidance towards the design of effective kernels for specific problems. In summary, the paper is helpful for understanding the power of quantum kernels, and I would like to recommend to accept this submission.
Decision: Accept (Poster)