Towards understanding the power of quantum kernels in the NISQ era

Xinbiao Wang, Yuxuan Du, Yong Luo, Dacheng Tao

Abstract: A key problem in the field of quantum computing is understanding whether quantum machine learning (QML) models implemented on noisy intermediate-scale quantum (NISQ) machines can achieve quantum advantages. Recently, Huang et al. [Nat Commun 12, 2631] partially answered this question by the lens of quantum kernel learning. Namely, they exhibited that quantum kernels can learn specific datasets with lower generalization error over the optimal classical kernel methods. However, most of their results are established on the ideal setting and ignore the caveats of near-term quantum machines. To this end, a crucial open question is: does the power of quantum kernels still hold under the NISQ setting? In this study, we fill this knowledge gap by exploiting the power of quantum kernels when the quantum system noise and sample error are considered. Concretely, we first prove that the advantage of quantum kernels is vanished for large size of datasets, few number of measurements, and large system noise. With the aim of preserving the superiority of quantum kernels in the NISQ era, we further devise an effective method via indefinite kernel learning. Numerical simulations accord with our theoretical results. Our work provides theoretical guidance of exploring advanced quantum kernels to attain quantum advantages on NISQ devices.

Introduction

This research, published in Quantum (2021), provides a critical reality check for the field of Quantum Machine Learning (QML). While theoretical proofs of "quantum advantage" often rely on perfect, noiseless hardware, this study dives into the messy reality of the Noisy Intermediate-Scale Quantum (NISQ) era to determine if quantum kernels can maintain their theoretical edge.

The NISQ Challenge: Noise and Sampling Errors

Recent breakthroughs have demonstrated that quantum kernels can achieve lower generalization errors than classical kernels for specific datasets. However, these proofs typically assume an "ideal" setting with zero noise and an infinite number of measurements. In practice, NISQ devices are plagued by system noise (decoherence) and sampling error (finite measurements).

Figure 1: Conceptual framework comparing classical feature spaces and kernels with quantum feature spaces and kernels.

These factors do more than just slow down computations; they can fundamentally break the mathematical properties of a kernel. A valid kernel must be "positive semi-definite" (PSD), but noise can transform it into an "indefinite" kernel, rendering standard machine learning algorithms invalid. The authors investigate whether the power of quantum kernels holds under these noisy, finite conditions.

Methodology and Mitigation Strategies

The authors address these challenges through a combination of rigorous theory and numerical simulation. They derived a new generalization error bound that explicitly accounts for depolarization noise ($p$) and the number of measurement shots ($m$).

To restore the mathematical validity of "broken" noisy kernel matrices, they employed three spectral transformation techniques from classical literature:

  • Clipping: Setting all negative eigenvalues of the kernel matrix to zero.
  • Flipping: Taking the absolute value of negative eigenvalues.
  • Shifting: Adding a constant to the diagonal of the matrix to push all eigenvalues into the positive range.

Numerical simulations were conducted using the Fashion-MNIST dataset, reduced via PCA to match qubit counts ($N=2$ or $N=8$), and reassigned labels based on "geometric difference" to ensure a theoretical quantum advantage was possible.

Key Insights: The "More Data" Paradox

A significant finding is the "More Data" Paradox. In classical ML, more data ($n$) typically improves generalization. However, the authors prove that for noisy quantum kernels, the error bound contains a term proportional to $n$. As the dataset grows, noise and estimation errors can overwhelm the learning process, causing accuracy to decline. To maintain a competitive edge, the number of measurements ($m$) must scale roughly with the cube of the dataset size ($n^3$), a high demand for current hardware.

Results and Hardware Validation

Applying spectral transformations improved the performance of noisy quantum kernels by up to 14%. Among the methods, "Shifting" the eigenvalues proved most effective at preserving relative similarities between data points while restoring the kernel's mathematical validity.

Figure 4: Accuracy vs. number of measurements for different indefinite kernel learning methods (Nearest, Clip, Flip, Shift) across varying noise levels and dataset sizes.

Even with noise, quantum kernels could outperform optimized RBF kernels, provided the noise was kept low (e.g., $\tilde{p} < 0.05$) and the measurement count was sufficient ($m > 500$). Simulations using noise models from real hardware (IBMQ-Melbourne) confirmed that these calibration methods are essential for running QML tasks on current devices.

Conclusion

By providing a mathematical map of where quantum advantage persists in the presence of noise, this work serves as a practical guide for researchers. While limitations remain—such as the focus on depolarization noise and the scalability of simulations beyond 8 qubits—this research establishes a foundation for achieving quantum advantages on NISQ devices through advanced kernel mitigation strategies.

Summary updated

Abstract

A key problem in the field of quantum computing is understanding whether quantum machine learning (QML) models implemented on noisy intermediate-scale quantum (NISQ) machines can achieve quantum advantages. Recently, Huang et al. [Nat Commun 12, 2631] partially answered this question by the lens of quantum kernel learning. Namely, they exhibited that quantum kernels can learn specific datasets with lower generalization error over the optimal classical kernel methods. However, most of their results are established on the ideal setting and ignore the caveats of near-term quantum machines. To this end, a crucial open question is: does the power of quantum kernels still hold under the NISQ setting? In this study, we fill this knowledge gap by exploiting the power of quantum kernels when the quantum system noise and sample error are considered. Concretely, we first prove that the advantage of quantum kernels is vanished for large size of datasets, few number of measurements, and large system noise. With the aim of preserving the superiority of quantum kernels in the NISQ era, we further devise an effective method via indefinite kernel learning. Numerical simulations accord with our theoretical results. Our work provides theoretical guidance of exploring advanced quantum kernels to attain quantum advantages on NISQ devices.
BibTeX
@article{wang2021towards,
  author = {Xinbiao Wang and Yuxuan Du and Yong Luo and Dacheng Tao},
  title = {{Towards understanding the power of quantum kernels in the NISQ era}},
  journal = {Quantum},
  year = {2021},
  doi = {10.22331/q-2021-08-30-531},
}
Figure