Pourrait-il y avoir une nouvelle forme de calcul au-delà du cadre de Turing ? En 1982, le physicien américain Richard Feynmannlauréat du prix Nobel, a proposé l’idée d’un calcul basé sur la mécanique quantique.

En 1995, Peter Shor, un mathématicien appliqué américain, a présenté un algorithme quantique pour factoriser des entiers en temps polynomial. Les mathématiciens pensent que cela est insoluble par les algorithmes en temps polynomial dans le cadre de Turing. Factoriser un entier signifie trouver un plus petit entier supérieur à 1 qui peut diviser l’entier. Par exemple, l’entier 688 826 081 est divisible par un entier plus petit 25 253, car 688 826 081 = 25 253 x 27 277.

Un algorithme majeur appelé le Algorithme RSA, largement utilisé dans la sécurisation des communications réseau, est basé sur la difficulté de calcul de la factorisation de grands nombres entiers. Le résultat de Shor suggère que l’informatique quantique, si elle devenait une réalité, changer le paysage de la cybersécurité.

Un ordinateur quantique à part entière peut-il être construit pour factoriser des nombres entiers et résoudre d’autres problèmes ? Certains scientifiques pensent que cela peut être le cas. Plusieurs groupes de scientifiques du monde entier travaillent à en construire un, et certains ont déjà construit des ordinateurs quantiques à petite échelle.

Néanmoins, comme toutes les nouvelles technologies inventées auparavant, il est presque certain que des problèmes avec le calcul quantique surgiront qui imposeraient de nouvelles limites.

Jie Wang est professeur d’informatique à UMass Lowell.

Cet article est republié de La conversation sous licence Creative Commons. Vous pouvez trouver le article original ici.