Certified Lower Bounds and Efficient Estimation of Minimum Accuracy in Quantum Kernel Methods
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914217722904576 |
|---|---|
| author | Gonçalves, Demerson N. Fernandes, Tharso D. Cordeiro, Andrias M. M. Lugao, Pedro H. G. Dias, João T. |
| author_facet | Gonçalves, Demerson N. Fernandes, Tharso D. Cordeiro, Andrias M. M. Lugao, Pedro H. G. Dias, João T. |
| contents | The minimum accuracy heuristic evaluates quantum feature maps without requiring full quantum support vector machine (QSVM) training. However, the original formulation is computationally expensive, restricted to balanced datasets, and lacks theoretical backing. This work generalizes the metric to arbitrary binary datasets and formally proves it constitutes a certified lower bound on the optimal empirical accuracy of any linear classifier in the same feature space. Furthermore, we introduce Monte Carlo strategies to efficiently estimate this bound using a random subset of Pauli directions, accompanied by rigorous probabilistic guarantees. These contributions establish minimum accuracy as a scalable, theoretically sound tool for pre-screening feature maps on near-term quantum devices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_20588 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Certified Lower Bounds and Efficient Estimation of Minimum Accuracy in Quantum Kernel Methods Gonçalves, Demerson N. Fernandes, Tharso D. Cordeiro, Andrias M. M. Lugao, Pedro H. G. Dias, João T. Quantum Physics Data Structures and Algorithms The minimum accuracy heuristic evaluates quantum feature maps without requiring full quantum support vector machine (QSVM) training. However, the original formulation is computationally expensive, restricted to balanced datasets, and lacks theoretical backing. This work generalizes the metric to arbitrary binary datasets and formally proves it constitutes a certified lower bound on the optimal empirical accuracy of any linear classifier in the same feature space. Furthermore, we introduce Monte Carlo strategies to efficiently estimate this bound using a random subset of Pauli directions, accompanied by rigorous probabilistic guarantees. These contributions establish minimum accuracy as a scalable, theoretically sound tool for pre-screening feature maps on near-term quantum devices. |
| title | Certified Lower Bounds and Efficient Estimation of Minimum Accuracy in Quantum Kernel Methods |
| topic | Quantum Physics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2512.20588 |