La communication quantique et le protocole BB84

Nouvelle vidéo sur la chaîne, une vidéo « un petit peu spéciale » en partenariat avec Echosciences PACA.

Le défi de cette vidéo était de donner quelques notions de communication quantique dans le format imposé de 3-4 minutes ! Pas la place donc pour y détailler un exemple de protocole d’échange de clé quantique comme le protocole BB84 dont j’esquisse juste le principe dans la vidéo. Voici donc quelques détails !

Non, BB84 n’est pas un lointain descendant du robot BB8, mais le nom du tout premier protocole d’échange de clé quantique qui a été imaginé en 1984 par les cryptologues Charles Bennett et Gilles Brassard. L’idée de ce protocole est de permettre l’échange sécurisé d’une clé de chiffrement, clé qui pourra être ensuite utilisée pour chiffrer un message qui sera ensuite transmis sur un canal de communication classique. Notez bien : ça n’est pas tout le message qui est transmis de façon « quantique », juste la clé de chiffrement.

Jouons avec la polarisation

Dans la vidéo, j’ai simplifié les choses en disant qu’un photon avait une polarisation horizontale, verticale, ou bien une superposition des deux dont les proportions pouvaient varier. Mais vous avez peut-être tiqué quand je parle d’horizontal et de vertical : certes, mais horizontal par rapport à quoi ? La gravité terrestre ? Qu’est-ce qu’elle viendrait faire là-dedans ?

En réalité, quand on souhaite mesurer la polarisation d’un photon, on doit se fixer ce qu’on appelle une base de mesure, sous la forme de deux axes orthogonaux situés dans le plan perpendiculaire à la direction de propagation du photon. Une manière concrète de se le représenter, c’est d’imaginer qu’un détecteur de polarisation est plan, qu’on le place perpendiculairement à la trajectoire du photon, et qu’il possède deux axes privilégiés, mais qu’on peut choisir de les faire tourner.

Il existe donc plein de façons de faire ce choix de base de mesure (une infinité en fait). Considérons donc deux bases possibles, l’une verticale/horizontale, et l’autre qui est tournée de 45° degrés. On va appeler ces bases respectivement « + » et « x ».  Et pour s’affranchir des mots « horizontal » et « vertical », on va appeler chaque axe respectivement 0 et 1.

Quand un photon vient traverser un détecteur , la réponse de la mesure sera soit 0, soit 1, désignant ainsi un des axes de la base de mesure. La notion de 0 ou 1 est donc toujours relative à la base de mesure. On va noter les 4 états avec lesquels on va jouer de la façon suivante : 0+, 1+, 0x et 1x, correspondant à la polarisation selon chacun des 4 axes.

Imaginons un photon 0+, c’est à dire d’état 0 de la base +. Si on le mesure dans la base + la réponse du détecteur sera forcément 0 (aux erreurs de mesure près).

Maintenant si on prépare un photon dans l’état 0+ et qu’on le mesure dans la base x, on obtiendra aléatoirement les réponses 0 ou 1 à 50% de probabilité. Une autre façon de le dire, c’est que l’état « pur » 0+ est un état « superposé » 50% de 0x et 50% de 1x dans la base x.

La notion d’état « pur » (on dit en fait « état propre ») ou « superposé » n’est donc pas absolue comme j’ai pu le sous-entendre, mais toujours relative à la base de mesure.

Dernier ingrédient à préciser : la projection de l’état quantique. Si vous mesurez un photon 0+ dans la base x, vous obtiendrez soit 0, soit 1. Mais à la suite de cette mesure, la polarisation sera dans l’état pur correspondant de la base x. Par exemple si vous obtenez 1, la polarisation sera changée en 1x. Et donc si vous le re-mesurez dans la base +, vous trouverez 0 ou 1 à 50/50 (et le re-changerez en 0+ ou 1+).

Tous les ingrédients sont en place, voyons le protocole BB84.

Le protocole BB84

Imaginons deux personnes souhaitant communiquer de façon sécurisée, et ayant besoin de partager une clé de chiffrement. Appelons-les Alice et Bob pour suivre la tradition en vigueur.

Pour faire un partage de clé quantique, Alice va envoyer une série de photons à Bob, et pour chacun de ces photons, elle va tirer au hasard à la fois une base (+ ou x) et un bit (0 ou 1). Chaque photon sera donc aléatoirement d’un l’un de ces 4 états : 0+, 1+, 0x ou 1x.

Bob voit arriver les photons et pour chacun d’entre eux il doit mesurer la polarisation. Mais il lui faut choisir une base de mesure. Pour chacun il la tire au hasard : + ou x, et note le résultat de sa mesure.

Si pour un photon donné, Bob a choisi la « bonne » base, c’est-à-dire la même qu’Alice, il obtiendra à coup sûr le bon bit, 0 ou 1, envoyé par Alice. Si en revanche il a choisi l’autre base, eh bien il obtiendra 0 ou 1 à 50% de probabilité. Et dans ce cas, il obtiendra le « mauvais » résultat une fois sur 2 en moyenne. Voici un exemple ci-dessous.

Une fois la transmission des photons réalisée, Alice et Bob se communiquent « publiquement » (sans canal sécurisé particulier) la liste des bases qu’ils ont utilisé pour chacun des photons. Et ils jettent de leur liste tous les photons pour lesquels les bases sont différentes (la moitié en moyenne).

Pour tous les photons restants, ils ont utilisé la même base et ont donc la certitude d’avoir les mêmes bits : 0 ou 1. Cette série de bits va constituer la clé de chiffrement qui est, de fait, connue d’eux deux.

Certes me direz-vous, mais comment est-on certains que l’échange n’a pas été intercepté ? Eh bien imaginons qu’un 3e larron (Eve, selon le choix consacré) pirate la communication et essaye de mesurer l’état de polarisation des photons pour découvrir la clé. On va se concentrer sur les photons pour lesquels Alice et Bob ont choisi la même base, puisque les autres seront de toute façon écartés. Comme Bob, Eve doit choisir à chaque photon une base de mesure + ou x. Dans 50% des cas elle va tomber juste. Mais dans les 50% restants elle choisira une base différente de la base d’Alice et Bob, par exemple elle choisit x alors qu’ils ont choisi +.

Imaginons un photon 0+ qu’Eve intercepte et mesure dans la base x. La mesure va le projeter dans l’état 0x ou 1x, et quand Bob mesurera à son tour dans la base +, il obtiendra 0 ou 1, à 50% de probabilité. S’il obtient 0 (ce qu’Alice avait envoyé), tout se passera comme si Eve n’avait pas été là, mais s’il obtient 1 il obtiendra un bit différent de ce qu’Alice avait envoyé…alors que leurs bases sont pourtant identiques !

Voici donc comment détecter la présence d’Eve. Comme je le disais au début : Alice envoie ses photons, Bob les mesure, ils comparent publiquement leurs bases et ne conservent que les cas où les bases coïncident. Mais il n’en font pas tout de suite une clé : d’abord, ils décident de sacrifier une partie de ces photons pour vérifier qu’ils ne sont pas espionnés. Pour cela ils révèlent (publiquement) les bits qu’ils ont respectivement envoyé et mesuré, et qui en principe devraient coïncider complètement. Si Eve était à l’écoute au milieu de la ligne, environ 25% de ces bits devraient différer, du fait des projections quantiques opérées par les mesures. Si c’est le cas, Alice et Bob peuvent jeter leur clé et tenter de recommencer. Si ça n’est pas le cas, ils ont l’assurance que l’échange de clé n’aura pas été intercepté.

Quelques subtilités

Un point essentiel de ce protocole, c’est le fait qu’Eve n’a aucun moyen de connaitre avec certitude l’état du photon envoyé par Alice. La seule chose qu’elle puisse faire c’est choisir une base et faire une mesure : mais si elle choisit + et obtient 0, elle n’a aucun moyen de savoir si l’état envoyé par Alice était bien précisément 0+, ou si Alice a envoyé 0x ou 1x, qui peuvent l’un et l’autre donner 0 une fois mesurés dans la base +.

Donc Eve n’a pas moyen de « connaitre exactement » le photon envoyé par Alice puis de le recréer « à l’identique » de façon à ce que Bob n’y voit que du feu. De façon générale, il existe en physique quantique un théorème dit de « non-clonage », qui dit qu’il est impossible de cloner exactement un état quantique, et c’est cela qui est à la base des protocoles d’échange de clé quantique.

Pour s’assurer de l’absence d’un espion, Alice et Bob doivent donc choisir un certain nombre de photons parmi ceux pour lesquels ils ont choisi la même base, et comparer leur valeurs de bits. Si Eve est à l’écoute, chacun de ces photons à 25% de chance de différer. Si on utilise N photons pour cela, la probabilité que Eve ne soit pas détectée est (3/4)^N. En choisissant N assez grand, on s’assure avec une grande probabilité que la communication est sécurisée.

Autre point : ce protocole protège des écoutes pirates, mais ne protège pas d’un autre type d’attaque cryptographique connu sous le nom de « man-in-the-middle ». Dans ce type d’attaque, plutôt que d’essayer d’écouter discrètement, Eve se fait passer pour Bob auprès d’Alice et pour Alice auprès de Bob.

Enfin il existe d’autres protocoles de communication quantique, le BB84 n’étant que le premier d’entre eux. Certains utilisent des états quantiques intriqués…mais en parler dans la vidéo initiale m’aurait emmené bien trop loin. J’en parlerai peut-être un jour, et en attendant je vous renvoie à ma vidéo sur l’intrication quantique !

Une intelligence artificielle peut-elle être créative ? Le cas des jeux.

La vidéo du jour parle de la créativité des IA, vue dans le contexte des jeux !

Pour ceux qui voudraient aller plus loin, quelques compléments d’usage.

Le MinMax

Un premier point que j’ai passé sous silence pour rester simple, c’est la façon dont on décide du « meilleur » coup une fois qu’on dispose de toutes les évaluations. Pour vous l’illustrer, voici une petite énigme.

Imaginez que j’aie 4 coups possibles, A, B, C et D, et que chacun de ces coups puisse appeler 4 réponses. Supposez que les résultats de l’évaluation des 16 positions résultantes soient les suivants, quel coup dois-je choisir ?

Si vous avez répondu « B » car c’est le coup qui mène à la position la plus intéressante (+8), vous êtes tombés dans le piège classique ! En effet il faut partir du principe que si on cherche à maximiser son score, l’adversaire lui a l’objectif inverse. Donc si il n’est pas plus bête que nous, il cherchera toujours à jouer la meilleure réponse (et donc si on joue B il jouera sa 4e option et le score sera 0).

La bonne réponse est donc C, car si l’adversaire joue son meilleur coup on sera à +1, ce qui est le mieux qu’on puisse espérer.

Ce petit exemple illustre le principe du MinMax, c’est-à-dire qu’on cherche le coup qui permet de maximiser son score sachant que l’adversaire va le minimiser.

Sur la manière de chercher dans l’arbre

Ma vidéo suggère qu’un algorithme comme celui qui tournait sur Deep Blue fait une recherche exhaustive dans l’arbre de façon totalement stupide. En réalité ça n’est pas si bourrin que ça.

Un simple petit calcul montre que si Deep Blue voulait chercher de façon exhaustive avec 12 coups d’anticipation, il faudrait 20^{12} évaluations, soit 4 millions de milliards. Même à 200 millions d’évaluations par secondes, cela fait longtemps à réfléchir.

Deep Blue était en fait basé sur une technique classique appelée « L’élagage d’arbre alpha/beta », qui permet d’éviter de visiter des branches dont on sait qu’elles n’amélioreront pas le meilleur résultat qu’on puisse espérer. Stockfish fonctionne sur un principe similaire.

Sur la base de données utilisée par AlphaGo

Il semble que j’ai fait une erreur ou du moins une exagération concernant la base de données utilisée par AlphaGo pour s’entrainer (version « Apprentissage supervisé », celle qui a battu Lee Sedol).

En effet la base est constituée de parties jouées par des joueurs 6e à 9e dan (que j’ai appelé de façon informelle « des grands maitres du go ») et a été extraite de la base online KGS.  Or j’ai l’impression qu’il y a une ambiguïté entre la notion de dan « amateur » et de dan « professionnel ». Et j’ai l’impression que la base KGS référence plutôt des parties amateurs.

Quelque part, c’est plutôt encore mieux pour AlphaGo, qui semble avoir appris en utilisant des données qui ne sont pas uniquement des parties de joueurs de classe internationale.

D’ailleurs c’est en fait un peu plus compliqué que ça puisque l’entrainement du réseau chargé de faire l’évaluation a bénéficié aussi d’apprentissage par renforcement.

Le fameux 37e coup

Quelques précisions concernant ce fameux coup. Je ne joue pas au go donc je n’ai clairement pas le niveau pour expliquer en quoi ce coup était inattendu. Mais il semble que généralement pour ce type de coup (appelé en anglais « shoulder hit ») qui consiste à se mettre en diagonale d’une pierre adverse, on se place sur la 3e ou la 4e ligne suivant qu’on veuille jouer défensif ou agressif. Mais semble-t-il, « jamais » sur la 5e ligne.

Alors en fait c’est plus compliqué que ça, et ça n’est pas le propos ici. Des « shoulder hits » sur la 5e ont l’air tout à fait possible, mais apparemment pas dans la situation qui se présentait à AlphaGo à ce moment là.

AlphaGo, AlphaGoZero et AlphaZero

Pour les besoins de la simplification de l’exposé, j’ai fait un raccourci dans ma présentation. Il y a eu en réalité (au moins) 3 versions de l’algorithme :

  • AlphaGo, qui a battu Lee Sedol
  • AlphaGo Zero, la première version fonctionnant purement en apprentissage par renforcement, mais uniquement pour le go.
  • AlphaZero, fonctionnant aussi bien pour le go, les échecs ou le shogi.

Je n’ai pas évoqué AlphaGo Zero, la version intermédiaire. Et en fait c’est elle qui a battu « Alpha Go Lee Sedol » par 100 à 0.

La différence entre AlphaGo Zero et AlphaZero, est que le premier exploite quelques spécificités du Go pour se simplifier la vie, ce que les spécialistes appellent du « domain knowledge », par exemple l’existence de symétries sur le plateau. Le fait de donner du « domain knowledge » permet de réduire la complexité de l’apprentissage par renforcement (et donc de l’accélérer), mais au prix d’une perte de généralité et de « pureté », puisqu’on aide l’algorithme en lui donnant des infos en plus.

AlphaZero est vraiment la version « pure », on ne lui donne aucun domain knowledge, vraiment juste les règles et rien que les règles. Il est un peu plus long à entrainer que la version précédente, mais l’avantage est qu’il marche aussi pour d’autres jeux abstraits. (Et au go il est légèrement supérieur à AlphaGo Zero).

Et les autres jeux vidéo ?

J’ai hésité dans cet épisode à parler des applications de l’IA à d’autres jeux, notamment vidéo. J’aurai pu par exemple évoquer DOTA2 ou StarCraft. Apparemment j’ai bien fait de m’abstenir, car à l’heure où j’écris ces lignes  DeepMind a annoncé qu’ils allaient faire une grosse annonce concernant StarCraft, le jour qui suit la publication de la vidéo. Donc à suivre !

Le jeu de la vie

La vidéo du jour traite des automates cellulaires, et en particulier de l’intriguant « jeu de la vie ».

Pour ceux que ça intéresse, je vais mettre le code en partage sur GitHub (si j’y arrive). Il est loin d’être parfait, et d’ailleurs je vous encourage à écrire le votre ! Mais vous y trouverez peut être quelques astuces intéressantes sur comment lire les fichiers RLE (qui encodent de façon compacte les situations de départ), ou bien génerer des vidéos à partir d’images MatPlotLib en Python.

Edit du 09/12 : le code est dispo sur GitHub Lire la suite

Le Bitcoin et la Blockchain

La vidéo du jour décrypte les mystères du bitcoin, et vous explique vraiment comment il marche, et ce qu’est cette mystérieuse blockchain.

Pour préparer cette vidéo, j’ai dû pas mal me documenter. J’ai trouvé beaucoup d’endroits où les grands principes du bitcoin sont expliqués, mais assez peu d’infos détaillées sur ce qu’il se passe vraiment « sous le capot ». A force de lecture, je pense avoir compris l’essentiel, et j’espère donc avoir donné à tout le monde les éléments nécessaires pour comprendre comment un système comme le bitcoin pouvait tenir debout, et en quoi le concept de la blockchain assure la décentralisation du système. Lire la suite