On Adaptivity in Quantum Testing

Omar Fawzi (1, 2) , Nicolas Flammarion (3) , Aurélien Garivier (4, 5, 1) , Aadil Oufkir (2)

1 ENS de Lyon - École normale supérieure de Lyon
2 QINFO - Traitement optimal de l'information avec des dispositifs quantiques
3 EPFL - Ecole Polytechnique Fédérale de Lausanne
4 UMPA-ENSL - Unité de Mathématiques Pures et Appliquées
5 MC2 - Modèles de calcul, Complexité, Combinatoire

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.

Domains: Data Structures and Algorithms [cs.DS]

Omar Fawzi, Nicolas Flammarion, Aurélien Garivier, Aadil Oufkir. On Adaptivity in Quantum Testing. Transactions on Machine Learning Research Journal, 2023, pp.1-33. ⟨hal-04107265⟩