Correspondance et solidité de l'essai Qubit

Cette séance de cours couvre les concepts d'exactitude et de solidité dans le contexte du test Qubit, en mettant l'accent sur les algorithmes polynômes probabilistes du temps et des trappes. L'instructeur explique les propriétés de la famille des fonctions, le mécanisme de la trappe et la propriété 2 à 1 du test. La séance de cours se penche sur l'inversion des fonctions, la signification du premier bit et les implications pour les circuits quantiques. Différents lemmas sont présentés pour illustrer les fondements théoriques du test Qubit.