KASHEFI Elham

Pas de résumé disponible.

Le calcul quantique multipartite (MPQC) a attiré beaucoup d'attention comme une application potentielle pour les réseaux quantiques grâce à sa capacité à préserver la confidentialité et l'intégrité des calculs de grande valeur qu'ils permettraient. Contribuant aux derniers défis dans ce domaine, nous présentons un protocole composable atteignant l'aveuglement et la vérifiabilité même dans le cas d'un seul client honnête. La sécurité de notre protocole est réduite, d'une manière sûre sur le plan de la théorie de l'information, à celle d'un calcul multipartite sécurisé (SMPC) composable classique utilisé pour coordonner les différentes parties. Notre schéma fournit donc une mise à niveau statistiquement sûre d'un tel schéma classique à un schéma quantique avec le même niveau de sécurité. En outre, (i) les clients peuvent déléguer leur calcul à un puissant serveur entièrement tolérant aux pannes et n'ont besoin d'effectuer que des opérations à un seul qubit pour libérer tout le potentiel du calcul quantique multipartite. (ii) la quantité de communication quantique avec le serveur est réduite à l'envoi d'états quantiques au début du calcul et à la réception des états de sortie à la fin, ce qui est optimal et supprime la nécessité d'une communication quantique interactive. et (iii) il a une faible surcharge constante de qubits multiplicatifs par rapport au protocole délégué à un seul client sur lequel il est construit. Le principal ingrédient technique de notre article est le bootstraping de la construction MPQC par Double Blind Quantum Computation, une nouvelle ressource composable pour le calcul quantique multipartite aveugle, qui démontre le fait surprenant que le protocole complet ne nécessite pas la vérifiabilité de tous les composants pour atteindre la sécurité.

L'application et l'analyse de la technique Cut-and-Choose dans les protocoles sécurisés contre les adversaires quantiques n'est pas une transposition directe du cas classique, entre autres en raison de la difficulté d'utiliser le rembobinage dans le domaine quantique. Nous introduisons une technique de calcul quantique "Cut-and-Choose" (QC-CC) qui est une généralisation de la technique classique "Cut-and-Choose" afin de construire des protocoles quantiques sécurisés contre des adversaires cachés quantiques. De tels adversaires peuvent dévier arbitrairement, à condition que leur déviation ne soit pas détectée. En tant qu'application du QC-CC, nous donnons un protocole pour effectuer de manière sécurisée un calcul quantique à deux parties avec une entrée/sortie classique. Nous utilisons comme base le calcul quantique délégué sécurisé (Broadbent et al 2009), et en particulier le calcul quantique brouillé de (Kashefi et al 2016) qui est sécurisé contre seulement un faible adversaire spécieux, défini dans (Dupuis et al 2010). Une propriété unique de ces protocoles est la séparation entre les communications classiques et quantiques et l'asymétrie entre le client et le serveur, ce qui nous permet de contourner les problèmes de rembobinage quantique. Cela ouvre la perspective d'utiliser le QC-CC à d'autres protocoles quantiques avec cette séparation. Dans notre preuve de sécurité, nous adaptons et utilisons (à différentes parties) deux techniques de rembobinage quantique, à savoir le rembobinage oblivious q de Watrous (Watrous 2009) et le rembobinage special q de Unruh (Unruh 2012). Notre protocole réalise la même fonctionnalité que dans les travaux précédents (par exemple, Dupuis et al 2012), cependant l'utilisation de la technique QC-CC sur le protocole de (Kashefi et al 2016) conduit aux améliorations clés suivantes : (i) seule une communication quantique unidirectionnelle hors ligne est nécessaire, (ii) seule une partie (serveur) doit avoir des capacités technologiques quantiques impliquées, (iii) seules des primitives cryptographiques supplémentaires minimales sont nécessaires, à savoir un transfert oblivious pour chaque bit d'entrée et des engagements quantiques sûrs.

Le calcul sécurisé à deux parties considère le problème de deux parties calculant une fonction conjointe de leurs entrées privées sans rien révéler au-delà de la sortie du calcul. Dans ce travail, nous faisons les premiers pas vers la compréhension de la situation dans laquelle les deux parties veulent évaluer une fonction quantique conjointe tout en utilisant uniquement un canal classique entre elles. Notre premier résultat indique qu'il est en général impossible de réaliser une fonctionnalité quantique à deux parties contre des adversaires malveillants avec une simulation en boîte noire, en se basant uniquement sur des canaux classiques. Le résultat négatif découle de la réduction de l'existence d'un simulateur de boîte noire à un extracteur de preuve classique de connaissance quantique, ce qui conduit à son tour à la violation du non-clonage quantique. Ensuite, nous introduisons la notion d'évaluation de fonction quantique oblivious (OQFE). Une OQFE est une primitive cryptographique quantique à deux parties avec une partie entièrement classique (Alice) dont l'entrée est (une description classique d'une) unité quantique, $U$, et une partie quantique (Bob) dont l'entrée est un état quantique, $\psi$. En particulier, Alice reçoit une sortie classique correspondant à la mesure de $U(\psi)$ tandis que Bob ne reçoit aucune sortie. Dans OQFE, Bob reste inconscient de l'entrée d'Alice, tandis qu'Alice n'apprend rien de plus sur $\psi$ que ce qui peut être appris de la sortie. Nous présentons deux constructions, une sécurisée contre les parties semi-honnêtes et l'autre contre les parties malveillantes. En raison du résultat no-go mentionné ci-dessus, nous considérons ce qui est sans doute la meilleure notion possible pouvant être obtenue dans notre modèle concernant les adversaires malveillants : la sécurité de simulation unilatérale. Notre protocole repose sur l'hypothèse d'OWFs à trappe homomorphique injective, qui à son tour repose sur le problème LWE. Par conséquent, nous présentons une première construction, simple et modulaire, du calcul bilatéral quantique unilatéral et du transfert oblivious quantique sur des réseaux classiques.

La cryptanalyse des systèmes cryptographiques quantiques standard consiste généralement à trouver des stratégies d'attaque optimales pour l'adversaire sur les protocoles sous-jacents. Le principe de base de la modélisation des attaques quantiques se réduit dans de nombreux cas à la capacité de l'adversaire à cloner des états quantiques inconnus, ce qui facilite l'extraction de certaines informations secrètes significatives. Les stratégies d'attaque optimales explicites nécessitent généralement des ressources de calcul élevées en raison de la grande profondeur des circuits ou, dans de nombreux cas, sont inconnues. Dans ce travail, nous proposons le clonage quantique variationnel (VQC), un algorithme de cryptanalyse basé sur l'apprentissage machine quantique qui permet à un adversaire d'obtenir des stratégies de clonage optimales (approximatives) avec des circuits quantiques de faible profondeur, formés à l'aide de techniques hybrides classiques-quantiques. L'algorithme contient des fonctions de coût significatives sur le plan opérationnel avec des garanties théoriques, un apprentissage de la structure des circuits quantiques et une optimisation basée sur la descente de gradient. Notre approche permet la découverte de bout en bout de circuits quantiques efficaces sur le plan matériel pour cloner des familles spécifiques d'états quantiques, ce qui conduit à une amélioration des fidélités de clonage lorsqu'elles sont mises en œuvre sur du matériel quantique : la puce Aspen de Rigetti. Enfin, nous relions ces résultats à des primitives cryptographiques quantiques, en particulier le tirage à pile ou face quantique. Nous dérivons des attaques sur deux protocoles à titre d'exemple, basées sur le clonage quantique et facilitées par VQC. Par conséquent, notre algorithme peut améliorer les attaques à court terme sur ces protocoles, en utilisant le clonage quantique approximatif comme ressource.

La modélisation générative est devenue un cas d'utilisation prometteur pour les ordinateurs quantiques à court terme. En particulier, en raison de la nature fondamentalement probabiliste de la mécanique quantique, les ordinateurs quantiques modélisent et apprennent naturellement des distributions de probabilité, peut-être plus efficacement que ce qui peut être réalisé classiquement. La machine de Born est un exemple d'un tel modèle, facile à mettre en œuvre sur les ordinateurs quantiques à court terme. Cependant, dans sa forme originale, la machine de Born ne représente naturellement que des distributions discrètes. Comme les distributions de probabilité de nature continue sont courantes dans le monde, il est essentiel de disposer d'un modèle capable de les représenter efficacement. Certaines propositions ont été faites dans la littérature pour compléter la machine de Born discrète avec des fonctionnalités supplémentaires afin d'apprendre plus facilement des distributions continues, cependant, toutes augmentent invariablement les ressources nécessaires dans une certaine mesure. Dans ce travail, nous présentons la machine de Born à variables continues, construite sur l'architecture alternative de l'informatique quantique à variables continues, qui est beaucoup plus appropriée pour modéliser de telles distributions de façon à minimiser les ressources. Nous fournissons des résultats numériques indiquant la capacité du modèle à apprendre des distributions continues tant quantiques que classiques, y compris en présence de bruit.

Trouver un cas d'utilisation concret pour les ordinateurs quantiques à court terme est encore une question ouverte, l'apprentissage automatique étant généralement présenté comme l'un des premiers domaines qui seront touchés par les technologies quantiques. Dans ce travail, nous étudions et comparons les capacités des modèles quantiques et classiques pour la modélisation générative dans l'apprentissage automatique. Nous utilisons un ensemble de données financières du monde réel composé de paires de devises corrélées et comparons deux modèles dans leur capacité à apprendre la distribution résultante - une machine de Boltzmann restreinte et une machine de Born à circuits quantiques. Nous fournissons des résultats numériques détaillés indiquant que la machine de Born simulée est toujours au moins aussi performante que la machine de Boltzmann dans cette tâche, et qu'elle démontre une performance supérieure à mesure que le modèle évolue. Nous réalisons des expériences sur des puces quantiques simulées et physiques à l'aide de la plateforme Rigetti forest, et nous sommes également en mesure d'entraîner partiellement la plus grande instance à ce jour d'une machine de Born à circuit quantique sur du matériel quantique. Enfin, en étudiant la capacité d'intrication des machines de Born d'entraînement, nous constatons que l'intrication joue généralement un rôle dans les instances du problème qui présentent un avantage par rapport à la machine de Boltzmann.

Nous dérivons un cadre général pour un schéma de métrologie quantique où les sondes quantiques sont échangées via un canal quantique non sécurisé. Nous construisons deux protocoles pour cette tâche qui offrent un compromis entre la difficulté d'implémentation et l'efficacité. Nous montrons que, pour les deux protocoles, un espion malveillant ne peut accéder à aucune information concernant le paramètre inconnu. Nous dérivons également des inégalités générales concernant la façon dont l'incertitude dans un état de ressource pour la métrologie quantique peut biaiser l'estimation et la précision. À partir de là, nous établissons un lien entre l'efficacité de la partie cryptographique du protocole et l'efficacité du schéma de métrologie avec un état de ressource de sonde (potentiellement) malveillant.

Récemment, des progrès importants ont été réalisés en vue de la mise en place de l'internet quantique pour permettre un large éventail d'applications qui seraient hors de portée de l'internet classique. La plupart de ces applications, comme le calcul quantique délégué, nécessitent l'exécution d'un protocole d'identification sécurisé entre une partie à faible ressource et une partie à haute ressource pour assurer une communication sécurisée. Les fonctions physiques inclinables (PUF) se sont révélées être des solutions matérielles efficaces en termes de ressources pour fournir des schémas d'identification sécurisés dans des contextes classiques et quantiques. Dans ce travail, nous proposons deux protocoles d'identification basés sur des PUF quantiques (qPUF) tels que définis par Arapinis et al. Dans le premier protocole, la partie à faibles ressources souhaite prouver son identité à la partie à fortes ressources et dans le second protocole, c'est l'inverse. Contrairement aux protocoles d'identification existants basés sur des PUF à lecture quantique qui reposent sur la sécurité contre une famille spécifique d'attaques, nos protocoles fournissent une sécurité exponentielle prouvable contre tout adversaire à temps polynomial quantique (QPT) avec des parties à ressources limitées. Nous fournissons une comparaison complète entre les deux protocoles proposés en termes de ressources telles que la mémoire quantique et la capacité de calcul requises dans les deux parties, ainsi que le surdébit de communication entre elles. Une caractéristique remarquable de notre deuxième protocole est l'identification sécurisée d'une partie à ressources élevées en exécutant un algorithme de vérification purement classique. Ceci est réalisé en déléguant des opérations quantiques à la partie à haute ressource et en utilisant les résultats classiques qui en résultent pour l'identification.

La physique quantique a apporté une révolution conceptuelle quant à la nature de notre monde et apporte aujourd’hui une révolution technologique. En effet, l’utilisation de l’information quantique promet des applications surclassant les machines actuelles, dites classiques. La théorie de l’information quantique en variable continue porte sur l’étude des possibilités qu’offre l’encodage de l’information dans des degrés de liberté continus de systèmes quantiques. Mathématiquement, cette théorie étend l’étude de l'information quantique aux états quantiques dans des espaces de Hilbert de dimension infinie. Elle offre des perspectives différentes de l’information quantique en variable discrète et est notamment adaptée à la description des états quantiques de lumière. L’optique quantique est ainsi une plateforme expérimentale naturelle pour développer des applications quantiques en variable continue. La thèse s’articule autour de trois questions principales : d’où provient l’avantage quantique, c est-à-dire la capacité des machines quantiques à surclasser les machines classiques ? Comment s assurer du bon fonctionnement d une machine quantique ? Quels avantages peut-on tirer de l'utilisation de l’information quantique ? Ces trois questions sont au cœur du développement des technologies quantiques, et nous y apportons plusieurs réponses dans le cadre de la théorie de l’information quantique en variable continue et de l’optique quantique linéaire.

Pas de résumé disponible.

Nous considérons un dispositif qui peut être programmé en utilisant des états cohérents de la lumière pour approximer une mesure projective donnée sur un état cohérent d'entrée. Nous fournissons et discutons trois implémentations pratiques de ce dispositif de mesure projective programmable avec une optique linéaire, impliquant seulement des séparateurs de faisceau équilibrés et des détecteurs à seuil de photons uniques. Les trois schémas donnent une approximation optimale de toute mesure projective sur un état cohérent programmé, de manière non destructive. Nous les étendons ensuite au cas où il n'y a aucune hypothèse sur l'état d'entrée. Dans ce contexte, nous montrons que notre schéma permet une vérification efficace d'une source non fiable et sans limites avec seulement des états cohérents locaux, des séparateurs de faisceau équilibrés et des détecteurs à seuil. En exploitant le lien entre les mesures programmables et le test de permutation généralisé, nous montrons, en tant qu'application directe, que nos schémas fournissent une amélioration asymptotiquement quadratique du protocole existant d'empreinte quantique pour approximer la distance euclidienne entre deux vecteurs unitaires.

Les récentes réalisations expérimentales suscitent un intérêt croissant de la part des entreprises qui commencent à ressentir les limites du calcul classique. Cependant, à la lumière des scandales actuels liés à la protection de la vie privée, la disponibilité future de l'informatique quantique par le biais de serveurs accessibles à distance pose des problèmes particuliers : Les clients aux capacités limitées par le calcul quantique veulent que leurs données et leurs algorithmes restent cachés, tout en étant capables de vérifier que leurs calculs sont effectués correctement. La recherche sur la délégation aveugle et vérifiable de l'informatique quantique tente de répondre à cette question. Toutefois, les techniques disponibles souffrent non seulement de frais généraux élevés, mais aussi d'une sensibilité excessive : Lorsqu'elles fonctionnent sur des dispositifs bruyants, les imperfections déclenchent les mêmes mécanismes de détection que les attaques malveillantes, ce qui entraîne l'interruption perpétuelle des calculs. Par conséquent, alors que les ordinateurs quantiques malveillants sont rendus inoffensifs par des protocoles aveugles et vérifiables, le bruit inhérent limite sévèrement leur utilisation. Nous abordons ce problème avec un schéma efficace, robuste, aveugle et vérifiable pour déléguer des calculs quantiques déterministes avec des entrées et des sorties classiques. Nous montrons que : 1) un serveur malveillant peut tricher au maximum avec une probabilité de succès exponentiellement petite. 2) en cas de bruit suffisamment petit, le protocole réussit avec une probabilité exponentiellement proche de 1. 3) l'overhead est à peine un nombre polynomial de répétitions du calcul initial intercalé avec des exécutions de test exigeant les mêmes ressources physiques en termes de mémoire et de portes. 4) la quantité de bruit tolérable, mesurée par la probabilité d'échouer à un essai, peut atteindre 25 % pour certains calculs et sera généralement limitée à 12,5 % lors de l'utilisation d'un état de ressources de graphe planaire. Les points clés sont que la sécurité peut être assurée sans graphe de calcul universel et que, dans notre cadre, la tolérance totale aux pannes n'est pas nécessaire pour amplifier le niveau de confiance de façon exponentielle près de 1.

La démonstration de l'accélération quantique, également appelée suprématie du calcul quantique, c'est-à-dire la capacité des ordinateurs quantiques à surpasser de façon spectaculaire leurs homologues classiques, est une étape importante dans le domaine du calcul quantique. Bien que les expériences d'accélération quantique échappent progressivement au régime de la simulation classique, elles manquent encore de protocoles de vérification efficaces et reposent sur une validation partielle. À cette fin, nous dérivons un protocole efficace pour vérifier, à l'aide de mesures gaussiennes monomodes, les états de sortie d'une grande classe de circuits quantiques à variables continues démontrant l'accélération quantique, y compris les expériences d'échantillonnage de Boson, avec et sans hypothèse i.i.d., permettant ainsi une démonstration convaincante de l'accélération quantique avec le calcul photonique. Au-delà de la démonstration de l'accélération quantique, nos résultats permettent également la certification efficace et fiable d'une grande classe d'états quantiques multimodes à variables continues difficiles à traiter.

Le calcul quantique délégué sécurisé permet à un client faible en calcul d'externaliser un calcul quantique arbitraire à un serveur quantique non fiable, tout en préservant la confidentialité. L'un des candidats prometteurs pour réaliser la délégation classique du calcul quantique est la préparation d'état à distance classique-client ($RSP_{CC}$), où un client prépare à distance un état quantique en utilisant un canal classique. Cependant, la perte de confidentialité encourue en employant $RSP_{CC}$ comme sous-module n'est pas claire. Dans ce travail, nous étudions cette question en utilisant le cadre de la Cryptographie Constructive de Maurer et Renner (ICS'11). Nous identifions d'abord l'objectif de $RSP_{CC}$ comme la construction de ressources RSP idéales à partir de canaux classiques, puis nous révélons les limites de sécurité de l'utilisation de $RSP_{CC}$. Tout d'abord, nous découvrons une relation fondamentale entre la construction de ressources RSP idéales (à partir de canaux classiques) et la tâche de clonage d'états quantiques. Toute ressource RSP idéale construite de manière classique doit laisser échapper au serveur la description classique complète (éventuellement sous une forme codée) de l'état quantique généré, même si nous visons uniquement la sécurité informatique. En conséquence, nous constatons que la réalisation de ressources RSP communes, sans affaiblir drastiquement leurs garanties, est impossible en raison du théorème de non-clonage. Deuxièmement, le résultat ci-dessus n'exclut pas qu'un protocole $RSP_{CC}$ spécifique puisse remplacer le canal quantique au moins dans certains contextes, comme le protocole Universal Blind Quantum Computing (UBQC) de Broadbent et al. (FOCS '09). Cependant, nous montrons que le protocole UBQC résultant ne peut pas maintenir sa sécurité composable prouvée dès que $RSP_{CC}$ est utilisé comme sous-routine. Troisièmement, nous montrons que le remplacement du canal quantique du protocole UBQC ci-dessus par le protocole $RSP_{CC}$ QFactory de Cojocaru et al. (Asiacrypt '19), préserve la sécurité plus faible, basée sur le jeu, de UBQC.

La recherche d'une application des dispositifs quantiques à court terme est très répandue. L'apprentissage par machine quantique est présenté comme une utilisation potentielle de ces dispositifs, en particulier ceux qui sont hors de portée des capacités de simulation des ordinateurs classiques. Dans ce travail, nous étudions une telle application dans la modélisation générative, en nous concentrant sur une classe de circuits quantiques connus sous le nom de machines de Born. Plus précisément, nous définissons un sous-ensemble de cette classe basé sur les Hamiltoniens d'Ising et nous montrons que les circuits rencontrés lors de l'apprentissage basé sur le gradient ne peuvent pas être échantillonnés efficacement de manière classique jusqu'à une erreur multiplicative dans le pire des cas. Nos méthodes d'apprentissage basées sur le gradient utilisent des fonctions de coût connues sous le nom de divergence de Sinkhorn et de divergence de Stein, qui n'ont pas été utilisées auparavant dans l'apprentissage de circuits quantiques basé sur le gradient, et nous introduisons également des noyaux quantiques dans la modélisation générative. Nous montrons que ces méthodes sont plus performantes que la méthode standard précédente, qui utilisait la divergence moyenne maximale (MMD) comme fonction de coût, et ce avec une surcharge minimale. Enfin, nous discutons de la capacité du modèle à apprendre des distributions difficiles et nous fournissons des définitions formelles de la "suprématie de l'apprentissage quantique". Nous illustrons également le travail de cet article en utilisant la modélisation générative pour effectuer la compilation de circuits quantiques.

Une croyance populaire veut que la sécurité des protocoles cryptographiques classiques soit automatiquement rompue si l'Adversaire est autorisé à effectuer des requêtes de superposition et si les joueurs honnêtes sont forcés d'effectuer des actions cohérentes sur des états quantiques. Une autre intuition largement répandue est que l'application de mesures sur les messages échangés suffit à protéger les protocoles contre ces attaques. Cependant, la réalité est beaucoup plus complexe. Les modèles de sécurité traitant des attaques par superposition ne considèrent que la sécurité inconditionnelle. A l'inverse, les modèles de sécurité considérant la sécurité computationnelle supposent que tous les messages supposés classiques sont mesurés, ce qui interdit par construction l'analyse des attaques par superposition. Boneh et Zhandry ont commencé à étudier la sécurité quantique computationnelle pour les primitives classiques dans leur travail séminal à Crypto'13, mais seulement dans le cadre d'une seule partie. À notre connaissance, il n'existe toujours pas de modèle équivalent dans le cadre multipartite. Dans ce travail, nous proposons le premier modèle de sécurité informatique prenant en compte les attaques par superposition pour les protocoles multipartites. Nous montrons que notre nouveau modèle de sécurité est satisfaisable en prouvant la sécurité du protocole bien connu One-Time-Pad et en donnant une attaque sur une variante du tout aussi réputé protocole Yao pour les calculs sécurisés à deux parties. Le post-mortem de cette attaque révèle les points précis d'échec, donnant des résultats très contre-intuitifs : L'ajout d'une communication classique supplémentaire, qui est inoffensive pour la sécurité classique, peut rendre le protocole sujet à des attaques par superposition. Nous utilisons ces nouvelles connaissances pour construire le premier protocole concret de calcul à deux parties sécurisé qui résiste aux attaques par superposition. Nos résultats montrent qu'il n'y a pas de réponse directe à apporter ni aux vulnérabilités des protocoles classiques aux attaques par superposition ni aux contre-mesures adaptées.

Pas de résumé disponible.

La fonctionnalité de qubits secrets aléatoires préparés à distance par des instructions classiques a été présentée dans (Cojocaru et al 2018) comme un moyen de permettre aux parties classiques de participer à des protocoles de calcul et de communication quantiques sécurisés. L'idée est qu'une partie classique (client) demande à une partie quantique (serveur) de générer un qubit du côté du serveur qui est aléatoire, inconnu du serveur mais connu du client. Une telle tâche n'est possible que sous des hypothèses de calcul. Dans cette contribution, nous définissons une primitive plus simple (de base) constituée uniquement d'états BB84, et donnons un protocole qui réalise cette primitive et qui est sécurisé contre l'adversaire le plus fort possible (un serveur malveillant qui dévie arbitrairement). Les fonctions spécifiques utilisées ont été construites sur la base de fonctions unidirectionnelles à trappe connues, de sorte que la sécurité de notre primitive de base est réduite à la dureté du problème de l'apprentissage avec erreurs. Nous présentons ensuite un certain nombre d'extensions, basées sur ce module de base : extension à un ensemble plus large d'états (incluant les états non-Clifford), prise en compte adéquate du cas d'abandon et vérifiabilité au niveau du module. Cette dernière est basée sur "l'auto-testing aveugle", une notion que nous avons introduite, prouvée dans un cadre limité et dont nous avons conjecturé la validité pour le cas le plus général.

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}}$.

En août 2015, le monde de la cryptographie a été secoué par une annonce soudaine et surprenante de l'Agence nationale de sécurité américaine NSA concernant des plans de transition vers des algorithmes post-quantiques. Depuis cette annonce, la cryptographie post-quantique est devenue un sujet de premier intérêt pour plusieurs organismes de normalisation. La transition des algorithmes à clé publique actuellement déployés vers des algorithmes post-quantiques s'est avérée être un défi à de nombreux égards. En particulier, le problème de l'évaluation de la sécurité quantique de ces cryptosystèmes post-quantiques reste largement ouvert. Bien sûr, cette question est d'une importance capitale dans le processus de normalisation des cryptosystèmes post-quantiques. Dans cet article, nous examinons la sécurité quantique du problème de la résolution d'un système d'équations quadratiques multivariées booléennes de $m$ dans $n$ variables} (\MQb), un problème central de la cryptographie post-quantique. Lorsque $n=m$, sous une hypothèse algébrique naturelle, nous présentons un algorithme quantique de Las-Vegas résolvant \MQb{} qui nécessite l'évaluation, en moyenne, de $O(2^{0.462n})$ portes quantiques. À notre connaissance, il s'agit de l'algorithme le plus rapide pour résoudre \MQb{}.

La recherche d'une application des dispositifs quantiques à court terme est très répandue. L'apprentissage par machine quantique est présenté comme une utilisation potentielle de ces dispositifs, en particulier ceux qui sont hors de portée des capacités de simulation des ordinateurs classiques. Dans ce travail, nous proposons un modèle génératif d'apprentissage de machine quantique, appelé Ising Born Machine (IBM), dont nous montrons qu'il ne peut pas, dans le pire des cas, et jusqu'à des notions d'erreur appropriées, être simulé efficacement par un dispositif classique. Nous montrons également que cela est valable pour toutes les familles de circuits rencontrées lors de l'apprentissage. En particulier, nous explorons l'apprentissage de circuits quantiques à l'aide de circuits non universels dérivés des hamiltoniens du modèle d'Ising, qui peuvent être mis en œuvre sur des dispositifs quantiques à court terme. Nous proposons deux nouvelles méthodes d'apprentissage pour l'IBM en utilisant les fonctions de coût de la divergence de Stein et de la divergence de Sinkhorn. Nous montrons numériquement, à la fois en utilisant un simulateur dans la plateforme Forest de Rigetti et sur la puce Aspen-1 16Q, que les fonctions de coût que nous suggérons sont plus performantes que le Maximum Mean Discrepancy (MMD), plus communément utilisé pour l'apprentissage différentiable. Nous proposons également une amélioration du MMD en proposant une nouvelle utilisation des noyaux quantiques, dont nous démontrons qu'elle apporte des améliorations par rapport à sa contrepartie classique. Nous discutons du potentiel de ces méthodes pour apprendre des distributions quantiques "dures", un exploit qui démontrerait l'avantage des ordinateurs quantiques sur les ordinateurs classiques, et nous fournissons les premières définitions formelles de ce que nous appelons la "suprématie de l'apprentissage quantique". Enfin, nous proposons une nouvelle vision du domaine de la compilation de circuits quantiques en utilisant IBM pour "imiter" des circuits quantiques cibles en utilisant uniquement des données de sortie classiques.

Alors que la recherche sur la construction d'ordinateurs quantiques évolutifs progresse, il est important de pouvoir certifier leur exactitude. En raison de la difficulté exponentielle de la simulation classique du calcul quantique, la vérification directe par ce moyen échoue. Cependant, nous pouvons simuler classiquement des calculs quantiques à petite échelle et, par conséquent, nous sommes en mesure de vérifier que les dispositifs se comportent comme prévu dans ce domaine. Cela constitue la première étape vers l'obtention de la confiance dans l'avantage quantique anticipé lorsque nous passons à des échelles qui ne peuvent plus être simulées. Les dispositifs réels ont des restrictions dues à leur architecture et des limitations dues aux imperfections physiques et au bruit. Dans cet article, nous étendons les simulations idéales habituelles en tenant compte de ces effets. Nous fournissons une méthodologie et un cadre général pour construire des simulations qui émulent le système physique. Ces simulations devraient fournir une référence pour les dispositifs réalistes et guider la recherche expérimentale dans la quête de l'avantage quantique. Pour illustrer notre méthodologie, nous donnons des exemples qui impliquent des architectures en réseau et le modèle de bruit du dispositif développé par le Networked Quantum Information Technologies Hub (NQIT). Pour nos simulations, nous utilisons, avec des modifications appropriées, le simulateur classique de Bravyi et Gosset, tandis que les problèmes spécifiques considérés appartiennent à la classe des temps polynomiaux quantiques instantanés. Cette classe est considérée comme difficile pour les dispositifs de calcul classiques, et est considérée comme un candidat prometteur pour la première démonstration de l'avantage quantique. Nous considérons d'abord une sous-classe de IQP, définie par Bermejo-Vega et al, impliquant des simulateurs quantiques dynamiques bidimensionnels, puis des instances générales de IQP, restreintes à l'architecture de NQIT.

Les dispositifs à variables continues (CV) constituent une plateforme prometteuse pour la démonstration de protocoles d'information quantique à grande échelle. Dans ce cadre, nous définissons un modèle général de calcul quantique basé sur un matériel CV. Il se compose d'états d'entrée dans le vide, d'un ensemble fini de portes - y compris des éléments non gaussiens - et d'une détection homodyne. Nous montrons que ce modèle intègre des codages suffisants pour un calcul quantique universel probabiliste tolérant aux fautes. De plus, nous montrons que ce modèle peut être adapté pour donner des problèmes d'échantillonnage qui ne peuvent pas être simulés efficacement avec un ordinateur classique, à moins que la hiérarchie polynomiale ne s'effondre. Cela nous permet de fournir un paradigme simple pour les expériences à court terme visant à sonder l'avantage quantique reposant sur les états gaussiens, la détection homodyne et une certaine forme d'évolution non gaussienne. Enfin, nous abordons le modèle récemment introduit de l'informatique quantique instantanée dans CV, et nous prouvons que l'énoncé de dureté est robuste par rapport à certaines simplifications expérimentales pertinentes dans la définition de ce modèle.

La contextualité est un comportement non classique que peuvent présenter les systèmes quantiques. Elle est de plus en plus étudiée pour sa relation avec les avantages quantiques sur classiques dans les tâches informatiques. Jusqu'à présent, elle a été largement étudiée dans des scénarios à variables discrètes, où les observables prennent des valeurs dans des ensembles discrets et généralement finis. En pratique, en revanche, les scénarios à variables continues offrent certains des candidats les plus prometteurs pour la mise en œuvre de calculs quantiques et de protocoles informatiques. Nous établissons ici un cadre pour traiter la contextualité dans les scénarios à variables continues. Nous montrons que le théorème de Fine--Abramsky--Brandenburger s'étend à ce cadre, ce qui a pour conséquence importante que la non-localité peut être considérée comme un cas particulier de contextualité, comme dans le cas discret. La fraction contextuelle, une mesure quantifiable de la contextualité qui a une relation précise avec les violations de l'inégalité de Bell et les avantages quantiques, peut également être définie dans ce cadre. On montre qu'il s'agit d'une monotone non croissante par rapport aux opérations classiques qui incluent le binning pour discrétiser les données. Enfin, nous examinons comment la fraction contextuelle peut être formulée comme un programme linéaire infini, et calculée avec une précision croissante en utilisant des approximations de programmation semi-définie.

Alors que la recherche sur la construction d'ordinateurs quantiques évolutifs progresse, il est important de pouvoir certifier leur exactitude. En raison de la difficulté exponentielle de la simulation classique du calcul quantique, la vérification directe par ce moyen échoue. Cependant, nous pouvons simuler classiquement des calculs quantiques à petite échelle et, par conséquent, nous sommes en mesure de vérifier que les dispositifs se comportent comme prévu dans ce domaine. Cela constitue la première étape vers l'obtention de la confiance dans l'avantage quantique anticipé lorsque nous passons à des échelles qui ne peuvent plus être simulées. Les dispositifs réels ont des restrictions dues à leur architecture et des limitations dues aux imperfections physiques et au bruit. Dans cet article, nous étendons les simulations idéales habituelles en tenant compte de ces effets. Nous fournissons une méthodologie et un cadre général pour construire des simulations qui émulent le système physique. Ces simulations devraient fournir une référence pour les dispositifs réalistes et guider la recherche expérimentale dans la quête de l'avantage quantique. Pour illustrer notre méthodologie, nous donnons des exemples qui impliquent des architectures en réseau et le modèle de bruit du dispositif développé par le Networked Quantum Information Technologies Hub (NQIT). Pour nos simulations, nous utilisons, avec des modifications appropriées, le simulateur classique de Bravyi et Gosset, tandis que les problèmes spécifiques considérés appartiennent à la classe du temps polynomial quantique instantané. Cette classe est considérée comme difficile pour les dispositifs de calcul classiques, et est considérée comme un candidat prometteur pour la première démonstration de l'avantage quantique. Nous considérons d'abord une sous-classe de IQP, définie par Bermejo-Vega et al, impliquant des simulateurs quantiques dynamiques bidimensionnels, puis des instances générales de IQP, restreintes à l'architecture de NQIT.

Pas de résumé disponible.

Pas de résumé disponible.

Pas de résumé disponible.

Les fonctions physiques non clonables (PUF) sont des dispositifs physiques au comportement unique qui sont difficiles à cloner. Une variété de schémas PUF ont été considérés dans des études théoriques ainsi que dans des implémentations pratiques de plusieurs primitives de sécurité telles que l'identification et la génération de clés. Récemment, la non-clonabilité inhérente des états quantiques a été exploitée pour définir un analogue quantique (partiel) des PUF classiques (contre des adversaires limités). Il existe également quelques propositions d'implémentations quantiques de PUF optiques classiques. Cependant, aucune de ces tentatives ne fournit une étude complète des fonctions physiques inclinables quantiques (QPUF) avec des outils de cryptographie quantique comme nous le présentons dans cet article. Nous définissons formellement les QPUFs, en encapsulant toutes les exigences des PUFs classiques et en introduisant de nouvelles exigences inhérentes au cadre quantique, comme la testabilité. Nous développons un cadre de sécurité basé sur les jeux quantiques pour notre analyse et définissons une nouvelle classe d'attaques quantiques, appelée attaque générale d'émulation quantique. Cette classe d'attaques exploite les paires défi-réponse valides capturées précédemment pour émuler l'action d'une transformation quantique inconnue sur une nouvelle entrée. Nous concevons une attaque concrète basée sur un algorithme d'émulation quantique existant et l'utilisons pour montrer qu'une famille de primitives cryptographiques quantiques qui reposent sur des transformations unitaires inconnues ne fournissent pas d'infalsifiabilité existentielle alors qu'elles fournissent une infalsifiabilité sélective. Ensuite, nous exprimons nos résultats dans le cas de QPUF comme une transformation unitaire inconnue.

La génération d'un caractère aléatoire certifiable est l'une des applications les plus prometteuses des technologies quantiques. En outre, la non-localité intrinsèque des corrélations quantiques nous permet de certifier le caractère aléatoire d'une manière indépendante du dispositif, c'est-à-dire sans avoir à faire d'hypothèses sur les dispositifs utilisés. Grâce aux travaux de Curchod et al, un seul état pur à deux qubits intriqués peut être utilisé pour produire des quantités arbitraires de caractère aléatoire certifié. Cependant, l'obtention de ce caractère aléatoire est un défi expérimental car elle nécessite un grand nombre de mesures, tant projectives que générales. Motivés par ces difficultés dans le cadre de l'indépendance des dispositifs, nous considérons plutôt le scénario de l'indépendance unilatérale des dispositifs, où certains dispositifs sont fiables et d'autres non, un scénario motivé par les montages expérimentaux asymétriques tels que les réseaux de photons ioniques. Nous montrons comment certains aspects des travaux précédents peuvent être adaptés à ce scénario et fournissons des limites théoriques sur la quantité d'aléatoire qui peut être certifiée. De plus, nous donnons un protocole pour la certification de l'aléatoire sans limite dans ce scénario, et nous fournissons des résultats numériques démontrant le protocole dans le cas idéal. Enfin, nous testons numériquement la possibilité de mettre en œuvre ce schéma sur les technologies quantiques à court terme, en examinant les performances du protocole sur plusieurs plateformes physiques.

Nous présentons d'abord la tomographie d'état quantique hétérodyne, une méthode fiable de certification d'état quantique à variation continue qui donne directement les éléments de la matrice de densité de l'état considéré et les intervalles de confiance analytiques, en utilisant la détection hétérodyne. Cette méthode ne nécessite ni reconstruction mathématique des données, ni binning discret de l'espace d'échantillonnage, et utilise un seul paramètre de mesure gaussien. Au-delà de la tomographie d'état quantique et sans son hypothèse de copies identiques, nous dérivons également un protocole général pour vérifier des états quantiques purs à variables continues avec des mesures gaussiennes contre des adversaires totalement malveillants. En particulier, nous utilisons une réduction de De Finetti pour les systèmes à dimension infinie. Comme application, nous considérons le calcul quantique universel vérifié à variables continues, avec une puissance de calcul limitée aux opérations gaussiennes et une source d'états non gaussiens non fiable. Ces résultats sont obtenus à l'aide d'un nouvel estimateur analytique de la valeur attendue de tout opérateur agissant sur un état quantique à variable continue avec un support limité sur la base de Fock, calculé avec des échantillons provenant de la détection hétérodyne de l'état.

Nous définissons la fonctionnalité de générateur de qubits aléatoires pseudo-secret délégué (PSRQG), où un client classique peut demander la préparation d'une séquence de qubits aléatoires à une partie distante. Leur description classique est inconnue (du point de vue informatique) de toute autre partie (y compris la partie distante qui les prépare) mais connue du client. Nous soulignons la caractéristique unique selon laquelle aucune communication quantique n'est nécessaire pour mettre en œuvre PSRQG. Cela permet aux clients classiques d'exécuter une classe de protocoles de communication quantique avec seulement un canal classique public avec un serveur quantique. Un exemple clé de ce type est le calcul quantique universel aveugle délégué. En utilisant notre fonctionnalité, on peut réaliser un calcul quantique universel délégué vérifiable et sécurisé par un client purement classique (également appelé calcul quantique aveugle vérifiable). Nous donnons un protocole concret (QFactory) mettant en œuvre PSRQG, en utilisant le problème de l'apprentissage par l'erreur pour construire une fonction unidirectionnelle à trappe avec certaines propriétés souhaitées (sécurité quantique, birégularité, résistance aux collisions). Nous prouvons ensuite la sécurité dans le cadre Quantum-Honest-But-Curious et discutons brièvement de l'extension au cas malveillant.

Les avancées récentes de Google, d'IBM et d'un certain nombre de groupes de recherche indiquent que les ordinateurs quantiques seront bientôt une réalité. Motivés par la menace de plus en plus réaliste que représentent les ordinateurs quantiques pour les protocoles cryptographiques classiques existants, les chercheurs ont mis au point plusieurs mécanismes de résistance aux "attaques quantiques". En particulier, pour le vote électronique, plusieurs schémas de vote électronique reposant sur les propriétés de la mécanique quantique ont été proposés. Cependant, chacune de ces propositions s'accompagne d'un modèle de corruption différent et souvent mal articulé, a des objectifs différents et s'accompagne de revendications de sécurité qui ne sont jamais formalisées et ne sont au mieux justifiées que contre des attaques spécifiques. Dans cet article, nous systématisons et évaluons la sécurité des protocoles de vote électronique proposés, basés sur la technologie quantique. Nous examinons les revendications de ces travaux concernant la confidentialité, la correction et la vérifiabilité, et si elles sont correctement attribuées aux protocoles proposés. Dans tous les cas non triviaux, nous avons identifié des attaques quantiques spécifiques qui violent ces propriétés. Nous soutenons que la cause de ces échecs réside dans l'absence de modèles de sécurité formels et dans un manque plus général de référence à la littérature cryptographique existante.

La non-localité intrinsèque des corrélations en mécanique quantique nous permet de certifier le comportement d'un mécanisme quantique d'une manière indépendante du dispositif. En particulier, nous présentons un nouveau protocole qui permet de certifier une quantité illimitée d'aléatoire comme étant légitimement la conséquence d'une mesure sur un état quantique. En utilisant une séquence de mesures non projectives sur un seul état, nous montrons une méthode plus robuste pour certifier un caractère aléatoire non limité que le protocole de [5], en passant à un scénario unilatéral indépendant du dispositif. Ce protocole ne suppose pas non plus un comportement spécifique de l'adversaire essayant de tromper les participants au protocole, ce qui est un avantage par rapport aux protocoles précédents basés sur la direction. Nous présentons des résultats numériques qui confirment le fonctionnement optimal de ce protocole dans le cas idéal. En outre, nous étudions également un scénario expérimental pour déterminer la faisabilité du protocole dans une mise en œuvre réaliste. L'effet du bruit dépolarisant est examiné, en étudiant un état potentiel produit par un système de pièges à ions en réseau.

Les technologies expérimentales de calcul quantique n'en étant qu'à leurs débuts, la recherche de moyens efficaces pour vérifier l'exactitude de ces calculs quantiques devient de plus en plus pressante. Une approche de la vérification des calculs quantiques dans le cadre des preuves interactives s'est avérée fructueuse pour résoudre ce problème. Plus précisément, un agent non fiable (le prouveur) qui prétend effectuer des calculs quantiques peut faire vérifier ses affirmations par un autre agent (le vérificateur) qui n'a accès qu'au calcul classique et à un petit dispositif quantique pour préparer ou mesurer des qubits uniques. Cependant, lorsque ce dispositif quantique est sujet à des erreurs, la vérification devient difficile et les protocoles existants traitent souvent ce problème en ajoutant des hypothèses supplémentaires, comme l'exigence que le bruit dans le dispositif ne soit pas corrélé avec le bruit sur les dispositifs du vérificateur. Dans cet article, nous présentons un protocole simple pour vérifier les calculs quantiques, en présence de dispositifs bruyants, sans hypothèses supplémentaires. Ce protocole est basé sur des techniques de vérification post hoc, qui permettent au prouveur de connaître le calcul quantique souhaité et son entrée. Nous réalisons également une simulation du protocole, pour un calcul à un qubit, et trouvons les seuils d'erreur lors de l'utilisation du code de répétition des qubits ainsi que du code de Steane.

L'informatique quantique passe à une vitesse fulgurante d'un domaine purement académique à un cadre entièrement industriel. Des progrès rapides sont réalisés tant dans les réalisations physiques des puces quantiques que dans leurs applications logicielles potentielles. En revanche, nous ne constatons pas une croissance aussi rapide dans les méthodologies de conception et de vérification des machines quantiques à grande échelle. Dans cet ouvrage, nous décrivons le domaine de la vérification des ordinateurs quantiques. Nous discutons des concepts sous-jacents de ce domaine, de ses défis théoriques et pratiques, et des approches les plus récentes pour relever ces défis. L'objectif de cet article est de faciliter les premiers efforts d'adaptation et de création de méthodologies de vérification pour les ordinateurs et systèmes quantiques. Sans ces efforts précoces, un écart débilitant pourrait se former entre l'état de l'art des technologies physiques de bas niveau pour les ordinateurs quantiques et notre capacité à construire des circuits quantiques intégrés à moyenne, grande et très grande échelle (M/L/VLSIQ).

Pas de résumé disponible.

Pas de résumé disponible.

Les dispositifs à variables continues (CV) constituent une plateforme prometteuse pour la démonstration de protocoles d'information quantique à grande échelle. Dans ce cadre, nous définissons un modèle général de calcul quantique basé sur un matériel CV. Il se compose d'états d'entrée dans le vide, d'un ensemble fini de portes - y compris des éléments non gaussiens - et d'une détection homodyne. Nous montrons que ce modèle intègre des codages suffisants pour un calcul quantique universel probabiliste tolérant aux fautes. De plus, nous montrons que ce modèle peut être adapté pour donner des problèmes d'échantillonnage qui ne peuvent pas être simulés efficacement avec un ordinateur classique, à moins que la hiérarchie polynomiale ne s'effondre. Cela nous permet de fournir un paradigme simple pour les expériences à court terme visant à sonder l'avantage quantique reposant sur les états gaussiens, la détection homodyne et une certaine forme d'évolution non gaussienne. Enfin, nous abordons le modèle récemment introduit de l'informatique quantique instantanée dans CV, et nous prouvons que la déclaration de dureté est robuste par rapport à certaines simplifications expérimentales pertinentes dans la définition de ce modèle.

Dans ce travail, nous démontrons une façon d'effectuer un calcul multipartite classique entre des parties ayant des ressources informatiques limitées. Notre méthode exploite les ressources quantiques pour augmenter la puissance de calcul des parties individuelles. Nous montrons comment un ensemble de clients limités à un traitement classique linéaire sont capables de calculer conjointement une fonction multivariable non linéaire qui se situe au-delà de leurs capacités individuelles. Les clients sont uniquement autorisés à effectuer des portes xor classiques et des portes à un seul qubit sur des états quantiques. Nous examinons également le type de sécurité qui peut être atteint dans ce cadre limité. Enfin, nous fournissons une mise en œuvre de preuve de concept utilisant des qubits photoniques qui permet à quatre clients de calculer un exemple spécifique de fonction multipartite, le ET par paire.

Pas de résumé disponible.

Pas de résumé disponible.

Pas de résumé disponible.

Pas de résumé disponible.

Pas de résumé disponible.

Pas de résumé disponible.

Pas de résumé disponible.