L'algorithme de Shor

L'algorithme de Shor est un algorithme quantique permettant de trouver les facteurs premiers d'un entier. Il a été développé en 1994 par le mathématicien américain Peter Shor . C'est l'un des rares algorithmes quantiques connus avec des applications potentielles convaincantes et de solides preuves d'accélération superpolynomiale par rapport aux meilleurs algorithmes classiques (non quantiques) connus. D'un autre côté, la factorisation de nombres d'importance pratique nécessite beaucoup plus de qubits que ceux disponibles dans un avenir proche. Une autre préoccupation est que le bruit dans les circuits quantiques peut nuire aux résultats, nécessitant des qubits supplémentaires pour la correction des erreurs quantiques .

Shor a proposé plusieurs algorithmes similaires pour résoudre le problème de factorisation , le problème du logarithme discret et le problème de recherche de période. L'« algorithme de Shor » fait généralement référence à l'algorithme de factorisation, mais peut faire référence à l'un des trois algorithmes. L'algorithme du logarithme discret et l'algorithme de factorisation sont des instances de l'algorithme de recherche de période, et tous trois sont des instances du problème du sous-groupe caché .

Sur un ordinateur quantique, pour factoriser un entier , l'algorithme de Shor s'exécute en temps polynomial , ce qui signifie que le temps pris est polynomial en . Il faut des portes quantiques d'ordre en utilisant une multiplication rapide, ou même en utilisant l'algorithme de multiplication asymptotiquement le plus rapide actuellement connu grâce à Harvey et Van Der Hoven, démontrant ainsi que le problème de factorisation d'entiers peut être résolu efficacement sur un ordinateur quantique et se situe par conséquent dans la classe de complexité BQP . C'est nettement plus rapide que l'algorithme de factorisation classique le plus efficace connu, le crible général de corps de nombres , qui fonctionne en temps sous-exponentiel : .

Si un ordinateur quantique doté d'un nombre suffisant de qubits pouvait fonctionner sans succomber au bruit quantique et à d'autres phénomènes de décohérence quantique , alors l'algorithme de Shor pourrait être utilisé pour briser les schémas de cryptographie à clé publique , tels que

• Le régime RSA
• L' échange de clés Diffie-Hellman à corps fini
• L'échange de clés Diffie-Hellman à courbe elliptique

RSA peut être déjoué si la factorisation de grands entiers est réalisable par calcul. Pour autant que l'on sache, cela n'est pas possible avec les ordinateurs classiques (non quantiques) ; aucun algorithme classique n'est connu capable de factoriser des entiers en temps polynomial. Cependant, l'algorithme de Shor montre que la factorisation d'entiers est efficace sur un ordinateur quantique idéal, il pourrait donc être possible de déjouer RSA en construisant un grand ordinateur quantique. Il a également été un puissant moteur pour la conception et la construction d'ordinateurs quantiques, et pour l'étude de nouveaux algorithmes d'ordinateurs quantiques. Il a également facilité la recherche sur de nouveaux cryptosystèmes sécurisés par rapport aux ordinateurs quantiques, collectivement appelés cryptographie post-quantique .

Étant donné les taux d’erreur élevés des ordinateurs quantiques contemporains et le nombre trop restreint de qubits pour utiliser la correction d’erreur quantique , les démonstrations en laboratoire n’obtiennent des résultats corrects que dans une fraction des tentatives.

En 2001, l'algorithme de Shor a été démontré par un groupe d' IBM , qui a factorisé en , en utilisant une implémentation RMN d'un ordinateur quantique avec sept qubits. Après la mise en œuvre d'IBM, deux groupes indépendants ont implémenté l'algorithme de Shor en utilisant des qubits photoniques , soulignant que l'intrication multi-qubits a été observée lors de l'exécution des circuits de l'algorithme de Shor. En 2012, la factorisation de a été réalisée avec des qubits à semi-conducteurs. Plus tard, en 2012, la factorisation de a été réalisée. En 2016, la factorisation de a été réalisée à nouveau en utilisant des qubits à ions piégés avec une technique de recyclage. En 2019, une tentative a été faite pour factoriser le nombre en utilisant l'algorithme de Shor sur un IBM Q System One , mais l'algorithme a échoué en raison d'erreurs accumulées. Cependant, toutes ces démonstrations ont compilé l'algorithme en utilisant la connaissance préalable de la réponse, et certaines ont même simplifié à outrance l'algorithme d'une manière qui le rend équivalent à un tirage au sort. De plus, des tentatives utilisant des ordinateurs quantiques avec d'autres algorithmes ont été faites. Cependant, ces algorithmes sont similaires à la vérification classique par force brute des facteurs, donc contrairement à l'algorithme de Shor, ils ne devraient jamais être plus performants que les algorithmes de factorisation classiques.

Les analyses théoriques de l'algorithme de Shor supposent un ordinateur quantique exempt de bruit et d'erreurs. Cependant, les implémentations pratiques à court terme devront faire face à de tels phénomènes indésirables (lorsque davantage de qubits seront disponibles, la correction d'erreur quantique pourra aider). En 2023, Jin-Yi Cai a montré qu'en présence de bruit, l'algorithme de Shor échoue asymptotiquement presque sûrement pour les grands nombres semi-premiers qui sont des produits de deux nombres premiers dans la séquence OEIS A073024. Ces nombres premiers ont la propriété d' avoir un facteur premier supérieur à , et ont une densité positive dans l'ensemble de tous les nombres premiers. Par conséquent, une correction d'erreur sera nécessaire pour pouvoir factoriser tous les nombres avec l'algorithme de Shor.

Le problème que nous essayons de résoudre est le suivant : étant donné un nombre composé impair , trouver ses facteurs entiers .

Pour y parvenir, l’algorithme de Shor se compose de deux parties :

1. Une réduction classique du problème de factorisation au problème de recherche d'ordre . Cette réduction est similaire à celle utilisée pour d'autres algorithmes de factorisation , tels que le crible quadratique .
2. Un algorithme quantique pour résoudre le problème de recherche d'ordre.

Un algorithme de factorisation complet est possible si nous sommes capables de factoriser efficacement des nombres arbitraires en seulement deux entiers et supérieurs à 1, car si l'un ou l'autre ne sont pas premiers, l'algorithme de factorisation peut à son tour être exécuté sur ceux-ci jusqu'à ce qu'il ne reste que des nombres premiers.

Une observation de base est que, en utilisant l'algorithme d'Euclide , nous pouvons toujours calculer efficacement le PGCD entre deux entiers. En particulier, cela signifie que nous pouvons vérifier efficacement si est pair, auquel cas 2 est trivialement un facteur. Supposons donc que est impair pour le reste de cette discussion. Ensuite, nous pouvons utiliser des algorithmes classiques efficaces pour vérifier si est une puissance première . Pour les puissances premières, des algorithmes de factorisation classiques efficaces existent, donc le reste de l'algorithme quantique peut supposer que n'est pas une puissance première.

Si ces cas simples ne produisent pas de facteur non trivial de , l'algorithme passe au cas restant. Nous choisissons un entier aléatoire . Un diviseur non trivial possible de peut être trouvé en calculant , ce qui peut être fait de manière classique et efficace en utilisant l' algorithme d'Euclide . Si cela produit un facteur non trivial (ce qui signifie ), l'algorithme est terminé, et l'autre facteur non trivial est . Si un facteur non trivial n'a pas été identifié, cela signifie que et le choix de sont premiers entre eux , donc est contenu dans le groupe multiplicatif des entiers modulo , ayant un inverse multiplicatif modulo . Ainsi, a un ordre multiplicatif modulo , ce qui signifie

et est le plus petit entier positif satisfaisant cette congruence.

La sous-routine quantique trouve . On peut le voir à partir de la congruence qui divise , écrite . Cela peut être factorisé en utilisant la différence des carrés : Puisque nous avons factorisé l'expression de cette manière, l'algorithme ne fonctionne pas pour impair (car doit être un entier), ce qui signifie que l'algorithme devrait recommencer avec un nouveau . Par la suite, nous pouvons donc supposer que est pair. Il ne peut pas être le cas que , car cela impliquerait , ce qui impliquerait contradictoirement que serait de l'ordre de , qui était déjà . À ce stade, il peut ou non être le cas que . S'il n'est pas vrai que , alors cela signifie que nous sommes capables de trouver un facteur non trivial de . Nous calculons Si , alors cela signifie était vrai, et un facteur non trivial de ne peut pas être obtenu à partir de , et l'algorithme doit recommencer avec un nouveau . Sinon, nous avons trouvé un facteur non trivial de , l'autre étant , et l'algorithme est terminé. Pour cette étape, il est également équivalent à calculer ; il produira un facteur non trivial si n'est pas trivial, et ne le fera pas s'il est trivial (où ).

L'algorithme reformulé est le suivant : soit impair, et non une puissance première. Nous voulons produire deux facteurs non triviaux de .

Il a été démontré que cela est susceptible de réussir après quelques essais. En pratique, un seul appel à la sous-routine de recherche d'ordre quantique suffit à factoriser complètement avec une très grande probabilité de succès si l'on utilise une réduction plus avancée.

L'objectif de la sous-routine quantique de l'algorithme de Shor est, étant donné des entiers premiers entre eux et , de trouver l' ordre de modulo , qui est le plus petit entier positif tel que . Pour y parvenir, l'algorithme de Shor utilise un circuit quantique impliquant deux registres. Le deuxième registre utilise des qubits, où est le plus petit entier tel que , c'est-à-dire . La taille du premier registre détermine la précision de l'approximation produite par le circuit. On peut montrer que l'utilisation de qubits donne une précision suffisante pour trouver . Le circuit quantique exact dépend des paramètres et , qui définissent le problème. La description suivante de l'algorithme utilise la notation bra–ket pour désigner les états quantiques et pour désigner le produit tensoriel , plutôt que le ET logique .

L'algorithme se compose de deux étapes principales :

1. Utiliser l'estimation de phase quantique avec unitaire représentant l'opération de multiplication par (modulo ), et l'état d'entrée (où le second registre est constitué de qubits). Les valeurs propres de celui-ci codent des informations sur la période, et peuvent être considérées comme inscriptibles comme une somme de ses vecteurs propres. Grâce à ces propriétés, l'étape d'estimation de phase quantique donne en sortie un entier aléatoire de la forme pour random .
2. Utilisez l' algorithme des fractions continues pour extraire la période des résultats de mesure obtenus à l'étape précédente. Il s'agit d'une procédure permettant de post-traiter (avec un ordinateur classique) les données de mesure obtenues à partir de la mesure des états quantiques de sortie et de récupérer la période.

Le lien avec l'estimation de phase quantique n'a pas été discuté dans la formulation originale de l'algorithme de Shor, mais a été proposé plus tard par Kitaev.

En général, l' algorithme d'estimation de phase quantique , pour tout état propre unitaire tel que , envoie des états d'entrée vers des états de sortie proches de , où est une superposition d'entiers proches de . En d'autres termes, il envoie chaque état propre de vers un état contenant des informations proches de la valeur propre associée. Aux fins de la recherche d'ordre quantique, nous utilisons cette stratégie en utilisant l'état unitaire défini par l'action L'action de sur les états avec n'est pas cruciale pour le fonctionnement de l'algorithme, mais doit être incluse pour garantir que la transformation globale est une porte quantique bien définie. La mise en œuvre du circuit d'estimation de phase quantique avec nécessite de pouvoir implémenter efficacement les portes . Cela peut être accompli via l'exponentiation modulaire , qui est la partie la plus lente de l'algorithme. La porte ainsi définie satisfait , ce qui implique immédiatement que ses valeurs propres sont les racines -ièmes de l'unité . De plus, chaque valeur propre possède un vecteur propre de la forme , et ces vecteurs propres sont tels que où la dernière identité découle de la formule de la série géométrique , ce qui implique .

L'utilisation de l'estimation de phase quantique sur un état d'entrée renverrait alors l'entier avec une probabilité élevée. Plus précisément, le circuit d'estimation de phase quantique envoie à tel que la distribution de probabilité résultante soit plafonnée autour de , avec . Cette probabilité peut être rendue arbitrairement proche de 1 en utilisant des qubits supplémentaires.

En appliquant le raisonnement ci-dessus à l'entrée , l'estimation de phase quantique aboutit ainsi à l'évolution. En mesurant le premier registre, nous avons maintenant une probabilité équilibrée de trouver chaque , chacun donnant une approximation entière de , qui peut être divisée par pour obtenir une approximation décimale pour .

Ensuite, nous appliquons l' algorithme des fractions continues pour trouver les entiers et , où donne la meilleure approximation de fraction pour l'approximation mesurée à partir du circuit, pour et premiers entre eux et . Le nombre de qubits dans le premier registre, , qui détermine la précision de l'approximation, garantit que la meilleure approximation à partir de la superposition de a été mesurée (ce qui peut être rendu arbitrairement probable en utilisant des bits supplémentaires et en tronquant la sortie). Cependant, alors que et sont premiers entre eux, il se peut que et ne le soient pas. À cause de cela, et peut avoir perdu certains facteurs qui étaient dans et . Cela peut être corrigé en réexécutant la sous-routine de recherche d'ordre quantique un nombre arbitraire de fois, pour produire une liste d'approximations de fraction où est le nombre de fois que la sous-routine a été exécutée. Chacun aura des facteurs différents supprimés car le circuit aura (probablement) mesuré plusieurs valeurs possibles différentes de . Pour récupérer la valeur réelle , nous pouvons prendre le plus petit multiple commun de chaque : Le plus petit multiple commun sera l'ordre de l'entier d'origine avec une probabilité élevée. En pratique, une seule exécution de la sous-routine de recherche d'ordre quantique est en général suffisante si un post-traitement plus avancé est utilisé.

L'estimation de phase nécessite de choisir la taille du premier registre pour déterminer la précision de l'algorithme, et pour la sous-routine quantique de l'algorithme de Shor, les qubits suffisent à garantir que la chaîne de bits optimale mesurée à partir de l'estimation de phase (ce qui signifie que où est l'approximation la plus précise de la phase à partir de l'estimation de phase) permettra de récupérer la valeur réelle de .

Chaque mesure précédente dans l'algorithme de Shor représente une superposition d'entiers se rapprochant de . Soit représente l'entier le plus optimal dans . Le théorème suivant garantit que l'algorithme des fractions continues se rétablira de :

Comme la chaîne de bits optimale issue de l'estimation de phase est précise au bit près, cela implique que l'algorithme des fractions continues récupérera et (ou avec leur plus grand diviseur commun retiré).

Le goulot d'étranglement du temps d'exécution de l'algorithme de Shor est l'exponentiation modulaire quantique , qui est de loin plus lente que la transformée de Fourier quantique et le pré-/post-traitement classique. Il existe plusieurs approches pour construire et optimiser des circuits pour l'exponentiation modulaire. L'approche la plus simple et (actuellement) la plus pratique consiste à imiter les circuits arithmétiques conventionnels avec des portes réversibles , en commençant par des additionneurs à ondulation de retenue . Connaître la base et le module d'exponentiation facilite d'autres optimisations. Les circuits réversibles utilisent généralement l'ordre des portes pour les qubits. D'autres techniques améliorent asymptotiquement le nombre de portes en utilisant des transformées de Fourier quantiques , mais ne sont pas compétitives avec moins de 600 qubits en raison de constantes élevées.

Les algorithmes de Shor pour le problème du logarithme discret et le problème de recherche d'ordre sont des exemples d'un algorithme résolvant le problème de recherche de période. . Tous trois sont des exemples du problème du sous-groupe caché .

Étant donné un groupe d'ordre et de générateur , supposons que nous sachions que , pour un certain , et que nous souhaitions calculer , qui est le logarithme discret : . Considérons le groupe abélien , où chaque facteur correspond à l'addition modulaire de valeurs. Considérons maintenant la fonction

Cela nous donne un problème de sous-groupe caché abélien , où correspond à un homomorphisme de groupe . Le noyau correspond aux multiples de . Donc, si nous pouvons trouver le noyau, nous pouvons trouver . Il existe un algorithme quantique pour résoudre ce problème. Cet algorithme est, comme l'algorithme de recherche de facteurs, dû à Peter Shor et les deux sont implémentés en créant une superposition en utilisant des portes de Hadamard, suivie d'une implémentation sous forme de transformation quantique, suivie enfin d'une transformation de Fourier quantique. De ce fait, l'algorithme quantique de calcul du logarithme discret est également parfois appelé « algorithme de Shor ».

Le problème de recherche d'ordre peut également être considéré comme un problème de sous-groupe caché. Pour voir cela, considérons le groupe d'entiers sous addition, et pour un donné tel que : , la fonction

Pour tout groupe abélien fini , il existe un algorithme quantique permettant de résoudre le sous-groupe caché en temps polynomial.