On Adaptivity in Quantum Testing
Abstract
Can adaptive strategies outperform non-adaptive ones for quantum hypothesis selection? We exhibit problems where adaptive strategies provably reduce the number of required samples by a factor four in the worst case, and possibly more when the actual difficulty of the problem makes it possible. In addition, we exhibit specific hypotheses classes for which there is a provable polynomial separation between adaptive and non-adaptive strategies -- a specificity of the quantum framework that does not appear in classical testing.
Cite
Text
Fawzi et al. "On Adaptivity in Quantum Testing." Transactions on Machine Learning Research, 2023.Markdown
[Fawzi et al. "On Adaptivity in Quantum Testing." Transactions on Machine Learning Research, 2023.](https://mlanthology.org/tmlr/2023/fawzi2023tmlr-adaptivity/)BibTeX
@article{fawzi2023tmlr-adaptivity,
title = {{On Adaptivity in Quantum Testing}},
author = {Fawzi, Omar and Flammarion, Nicolas and Garivier, Aurélien and Oufkir, Aadil},
journal = {Transactions on Machine Learning Research},
year = {2023},
url = {https://mlanthology.org/tmlr/2023/fawzi2023tmlr-adaptivity/}
}