Classical Verification of Quantum Learning

Cette présentation aborde le problème de la vérification classique de l’apprentissage quantique. Matthias Caro introduit d’abord le cadre de l’apprentissage agnostique, où l’on cherche à approximer une fonction inconnue avec une classe de modèles donnée. Il rappelle l’importance de l’analyse de Fourier pour les fonctions booléennes et comment elle permet d’apprendre certaines classes comme les parités ou les fonctions à spectre creux. Le cœur du travail est la définition d’un nouveau type de données quantiques appelées « mixture-of-superpositions » : au lieu de fournir des états superposés purs correspondant à une fonction déterministe, l’oracle tire d’abord une fonction selon la distribution inconnue, puis prépare la superposition associée. Ce modèle généralise les exemples superposés classiques tout en restant compatible avec la distribution agnostique. L’orateur montre ensuite comment, à partir de quelques copies de ces états, on peut approximer efficacement le spectre de Fourier de la fonction de label conditionnel. Cette approximation est utilisée pour construire des algorithmes d’apprentissage pour des problèmes comme les parités et les fonctions à spectre creux, qui sont inaccessibles aux apprenants purement classiques. Enfin, il présente un protocole de vérification interactive : un vérificateur classique, muni d’exemples aléatoires ou de requêtes statistiques, peut déléguer la tâche d’apprentissage à un prouveur quantique non fiable et vérifier efficacement le résultat. Les résultats montrent que les avantages de l’apprentissage quantique peuvent être exploités de manière fiable et vérifiable, tout en soulignant que ces avantages ne sont pas sans limites : dans certains scénarios, les exemples quantiques n’apportent pas d’amélioration de la complexité d’échantillonnage par rapport aux données classiques.