Neural Auto-designer for Enhanced Quantum Kernels

Thanks to the precious suggestions made by the Reviewer 3hUP. These suggestions provide us with a lot of insights and help us improve the quality of our work. We are also highly grateful to the reviewer for dedicating her/his time and effort to help us improve the quality of our paper. Additionally, based on the guidance reviewer provided in the ICLR 2024, we have found that your comments do not strictly align with the criteria for a strong rejection. In response to your concerns, we have provided detailed responses and we kindly request that you reconsider the quality of our work.

Q1: The problem of quantum kernel ...... instead of the general QAS problem.

A1: Thanks for your comment. We will primarily address your question from the following two aspects:

1. Quantum kernel search vs QAS. Quantum kernel search is not a special case of QAS because we cannot directly apply QAS methods to design the quantum kernel due to the high complexity of evaluating the quantum kernel. Therefore, the one of main contributions of our paper is the introduction of kernel-target alignment (KTA), which greatly reduces the complexity of evaluating the quantum kernel (from $O(n^3)$ to $O(n^2p)$, $n$ is the number of samples, $p$ refers to the dimensionality of the data after dimensionality reduction), making quantum kernel search possible.
2. Complementarity. Quantum kernel search and QAS are complementary as designing a good quantum kernel. On the other hand, quantum kernel search and QAS are all can borrow ideas form Neural Architecture Search (NAS). From this perspective, quantum kernel search cannot be a subset of QAS.

Q2: [3] proposed a very similar QAS ...... too simple with no novelty at all.

A2: Thanks for your suggestion. We address your concerns in order.

1. Not cite paper [3]. Quantum kernel search is not a subset of QAS as they are complementary to each other. Additionally, our work is primarily based on paper [4], not paper [3]. Ref. [3] does not utilize a neural predictor to evaluate the performance of QNNs.
2. Cite 7 other papers. The reason we cited these seven papers is because they are highly relevant to our work. If the reviewer has concerns about any specific paper, we are open to discussing it separately. If some of them are ultimately found to be inappropriate, we will remove them accordingly.
3. No novelty. As mentioned in the first paragraph on the page 2 of our paper, “quantum kernels associated with inappropriate quantum feature maps tend to be inferior to that of classical kernels [5]. Even worse, when the quantum feature map involves deep circuit depth, a large number of qubits, and too many noisy gates, the corresponding quantum kernel may encounter the vanishing similarity [6] and the degraded generalization ability [7], precluding any potential computational advantages.” These indicates that designing a good quantum feature map is very important. However, it is not clear how to design a good quantum kernel as there is no prior knowledge to guide us in designing the kernel. Our work takes a first step in quantum kernel search. And our main innovation lies in the introduction of KTA with neural predictor to extremely reduce the time complexity of evaluating the quantum kernel, combined with feature selection to make our method applicable to high-dimensional real-world data. And our approach can be seen as a generalization in the field of quantum kernel search as we simultaneously consider the circuit layout and variational parameters.

If you still have any concerns, we will provide further explanations to address them.

Q3: The experimental results are weak ...... not considering noise models or quantum devices.

A3: Thanks for your comment. The noise simulation results are displayed in Appendix C.7 of our original manuscript. The main results is that our method exhibits good adaptability across different levels of noise and performs well on real quantum devices. It is capable of finding quantum kernel with good performance.

[1] Lu X, Pan K, et al. QAS-Bench: Rethinking Quantum Architecture Search and A Benchmark[J]. 2023.

[2] Wu W, et al. QuantumDARTS: Differentiable Quantum Architecture Search for Variational Quantum Algorithms[J]. 2023.

[3] Du Y, Huang T, et al. Quantum circuit architecture search for variational quantum algorithms[J]. npj Quantum Information, 2022, 8(1): 62.

[4] Shi-Xin Zhang, et a. Neural predictor based quantum architecture search. Machine Learning: Science and Technology, 2(4):045027, 2021.

[5] Hsin-Yuan Huang, et a. Power of data in quantum machine learning. Nature communications, 12(1):2631, 2021.

[6] Supanut Thanasilp, et a. Exponential concentration and untrainability in quantum kernel methods. arXiv preprint arXiv:2208.11060, 2022.

[7] Xinbiao Wang, et al. Towards understanding the power of quantum kernels in the nisq era. Quantum, 5:531, 2021.

We would like to reiterate our deep appreciation for the reviewer's dedicated time and effort in scrutinizing our paper and providing invaluable feedback.

Thanks to the precious suggestions made by the Reviewer oLos. These suggestions provide us with a lot of insights and help us improve the quality of our work. We are also highly grateful to the reviewer for dedicating her/his time and effort to help us improve the quality of our paper. Additionally, we have provided detailed responses and hope that the reviewer will reconsider the quality of our paper.

Q1:Since ...is not a key topic.

A1: Thanks for your comment. As mentioned in the first paragraph on the page 2 of our paper, “quantum kernels associated with inappropriate quantum feature maps tend to be inferior to that of classical kernels [1]. Even worse, when the quantum feature map involves deep circuit depth, a large number of qubits, and too many noisy gates, the corresponding quantum kernel may encounter the vanishing similarity [2] and the degraded generalization ability [3], precluding any potential computational advantages.” These indicates that designing a good quantum feature map is very important. However, it is not clear how to design a good quantum kernel as there is no prior knowledge to guide us in designing the kernel.

On the one hand, quantum kernel design is quite different from the field of deep learning, where there are many well-performing structures that can serve as basic modules to construct neural networks, such as CNN, RNN, and Transformer. In contrast, quantum machine learning is still in its early stages, and we are uncertain about which well-structured modules can be used to build quantum kernels. This situation is even more challenging in the near-term quantum devices, as it requires considering noise, topology, and various limitations. Designing a good quantum kernel becomes more challenging. In such cases, using automated search methods to design quantum kernels becomes one of the approaches to address this problem. Consequently, many researchers have conducted extensive studies in this area. In the NISQ era, quantum kernels have the potential to be a promising approach for achieving quantum advantage [4]. And quantum kernels also have a solid theoretical foundation [5-7]. Another hot topic is Quantum Architecture Search (QAS) [8-10]. There are also exists some papers related to quantum feature map design suggest that adjusting quantum kernels can improve their performance on downstream tasks [11-13].

Therefore, designing better quantum kernels is both urgent and crucial, as it represents a key step towards achieving potential quantum advantage on near-term quantum devices.

To address your concern, we have added a discussion on motivation of our work in the Appendix of the revised version of manuscript.

Q2: The computation cost... to large datasets.

A2: Thanks for your comment. We respectfully disagree with your viewpoint that the computation cost of the two-stage optimization for the objective as Eq. (4) is such high.

The one of objectives of this paper is to significantly reduce the optimization complexity. Therefore, we leverage kernel-target alignment (KTA) and the neural predictor to rapidly evaluate the performance of quantum kernels. Our method has significantly reduced the time cost compared to brute force search (from $O(n^3)$ to $O(n2p)$, $n$ is the number of samples, $p$ refers to the dimensionality of the data after dimensionality reduction). More specifically, in the data collection stage, calculating the KTA is more time efficiency than computing the training accuracy on the Tailored MNIST, Tailored CC and Synthetic dataset (e.g., 288s vs 1138s, 86s vs 331s, and 48 vs 188s). While in search stage, our method is more efficient, as it can complete performance evaluation of 50,000 kernels within 75 seconds. From this point of view, the computation cost of our method would not be very high.

The reason for using a small subset of MNIST samples can be attributed to two main factors. Firstly, it is widely acknowledged in the quantum machine learning to use a subset of MNIST for experimentation [1,14,15]. Secondly, this small dataset is sufficient to demonstrate the effectiveness of our method.

Regarding randomized quantum kernel, we have found a reference [16]. If reviewer confirm that this is the correct paper, we can proceed with further discussion, or if reviewer provide the corresponding reference, we can discuss it accordingly.

Q3: The performance ... quantum kernel.

A3: Thanks for your comment. To address your concern, we have increased the dimensionality of the Tailored MNIST dataset to 80 and conducted further experiments. The results are presented in the table below. The results demonstrate our method can still find kernels with better performance on higher-dimensional data.

Dear Reviewer oLos!

Sincere gratitude for your comment. We have addressed all the comments raised by you. Item by item responses to the your comments are listed above this response. We are looking forward to your feedback.

Best wishes!

Authors.

Thanks to the precious suggestions made by the Reviewer e6Tr. These suggestions provide us with a lot of insights and help us improve the quality of our work. We are also highly grateful to the reviewer for dedicating her/his time and effort to help us improve the quality of our paper.

Q1: The method is benchmarked against,...... I did not see how the parameters of the RBF were tuned.

A1: Thanks for your comment. We will address your two questions in order. The first question pertains to the issue of using a classical kernel with adaptive data, and the second question relates to the parameters of the RBF kernel.

We follow the Ref. [1] and conducted 5 random experiments with the default parameters based on the official code of [1], and the results are summarized in the table below. Neural Kernel Network (NKN) is the method proposed in paper [1]. The test accuracy are provided in the table below. The performance of NKN is lower than our method on all three datasets.

We next address the concern about the parameters of the RBF. We are kindly remind the reviewer, in fact, we have introduced the relevant parameter of the RBF in the original manuscript. In brief, we only varied the $\gamma$ of the RBF, and $\gamma \in \{ 1, 2, 3, 4, 5\} /(p \text{ Var}[x_j^{(i)}])$. More details are introduced in the Appendix C.2.

Q2: I did not see a clear benefit ...... suboptimal in this large search space.

A2: Thanks for your comment. Before addressing your detailed concerns, we first highlight our key motivation. 1) Quantum kernel has a rich theoretical foundation. For example, Ref. [2] rigorously proves the superiority of quantum kernels in the discrete logarithm problem, while Ref. [3] demonstrates their advantage in the synthetic data. Ref. [4] proved that kernel-based training is guaranteed to find better or equally good quantum models than variational circuit training in supervised machine learning. In contrast, there is limited research in this aspect for Quantum Neural Network (QNN). 2) Quantum kernel is not equivalent to the QNN. Although there is a certain mapping relationship between quantum kernel and QNN, it is maybe that QNN requires an exponential number of qubits to achieve the same effect of the quantum kernel [5]. 3) The potential of quantum kernel. In the field of quantum kernel, there are two main focus. The first is the performance of quantum kernel, examining its capabilities and limitations. The second focus is whether it exhibits quantum advantage, meaning whether it can outperform classical approaches for certain tasks. Therefore, researching quantum kernels is both feasible and important.

When designing quantum kernels, the only similarity with Quantum Architecture Search (QAS) is that borrowing ideas from Neural Architecture Search (NAS), transforming the design of quantum kernel into a discrete-continuous optimization problem. However, as mentioned in the last sentence of the second paragraph on the third page of our paper “The fundamental difference between neural networks and kernels hints the hardness of directly employing QAS to automatically design quantum kernels”. In order to effectively utilize NAS for quantum kernel design, we introduced Kernel Target Alignment (KTA) to reduce the time complexity (from $O(n^3)$ to $O(n^2p)$, $n$ is the number of samples,$p$ refers to the dimensionality of the data after dimensionality reduction) required for evaluating kernel performance.

We next answer your questions one by one.

Essentially, we are aiming to solve a discrete-continuous optimization problem. In NAS, there are many choices, and we chose to use a neural predictor because it is a mature solution in NAS [6] and has also been applied in QAS [7]. Therefore, we consider the neural predictor as our approach to explore. In the neural predictor, our main consideration is the trade-off between runtime cost and performance of quantum kernels.

1. Benefit of neural predictor. Time cost: Evaluating the performance of quantum kernels generated by different circuits through random sampling can be extremely time-consuming. Since the time complexity of evaluating the quantum kernel with train accuracy is $O(n^3)$, and $n$ is the number of samples. For example, calculating the training accuracy on the three datasets (Tailored MNIST, Tailored CC, Synthetic dataset) takes 1138s, 331s, and 188s, respectively. Using a neural predictor can greatly reduce the time cost of evaluating kernel performance (e.g., evaluating 50,000 kernels only takes 75s). Using random sampling limits our ability to explore more kernels.

However, the neural predictor enables us to quickly evaluate the performance of a large number of different kernels. For example, evaluating 50,000 kernels only takes 75s. Performance: The performance of the kernels corresponding to the randomly sampled and the ones searched through the neural predictor are shown in Fig. 12 (Appendix C.5). The main result is that the performance of kernels found by the neural predictor is significantly higher than randomly searched kernels on Tailored MNIST and Tailored CC datasets (i.e., [75%, 88%] versus [50%, 75%] test accuracy on Tailored MNIST). However, on the Synthetic dataset, the performance is slightly higher than randomly searched kernels.

It is worth noting that, the neural predictor is not the only way to implement the quantum kernel search. Our goal is to automatically design a good quantum kernel, and the neural predictor is just one way to achieve that. To address your concerns better, we have included new discussions in the revised version of the paper.

2. Random sampling vs Neural predictor. The reviewer’s question refers to $M$ or $M'$, so we will answer it in two steps.

If you are referring to $M$: the validation accuracy of 200 kernels selected by QuKerNet and random search are shown in Fig. 12 (Appendix C.5). And the main result is that the performance of kernels found by the neural predictor is significantly higher than randomly searched kernels on Tailored MNIST and Tailored CC datasets, and is slightly higher than randomly searched kernels on Synthetic dataset.

If you are referring to $M'$: the time for evaluating $M'$ kernels by randomly search is not feasible. For example, estimating 50,000 kernels on the three datasets would require approximately 56,900,000s, 16,550,000s, and 9,400,000s, respectively.

3. Activate learning: As mentioned in the first sentence of the first paragraph on the page 7 of our paper “Our proposed scheme in QuKerNet offers a general framework that can be seamlessly integrated with various advanced methods and techniques.”. This means we provided a paradigm that is highly flexible. And we also mentioned in the second sentence of the second paragraph on the page 2 of our paper “Specifically, ……tuning variational parameters within the quantum feature maps and employing evolutionary or Bayesian algorithms to continually adjust the arrangement of quantum gates within the feature map”. So we can utilize methods such as Bayesian optimization (BO) [8] or genetic algorithms [9] to guide kernel search process. These methods are complementary and compatible with our approach. Additionally, we implemented Bayesian optimization for quantum kernel search using Optuna [10] to address reviewer’s concern. We set the number of iterations to 1000, and the experimental results are shown in the table below. The kernel searched by Bayesian optimization did not surpass the random search approach, which may be due to the limited number of iterations. | | Training data | Candidate | Fine-tune| | -------- | -------- | -------- | -------- | | Tailored MNIST BO | 82.12±0.27| 83.20±1.66| 85.60±1.44| | Tailored MNIST Ours | 82.12±0.27| 85.87±1.43| 86.80±1.36| | Tailored CC BO| 87.00±0.00| 89.80±1.72| 93.00±1.41| | Tailored CC Ours| 87.00±0.00| 92.20±1.17| 94.40±0.80| | Synthetic dataset BO| 80.33±0.67| 76.67±6.15| 89.34±2.26| | Synthetic dataset Ours| 80.33±0.67| 84.00±3.89| 91.33±1.63|

Q3: What is M' (number of sampled layouts) used in the experiments?

A3: Thanks for your comment. In our experiments, $M'$ was indeed set to 50,000, which is consistent with $|S|$. This is a typo and we have made the revision in the revised version of the paper.

Q4: Can you try ......quantify the quantum advantage?

A4: Thanks for your suggestion. Before addressing your detailed concerns, let us first recall our statement in introduction, the second sentence of the second paragraph on the page 1, “quantum advantages may arise if two conditions are met: the reproducing kernel Hilbert space formed by quantum kernels encompasses functions that are computationally hard to evaluate classically, and the target concept resides within this class of functions.” This implies that quantum kernels with prior knowledge are likely to exhibit quantum advantage. On the other hand, we can quantify the performance gap between classical kernel and quantum kernel on a given dataset using the metric geometric difference proposed in reference [3]. Through this metric, we can demonstrate that quantum kernels have better performance on certain datasets that are well-suited for quantum models. That is why we chose synthetic dataset for our experiments. Additionally, we also hope to achieve quantum advantage on real-world data, which is why we selected Tailored MNIST and Tailored CC datasets.

Thanks to the precious suggestions made by the Reviewer FSEH. These suggestions provide us with a lot of insights and help us improve the quality of our work. We are also highly grateful to the reviewer for dedicating her/his time and effort to help us improve the quality of our paper. Additionally, we have provided detailed responses and hope that the reviewer will reconsider the quality of our paper.

Q1: The author ......more convincing.

A1: Thanks for your comment. We will separately reply your questions.

1. Related to quantum feature map of NISQ devices. We respectfully disagree with your viewpoint that our approach only suitable for NISQ devices.

Before addressing your detailed concerns, we first explain our key motivation. As mentioned in the first paragraph on the page 2 of our paper, “quantum kernels associated with inappropriate quantum feature maps tend to be inferior to that of classical kernels [4]. Even worse, when the quantum feature map involves deep circuit depth, a large number of qubits, and too many noisy gates, the corresponding quantum kernel may encounter the vanishing similarity [5] and the degraded generalization ability [6], precluding any potential computational advantages.” These indicates that designing a good quantum feature map is very important. On the other hand, several papers have demonstrated the advantage of quantum kernels in certain tasks or datasets. For example, Ref. [7] rigorously proves the superiority of quantum kernels in the discrete logarithm problem, while Ref. [4] demonstrates their advantage in the synthetic data. These papers indirectly confirm the potential advantage of quantum kernels. This is why our work focus on quantum kernel design.

Our approach is not only applicable to NISQ devices but also to fault-tolerant quantum devices. Currently, we are in the NISQ era, where many applications are implemented on NISQ devices. Therefore, we conducted relevant experiments specifically targeting NISQ devices. We also conduct many experiments on fault-tolerant quantum devices (refers to the page 9 of our paper). Therefore, in the revised version's appendix, we will explain that our method is not only applicable to NISQ devices.

Additionally, in the second sentence of the first paragraph on the page 7 of our paper, we mentioned that “can be modified to accommodate different quantum hardware platforms, enabling flexibility and adaptability.” This indicates our approach is suitable for different quantum devices, encompassing both hardware-adaptive and problem-adaptive solutions. It is not limited to NISQ devices alone. Moreover, on NISQ devices, quantum kernels can exhibit characteristics that are difficult to simulate classically, such as high entanglement or deep circuits. In such cases, the generated quantum kernels may not be easily simulated classically. On the other hand, since our approach is hardware-adaptive, as devices upgrade and the number of qubits increases, we can search for more complex kernels. These kernels are likely to be difficult to simulate classically.

2. Quantum advantage with theoretical explanation: Quantum advantage with theoretical explanation is challenging.

We primarily aim to demonstrate from both practical and theoretical perspectives that achieving provable quantum advantage is challenging.

Practical perspective: We hope to transfer the quantum advantage present in synthetic data to real-world data, but this is often challenging. Currently, there is no literature proposing quantum neural network (QNN) or quantum kernels with provable quantum advantage in practical problems. Firstly, quantum advantage is just one aspect that this paper focuses on. Our main emphasis is on improving the performance of quantum kernels on real-world datasets to narrow the gap with kernels on synthetic datasets. Secondly, quantum advantage is influenced by various factors. For instance, Ref. [4] demonstrates that quantum advantage is related to the structure of the data itself. Additionally, Ref. [8] provides two conditions for achieving quantum advantage, namely, quantum kernels encompasses functions that are computationally hard to evaluate classically, and the target concept resides within this class of functions. Therefore, the quantum advantage demonstrated in this paper is not necessarily obvious.

Theoretical perspective: Paper [4] stated that Learning is only possible if the distribution, model and/or model selection strategy contains a lot of structure, which is not always easy to analyse theoretically. For example, deep learning can learn a distribution from data, but can not construct this distribution through mathematical formulas. This also highlights that many real-world problems cannot be easily expressed in mathematical forms, which hinders the progress of proving quantum advantage theoretically. However, problems that can be well-defined are possible candidates for demonstrating quantum advantage [4,7].

And it is worth mentioning that proving quantum advantage theoretically is a valuable direction for future work, and it can be considered as an area of interest.

Q2: In the field of quantum machine learning ... proposed QuKerNet in this paper.

A2: QAS methods are complementary to our approach, and our solution is not an incremental work on QAS.

Thanks for your comment. QAS methods are complementary to our approach, and our solution is not an incremental work on QAS.

We will address your concerns from two aspects.

1. Quantum kernel vs QNN. Quantum kernel has a rich theoretical foundation. For example, Ref. [7] rigorously proves the superiority of quantum kernels in the discrete logarithm problem, while Ref. [4] demonstrates their advantage in the synthetic data. Ref. [10] proved that kernel-based training is guaranteed to find better or equally good quantum models than variational circuit training in supervised machine learning. In contrast, there is limited research in this aspect for QNN. And quantum kernel is not equivalent to the QNN. Although there is a certain mapping relationship between quantum kernel and QNN, it is maybe that QNN requires an exponential number of qubits to achieve the same effect of the quantum kernel [11].
2. QAS for quantum kernel search is not straightforward. QAS cannot be adapted to quantum kernel search, primarily due to the requirement of calculating Kernel Target Alignment (KTA) during the evaluation process of kernel search. Obtaining KTA needs to be computed based on the kernel matrix derived from the data. As mentioned in Section 3.2 of our paper, QuKerNet is highly flexible, allowing various QAS techniques to be utilized in QuKerNet. Regarding the explanation of the differences between QAS and quantum kernel search, we will provide supplementary information and clarification in the revised version of this paper.

The core idea of the two works mentioned by the reviewer [1] and [2] is consistent with Ref. [12], which is to continuousize the discrete space to accelerate the search process with advanced gradient-based methods. And in Section 3.2 of our paper, we also discuss various variants of our approach. The essence of our work lies in utilizing KTA and Neural Architecture Search (NAS) to efficiently implement quantum kernel design based on a discrete-continuous optimization problem. The reviewer's suggestion of using differentiable methods for quantum kernel search is also feasible in our framework.

Q3: While transfer ... quantum feature maps.

A3: Thanks for your common. We respectfully reminder the reviewer transfer some ideas of QAS to quantum kernel methods is not one of the contributions of this paper.

On the one hand, QAS and quantum kernel search are all borrow ideas from NAS. On the other hand, as mentioned in our response to question 2, quantum kernels and QNNs have inherent differences, which is why we cannot directly apply the QAS approach to quantum kernel search. As mentioned earlier, the main contribution of this work is the introduction of KTA. Evaluating the performance of a kernel requires computing the kernel matrix based on the entire training data, unlike QAS which can use a smaller amount of data or fewer epochs to quickly estimate the performance of a Quantum Neural Network (QNN). Therefore, directly transferring QAS ideas to quantum kernel search is not feasible. However, by leveraging KTA, we greatly reduce the evaluation time of kernels from $O(n^3)$ to $O(n^2p)$ ($n$ is the number of samples, $p$ refers to the dimensionality of the data after dimensionality reduction), making quantum kernel search possible. More concretely, calculating the training accuracy on the three datasets (Tailored MNIST, Tailored CC, Synthetic dataset) takes 1138s, 331s, and 188s, respectively. However, the neural predictor enables us to quickly evaluate the performance of a large number of different kernels. For example, evaluating 50,000 kernels only takes 75s.

We respectfully disagree with your viewpoint that the NAS method utilized in this paper is somewhat outdated and lack timeliness.

Currently, in the field of quantum kernel design, there is no well-established solution. Considering the time required for kernel evaluation, we have employed the neural predictor with KTA to efficiently search kernels. This is our first step in quantum kernel search, and there is ample room for improvement. In future work, we will explore more advanced NAS approaches to design quantum kernels.

The implementation method, as discussed in Section 3.2, is flexible and open to various approaches. At the same, as mentioned in our response to question 2, QAS methods are complementary to our approach. Therefore, the methods mentioned by the reviewer in [1-3] are all applicable and can be considered for future work to further enhance the performance of the quantum kernel. We also discuss these approaches in revised version of this paper.

Thank you for the author's reply. I believe that in some of the responses, the author fails to fully satisfy the reviewer, so I decide to maintain my score.

Firstly, the quantum kernel, as a powerful tool for studying the advantages and limitations of quantum variational algorithms on real/synthetic datasets, has been theoretically investigated in related papers, including the Neural Tangents Kernel (NTK) [1] and some geometric metrics [2]. Based on this foundation, I think the author should at least adopt one of these methods to discuss whether the auto-designed quantum kernel corresponds to a quantum feature map that is stronger than manually designed ones or those generated by other QAS. The discussion should go beyond empirical observations.

Furthermore, the reviewers maintain the same stance as Weakness 2. Although the quantum kernel is generally not equivalent to Quantum Neural Networks (QNN) due to the existence of some implicit quantum kernels that require an exponential number of quantum gates to implement, the reviewers believe that the proposed quantum kernel by the author still falls within the scope of QNN. The use of Kernel Target Alignment (KTA) to compute the kernel matrix and then search for the optimal kernel appears redundant. After all, the quantum circuit has already generated an explicit quantum feature map, and such a feature map can be optimized by the loss function (Eq. 4) without the immediate need to construct a kernel matrix.

Lastly, it is regrettable that the author has not incorporated relevant SOTA baselines [3,4] for comparison so far. Reviewer believes that the methods in [3,4] could potentially be strong competitors empirically surpassing the results presented in this paper.

[1] Liu J, Tacchino F, Glick J R, et al. Representation learning via quantum neural tangent kernels[J]. PRX Quantum, 2022, 3(3): 030323.

[2] Huang, HY., Broughton, M., Mohseni, M. et al. Power of data in quantum machine learning. Nat Commun 12, 2631 (2021).

[3] Wu W, Yan G, Lu X, et al. QuantumDARTS: Differentiable Quantum Architecture Search for Variational Quantum Algorithms. ICML, 2023.

[4] Lu X, Pan K, Yan G, et al. QAS-Bench: Rethinking Quantum Architecture Search and A Benchmark. ICML, 2023.

Q3: Lastly, it is regrettable ... surpassing the results presented in this paper.

A3: Thank you for your comment. We fail to incorporate relevant SOTA baselines [9,10] for comparison, because we could not find the relevant public code. More precisely, there is no code provided in [9], and the link provided in the literature [10] is no longer accessible. Additionally, we extensively searched on platforms such as GitHub or Paper with Code but could not find the corresponding code. Furthermore, due to time constraints, we did not have enough time to reproduce the code from these papers. That is why we were unable to conduct experiments related to them. We will promptly supplement the relevant experiments, as long as the codes of Refs.[9,10] have released.

[1] Liu J, Tacchino F, Glick J R, et al. Representation learning via quantum neural tangent kernels[J]. PRX Quantum, 2022, 3(3): 030323.

[2] Liu J, Zhong C, Otten M, et al. Quantum Kerr learning[J]. Machine Learning: Science and Technology, 2023, 4(2): 025003.

[3] Wang X, Liu J, Liu T, et al. Symmetric pruning in quantum neural networks[J]. arXiv preprint arXiv:2208.14057, 2022.

[4] Nakaji K, Tezuka H, Yamamoto N. Quantum-enhanced neural networks in the neural tangent kernel framework[J]. arXiv preprint arXiv:2109.03786, 2021.

[5] Shirai N, Kubo K, Mitarai K, et al. Quantum tangent kernel[J]. arXiv preprint arXiv:2111.02951, 2021.

[6] Li L, Fan M, Coram M, et al. Quantum optimization with a novel Gibbs objective function and ansatz architecture search[J]. Physical Review Research, 2020, 2(2): 023074.

[7] Zhang S X, Hsieh C Y, Zhang S, et al. Differentiable quantum architecture search[J]. Quantum Science and Technology, 2022, 7(4): 045023.

[8] Ostaszewski M, Trenkwalder L M, Masarczyk W, et al. Reinforcement learning for optimization of variational quantum circuit architectures[J]. Advances in Neural Information Processing Systems, 2021, 34: 18182-18194.

[9] Wu W, Yan G, Lu X, et al. QuantumDARTS: Differentiable Quantum Architecture Search for Variational Quantum Algorithms. ICML, 2023.

[10] Lu X, Pan K, Yan G, et al. QAS-Bench: Rethinking Quantum Architecture Search and A Benchmark. ICML, 2023.

[11] Jerbi S, Fiderer L J, Poulsen Nautrup H, et al. Quantum machine learning beyond kernel methods[J]. Nature Communications, 2023, 14(1): 517.

[12] Zhang S X, Hsieh C Y, Zhang S, et al. Neural predictor based quantum architecture search[J]. Machine Learning: Science and Technology, 2021, 2(4): 045027.

Thanks to the reviewer FSEH for providing valuable suggestions. We will now respond to them one by one.

Q1: Firstly, the quantum kernel,... should go beyond empirical observations.

A1: Thanks for your comment. We kindly reminder reviewer that Quantum Neural Tangents Kernel (QNTK) [1] is used to analyse dynamic of Quantum Neural Networks (QNNs), and investigate how the QNNs converge around the global minimum. And relevant theoretical results only support on ground energy estimation [2-4]. The provable perfect classification with QNTK is still an open question. On the other hand, compared to QNNs, quantum kernel method has the advantages that it does not require gradient-descent optimization and has theoretical simplicity [5]. This is also one of the motivations for exploring the quantum kernel in this paper.

Currently, the field of Quantum Architecture Search (QAS) primarily emphasizes empirical studies. For example, Refs. [6,7] employs QAS to address combinatorial optimization. Paper [8] utilizes QAS to chemistry. And these studies have made a huge difference to the quantum machine learning.

However, demonstrating provable advantages of quantum kernels on real-world problems is also a sought-after goal within the field and can serve as a direction for our future work.

Q2: Furthermore, the reviewers maintain ... immediate need to construct a kernel matrix.

A2: Thanks for your comment. We will address your concerns one by one.

1. Proposed quantum kernel still falls within the scope of QNN We would like to kindly remind you once again that our method is adaptable to various quantum devices. When these devices undergo upgrades (e.g., the number of qubits increases, the noise decreases), the resulting kernels often become difficult to simulate classically. In such cases, the differences between quantum kernels and QNN (Quantum Neural Network) become even more pronounced.

To better address the reviewer’s concern. We have conduct relevant experiments on the Tailored CC and Synthetic dataset based on the code provided in paper [11]. Detailed parameters are as follows, $N=5, p=5, L_0=3$, epoch=10. The results are shown in table below.

The results show that there is a significant performance gap between the quantum kernel and QNN.(e.g., 66.67% vs 55.00% on Tailored MNIST).

2. Kernel Target Alignment (KTA) is redundant We would like to kindly clarify that we did not mention using KTA to compute the kernel matrix. Instead, the computation of KTA requires the kernel matrix as a prerequisite. Our contribution lies in using KTA as a replacement for train accuracy to evaluate the performance of the kernels. This significantly reduces the time complexity of evaluating the kernels. Furthermore, as mentioned in our response to question 1, the quantum kernel does not require gradient-based optimization. This, compared to QNN, can save training time, which is another advantage. Since the training of QNN often takes an enormous amount of time and resources [12]. For example, we tested the time required for training QNN based on the code provided by the paper [11]. We set $N=5, p=5$, batch_size=64, and test on 10,000 samples and the relationship between training time and the number of parameters can be seen from the table below. We observed that the training time is directly proportional to the number of parameters. Furthermore, even with only 225 parameters (much smaller than the number of parameters in classical neural networks), training one epoch takes close to 1 hour.

The construction of the kernel matrix occurs during the data collection stage, where the kernel matrix is computed to evaluate the performance of the kernel based on KTA. This KTA value is then used as a label for training. Regarding your statement that the quantum circuit has already generated an explicit quantum feature map, but its corresponding kernel is implicit, it is important to note that evaluating the performance of a feature map alone is not sufficient as it is data-dependent. Therefore, we need to compute the kernel based on the feature map and the data in order to assess the performance of the feature map on a given dataset. Thus, computing the kernel matrix is essential.