Power Characterization of Noisy Quantum Kernels

Thank you very much for your helpful comments and suggestions.

Firstly, following your constructive advice, we have thoroughly revised Sec. 1.2 Related Work to present our contributions and the differences from prior works more clearly.

Secondly, although the result itself may not be very surprising, we do explicitly depict the speed of the prediction concentration of noisy quantum kernels in terms of the strength of depolarization noise, the size of training samples, the number of qubits, the number of layers affected by quantum noise, and the number of measurement shots. This helps us quantitatively understand the limits of noisy quantum kernel methods. As an illustration, for a training sample set, whose scale is exponential in the number of qubits $N$, like $q^N$ for some $q>1$, noisy quantum kernel methods fail once the number of noisy layers exceeds $N\log\_{(1−\tilde{p} )^{−2}} q$.

Thirdly, when presenting negative results concerning noisy quantum kernels, we feel it is better to assume a relatively weaker noise model. Once the kernel methods fail under weaker noise, they fail under stronger ones in general. In the reply to your last question, we detailedly explain that our global noise model is actually weaker than the noise models considered in previous works. In addition, the noise rate $\tilde{p}>0$ in our work can be arbitrarily small. Therefore, it can depict the case where the noise influence is very weak, namely, after the noise the quantum state is left untouched with a very high probability $1-\tilde{p}$. Thus, in this sense, our global depolarizing model is an appropriate starting point to study the limitations of noisy quantum kernel methods. We have made this clearer in the revised manuscript after Eq. (12).

We agree with you that much work needs to be done to further investigate the limitations of quantum kernel methods. For example, consider more realistic quantum noise including the effect of mitigation, and conduct experiments on real quantum devices. We leave them for future research. Thank you for pointing out these potential research directions.

• Do you have experiments showing the test errors and generalization errors for different numbers of training data (fixing other parameters)?

Yes, we also consider the case where the number of training data is 100, which is polynomial in the number of qubits $N$. In this case the numerical results also match well with our theoretical results.

• Line -5 before Sec. 1.3: “...required for probably successful training”, what does “probably successful” mean?

We mean that for those cases, to have a good training, a necessary condition is that exponentially many resources are required. However, this is not a sufficient condition, namely, exponential number of resources do not necessarily guarantee a good training under those scenarios. In the revised paper, we have removed “probably successful” to avoid possible confusion.

• Page 2, line -7: what is $q$ in $q^N$? Is it a circuit parameter or any constant?

It is one of the typical sizes of the training sample we consider. To be specific, $q^N$ with $q>1$ denotes that the size of the training sample is exponentially large in the number of qubits $N$. We have made this clearer in the revised version.

• Page 3: “indicate that good generalization alone does not necessarily guarantee good prediction for new data”. Does “good generalization” mean the generalization of the noiseless kernel?

Here, “good generalization” refers to the generalization for general quantum machine learning methods. Recall that generalization error is the difference between the prediction error and the training error. When both the training and prediction are bad, its generalization error may still be small. Thus, for any quantum machine learning methods, only having good generalization cannot necessarily guarantee good prediction. To have good prediction, both the training and generalization errors should be small. We have revised the paper to make it clearer.

• Eq. (3): it is unclear whether the square is inside or outside of the expectation.

We have revised the expression to make it clearer. Thank you for pointing out the potential confusion.

• Sec. 2.2: the introduction to the quantum kernel method is not self-contained. A complete workflow should be given for the ease of readers who are unfamiliar with this field. And it should mention which part is quantum and which part is classical.

We have revised Sec. 2.2 to make it more self-contained. Specifically, we have clearly pointed out which part is quantum and which part is classical. Thank you for your suggestion.

• Page 7, line 5: “The depolarization noise model in Theorem 3.1 is weaker than the noise model…” Weaker in what sense? Could you state it more explicitly?

Thank you for your constructive comment. We have added more explanations on “weaker” in what sense in the revised manuscript. In one word, our noise model is weaker in the sense that with the same depolarizing rate $\tilde{p}$, under our noise model the quantum state is left untouched with an exponentially larger probability $(1-\tilde{p})$ as compared to that $(1-\tilde{p})^N$ under the noise model considered in previous works. Here, $N$ denotes the number of qubits.

Specifically, in our work, the noise model, $\mathcal{N}\_{\tilde{p}}=(1-\tilde{p})\rho+\tilde{p}\frac{1}{D}I$ with rate $\tilde{p}$, is referred to as “global” as it applies onto all qubits after each layer of ideal unitary gates. While in Stilck Franca & Garcia-Patron (2021) and De Palma et al. (2023), the considered noise model is the local depolarizing noise. However, it applies to each qubit. Thus, their noise channel applied after each layer of unitary gates is $\mathcal{D}\_{\tilde{p}}^{\otimes N}$, with $\mathcal{D}\_{\tilde{p}}=(1-\tilde{p})\rho+\frac{1}{2}I$ and $N$ being the number of qubits. We have rewritten it using our notation for convenience of comparison. With the same noise rate $\tilde{p}$, we can compare our global depolarizing noise $\mathcal{N}\_{\tilde{p}}$ with its counterpart $\mathcal{D}\_{\tilde{p}}^{\otimes N}$. It can be seen that under our global noise, the quantum state is left untouched with probability $1-\tilde{p}$, while under the so-called local noise, the probability of the state remaining unchanged is only $(1-\tilde{p})^N$, which is exponentially small in $N$. Thus, in this sense our global depolarizing model is weaker than the so-called local depolarizing model. As for the Pauli noise model considered in Thanasilp et al. (2022), following a similar analysis, we can see that the Pauli noise is also stronger than ours. We have made this clearer in the revised manuscript after Eq. (12).

Dear Reviewer XjgB,

Many thanks for your dedicated time to review our work. We have taken your insightful comments seriously and have made necessary modifications based on your constructive suggestions. With the imminent closure of the discussion period, time is of the essence.

Given that our work received your’s less favorable scores, we worked diligently to clarify the difference from prior works and answer your specific questions during the rebuttal period, demonstrating our unwavering commitment to addressing every facet of your feedback.

We kindly request your esteemed attention to our rebuttal response. Your responsible and positive endorsement holds paramount significance during this critical phase.

Wishing you all the best and awaiting your valued evaluation.

Best regards,

Authors

Thank you so much for your feedback. We have worked diligently for a continuous span of ten days during the rebuttal period to explore this issue on local depolarizing noise. Finally, we are excited to share with you that we find our main result can be pushed to local depolarizing noise so that the prediction difference $\vert \tilde{h}-\bar{h} \vert$ converges to zero with the circuit depth increasing. Specifically, we outline the additional proof for local depolarizing noises as follows.

Firstly, after 1-layer of $N$-fold local depolarizing channel, the relative entropy satisfies $S(\mathcal{D}\_{\tilde{p}}^{\otimes N}(\rho\_{0})\Vert \frac{1}{D}I)\leq (1-\tilde{p})^2 S(\rho\_{0}\Vert \frac{1}{D}I)$ [1].

Secondly, similar to Eq. (14) in our paper, denote by $\rho\_{\mathcal{D}}(x; x\_{i})$ the final state of the $2L$-layer local depolarizing noisy quantum circuit. Then, the corresponding kernel value is \mathcal{K}(x,x\_{i})={\rm Tr} \left P_{0} \ \rho_{\mathcal{D}}(x; x_{i})\right $$. For local-depolarizing noise, we have $\vert \mathcal{K}(x,x\_{i}) - \overline{\mathcal{K}}(x,x\_{i}) \vert \leq \Vert \rho\_{\mathcal{D}}(x; x\_{i})-\frac{1}{D}I \Vert\_{1} \leq \sqrt{2 \ln 2\ S(\rho\_{\mathcal{D}}(x; x\_{i})\Vert\frac{1}{D}I)} \leq (1-\tilde{p})^{2L}\sqrt{2 \ln 2\ S(\rho\_{0}\Vert\frac{1}{D}I)}$, where the first two inequality come from the matrix H$\ddot{\rm o}$lder Inequality and quantum Pinsker Inequality [2], respectively. Thus, $\vert h(x)-\bar{h}(x) \vert = \mathcal{O}(n\vert \mathcal{K}(x,x\_{i}) - \overline{\mathcal{K}}(x,x\_{i}) \vert)=\mathcal{O}(n(1-\tilde{p})^{2L})$, where $n$ is the sample size.

Thirdly, for our global depolarizing noise, since $S(\mathcal{N}\_{\tilde{p}} (\rho\_{0})\Vert \frac{1}{D}I)\leq (1-\tilde{p}) S(\rho\_{0}\Vert \frac{1}{D}I)$, we have $\vert h(x)-\bar{h}(x) \vert = \mathcal{O}(n(1-\tilde{p})^{L})$ by following a similar analysis.

Combing the above statements, we can find that after local depolarizing noise, the kernel tends to get worse even for shallow circuits. The fundamental reason is that after an 1-layer of global depolarizing channel, the relative entropy decays as $S(\mathcal{N}\_{\tilde{p}} (\rho\_{0})\Vert \frac{1}{D}I)\leq (1-\tilde{p}) S(\rho\_{0}\Vert \frac{1}{D}I)$, while for the local depolarizing noise $S(\mathcal{D}\_{\tilde{p}}^{\otimes N}(\rho\_{0})\Vert \frac{1}{D}I)\leq (1-\tilde{p})^2 S(\rho\_{0}\Vert \frac{1}{D}I)$, which decays in a faster way.

In the current quantum devices, the noise is vital of consideration before realizing quantum error correction and fault tolerant quantum computing. To this end, we and the authors in many Related Works are focusing on the effect of quantum noise and provide a crucial warning to utilize noisy quantum kernels under different noise models.

In a word, for the ultimate goal of machine learning, i.e., prediction, the local depolarizing noise model is usually “stronger” than our global one. Our work is especially useful for developing quantum kernel methods in noisy intermediate-scale quantum (NISQ) era where we have no sufficient capability for quantum error correction. We agree with you that further work is worthing being presented to discuss the different performance and effects of quantum error correction and quantum error mitigation for various noise models.

[1] Stilck França, D., García-Patrón, R. Limitations of optimization algorithms on noisy quantum devices. Nat. Phys. 17, 1221–1227 (2021). https://doi.org/10.1038/s41567-021-01356-3

[2] Watrous, J. The Theory of Quantum Information. Cambridge: Cambridge University Press. https://doi.org/10.1017/9781316848142, Theorem 5.38 for quantum Pinsker Inequality.

We do expect that our further clarification addresses your concerns. Nevertheless, the final decision for endorsement or rejection ultimately lies with you, and we deeply respect that.

Many thanks for your advice, suggestions and feedback, and wish you all the best.

Best regards,

Authors

Thank you very much for your constructive comments and suggestions.

Following your advice, we have added the needed definition and revised the typos. We have revised these paragraphs after Theorem 3.1 to better present the implications about the main result and to make it clearer how the main result ties to Figure 1. For more details, please see the revised paper (highlighted by a blue font for your convenience).

We agree with you that the overall picture may not be too surprising. However, we explicitly depict the speed of the prediction concentration of noisy quantum kernels in terms of the strength of depolarization noise, the size of training samples, the number of qubits, the number of layers affected by quantum noise, and the number of measurement shots. This helps us quantitatively understand the limits of noisy quantum kernel methods. As an illustration, for a training sample set, whose scale is exponential in the number of qubits $N$, like $q^N$ for some $q>1$, noisy quantum kernel methods fail once the number of noisy layers exceeds $N\log\_{(1−\tilde{p} )^{−2}} q$.

Thank you so much for your insightful advice for investigating local depolarizing noise. We completely agree with you that "Pushing the result in this direction would significantly strengthen the result". We have worked diligently for a continuous span of ten days during the rebuttal period to explore this problem. Finally, we are excited to share with you that we find our result can be pushed to local depolarizing noise so that the prediction difference $\vert \tilde{h}-\bar{h} \vert$ converges to zero with the circuit depth increasing. Specifically, we outline the additional proof for local depolarizing noises as follows.

Firstly, after 1-layer of $N$-fold local depolarizing channel, the relative entropy satisfies $S(\mathcal{D}\_{\tilde{p}}^{\otimes N}(\rho\_{0})\Vert \frac{1}{D}I)\leq (1-\tilde{p})^2 S(\rho\_{0}\Vert \frac{1}{D}I)$ [1].

Secondly, similar to Eq. (14) in our paper, denote by $\rho\_{\mathcal{D}}(x; x\_{i})$ the final state of the $2L$-layer local depolarizing noisy quantum circuit. Then, the corresponding kernel value is \mathcal{K}(x,x\_{i})={\rm Tr} \left P_{0} \ \rho_{\mathcal{D}}(x; x_{i})\right $$. For local-depolarizing noise, we have $\vert \mathcal{K}(x,x\_{i}) - \overline{\mathcal{K}}(x,x\_{i}) \vert \leq \Vert \rho\_{\mathcal{D}}(x; x\_{i})-\frac{1}{D}I \Vert\_{1} \leq \sqrt{2 \ln 2\ S(\rho\_{\mathcal{D}}(x; x\_{i})\Vert\frac{1}{D}I)} \leq (1-\tilde{p})^{2L}\sqrt{2 \ln 2\ S(\rho\_{0}\Vert\frac{1}{D}I)}$, where the first two inequality come from the matrix H$\ddot{\rm o}$lder Inequality and quantum Pinsker Inequality [2], respectively. Thus, $\vert h(x)-\bar{h}(x) \vert = \mathcal{O}(n\vert \mathcal{K}(x,x\_{i}) - \overline{\mathcal{K}}(x,x\_{i}) \vert)=\mathcal{O}(n(1-\tilde{p})^{2L})$, where $n$ is the sample size.

Thirdly, for our global depolarizing noise, since $S(\mathcal{N}\_{\tilde{p}} (\rho\_{0})\Vert \frac{1}{D}I)\leq (1-\tilde{p}) S(\rho\_{0}\Vert \frac{1}{D}I)$, we have $\vert h(x)-\bar{h}(x) \vert = \mathcal{O}(n(1-\tilde{p})^{L})$ by following a similar analysis.

Combing the above statements, we can find that after local depolarizing noise, the kernel tends to get worse even for shallow circuits. The fundamental reason is that after an 1-layer of global depolarizing channel, the relative entropy decays as $S(\mathcal{N}\_{\tilde{p}} (\rho\_{0})\Vert \frac{1}{D}I)\leq (1-\tilde{p}) S(\rho\_{0}\Vert \frac{1}{D}I)$, while for the local depolarizing noise $S(\mathcal{D}\_{\tilde{p}}^{\otimes N}(\rho\_{0})\Vert \frac{1}{D}I)\leq (1-\tilde{p})^2 S(\rho\_{0}\Vert \frac{1}{D}I)$, which decays in a faster way.

[1] Stilck França, D., García-Patrón, R. Limitations of optimization algorithms on noisy quantum devices. Nat. Phys. 17, 1221–1227 (2021). https://doi.org/10.1038/s41567-021-01356-3

[2] Watrous, J. The Theory of Quantum Information. Cambridge: Cambridge University Press. https://doi.org/10.1017/9781316848142, Theorem 5.38 for quantum Pinsker Inequality.

Thank you very much for your helpful comments and suggestions.

First of all, we would like to point out that, for the problem of power characterization under consideration, our global noise model is actually weaker than the noise models considered in previous works you mentioned, such as, Stilck Franca & Garcia-Patron (2021), De Palma et al. (2023) and Thanasilp et al. (2022).

Specifically, in our work, the noise model, $\mathcal{N}\_{\tilde{p}}=(1-\tilde{p})\rho+\tilde{p}\frac{1}{D}I$ with rate $\tilde{p}$, is referred to as “global” as it applies onto all qubits after each layer of ideal unitary gates. While in Stilck Franca & Garcia-Patron (2021) and De Palma et al. (2023), the considered noise model is the local depolarizing noise. However, it applies to each qubit. Thus, their noise channel applied after each ideal unitary layer is $\mathcal{D}\_{\tilde{p}}^{\otimes N}$, with $\mathcal{D}\_{\tilde{p}}=(1-\tilde{p})\rho+\frac{1}{2}I$ and $N$ being the number of qubits. We have rewritten it using our notation for convenience of comparison. With the same noise rate $\tilde{p}$, we can compare our global depolarizing noise $\mathcal{N}\_{\tilde{p}}$ with its counterpart $\mathcal{D}\_{\tilde{p}}^{\otimes N}$. It can be seen that under our global noise, the quantum state is left untouched with probability $1-\tilde{p}$, while under the so-called local noise, the probability of the state remaining unchanged is only $(1-\tilde{p})^N$, which is exponentially small in $N$. Thus, in this sense our global depolarizing model is weaker than the so-called local depolarizing model. As for the Pauli noise model considered in Thanasilp et al. (2022), following a similar analysis, we can see that the Pauli noise is also stronger than ours.

When presenting negative results concerning noisy quantum kernels, it is better to assume a relatively weaker noise model. Once the kernel methods fail under weaker noises, they fail under stronger ones in general. Note that the noise rate $\tilde{p}>0$ in our work can be arbitrarily small. Thus, it can depict the case where the noise influence is very weak, namely, after the noise the quantum state is left untouched with a very high probability $1-\tilde{p}$. Thus, in this sense, our global depolarizing model is an appropriate starting point to study the limitations of noisy quantum kernel methods. We have made this clearer in the revised manuscript after Eq. (12). As you suggested, much work needs to be done to further investigate the limitations of quantum kernel methods, e.g., under more realistic quantum noise. We leave this for future research.

To address your constructive question "What are the key new findings on the noisy quantum kernel model compared with previous works", we have thoroughly revised Sec. 1.2 Related Work to compare our work with previous works. Your question definitely helps us to present our key new findings and the differences from the existing works more clearly. For more details, please refer to revised Sec. 1.2 Related Work as well as the above response to your question regarding global depolarizing noise.

Dear Reviewer 5XBn,

Many thanks for your dedicated time to review our work. We have taken your insightful comments seriously and have made necessary modifications based on your suggestions. With the imminent closure of the discussion period, time is of the essence.

Given that our work received your’s less favorable scores, we worked diligently to clarify our assumption and difference from prior work during the rebuttal period, demonstrating our unwavering commitment to addressing every facet of your feedback.

We kindly request your esteemed attention to our rebuttal response. Your responsible and positive endorsement holds paramount significance during this critical phase.

Wishing you all the best and awaiting your valued evaluation.

Best regards,

Authors

Thank you so much for your insightful advice for investigating other noise. We have worked diligently for a continuous span of ten days during the rebuttal period to explore this problem. Finally, we are excited to share with you that we find our result can be pushed to local depolarizing noise so that the prediction difference $\vert \tilde{h}-\bar{h} \vert$ converges to zero with the circuit depth increasing. Specifically, we outline the additional proof for local depolarizing noises as follows.

Firstly, after 1-layer of $N$-fold local depolarizing channel, the relative entropy satisfies $S(\mathcal{D}\_{\tilde{p}}^{\otimes N}(\rho\_{0})\Vert \frac{1}{D}I)\leq (1-\tilde{p})^2 S(\rho\_{0}\Vert \frac{1}{D}I)$ [1].

Secondly, similar to Eq. (14) in our paper, denote by $\rho\_{\mathcal{D}}(x; x\_{i})$ the final state of the $2L$-layer local depolarizing noisy quantum circuit. Then, the corresponding kernel value is \mathcal{K}(x,x\_{i})={\rm Tr} \left P_{0} \ \rho_{\mathcal{D}}(x; x_{i})\right $$. For local-depolarizing noise, we have $\vert \mathcal{K}(x,x\_{i}) - \overline{\mathcal{K}}(x,x\_{i}) \vert \leq \Vert \rho\_{\mathcal{D}}(x; x\_{i})-\frac{1}{D}I \Vert\_{1} \leq \sqrt{2 \ln 2\ S(\rho\_{\mathcal{D}}(x; x\_{i})\Vert\frac{1}{D}I)} \leq (1-\tilde{p})^{2L}\sqrt{2 \ln 2\ S(\rho\_{0}\Vert\frac{1}{D}I)}$, where the first two inequality come from the matrix H$\ddot{\rm o}$lder Inequality and quantum Pinsker Inequality [2], respectively. Thus, $\vert h(x)-\bar{h}(x) \vert = \mathcal{O}(n\vert \mathcal{K}(x,x\_{i}) - \overline{\mathcal{K}}(x,x\_{i}) \vert)=\mathcal{O}(n(1-\tilde{p})^{2L})$, where $n$ is the sample size.

Thirdly, for our global depolarizing noise, since $S(\mathcal{N}\_{\tilde{p}} (\rho\_{0})\Vert \frac{1}{D}I)\leq (1-\tilde{p}) S(\rho\_{0}\Vert \frac{1}{D}I)$, we have $\vert h(x)-\bar{h}(x) \vert = \mathcal{O}(n(1-\tilde{p})^{L})$ by following a similar analysis.

Combing the above statements, we can find that after local depolarizing noise, the kernel tends to get worse even for shallow circuits. The fundamental reason is that after an 1-layer of global depolarizing channel, the relative entropy decays as $S(\mathcal{N}\_{\tilde{p}} (\rho\_{0})\Vert \frac{1}{D}I)\leq (1-\tilde{p}) S(\rho\_{0}\Vert \frac{1}{D}I)$, while for the local depolarizing noise $S(\mathcal{D}\_{\tilde{p}}^{\otimes N}(\rho\_{0})\Vert \frac{1}{D}I)\leq (1-\tilde{p})^2 S(\rho\_{0}\Vert \frac{1}{D}I)$, which decays in a faster way.

[1] Stilck França, D., García-Patrón, R. Limitations of optimization algorithms on noisy quantum devices. Nat. Phys. 17, 1221–1227 (2021). https://doi.org/10.1038/s41567-021-01356-3

[2] Watrous, J. The Theory of Quantum Information. Cambridge: Cambridge University Press. https://doi.org/10.1017/9781316848142, Theorem 5.38 for quantum Pinsker Inequality.

Thank you very much for your helpful comments and suggestions as well as pointing out the useful reference.

• The authors should provide analytical results based on local depolarization noise. Techniques from https://arxiv.org/abs/2210.11505 and related works should be helpful in this case.

We agree with you that the local depolarizing noise is a natural noise model, where each qubit is subject to a small amount of noise. As compared with it, our global depolarizing model is a stronger assumption about the noise at first glance. However, on second thought, our global depolarizing model is actually weaker than the so-called local one for our problem in this paper. The reason is as follows.

In our work, as illustrated in Fig. 2(c), after each layer of ideal unitary gates, a depolarizing channel, $\mathcal{N}\_{\tilde{p}}=(1-\tilde{p})\rho+\tilde{p}\frac{1}{D}I$ with rate $\tilde{p}$ is applied. We refer to it “global” as it applies onto all qubits. In your mentioned paper ( https://arxiv.org/abs/2210.11505), two kinds of noise models are considered. The first one is the so-called local depolarizing noise acting on each qubit, which reads $\mathcal{D}\_{\tilde{p}}=(1-\tilde{p})\rho+\frac{1}{2}I$. We have rewritten it using our notation for convenience of comparison. As demonstrated by Fig. 1 in the mentioned paper, the noise channel applied after each layer of ideal unitary gates should be $\mathcal{D}\_{\tilde{p}}^{\otimes N}$ with $N$ being the number of qubits. Now we can compare our global depolarizing noise $\mathcal{N}\_{\tilde{p}}$ with its counterpart $\mathcal{D}\_{\tilde{p}}^{\otimes N}$ under the same noise rate $\tilde{p}$. It can be seen that under our global depolarizing noise, the quantum state is left untouched with probability $1-\tilde{p}$, while under the so-called local noise, the probability of the state remaining unchanged is only $(1-\tilde{p})^N$, which is exponentially small in $N$. Therefore, in this sense our global depolarizing model is weaker than the so-called local depolarizing model. Another considered noise model in the mentioned paper is non-unital noise acting on each qubit. Following a similar analysis to the above local depolarizing noise, it can be seen that the non-unital noise is also stronger than ours.

When presenting negative results concerning noisy quantum kernels, it is better to assume a relatively weaker noise model. Once the kernel methods fail under weaker noises, they fail under stronger ones in general. Note that the noise rate $\tilde{p}>0$ in our work can be arbitrarily small. Thus, it can depict the case where the noise influence is very weak, namely, after the noise the quantum state is left untouched with a very high probability $1-\tilde{p}$. Thus, in this sense, our global depolarizing model is an appropriate starting point to study the limitations of noisy quantum kernel methods. We have made this clearer in the revised manuscript after Eq. (12). We completely agree with you that much work needs to be done to further investigate the limitations of quantum kernel methods under more realistic quantum noise. We leave this for our future research.

We agree with you that the key behaviors of noisy quantum kernel methods are expected. However, one of our key contributions is that we explicitly depict the speed of the prediction concentration of noisy quantum kernels in terms of the strength of depolarization noise, the size of training samples, the number of qubits, the number of layers affected by quantum noise, and the number of measurement shots. This helps us quantitatively understand the limits of noisy quantum kernel methods. As an illustration, for a training sample set, whose scale is exponential in the number of qubits $N$, like $q^N$ for some $q>1$, noisy quantum kernel methods fail once the number of noisy layers exceeds $N\log\_{(1−\tilde{p} )^{−2}} q$.

• The numerical experiments can be improved to showcase the dependence on other parameters such as system size and noise rate.

We agree with you that the numerical results can be improved to showcase the dependence on other parameters such as system size and noise rate. In our paper, since we mainly focus on the influence of noise accumulation on the capability of quantum kernel methods, we only illustrate the dependence of the hypothesis function and the training error as well as the test error on the number of noisy layers. There are many open problems for future research.

Thank you so much for your constructive advice for investigating local depolarizing noise. We have worked diligently for a continuous span of ten days during the rebuttal period to explore this problem. Finally, we are excited to share with you that we find our main result can be pushed to local depolarizing noise so that the prediction difference $\vert \tilde{h}-\bar{h} \vert$ converges to zero with the circuit depth increasing. Specifically, we outline the additional proof for local depolarizing noises as follows.

Firstly, after 1-layer of $N$-fold local depolarizing channel, the relative entropy satisfies $S(\mathcal{D}\_{\tilde{p}}^{\otimes N}(\rho\_{0})\Vert \frac{1}{D}I)\leq (1-\tilde{p})^2 S(\rho\_{0}\Vert \frac{1}{D}I)$ [1].

Secondly, similar to Eq. (14) in our paper, denote by $\rho\_{\mathcal{D}}(x; x\_{i})$ the final state of the $2L$-layer local depolarizing noisy quantum circuit. Then, the corresponding kernel value is \mathcal{K}(x,x\_{i})={\rm Tr} \left P_{0} \ \rho_{\mathcal{D}}(x; x_{i})\right $$. For local-depolarizing noise, we have $\vert \mathcal{K}(x,x\_{i}) - \overline{\mathcal{K}}(x,x\_{i}) \vert \leq \Vert \rho\_{\mathcal{D}}(x; x\_{i})-\frac{1}{D}I \Vert\_{1} \leq \sqrt{2 \ln 2\ S(\rho\_{\mathcal{D}}(x; x\_{i})\Vert\frac{1}{D}I)} \leq (1-\tilde{p})^{2L}\sqrt{2 \ln 2\ S(\rho\_{0}\Vert\frac{1}{D}I)}$, where the first two inequality come from the matrix H$\ddot{\rm o}$lder Inequality and quantum Pinsker Inequality [2], respectively. Thus, $\vert h(x)-\bar{h}(x) \vert = \mathcal{O}(n\vert \mathcal{K}(x,x\_{i}) - \overline{\mathcal{K}}(x,x\_{i}) \vert)=\mathcal{O}(n(1-\tilde{p})^{2L})$, where $n$ is the sample size.

Thirdly, for our global depolarizing noise, since $S(\mathcal{N}\_{\tilde{p}} (\rho\_{0})\Vert \frac{1}{D}I)\leq (1-\tilde{p}) S(\rho\_{0}\Vert \frac{1}{D}I)$, we have $\vert h(x)-\bar{h}(x) \vert = \mathcal{O}(n(1-\tilde{p})^{L})$ following a similar analysis. Combing the above statements, we can find that after local depolarizing noise, the kernel tends to get worse even for shallow circuits. The fundamental reason is that after an 1-layer of global depolarizing channel, the relative entropy decays as $S(\mathcal{N}\_{\tilde{p}} (\rho\_{0})\Vert \frac{1}{D}I)\leq (1-\tilde{p}) S(\rho\_{0}\Vert \frac{1}{D}I)$, while for the local depolarizing noise $S(\mathcal{D}\_{\tilde{p}}^{\otimes N}(\rho\_{0})\Vert \frac{1}{D}I)\leq (1-\tilde{p})^2 S(\rho\_{0}\Vert \frac{1}{D}I)$, which decays in a faster way.

In the current quantum devices, the noise is vital of consideration before realizing quantum error correction and fault tolerant quantum computing. To this end, we and the authors in many Related Works are focusing on the effect of quantum noise and provide a crucial warning to utilize noisy quantum kernels under different noise models.

In a word, for the ultimate goal of machine learning, i.e., prediction, the local depolarizing noise model is usually “stronger” than our global one. Our work is especially useful for developing quantum kernel methods in noisy intermediate-scale quantum (NISQ) era where we have insufficient capability for quantum error correction. We agree with you that further work is worthing being presented to discuss the different performance and effects of quantum error correction and quantum error mitigation for global depolarizing noise and local depolarizing noise.

[1] Stilck França, D., García-Patrón, R. Limitations of optimization algorithms on noisy quantum devices. Nat. Phys. 17, 1221–1227 (2021). https://doi.org/10.1038/s41567-021-01356-3

[2] Watrous, J. The Theory of Quantum Information. Cambridge: Cambridge University Press. https://doi.org/10.1017/9781316848142, Theorem 5.38 for quantum Pinsker Inequality.

We apologize that we did not include new numerical experiments in the revised paper due to limited time. We had focused on presenting more convincing explanations on the employment of global depolarizing noise and the critical applicability issue on local depolarizing noise. We have started to implement experiments to obtain additional numerical results but it will take too much time to generate sufficient results showcasing the dependence on other parameters (e.g., a simple experiment needs to run more than 30 hours). In principle, we do not find any technical difficulty at this stage and will present additional results in the near future. We appreciate your constructive feedback and advice.

Thank you very much for your insightful comments.

• Why does the bound in Theorem 3.1 still converge to zero as $p=0$?

As you mentioned, Equation (20) in the theorem bounds the distance between the quantum kernel's choice $\tilde{h}$ and the worst possible predictor $\bar{h}$. It consists of three terms. The third term converges to 0 as $n$ increases, and the second term approaches to 0 as $n$ and $D$ increase (as long as $n$ is not in the order of $D$). While the first term $f(\cdot)$ goes to 0 if and only if its argument goes to 0. If we set $p=0$, then the argument of the first term $f(\cdot)$ is a constant of $\frac{n}{\lambda}(1+\frac{1}{D})$, and in turn the bound does not converge to zero. Thank you for pointing out this potential ambiguity. Following your insightful comments, we have made it clearer in the revised manuscript.

• The samples are classical in this work, but the kernel is quantum. What can be done with your work for the quantum samples?

In our work, the samples are classical and encoded into quantum states to compute their kernels. If the samples are quantum, our technique can still be applied to analyze the impact of noise on quantum kernel methods if the depolarizing noise occurs during the generation of quantum samples or during the computation of kernels. We leave this as future work for a more detailed analysis. Thank you for your insightful comments.

Dear Reviewer 8JA5,

Many thanks for your dedicated time to review our work. We have taken your comments seriously and have made the necessary explanations based on your suggestions. With the imminent closure of the discussion period, time is of the essence.

Given that our work received your’s less favorable scores, we worked diligently to clarify the technical details during the rebuttal period, demonstrating our unwavering commitment to addressing every facet of your feedback.

We kindly request your esteemed attention to our rebuttal response. Your responsible and positive endorsement holds paramount significance during this critical phase.

Wishing you all the best and awaiting your valued evaluation.

Best regards,

Authors

Dear Reviewer 8JA5,

Thank you so much for reviewing our paper. We have worked diligently for a continuous span of ten days during the rebuttal period to explore this issue on local depolarizing noise. Finally, we are excited to share with you that we find our main result can be pushed to local depolarizing noise so that the prediction difference $\vert \tilde{h}-\bar{h} \vert$ converges to zero with the circuit depth increasing. Specifically, we outline the additional proof for local depolarizing noises as follows.

Firstly, after 1-layer of $N$-fold local depolarizing channel, the relative entropy satisfies $S(\mathcal{D}\_{\tilde{p}}^{\otimes N}(\rho\_{0})\Vert \frac{1}{D}I)\leq (1-\tilde{p})^2 S(\rho\_{0}\Vert \frac{1}{D}I)$ [1].

Secondly, similar to Eq. (14) in our paper, denote by $\rho\_{\mathcal{D}}(x; x\_{i})$ the final state of the $2L$-layer local depolarizing noisy quantum circuit. Then, the corresponding kernel value is \mathcal{K}(x,x\_{i})={\rm Tr} \left P_{0} \ \rho_{\mathcal{D}}(x; x_{i})\right $$. For local-depolarizing noise, we have $\vert \mathcal{K}(x,x\_{i}) - \overline{\mathcal{K}}(x,x\_{i}) \vert \leq \Vert \rho\_{\mathcal{D}}(x; x\_{i})-\frac{1}{D}I \Vert\_{1} \leq \sqrt{2 \ln 2\ S(\rho\_{\mathcal{D}}(x; x\_{i})\Vert\frac{1}{D}I)} \leq (1-\tilde{p})^{2L}\sqrt{2 \ln 2\ S(\rho\_{0}\Vert\frac{1}{D}I)}$, where the first two inequality come from the matrix H$\ddot{\rm o}$lder Inequality and quantum Pinsker Inequality [2], respectively. Thus, $\vert h(x)-\bar{h}(x) \vert = \mathcal{O}(n\vert \mathcal{K}(x,x\_{i}) - \overline{\mathcal{K}}(x,x\_{i}) \vert)=\mathcal{O}(n(1-\tilde{p})^{2L})$, where $n$ is the sample size.

Thirdly, for our global depolarizing noise, since $S(\mathcal{N}\_{\tilde{p}} (\rho\_{0})\Vert \frac{1}{D}I)\leq (1-\tilde{p}) S(\rho\_{0}\Vert \frac{1}{D}I)$, we have $\vert h(x)-\bar{h}(x) \vert = \mathcal{O}(n(1-\tilde{p})^{L})$ by following a similar analysis.

Combing the above statements, we can find that after local depolarizing noise, the kernel tends to get worse even for shallow circuits. The fundamental reason is that after an 1-layer of global depolarizing channel, the relative entropy decays as $S(\mathcal{N}\_{\tilde{p}} (\rho\_{0})\Vert \frac{1}{D}I)\leq (1-\tilde{p}) S(\rho\_{0}\Vert \frac{1}{D}I)$, while for the local depolarizing noise $S(\mathcal{D}\_{\tilde{p}}^{\otimes N}(\rho\_{0})\Vert \frac{1}{D}I)\leq (1-\tilde{p})^2 S(\rho\_{0}\Vert \frac{1}{D}I)$, which decays in a faster way.

In the current quantum devices, the noise is vital of consideration before realizing quantum error correction and fault tolerant quantum computing. To this end, we and the authors in many Related Works are focusing on the effect of quantum noise and provide a crucial warning to utilize noisy quantum kernels under different noise models.

In a word, for the ultimate goal of machine learning, i.e., prediction, the local depolarizing noise model is usually “stronger” than our global one. Our work is especially useful for developing quantum kernel methods in noisy intermediate-scale quantum (NISQ) era where we have no sufficient capability for quantum error correction.

[1] Stilck França, D., García-Patrón, R. Limitations of optimization algorithms on noisy quantum devices. Nat. Phys. 17, 1221–1227 (2021). https://doi.org/10.1038/s41567-021-01356-3

[2] Watrous, J. The Theory of Quantum Information. Cambridge: Cambridge University Press. https://doi.org/10.1017/9781316848142, Theorem 5.38 for quantum Pinsker Inequality.

We do expect that our further clarification addresses your concerns. Nevertheless, the final decision for endorsement or rejection ultimately lies with you, and we deeply respect that.

Many thanks for your advice, suggestions and feedback, and wish you all the best.

Best regards,

Authors

Thank you very much for your feedback.

In fact, our main result holds only for the noisy case. Note that the function $f(z)$ in the RHS of Eq. (20) has the form of $f\left( z\right) =\frac{z+8\sqrt{\frac{z}{\lambda}}}{1-z}$. To make it meaningful, its argument must be less than 1. Thus, in Eq. (20), $\frac{n}{\lambda}(1-p)(1+\frac{1}{D})$ should be less than 1. This corresponds to noisy channels rather than the ideal case. This is because $1-p=(1-\tilde{p})^{2L}$. In the idea case $\tilde{p}=0$, then $1-p=1$. This leads to $\frac{n}{\lambda}(1-p)(1+\frac{1}{D}) > 1$.

To sum up, in this paper, we focus on the effect of quantum noise and provide a crucial warning to utilize noisy quantum kernels. Our main results are indicative for noisy deep quantum circuits.