Comment transformer un ordinateur quantique en un générateur de nombres aléatoires parfait

Une coïncidence pure et vérifiable est difficile à trouver. Deux nouvelles phrases montrent comment fabriquer des usines de nombres aléatoires à partir d'ordinateurs quantiques.

Dites «excellence quantique» à toute réunion d'informaticiens, et vous les verrez probablement rouler des yeux. Cette phrase fait référence à l'idée que les ordinateurs quantiques franchiront bientôt la ligne, au-delà de laquelle ils pourront effectuer des tâches extrêmement difficiles pour les ordinateurs classiques avec une relative facilité. Et jusqu'à récemment, ces tâches étaient considérées comme peu utiles pour des applications réelles - d'où le roulement des yeux.

Mais maintenant que le processeur de Google serait proche de cet objectif, une supériorité quantique imminente pourrait avoir une utilisation importante: générer un pur hasard.

L'aléatoire est important pour presque tout ce qui se passe dans l'infrastructure informatique et de communication. En particulier, il est utilisé pour crypter des données qui protègent tout, des conversations ordinaires aux transactions financières et aux secrets d'État.

Le caractère aléatoire réel et confirmé - imaginez-le comme une propriété qui existe dans une séquence de nombres et rend impossible de prédire le nombre suivant dans une séquence - est extrêmement difficile à trouver.

Mais cette situation peut changer lorsque les ordinateurs quantiques démontrent leur supériorité. Ces premières tâches, qui devaient au départ simplement démontrer la supériorité de la technologie, peuvent également donner lieu à une véritable coïncidence certifiée. "Nous sommes ravis de l'accueillir", a déclaré John Martinis , physicien à l'Université de Californie à Santa Barbara, qui dirige le projet d'informatique quantique chez Google. "Nous espérons que ce sera la première utilisation d'un ordinateur quantique."

Aléatoire et entropie

L'aléatoire et la théorie quantique vont de pair comme le tonnerre et la foudre. Dans les deux cas, la première est une conséquence inévitable de la seconde. Dans le monde quantique, on dit souvent que les systèmes sont dans une combinaison de plusieurs états - les soi-disant "Superposition". Lorsque vous mesurez un système, il «s'effondre» dans l'un de ces états. Et tandis que la théorie quantique vous permet de calculer les probabilités de ce que vous découvrirez dans une mesure, le résultat exact sera toujours fondamentalement aléatoire.

Les physiciens ont étudié cette connexion afin de créer des générateurs de nombres aléatoires. Ils s'appuient tous sur des mesures d'une sorte de superposition quantique. Et bien que pour la plupart des méthodes de génération de nombres aléatoires dont les gens ont besoin, ces systèmes suffisent, il peut être difficile de travailler avec eux. De plus, il est très difficile de prouver au sceptique le véritable caractère aléatoire de ces générateurs de nombres aléatoires. Enfin, certaines des méthodes les plus efficaces pour générer un caractère aléatoire confirmé nécessitent des conceptions sophistiquées à partir de plusieurs appareils séparés par de grandes distances.


Google AI Lab présente le processeur quantique Bristlecone 72-Qubit en 2018

Une proposition récente visant à extraire le caractère aléatoire d'un seul appareil - un ordinateur quantique - utilise ce qu'on appelle. la tâche d'échantillonnage, qui sera l'un des premiers tests de supériorité quantique. Pour le comprendre, imaginez qu'on vous ait remis une boîte de tuiles. Sur chaque tuile, il y a plusieurs unités et plusieurs zéros - 000, 010, 101 et ainsi de suite.

S'il n'y a que trois bits, il y a huit options possibles. Cependant, il peut y avoir plusieurs copies de chaque tuile dans la boîte. Il peut y avoir 50 tuiles étiquetées 010 et 25 tuiles étiquetées 001. La distribution des tuiles détermine la probabilité que vous retiriez accidentellement une tuile particulière. Dans notre cas, vous pouvez retirer la tuile 010 avec une probabilité deux fois plus élevée que la tuile 001.

La tâche d'échantillonnage comprend un algorithme informatique équivalent à extraire au hasard des tuiles de la boîte avec une distribution de tuiles spécifique. Plus la probabilité définie pour n'importe quelle tuile de la distribution est élevée, plus l'algorithme tirera probablement cette tuile.

Bien sûr, l'algorithme ne tire pas de vraies tuiles d'une vraie boîte. Il produit juste au hasard un nombre binaire de 50 bits de longueur, ayant reçu une distribution qui détermine la probabilité souhaitée pour chacune des lignes possibles de 50 bits de longueur.

Pour un ordinateur classique, la complexité de cette tâche augmente de façon exponentielle avec une augmentation du nombre de bits dans une chaîne. Mais pour un ordinateur quantique, la tâche devrait rester à peu près la même pour 5 bits et 50.

Un ordinateur quantique commence par dire que tous ses bits quantiques - qubits - sont dans un certain état. Supposons qu'ils commencent tous par 0. Comment les ordinateurs classiques peuvent travailler avec des bits classiques en utilisant ce qu'on appelle. les portes logiques et les ordinateurs quantiques manipulent les qubits en utilisant leur équivalent quantique, les portes quantiques.

Cependant, les portes quantiques peuvent placer des qubits dans des états étranges. Par exemple, un type de porte peut placer un qubit qui commence par une valeur de 0 dans une superposition de 0 et 1. Si vous mesurez ensuite l'état d'un qubit, il s'effondre au hasard à 0 ou 1 avec une probabilité égale.

Encore plus étrange, les portes quantiques qui peuvent fonctionner avec deux qubits ou plus en même temps peuvent provoquer un enchevêtrement entre les qubits. Dans ce cas, les états des qubits sont entrelacés de sorte que maintenant tous ces qubits peuvent être décrits en utilisant un seul état quantique.

Si vous amenez un tas de portes quantiques à un endroit, puis les faites fonctionner avec un ensemble de qubits dans une certaine séquence, ce sera un circuit quantique. Dans notre cas, pour dériver une chaîne aléatoire de 50 bits, vous pouvez construire un circuit quantique qui place 50 qubits dans une superposition d'états qui décrit la distribution dont vous avez besoin.

Lors de la mesure des qubits, la superposition entière s'effondre de manière aléatoire en une seule chaîne de 50 bits. La probabilité qu'il s'effondre dans une certaine ligne est déterminée par la distribution déterminée par le contour quantique. La mesure des qubits est similaire à la façon dont un homme aux yeux bandés tend la main dans un sac et tire accidentellement une ligne avec la distribution.


Scott Aaronson, spécialiste en informatique, Université du Texas à Austin

Et comment tout cela est-il lié aux nombres aléatoires? Il est important que la chaîne de 50 bits sélectionnée par l'ordinateur quantique contienne beaucoup d'entropie, une mesure de désordre ou d'imprévisibilité, et donc d'aléatoire. "Et cela, en fait, peut avoir des conséquences très graves", a déclaré Scott Aaronson , un spécialiste en informatique à l'Université du Texas à Austin qui a mis au point un nouveau protocole. "Non pas parce que c'est l'utilisation la plus importante des ordinateurs quantiques - je pense que c'est loin de là - mais parce que cela ressemble peut-être à la première utilisation des ordinateurs quantiques qui peut être mise en pratique."

Le protocole d'Aaronson pour générer des nombres aléatoires est assez simple. Un ordinateur classique collecte d'abord quelques bits aléatoires à partir d'une source fiable, puis utilise cette «graine d'aléatoire» pour générer une description du contour quantique. Les bits aléatoires déterminent le type de portes quantiques et la séquence dans laquelle ils doivent agir sur les qubits. Un ordinateur classique envoie une description à un ordinateur quantique qui implémente un circuit quantique, mesure les qubits et renvoie une chaîne de 50 bits. Ainsi, il s'avère être choisi au hasard dans la distribution définie par le contour.

Répétez ensuite ce processus plusieurs fois - par exemple, 10 fois pour chaque circuit quantique. Un ordinateur classique utilise des tests statistiques pour s'assurer que les lignes de sortie contiennent une bonne quantité d'entropie. Aaronson a montré (en partie dans un ouvrage publié en collaboration avec Lijie Chen et en partie dans un ouvrage à paraître) que, sous certaines hypothèses raisonnables que ces tâches sont complexes sur le plan informatique, aucun ordinateur classique ne peut générer une telle entropie dans temps comparable au temps pendant lequel un ordinateur quantique crée une telle sélection aléatoire à partir de la distribution. Après les vérifications, l'ordinateur classique collecte toutes les chaînes de 50 bits et les transmet à l'algorithme classique bien connu. "Il produit une longue chaîne presque parfaitement aléatoire", a déclaré Aaronson.

Piège quantique

Le protocole Aaronson est mieux adapté aux ordinateurs quantiques avec des qubits de 50 à 100. Lorsque le nombre de qubits dépasse ces limites, la complexité de calcul ne permet même pas aux superordinateurs classiques d'utiliser ce protocole. Dans ce cas, un autre schéma pour générer des nombres aléatoires vérifiables à l'aide d'ordinateurs quantiques entre en scène. Il utilise une technique mathématique existante avec la fonction sans griffe de trappe de nom complexe. "Cela semble pire que la réalité", ont déclaré Umesh Wazirani , spécialiste informatique à l'Université de Californie à Berkeley, qui a développé une nouvelle stratégie qui a été aidée par Zvika Brackerski , Paul Cristiano , Urmila Mahadev et Thomas Vidik .

Présentez notre boîte. Au lieu d'y entrer et d'extraire une chaîne, nous y jetons une chaîne de n bits, l'appelons x, puis supprimons une autre chaîne de n bits. La boîte correspond en quelque sorte à la ligne d'entrée et à la ligne de sortie. Mais il a une propriété spéciale: pour chaque x, il y a une autre ligne d'entrée y, qui produit exactement la même ligne de sortie.

En d'autres termes, il existe deux lignes d'entrée uniques - x et y - pour lesquelles la boîte renvoie la même ligne de sortie z. Ce triple, x, y et z, s'appelle une griffe. Encadré dans le langage de l'informatique - une fonction. Cette fonction est facile à calculer, c'est-à-dire que pour tout x et y, il est facile de calculer z. Mais si vous ne prenez que x et z, il est impossible de trouver y - et toute la griffe - même pour un ordinateur quantique.


Urmila Mahadev, Umesh Vazirani et Thomas Vidik

La seule façon d'obtenir la griffe entière est de trouver des informations supplémentaires, le soi-disant un piège.

Vazirani et ses collègues veulent utiliser ces fonctions non seulement pour forcer les ordinateurs quantiques à générer des nombres aléatoires, mais aussi pour vérifier que les ordinateurs quantiques fonctionnent réellement selon les lois quantiques - ce qui est nécessaire pour renforcer la confiance dans les séquences aléatoires.

Le protocole commence par un ordinateur quantique plaçant n qubits dans une superposition de toutes les chaînes de n bits. Ensuite, l'ordinateur classique envoie une description du contour quantique, déterminant la fonction à appliquer à la superposition - la fonction piège sans griffes. Un ordinateur quantique implémente un circuit sans rien savoir du piège.

À ce stade, l'ordinateur quantique entre dans un état dans lequel un ensemble de ses qubits se trouve dans une superposition de toutes les chaînes de n bits, et l'autre contient le résultat de l'application de la fonction à cette superposition. Deux ensembles de qubits sont entremêlés.

Un ordinateur quantique mesurant un deuxième ensemble de qubits réduit au hasard une superposition en un certain résultat z. Le premier ensemble de qubits s'effondre en une superposition similaire de deux chaînes de n bits, x et y, car chacune d'elles peut servir d'entrée pour une fonction émettant z.

Un ordinateur classique reçoit une valeur de sortie de z, puis effectue l'une des deux opérations suivantes. Dans la plupart des cas, il demande à l'ordinateur quantique de mesurer les qubits restants. Cela réduit la superposition en x ou en y, avec 50% de chances. Cela équivaut à obtenir au hasard 0 ou 1.

Parfois, pour tester un ordinateur quantique quantique, un ordinateur classique demande une mesure spéciale. La mesure et son résultat sont conçus pour qu'un ordinateur classique à l'aide d'un piège auquel lui seul ait accès puisse garantir que le dispositif répondant à ses demandes est vraiment quantique. Vazirani et ses collègues ont montré que si l'appareil donne la bonne réponse à une dimension particulière sans utiliser l'effondrement des qubits, cela équivaudra à trouver une griffe sans piège. Et c'est impossible. Par conséquent, au moins un qubit (donnant 0 ou 1 au hasard) doit s'effondrer dans l'appareil. "Le protocole crée un qubit testé dans un ordinateur quantique auquel nous ne faisons pas confiance", a déclaré Vazirani.

Ce qubit testé donne un bit d'information vraiment aléatoire pour chaque enquête; une séquence de ces requêtes peut être utilisée pour créer de longues chaînes aléatoires.

Ce schéma peut fonctionner plus rapidement que le protocole Aaronson, mais il a un défaut évident. "Avec un nombre de qubit de 50 ou 70, ce ne sera pas pratique", a déclaré Aaronson.

Aaronson attend toujours l'apparition d'un système de Google. "Que la qualité de ce qu'ils nous montrent soit suffisante pour vraiment atteindre la supériorité quantique est une grande question", a-t-il dit.

Si l'entreprise réussit, l'aléa quantique garanti est déjà à nos portes. "Nous pensons que ce sera un marché utile et prometteur, et c'est ce que nous aimerions offrir aux gens", a déclaré Martinis.