On classical advice, sampling advice and complexity assumptions for learning separations
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916943617851392 |
|---|---|
| author | Pérez-Guijarro, Jordi |
| author_facet | Pérez-Guijarro, Jordi |
| contents | In this paper, we study the relationship between advice in the form of a training set and classical advice. We do this by analyzing the class $\mathsf{BPP/samp}$ and certain variants of it. Specifically, our main result demonstrates that $\mathsf{BPP/samp}$ is a proper subset of the class $\mathsf{P/poly}$, which implies that advice in the form of a training set is strictly weaker than classical advice. This result remains valid when considering quantum advice and a quantum generalization of the training set. Finally, leveraging the insights from our proofs, we identify both sufficient and necessary complexity-theoretic assumptions for the existence of concept classes that exhibit a quantum learning speed-up. We consider both the worst-case setting, where accurate results are required for all inputs, and the average-case setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_13880 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On classical advice, sampling advice and complexity assumptions for learning separations Pérez-Guijarro, Jordi Quantum Physics Computational Complexity In this paper, we study the relationship between advice in the form of a training set and classical advice. We do this by analyzing the class $\mathsf{BPP/samp}$ and certain variants of it. Specifically, our main result demonstrates that $\mathsf{BPP/samp}$ is a proper subset of the class $\mathsf{P/poly}$, which implies that advice in the form of a training set is strictly weaker than classical advice. This result remains valid when considering quantum advice and a quantum generalization of the training set. Finally, leveraging the insights from our proofs, we identify both sufficient and necessary complexity-theoretic assumptions for the existence of concept classes that exhibit a quantum learning speed-up. We consider both the worst-case setting, where accurate results are required for all inputs, and the average-case setting. |
| title | On classical advice, sampling advice and complexity assumptions for learning separations |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2408.13880 |