J'ai récemment rencontré un article de Coudron et Yuen sur l'expansion aléatoire à l'aide d'appareils quantiques. Le résultat principal du travail est qu'il est possible de générer un caractère aléatoire "infini" à partir d'un nombre constant de sources (c'est-à-dire que le nombre de bits aléatoires générés ne dépend que du nombre de tours du protocole et non du nombre de sources ).
Naïvement, cela me semble que le résultat permet la dérandomisation de tout algorithme randomisé avec des sources quantiques, et impliquerait une sorte de confinement des classes de complexité randomisées à l'intérieur d'une classe quantique correspondante.
Mais je ne comprends pas vraiment la théorie de l'information quantique, et je suis sûr qu'il manque de nombreuses subtilités. Sans compter que si de telles affirmations étaient possibles, les auteurs l'auraient fait. Ma question est donc:
L'existence d'une "expansion infinie du caractère aléatoire" telle que décrite dans l'article (et tous les travaux connexes) implique-t-elle une sorte d'énoncés de dérandomisation pour les classes de complexité aléatoires? Et si non, pourquoi pas ?
Mise à jour: J'ai été signalé à cet excellent aperçu de haut niveau de la région et du document ci-dessus par Scott Aaronson. Malheureusement, je suis toujours confus :).
la source
Réponses:
C'est une excellente question, Suresh!
Notre résultat de l' expansion de l' aléatoire ne pas implique aucun résultat théorétique de la complexité. Voici une façon de comprendre le résultat: nous pensons que la mécanique quantique régit le monde, et selon cette hypothèse, il existe des dispositifs quantiques qui génèrent un véritable, vrai, aléatoire de la théorie de l'information.
Cependant, imaginez que vous vous méfiez de ces boîtes qui prétendent faire ce truc quantique chancelant et générer du hasard (pour certains, cela peut ne pas prendre trop d'imagination). Vous ne voulez pas traiter les qubits. Tout ce que vous comprenez, ce sont des chaînes de bits classiques.
L'expansion aléatoire est un protocole où vous, en tant que vérificateur classique, pouvez interagir avec un tas de boîtes noires (pensez-y comme des prouveurs non communicants ), et après avoir exécuté un protocole avec ces boîtes noires, vous avez certifié que leurs sorties contiennent entropie très élevée - si les étalons passent. De plus, la quantité d'aléatoire avec laquelle vous avez commencé est bien inférieure à l'entropie de sortie que vous avez certifiée.
En d'autres termes, c'est une preuve interactive pour la génération aléatoire.
Ainsi, le seul aspect de "dérandomisation" de celui-ci est de faire valoir que le protocole lui-même nécessite un petit caractère aléatoire au démarrage. Mais le résultat est très dérandomisé: le résultat produit par les boîtes est le vrai hasard, pas le pseudo-aléatoire (c'est-à-dire pas d'hypothèses de calcul).
la source