Je voulais parler de calcul quantique.

Je le fais enfin en deux ou trois chapitres.

Pour commencer, Gudule va vous spoiler leur contenu. Vas-y, Gudule.

Gudule : c'est trop bien.

Merci Gudule.

1. Charlot 2

Depuis les années 30 et l'invention du lambda-calcul, ainsi que des machines de Turing (merci qui ?), nous avons une notion assez bien arrêtée de ce qu'est un calcul, formalisée en la personne de Charlot le petit robot.

Charlot lit et écrit des trucs sur un ruban infini en fonction de ce qu'on lui a demandé de faire. Il calcule.

Vous pouvez aussi imaginer, pour faire encore plus simple, Charlot 2. Il dispose d'une entrée qui contient des 0 ou des 1 (je dirai un « mot », parce qu'une chaîne de caractères, c'est un mot), et il effectue certaines opérations en fonction de ses instructions. Dans le monde booléen, 0 est « faux », 1 est « vrai ».

Les opérations OU, ET, NON sont alors formalisées par des « portes logiques », et on peut faire de superbes petits diagrammes avec des petits fils joignant les portes et aboutissant au résultat. D'ailleurs, on apprend même au passage que toutes les opérations peuvent être simulées à l'aide de portes NAND (AND puis NON sur le résultat). C'est amusant, mais c'est assez facile à démontrer.

Imaginons que nous ayons une fonction f, par exemple une fonction qui dit « oui » si le mot en entrée ne contient que des 1 et « non » sinon. Dire que nous pouvons calculer f, c'est dire que sur n'importe quelle taille de mot en entrée, il nous est possible de construire un circuit pour Charlot 2 qui effectue ce calcul, donc qui finisse par une sortie sur laquelle on peut lire le résultat : 0 ou 1.

Quant à savoir si on fait ce calcul rapidement... on va s'astreindre à construire un tel circuit sans prendre trop de temps, ou construire un circuit pas trop gros. (Parce que sinon, ce serait stupide, on encoderait directement le résultat : "si l'entrée est xxx renvoyer yyy", et on ferait ça pour toutes les entres possibles. Gros, gros circuit !).

Je parle de circuits parce que c'est une idée importante. Et puis, assez proche de notre imagination quand on pense à ce qui se passe à l'intérieur d'un ordinateur.

Gudule : et ce qui, rappelons-le, ne nous intéresse pas. Car ici même quand on parle de circuits, on ne parle que de maths.

Donc je résume, les amis : calculer, c'est aussi faire de jolis circuits avec des portes logiques qui font des opérations logiques, pour arriver au résultat qu'on cherche.

Un problème perturbe les informaticiens depuis l'invention de la notion de « calcul ». Et il est le suivant : comment calcule la Nature ? Existe-t-il des méthodes plus efficaces que Charlot ?

(Le FTM apparaît dans un déluge d'explosions, les budgets ayant augmenté grâce à la Wattpad money des Chroniques de Gudule).

FTM : spoiler. En fait, oui.

(Après avoir effectué son spoiler, le FTM s'envole vers l'infini de l'espace en songeant à son prochain Évangile pastafariste).

2. Randomisons Charlot

J'ai une première idée pour vous, et ce n'est pas une nouveauté. Pour accélérer Charlot, nous allons le « randomiser ». Autrement dit, nous allons l'autoriser à :

– renvoyer des fausses réponses (mais pas trop tout de même)

– lancer des pièces

Quand je dis « lancer une pièce », c'est faire un choix aléatoire. De toute façon, tous les formalismes sont équivalents ; lancer des pièces, des dés, ou Gudule (pour voir s'il retombe sur ses pieds ou pas) c'est pareil.

(Pour Gudule, c'est plus difficile car il faut l'attraper d'abord. Quantité d'outils existent, je vous conseille une épuisette en nylon.)

Surprise, c'est très efficace. Il existe aujourd'hui des algorithmes « randomisés » plus efficaces que leur version « déterministe », et qu'on ne sait pas « dérandomiser ». Du coup, c'est une première bonne idée : si le hasard existe dans la nature, autant s'en servir.

En pratique, bien sûr, le hasard est une notion compliquée en informatique (il n'y a pas de cousin de Gudule caché dans votre ordinateur pour lancer une pièce).

Gudule : eh, salut, Jean-Hubert.

Jean-Hubert : eh, salut, Gudule. Alors, comment ça va ? La forme ?

Gudule : je suis assailli par mes fans depuis que j'ai commencé mes chroniques. Et j'ai failli tomber amoureux de l'éditrice qui m'a kidnappé. Et toi ?

Jean-Hubert : eh ben, je lance des pièces, comme toujours. Des fois ça fait pile, des fois ça fait face. Bon, je te laisse, on a besoin de moi. On s'appelle !

Il faut donc prendre des choses qui ont l'air un peu hasardeuses, ce qui n'est pas très difficile. La Nature en est pleine, les maths aussi. Ici l'important c'est d'avoir l'air aléatoire, pas forcément de l'être. Contrairement à ce que vous allez penser, cette phrase est fondamentale au regard de ce qui se passe en cryptographie.

Bien. Nous introduisons Jean-Hubert dans la tête de Charlot, qui devient plus puissant.

Charlot : transformation !

(De nouvelles explosions ont lieu, CN tousse.)

Mais ceci n'était qu'un avant-goût. La Nature est merveilleuse, et elle ne se contente jamais de faire les choses au hasard : il existe quantité de lois physiques.

Nous pouvons donc utiliser la physique pour faire des calculs à notre place : par exemple, assembler des circuits électriques avec bobines, condensateurs (évitez Gudule car cela risquerait d'altérer son bon fonctionnement), placer ces systèmes dans certaines conditions précises et observer ce que ça donne. Typiquement, des oscillations en sortie.

La physique a fait les calculs toute seule. On mesure, on a ce qu'on voulait. À condition d'avoir bien paramétré et contrôlé le système, ce qui devient la grande difficulté.

Je ne suis pas certain (et je crois que personne ne l'est) que les calculs analogiques (à l'opposé de numérique) soient effectivement plus puissants que les calculs numériques. Ce n'est pas du tout mon sujet. Non, car nous allons aller beaucoup plus loin. Nous allons non seulement utiliser la physique, mais surtout l'une des branches de la physique les plus bizarres qui soient : la mécanique quantique.

À suivre...