Breveter les innovations en informatique quantique – Partie 5 : L'algorithme de Shor et conclusions

Par Sinan Utku

Exemple 4 : L'algorithme de Shor

L'algorithme de Shor factorise efficacement les grands entiers en leurs facteurs premiers en réduisant le problème à une tâche de recherche de période, qui peut être résolue beaucoup plus efficacement sur un ordinateur quantique que sur un ordinateur classique. L'algorithme consiste à préparer une superposition quantique d'entrées et à préparer une porte quantique pour évaluer une fonction d'exponentiation modulaire. Il applique ensuite une estimation de phase quantique pour extraire la période de cette fonction. Cela implique l'application de puissances contrôlées de la porte quantique pour l'exponentiation modulaire, puis l'exécution d'une transformée de Fourier quantique inverse pour obtenir des informations sur la période. Une fois la période déterminée, un algorithme classique l'utilise pour calculer relativement facilement les facteurs premiers de l'entier. Parce que l'algorithme de Shor est exponentiellement plus rapide que les meilleurs algorithmes de factorisation classiques connus, il pose une menace significative pour les cryptosystèmes à clé publique largement utilisés tels que RSA, qui reposent sur la difficulté de factoriser de grands entiers.