Limites théoriques de la complexité du calcul quantique délégué aveugle.

Résumé Les protocoles de délégation aveugle permettent à un client de déléguer un calcul à un serveur de sorte que ce dernier ne sache rien de l'entrée du calcul, hormis sa taille. Pour le cas spécifique du calcul quantique, nous savons que les protocoles de délégation aveugle peuvent atteindre la sécurité théorique de l'information. Dans cet article, nous prouvons, à condition que certaines conjectures de la théorie de la complexité soient vraies, que la puissance des protocoles de délégation aveugle sécurisés sur le plan de l'information pour le calcul quantique (protocoles ITS-BQC) est limitée de plusieurs façons. Dans la première partie de notre article, nous donnons quelques indications sur le fait qu'il est peu probable que des protocoles ITS-BQC pour la délégation de calculs $\sf BQP$ dans lesquels le client et le serveur n'interagissent que classiquement existent. Nous montrons d'abord que l'existence d'un tel protocole avec $O(n^d)$ bits de communication classique implique que $\mathsf{BQP} \sous-ensemble \mathsf{MA/O(n^d)}$. Nous conjecturons que ce confinement est improbable en fournissant un oracle par rapport auquel $\mathsf{BQP} \not\sous-ensemble \mathsf{MA/O(n^d)}$. Nous montrons ensuite que si un protocole ITS-BQC existe avec une communication classique polynomiale et qui permet au client de déléguer les problèmes d'échantillonnage quantique, alors il existe des circuits non-uniformes de taille $2^{n - \mathsf{\Omega}(n/log(n))}$, effectuant des requêtes de taille polynomiale à un oracle $\sf NP^{NP}$, pour calculer la permanente d'une matrice $n \times n$. La deuxième partie de notre article concerne les protocoles ITS-BQC dans lesquels le client et le serveur s'engagent dans un tour de communication quantique et échangent ensuite un nombre polynomial de messages classiques. Tout d'abord, nous fournissons une limite supérieure théorique de complexité sur les types de fonctions qui pourraient être déléguées dans un tel protocole, à savoir $\mathsf{QCMA/qpoly \cap coQCMA/qpoly}$. Ensuite, nous montrons que l'existence d'un tel protocole pour déléguer les fonctions difficiles $\mathsf{NP}$ implique $\mathsf{coNP^{NP^{NP}}$.} \subseteq \mathsf{NP^{NP^{PromesseQMA}}$.