On classical advice, sampling advise and complexity assumptions for learning separations
<|reference_start|>On classical advice, sampling advise and complexity assumptions for learning separations: In this paper, we prove the equivalence between sampling advice, i.e., advice in the form of a training set, and classical advice. Specifically, our main result demonstrates that BPP/samp is equal to P/poly. Additionally, we delve into the analysis of these relationships under the constraint of a fixed distribution. Notably, we show that under such circumstances, the equality does not hold. This result remains valid when considering quantum advice and a quantum generalization of the training set. Finally, leveraging the insights gained from these proofs, we identify sufficient and necessary complexity assumptions for the existence of concept classes that exhibit a quantum learning speed-up in the worst-case scenario, i.e., when accurate results are required for all inputs.<|reference_end|>
@article{pérez-guijarro2024on,
    title={On classical advice, sampling advise and complexity assumptions for
  learning separations},
    author={Jordi P'erez-Guijarro},
    journal={arXiv preprint arXiv:2408.13880},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.13880},
    primaryClass={quant-ph cs.CC}
}