Après Grover, il est temps de passer à l’algorithme de Shor. Il est souvent présenté comme le tueur du cryptage RSA. Cela est vrai en théorie, mais comme c’est souvent le cas dans le domaine quantique, il y a un grand pas à franchir pour passer à la pratique. C’est l’occasion de rappeler l’importance des qubits, de la correction d’erreurs et des portes logiques. En tout cas, Shor fonctionne, il a déjà permis de factoriser des nombres.
Dans le cadre de notre rapport sur l’informatique quantique, nous avons déjà expliqué ce que sont les qubits, des bits qui valent à la fois 0 et 1 (pour simplifier). On ne parle plus de portes logiques, mais de portes quantiques avec différents modes de fonctionnement. Ils doivent notamment obéir aux autres règles de la physique quantique, et donc être réversibles. Rien d’insurmontable, mais cela implique souvent une augmentation de la complexité du traitement des données. Le gain réside dans la rapidité de calcul, qui est incommensurable.
Nous avons également détaillé le principe de fonctionnement de l’algorithme de Grover, exemple pratique d’utilisation de l’informatique quantique… modulo tout de même l’utilisation de « l’oracle » encore appelé « boîte noire ». Passons maintenant à un autre algorithme qui a fait l’objet de beaucoup d’attention ces dernières années : celui de Shor.
