L'algorithme de Shor

Pour ce module Qiskit en classe, les étudiants doivent disposer d'un environnement Python fonctionnel avec les packages suivants installés :

• qiskit v2.1.0 ou plus récent
• qiskit-ibm-runtime v0.40.1 ou plus récent
• qiskit-aer v0.17.0 ou plus récent
• qiskit.visualization
• numpy
• pylatexenc

Pour configurer et installer les packages ci-dessus, consulte le guide Installer Qiskit. Pour exécuter des jobs sur de vrais ordinateurs quantiques, les étudiants devront créer un compte IBM Quantum® en suivant les étapes du guide Configurer ton compte IBM Cloud.

Ce module a été testé et a utilisé trois secondes de temps QPU. Il s'agit d'une estimation uniquement. Ton utilisation réelle peut varier.

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

Introduction

Au début des années 1990, un enthousiasme croissant entourait le potentiel des ordinateurs quantiques à résoudre des problèmes difficiles pour les ordinateurs classiques. Quelques informaticiens talentueux avaient mis au point des algorithmes illustrant la puissance du calcul quantique pour des problèmes de niche artificiels, mais personne n'avait trouvé une seule "application phare" du calcul quantique qui révolutionnerait à coup sûr le domaine. Ce fut le cas jusqu'en 1994, lorsque Peter Shor mit au point ce qu'on appelle aujourd'hui l'algorithme de Shor pour factoriser de grands nombres.

Il était bien connu à l'époque que trouver les facteurs premiers d'un grand nombre était extrêmement difficile pour un ordinateur classique. En fait, les protocoles de sécurité sur internet reposaient sur cette difficulté. Shor a trouvé un moyen de trouver ces facteurs de manière exponentiellement plus efficace en confiant certaines des étapes les plus délicates à un futur ordinateur quantique théorique.

Dans ce module, nous allons explorer l'algorithme de Shor. D'abord, nous donnerons un peu plus de contexte à l'algorithme, en formalisant le problème qu'il résout et en expliquant la pertinence pour la cybersécurité. Ensuite, nous donnerons un aperçu des mathématiques modulaires et de leur application au problème de factorisation, en montrant comment la factorisation se réduit à un autre problème appelé « recherche d'ordre ». Nous verrons comment la Transformée de Fourier Quantique et l'Estimation de Phase Quantique, étudiées dans un module précédent, entrent en jeu, et comment les utiliser pour résoudre le problème de recherche d'ordre.

Enfin, nous exécuterons l'algorithme de Shor sur un vrai ordinateur quantique ! Garde à l'esprit, cependant, que cet algorithme ne sera vraiment utile que lorsque nous disposerons d'un grand ordinateur quantique tolérant aux pannes, ce qui est encore à quelques années de nous. Nous allons donc simplement factoriser un petit nombre pour illustrer le fonctionnement de l'algorithme.

Le problème de factorisation

L'objectif du problème de factorisation est de trouver les facteurs premiers d'un nombre $N$. Pour certains nombres $N$, c'est assez simple. Par exemple, si $N$ est pair, l'un de ses facteurs premiers sera 2. Si $N$ est une puissance d'un premier, c'est-à-dire $N=p^k$ pour un certain nombre premier $p$, il est également assez facile de trouver $p$ : on approxime la $k^{\text{ième}}$ racine de $N$ et on cherche des nombres premiers proches qui pourraient être $p$.

Là où les ordinateurs classiques peinent, c'est lorsque $N$ est impair et n'est pas une puissance d'un premier. C'est le cas que traite l'algorithme de Shor. L'algorithme trouve deux facteurs $p$ et $q$ tels que $N=pq$. Il peut être appliqué récursivement jusqu'à ce que tous les facteurs soient premiers. Dans les sections suivantes, nous verrons comment ce problème est abordé.

Pertinence pour la cybersécurité

De nombreux schémas cryptographiques ont été construits sur le fait que la factorisation de grands nombres est difficile, notamment un schéma couramment utilisé aujourd'hui, appelé RSA. Dans RSA, une clé publique est créée en multipliant deux grands nombres premiers pour obtenir $N = p\cdot q$. Ensuite, n'importe qui peut utiliser cette clé publique pour chiffrer des données. Mais seule une personne disposant de la clé privée, $p$ et $q$, peut déchiffrer ces données.

Si $N$ était facile à factoriser, alors n'importe qui pourrait déterminer $p$ et $q$ et casser le chiffrement. Mais ce n'est pas le cas. C'est un problème notoirement difficile. En fait, les facteurs premiers d'un nombre appelé RSA1024, qui fait 1024 chiffres binaires et 309 chiffres décimaux, n'ont toujours pas été trouvés, malgré un prix de $100 000 offert pour sa factorisation dès 1991.

La solution de Shor

En 1994, Peter Shor a réalisé qu'un ordinateur quantique pouvait factoriser un grand nombre de manière exponentiellement plus efficace qu'un ordinateur classique. Son intuition reposait sur la relation entre ce problème de factorisation et l'arithmétique modulaire. Nous allons faire un bref rappel sur l'arithmétique modulaire, puis nous verrons comment l'utiliser pour factoriser $N$.

Arithmétique modulaire

L'arithmétique modulaire est un système de comptage cyclique, c'est-à-dire que si le comptage commence de la manière habituelle, avec les entiers 0, 1, 2, etc., à un certain moment, après une période $N$, le comptage recommence depuis le début. Voyons comment cela fonctionne avec un exemple. Supposons que notre période soit 5. Alors, en comptant, là où on atteindrait normalement 5, on repart à 0 :

$0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, ...$

C'est parce que dans le monde « modulo-5 », 5 est équivalent à 0. On dit que $5\bmod 5 \ = 0$. En fait, tous les multiples de 5 seront équivalents à $0\bmod 5$.

Vérifie ta compréhension

Lis la ou les questions ci-dessous, réfléchis à ta réponse, puis clique sur le triangle pour révéler la solution.

Utilise l'arithmétique modulaire pour résoudre le problème suivant :

Tu pars pour un long voyage en train transcontinental à 8h. Le trajet dure 60 heures. À quelle heure arrives-tu ?

Réponse :

La période est 24, puisqu'il y a 24 heures dans une journée. Donc, ce problème peut s'écrire en arithmétique modulaire comme :

$(8+60)\text{mod}(24) = 20$

Donc, tu arriverais à destination à 20h00.

$\mathbb{Z}_N$ et $\mathbb{Z}_N^*$

Il est souvent utile d'introduire deux ensembles, $\mathbb{Z}_N$ et $\mathbb{Z}_N^*$. $\mathbb{Z}_N$ est simplement l'ensemble des nombres qui existent dans un monde « modulo-$N$ ». Par exemple, quand on comptait modulo-5, l'ensemble serait $\mathbb{Z}_5=\{0,1,2,3,4\}$. Autre exemple : $\mathbb{Z}_{15} = \{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14\}$. On peut effectuer des additions et des multiplications (modulo $N$) sur les éléments de $\mathbb{Z}_N$, et le résultat de chacune de ces opérations est également un élément de $\mathbb{Z}_N$, ce qui fait de $\mathbb{Z}_N$ un objet mathématique appelé anneau.

Il existe un sous-ensemble particulier de $\mathbb{Z}_N$ qui nous intéresse tout particulièrement pour l'algorithme de Shor. C'est le sous-ensemble des nombres de $\mathbb{Z}_N$ tels que le plus grand diviseur commun entre chaque élément et $N$ est 1, donc chaque élément est « co-premier » avec $N$. Si on prend l'ensemble de ces nombres avec l'opération de multiplication modulaire, on obtient un autre objet mathématique appelé groupe. On appelle ce groupe $\mathbb{Z}_N^*$. Il s'avère qu'avec $\mathbb{Z}_N^*$ (et les groupes finis en général), si on choisit n'importe quel élément $a \in \mathbb{Z}_N^*$ et qu'on multiplie $a$ par lui-même de façon répétée, on finira toujours par obtenir le nombre $1$. Le nombre minimal de fois qu'il faut multiplier $a$ par lui-même pour obtenir $1$ est appelé l'ordre de $a$. Ce fait sera très important pour notre discussion sur la façon de factoriser des nombres ci-dessous.

Vérifie ta compréhension

Lis la ou les questions ci-dessous, réfléchis à ta réponse, puis clique sur le triangle pour révéler la solution.

Quel est $\mathbb{Z}_{15}^*$ ?

Réponse :

$\mathbb{Z}_{15}^* = \{1,2,4,7,8,11,13,14\}$

Nous avons exclu les nombres suivants :

$$\begin{aligned} 3: PGCD(3,15)=3 \\ 5: PGCD(5,15)=5 \\ 6: PGCD(6,15)=3 \\ 9: PGCD(9,15)=3 \\ 10: PGCD(10,15)=5 \\ 12: PGCD(12,15)=3 \\ \end{aligned}$$

Quel est l'ordre de chacun des éléments de $\mathbb{Z}_{15}^*$ ?

Réponse :

L'ordre $r$ est le plus petit nombre tel que $a^r\text{mod}(15)=1$ pour chaque élément $a$.

$$\begin{aligned} 1^1\text{mod}(15) = 1, r=1 \\ 2^4\text{mod}(15) = 1, r=4 \\ 4^2\text{mod}(15) = 1, r=2 \\ 7^4\text{mod}(15) = 1, r=4 \\ 8^4\text{mod}(15) = 1, r=4 \\ 11^2\text{mod}(15) = 1, r=2 \\ 13^4\text{mod}(15) = 1, r=4 \\ 14^2\text{mod}(15) = 1, r=2 \\ \end{aligned}$$

Remarque que, bien que nous ayons pu trouver l'ordre des nombres dans $\mathbb{Z}_{15}^*$, ce n'est PAS une tâche facile en général, pour des $N$ plus grands. C'est là le nœud du problème de factorisation et la raison pour laquelle nous avons besoin d'un ordinateur quantique. Nous verrons pourquoi en parcourant le reste du cahier de travail.

Appliquer l'arithmétique modulaire au problème de factorisation

La clé pour trouver les facteurs $p$ et $q$ tels que $N=pq$ revient à trouver un autre entier $x$ tel que

$x^2 \equiv 1 \bmod N$ et $x \not\equiv \pm 1 \bmod N.$

Comment trouver $x$ nous aide-t-il à trouver les facteurs $p$ et $q$ ? Déroulons l'argument maintenant. Puisque $x^2 \equiv 1 \bmod N$, cela signifie que $x^2 - 1 \equiv 0 \bmod N$. En d'autres termes, $x^2 - 1$ est un multiple de $N$. Donc, pour un certain entier $l$,

$x^2 - 1 = l N$

On peut factoriser $x^2 - 1$ pour obtenir :

$(x+1)(x-1) = l N$

D'après nos hypothèses initiales, nous savons que $x \not\equiv \pm 1 \bmod N$, donc $N$ ne divise pas exactement $x+1$ ni $x-1$. Ainsi, les deux facteurs de $N$, $p$ et $q$, doivent chacun diviser $x-1$ et $x+1$. Soit $p$ est un facteur de $x-1$ et $q$ est un facteur de $x+1$, soit l'inverse. Par conséquent, si on calcule les plus grands diviseurs communs (PGCD) entre $N$ et $x-1$ d'une part, et $x+1$ d'autre part, on obtiendra les facteurs $p$ et $q$. Calculer le PGCD entre deux nombres est une tâche classiquement facile qui peut être accomplie, par exemple, à l'aide de l'algorithme d'Euclide.

Vérifie ta compréhension

Lis la ou les questions ci-dessous, réfléchis à ta réponse, puis clique sur le triangle pour révéler la solution.

Chaque étape du raisonnement ci-dessus peut être difficile à suivre, alors essaie de la dérouler avec un exemple. Utilise $N=15$ et $x=11$. D'abord, vérifie que $x^2 \equiv 1 \text{mod}(N)$ et $x \not\equiv \pm 1 \bmod N$. Puis continue à vérifier chaque étape. Enfin, calcule $\text{PGCD}(11\pm1,15)$ et vérifie que ce sont bien les facteurs de $15$.

Réponse :

$11^2 = 121$, ce qui vaut $15*8 + 1$, donc $11^2\bmod 15 = 1$. $\checkmark$

$11 - 1 = 10$, qui n'est pas équivalent à $0\bmod 15$. $\checkmark$

$11 + 1 = 12$, qui n'est pas équivalent à $0\bmod 15$. $\checkmark$

Maintenant, on sait que $(x+1)(x-1) = l N$ pour un certain entier $l$. Ceci est vérifié en remplaçant $x$ et $N$ : $(12)(10) = l 15$ quand $l = 8$. $\checkmark$

Maintenant, il faut calculer $\text{PGCD}(12,15)$ et $\text{PGCD}(10,15)$.

$$\begin{aligned} \text{PGCD}(12,15) = 3 \\ \text{PGCD}(10,15) = 5 \end{aligned}$$

Nous avons donc trouvé les facteurs de $15$ !

L'algorithme

Maintenant que nous avons vu comment trouver un entier $x$ tel que $x^2 \equiv 1\bmod N$ nous aide à factoriser $N$, nous pouvons parcourir l'algorithme de Shor. Il se résume essentiellement à trouver $x$ :

1. Choisir un entier aléatoire Choisis un entier aléatoire $a$ tel que $1 < a < N$.

• Calcule $\text{PGCD}(a, N)$ de manière classique.
  • Si $\text{PGCD}(a, N) > 1$, tu as déjà trouvé un facteur. Arrête-toi.
  • Sinon, continue.

2. Trouver l'ordre $r$ de $a$ modulo $N$ Trouve le plus petit entier positif $r$ qui satisfait $a^r \equiv 1 \pmod N$.

3. Vérifier si l'ordre est pair

• Si $r$ est impair, reviens à l'étape 1 et choisis un nouveau $a$.
• Si $r$ est pair, passe à l'étape 4.

4. Calculer $x = a^{r/2} \bmod N$

• Vérifie que $x \not\equiv 1 \pmod N$ et $x \not\equiv -1 \pmod N$.
  • Si $x \equiv \pm 1 \pmod N$, reviens à l'étape 1 et choisis un nouveau $a$.
• Sinon, calcule les PGCD pour extraire les facteurs :

$$p = \text{PGCD}(x-1, N), \quad q = \text{PGCD}(x+1, N)$$

Ce seront des facteurs non triviaux de $N$.

5. Factoriser récursivement si nécessaire

• Si $p$ et/ou $q$ ne sont pas premiers, applique l'algorithme récursivement pour les factoriser complètement.
• Une fois tous les facteurs premiers, la factorisation est terminée.

Sur la base de cette procédure, il n'est peut-être pas évident de voir pourquoi un ordinateur quantique est nécessaire pour accomplir cette tâche. C'est nécessaire parce que l'étape 2, trouver l'ordre de $a$ modulo $N$, est classiquement un problème très difficile. La complexité croît de façon exponentielle avec le nombre $N$. Mais avec un ordinateur quantique, il suffit d'utiliser l'Estimation de Phase Quantique pour le résoudre. L'étape 4, trouver le PGCD de deux entiers, est en fait assez facile à faire classiquement. Donc, la seule étape qui a réellement besoin de la puissance d'un ordinateur quantique est l'étape de recherche d'ordre. On dit que le problème de factorisation « se réduit » au problème de recherche d'ordre.

La partie difficile : la recherche d'ordre

Maintenant, nous allons voir comment utiliser un ordinateur quantique pour la recherche d'ordre. D'abord, précisons ce qu'on entend par « ordre ». Bien sûr, je t'ai déjà dit ce que l'ordre signifie mathématiquement : c'est le premier entier non nul $r$ tel que $a^r = 1 \pmod N.$ Mais voyons si on peut développer un peu plus l'intuition pour ce concept.

Pour des $N$ suffisamment petits, on peut simplement déterminer l'ordre en calculant chaque puissance de $a$, en prenant le modulo $N$ de ce nombre, puis en s'arrêtant lorsqu'on trouve la puissance $r$ qui satisfait $a^r = 1 \text{mod}(N)$. C'est ce qu'on a fait avec notre exemple, $N=15$, ci-dessus. Regardons quelques graphiques de ces puissances modulaires pour quelques valeurs exemples de $a$ et $N$ :

Tu remarques quelque chose ? Ce sont des fonctions périodiques ! Et l'ordre $r$ est le même que la période ! Donc, la recherche d'ordre est équivalente à la recherche de période.

Les ordinateurs quantiques sont très bien adaptés pour trouver la période de fonctions. Pour cela, on peut utiliser une sous-routine algorithmique appelée Estimation de Phase Quantique. Nous avons abordé QPE et sa relation avec la Transformée de Fourier Quantique dans le module précédent. Pour un rappel détaillé, consulte le module QFT ou la leçon de John Watrous sur l'Estimation de Phase Quantique dans son cours sur les algorithmes quantiques. Voici l'essentiel de la procédure :

Dans l'Estimation de Phase Quantique (QPE), on commence avec un unitaire $U$ et un état propre de cet unitaire $|\psi\rangle$. Ensuite, on utilise QPE pour approximer la valeur propre correspondante, qui, puisque l'opérateur est unitaire, sera de la forme $e^{2\pi i \theta}$. Ainsi, trouver la valeur propre est équivalent à trouver la valeur de $\theta$ dans la fonction périodique. Le circuit ressemble à ceci :

où le nombre de qubits de contrôle (les $m$ qubits du haut dans la figure ci-dessus) détermine la précision de l'approximation.

Dans l'algorithme de Shor, on utilise QPE sur l'opérateur unitaire $M_a$ :

$M_a|y\rangle \equiv |ay \mod N \rangle .$

Ici, $|y\rangle$ désigne un état de base computationnel du registre multi-qubit, où la valeur binaire des qubits correspond à l'entier $y$. Par exemple, si $N=15$ et $y = 2$, alors $|y\rangle$ est représenté par l'état de base à quatre qubits $|0010\rangle$, puisque quatre qubits sont nécessaires pour encoder les nombres jusqu'à 15. (Si ce concept n'est pas familier, consulte le module introductif Qiskit en classe pour un rappel sur l'encodage binaire des états quantiques.)

Maintenant, il faut trouver un état propre de cet unitaire. Si on commence dans l'état $|1\rangle$, on peut voir que chaque application successive de $U$ multipliera l'état de notre registre par $a \pmod N$, et après $r$ applications, on reviendra à l'état $|1\rangle$. Par exemple avec $a = 3$ et $N = 35$ :

$$\begin{aligned} M_3|1\rangle &= |3\rangle & \\ M_3^2|1\rangle &= |9\rangle \\ M_3^3|1\rangle &= |27\rangle \\ & \vdots \\ M_3^{(r-1)}|1\rangle &= |12\rangle \\ M_3^r|1\rangle &= |1\rangle \end{aligned}$$

Donc les superpositions des états dans ce cycle ($|\psi_j\rangle$) de la forme :

$|\psi_j\rangle = \tfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}{e^{\frac{2 \pi i j k}{r}} |a^k \rangle}$

sont toutes des états propres de $M_a$. (Il y a plus d'états propres que ceux-là. Mais nous ne nous intéressons qu'à ceux de la forme ci-dessus.)

Vérifie ta compréhension

Lis la ou les questions ci-dessous, réfléchis à ta réponse, puis clique sur le triangle pour révéler la solution.

Trouve un état propre de l'unitaire correspondant à $a=2$ et $N = 15$.

Réponse :

$$\begin{aligned} M_2|1\rangle &= |2\rangle & \\ M_2^2|1\rangle &= |4\rangle \\ M_2^3|1\rangle &= |8\rangle \\ M_2^4|1\rangle &= |1\rangle \\ \end{aligned}$$

Donc, l'ordre $r=4$. Les états propres qui nous intéressent seront une superposition égale de tous les états parcourus ci-dessus, avec diverses phases :

$$\begin{aligned} |\psi_0\rangle &= \frac{1}{2}(|1\rangle+|2\rangle+|4\rangle+|8\rangle) \\ |\psi_1\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{1}{4}}|2\rangle+e^{2 \pi i \frac{2}{4}}|4\rangle+e^{2 \pi i \frac{3}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle+i|2\rangle-|4\rangle-i|8\rangle) \\ |\psi_2\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{2}{4}}|2\rangle+e^{2 \pi i \frac{4}{4}}|4\rangle+e^{2 \pi i \frac{6}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle-|2\rangle+|4\rangle-|8\rangle) \\ |\psi_3\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{3}{4}}|2\rangle+e^{2 \pi i \frac{6}{4}}|4\rangle+e^{2 \pi i \frac{9}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ \end{aligned}$$

Supposons que nous puissions initialiser notre état de qubit dans l'un de ces états propres (spoiler — ce n'est pas le cas. Ou du moins, pas facilement. Nous expliquerons pourquoi et ce que nous pouvons faire à la place sous peu). Nous pourrions alors utiliser QPE pour estimer la valeur propre correspondante, $\omega_j = e^{2 \pi i \theta_j}$ où $\theta_j = \frac{j}{r}$. Ensuite, nous pourrons déterminer l'ordre $r$ par la simple équation :

$r = \frac{j}{\theta_j}.$

Mais rappelle-toi, j'ai dit que QPE estime $\theta_j$ — il ne nous donne pas une valeur exacte. Il faut que l'estimation soit suffisamment bonne pour différencier $r$ de $r+1$. Plus on a de qubits de contrôle $m$, meilleure sera l'estimation. Dans les exercices à la fin de la leçon, on te demandera de déterminer le $m$ minimum nécessaire pour factoriser un nombre $N$.

Maintenant, nous devons résoudre un problème. Toute l'explication ci-dessus sur la façon de trouver $r$ commence par la préparation de l'état propre $|\psi_j\rangle = \tfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}{e^{\frac{2 \pi i j k}{r}} |a^k \rangle}$. Mais nous ne savons pas comment faire cela sans déjà connaître $r$. Le raisonnement est circulaire. Nous avons besoin d'un moyen d'estimer la valeur propre sans initialiser l'état propre.

Au lieu de commencer avec un état propre de $M_a$, on peut préparer l'état initial dans l'état à $n$ qubits correspondant à $|1\rangle$ en binaire (c'est-à-dire $|000...01\rangle$). Bien que cet état lui-même ne soit évidemment pas un état propre de $M_a$, il est une superposition de tous les états propres $|\psi_k\rangle$ :

$|1\rangle = \frac{1}{\sqrt{r}} \sum\limits_{k=0}^{r-1}{|\psi_k\rangle}$

Vérifie ta compréhension

Lis la ou les questions ci-dessous, réfléchis à ta réponse, puis clique sur le triangle pour révéler la solution.

Vérifie que $|1\rangle$ est équivalent à la superposition sur les états propres que tu as trouvés pour $N=15$ et $a=2$ dans la question de vérification précédente.

Réponse :

Les quatre états propres étaient :

$$\begin{aligned} |\psi_0\rangle &= \frac{1}{2}(|1\rangle+|2\rangle+|4\rangle+|8\rangle) \\ |\psi_1\rangle &= \frac{1}{2}(|1\rangle+i|2\rangle-|4\rangle-i|8\rangle) \\ |\psi_2\rangle &= \frac{1}{2}(|1\rangle-|2\rangle+|4\rangle-|8\rangle) \\ |\psi_3\rangle &= \frac{1}{2}(|1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ \end{aligned}$$

Donc,

$$\begin{aligned} \frac{1}{\sqrt{r}} \sum\limits_{k=0}^{r-1}{|\psi_k\rangle} &= \frac{1}{2}(|\psi_0\rangle + |\psi_1\rangle + |\psi_2\rangle + |\psi_3\rangle ) \\ &= \frac{1}{4}(|1\rangle+|2\rangle+|4\rangle+|8\rangle+|1\rangle+i|2\rangle-|4\rangle-i|8\rangle+|1\rangle-|2\rangle+|4\rangle-|8\rangle + |1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ &= \frac{1}{4}(4|1\rangle) = |1\rangle \end{aligned}$$

Comment cela nous permet-il de trouver l'ordre $r$ ? Puisque l'état de départ est une superposition de tous les états propres de la forme listée ci-dessus, l'algorithme QPE estime simultanément chacun des $\theta_k$ correspondant à ces états propres. Ainsi, la mesure des $m$ qubits de contrôle à la fin donnera une approximation de la valeur $k/r$ où $k \in \{0,1,2,...,r-1\}$ est l'une des valeurs propres choisie aléatoirement. Si on répète ce circuit quelques fois et qu'on obtient quelques échantillons avec différentes valeurs de $k$, on sera rapidement en mesure de déduire $r$.

Implémenter dans Qiskit

Comme nous l'avons mentionné précédemment, notre matériel n'est pas encore au point pour factoriser de grands nombres comme RSA1024. Nous allons simplement factoriser un petit nombre pour illustrer le fonctionnement de l'algorithme. Pour cette démo, nous utiliserons une version simplifiée du code présenté dans le tutoriel sur l'algorithme de Shor. Pour plus de détails, consulte le tutoriel.

Nous allons exécuter l'algorithme en utilisant notre cadre standard pour résoudre les problèmes quantiques, appelé le cadre Qiskit patterns. Il se compose de quatre étapes :

1. Mapper ton problème à un circuit quantique
2. Optimiser le circuit pour l'exécuter sur du matériel quantique
3. Exécuter ton circuit sur l'ordinateur quantique
4. Post-traiter les mesures

1. Mapper

Factorisons $N=15$, en choisissant $a=2$ comme entier co-premier.

D'abord, il faut construire le circuit qui implémentera l'unitaire de multiplication modulaire, $M_a$. C'est en fait la partie la plus délicate de toute l'implémentation, et cela peut être très coûteux en calcul, selon la façon dont c'est fait. Pour cela, nous allons tricher un peu : nous savons que nous commençons dans l'état $|1\rangle$, et d'après une question de vérification précédente,

$$\begin{aligned} M_2|1\rangle &= |2\rangle & \\ M_2|2\rangle &= |4\rangle \\ M_2|4\rangle &= |8\rangle \\ M_2|8\rangle &= |1\rangle \\ \end{aligned}$$

Donc, nous allons construire un unitaire qui effectue les bonnes opérations sur ces quatre états, mais laisse tous les autres états inchangés. C'est de la triche parce que nous utilisons notre connaissance de l'ordre de $2\bmod 15$ pour simplifier l'unitaire. Si nous essayions réellement de factoriser un nombre dont les facteurs nous sont inconnus, nous ne pourrions pas faire cela.

Vérifie ta compréhension

Lis la ou les questions ci-dessous, réfléchis à ta réponse, puis clique sur le triangle pour révéler la solution.

Avec ta connaissance de la façon dont l'opérateur $M_2$ transforme les états ci-dessus, construis l'opérateur à partir d'une série de portes SWAP, qui échangent les états de deux Qubits. (Indice : écrire chaque état $|i\rangle$ en binaire aidera.)

Réponse :

Réécrivons l'action de $M_2$ sur les états en binaire :

$$\begin{aligned} M_2|0001\rangle &= |0010\rangle \\ M_2|0010\rangle &= |0100\rangle \\ M_2|0100\rangle &= |1000\rangle \\ M_2|1000\rangle &= |0001\rangle \\ \end{aligned}$$

Chacune de ces actions peut être accomplie avec un simple SWAP. $M_2|0001\rangle$ est obtenu en échangeant les états du qubit $0$ et $1$. $M_2|0010\rangle$ est obtenu en échangeant les états du qubit $1$ et $2$. Et ainsi de suite. Donc, on peut décomposer la matrice $M_2$ en la série de portes SWAP suivante :

$$M_2 = SWAP(0,1)SWAP(1,2)SWAP(2,3)$$

En se rappelant que les opérateurs agissent de droite à gauche, vérifions que cela a l'effet souhaité sur chacun des états :

$$\begin{aligned} M_2|0001\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0001\rangle \\ &= SWAP(0,1)SWAP(1,2)|0001\rangle \\ &= SWAP(0,1)|0001\rangle \\ &=|0010\rangle \checkmark \\ M_2|0010\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0010\rangle \\ &= SWAP(0,1)SWAP(1,2)|0010\rangle \\ &= SWAP(0,1)|0100\rangle \\ &=|0100\rangle \checkmark \\ M_2|0100\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0100\rangle \\ &= SWAP(0,1)SWAP(1,2)|1000\rangle \\ &= SWAP(0,1)|1000\rangle \\ &=|1000\rangle \checkmark \\ M_2|1000\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|1000\rangle \\ &= SWAP(0,1)SWAP(1,2)|0100\rangle \\ &= SWAP(0,1)|0010\rangle \\ &=|0001\rangle \checkmark \\ \end{aligned}$$

Nous pouvons maintenant coder le circuit équivalent à cet opérateur dans Qiskit.

D'abord, nous importons les packages nécessaires :

# Import necessary packages

import numpy as np
from fractions import Fraction
from math import floor, gcd, log

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit.circuit.library import QFTGate
from qiskit.transpiler import generate_preset_pass_manager
from qiskit.visualization import plot_histogram

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import SamplerV2 as Sampler

Ensuite, nous créons l'opérateur $M_2$ :

def M2mod15():
    """
    M2 (mod 15)
    """
    b = 2
    U = QuantumCircuit(4)

    U.swap(2, 3)
    U.swap(1, 2)
    U.swap(0, 1)

    U = U.to_gate()
    U.name = f"M_{b}"

    return U

# Get the M2 operator
M2 = M2mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(4)
circ.compose(M2, inplace=True)
circ.decompose(reps=2).draw(output="mpl", fold=-1)

L'algorithme QPE utilise une porte $U$ contrôlée. Donc, maintenant que nous avons un circuit $M_2$, nous devons en faire un circuit contrôlé-$M_2$ :

def controlled_M2mod15():
    """
    Controlled M2 (mod 15)
    """
    b = 2
    U = QuantumCircuit(4)

    U.swap(2, 3)
    U.swap(1, 2)
    U.swap(0, 1)

    U = U.to_gate()
    U.name = f"M_{b}"
    c_U = U.control()

    return c_U

# Get the controlled-M2 operator
controlled_M2 = controlled_M2mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(5)
circ.compose(controlled_M2, inplace=True)
circ.decompose(reps=1).draw(output="mpl", fold=-1)

Nous avons maintenant notre porte $U$ contrôlée. Mais pour exécuter l'algorithme d'Estimation de Phase Quantique, il nous faudra le $U^2$ contrôlé, le $U^4$ contrôlé, jusqu'au $U^{2^{m-1}}$ contrôlé, où $m$ est le nombre de qubits utilisés pour estimer la phase. Plus il y a de qubits, plus l'estimation de phase sera précise. Nous utiliserons $m=8$ qubits de contrôle pour notre procédure d'estimation de phase. Donc, il nous faut :

$$M_{a^{2^k}}|y\rangle \equiv |a^{2^k} y \bmod N \rangle$$

où l'indice $k$, avec $0 \le k \le m-1 = 7$, correspond au qubit de contrôle. Calculons maintenant $a^{2^k}\bmod N$ pour chaque valeur de $k$ :

def a2kmodN(a, k, N):
    """Compute a^{2^k} (mod N) by repeated squaring"""
    for _ in range(k):
        a = int(np.mod(a**2, N))
    return a

k_list = range(8)
b_list = [a2kmodN(2, k, 15) for k in k_list]

print(b_list)

[2, 4, 1, 1, 1, 1, 1, 1]

Puisque $a^{2^k} \bmod N = 1$ pour $k \ge 2$, tous les opérateurs correspondants ($M_8$ et au-delà) sont équivalents à l'identité. Donc, nous n'avons besoin de construire qu'une seule matrice supplémentaire, $M_4.$

Remarque : Cette simplification ne fonctionne ici que parce que l'ordre de $2 \bmod 15$ est $4$. Une fois que $k=2$ (donc $2^k = 4$), chaque puissance suivante de l'opérateur est l'identité. En général, pour des nombres $N$ plus grands ou des choix différents de $a$, on ne peut pas éviter de construire les puissances supérieures. C'est l'une des raisons pour lesquelles ceci est considéré comme un exemple jouet : les petits nombres permettent des raccourcis qui ne fonctionneraient pas pour des cas plus grands.

def M4mod15():
    """
    M4 (mod 15)
    """
    b = 4
    U = QuantumCircuit(4)

    U.swap(1, 3)
    U.swap(0, 2)

    U = U.to_gate()
    U.name = f"M_{b}"

    return U

# Get the M4 operator
M4 = M4mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(4)
circ.compose(M4, inplace=True)
circ.decompose(reps=2).draw(output="mpl", fold=-1)

Et comme précédemment, nous en faisons un opérateur contrôlé-$M_4$ :

def controlled_M4mod15():
    """
    Controlled M4 (mod 15)
    """
    b = 4
    U = QuantumCircuit(4)

    U.swap(1, 3)
    U.swap(0, 2)

    U = U.to_gate()
    U.name = f"M_{b}"
    c_U = U.control()

    return c_U

# Get the controlled-M4 operator
controlled_M4 = controlled_M4mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(5)
circ.compose(controlled_M4, inplace=True)
circ.decompose(reps=1).draw(output="mpl", fold=-1)

Nous pouvons maintenant tout assembler pour trouver l'ordre de $2\bmod 15$ avec un circuit quantique, en utilisant l'estimation de phase :

# Order finding problem for N = 15 with a = 2
N = 15
a = 2

# Number of qubits
num_target = floor(log(N - 1, 2)) + 1  # for modular exponentiation operators
num_control = 2 * num_target  # for enough precision of estimation

# List of M_b operators in order
k_list = range(num_control)
b_list = [a2kmodN(2, k, 15) for k in k_list]

# Initialize the circuit
control = QuantumRegister(num_control, name="C")
target = QuantumRegister(num_target, name="T")
output = ClassicalRegister(num_control, name="out")
circuit = QuantumCircuit(control, target, output)

# Initialize the target register to the state |1>
circuit.x(num_control)

# Add the Hadamard gates and controlled versions of the
# multiplication gates
for k, qubit in enumerate(control):
    circuit.h(k)
    b = b_list[k]
    if b == 2:
        circuit.compose(
            M2mod15().control(), qubits=[qubit] + list(target), inplace=True
        )
    elif b == 4:
        circuit.compose(
            M4mod15().control(), qubits=[qubit] + list(target), inplace=True
        )
    else:
        continue  # M1 is the identity operator

# Apply the inverse QFT to the control register
circuit.compose(QFTGate(num_control).inverse(), qubits=control, inplace=True)

# Measure the control register
circuit.measure(control, output)

circuit.draw("mpl", fold=-1)

2. Optimiser

Maintenant que nous avons mappé notre circuit, l'étape suivante consiste à l'optimiser pour l'exécuter sur un ordinateur quantique particulier. Il faut d'abord charger le backend.

service = QiskitRuntimeService()

backend = service.backend("ibm_marrakesh")

Si tu n'as pas de temps disponible sur ton compte ou que tu veux utiliser un simulateur pour quelque raison que ce soit, tu peux exécuter la cellule ci-dessous pour configurer un simulateur qui imitera le dispositif quantique que nous avons sélectionné ci-dessus :

pm = generate_preset_pass_manager(optimization_level=2, backend=backend)

transpiled_circuit = pm.run(circuit)

print(f"2q-depth: {transpiled_circuit.depth(lambda x: x.operation.num_qubits==2)}")
print(f"2q-size: {transpiled_circuit.size(lambda x: x.operation.num_qubits==2)}")
print(f"Operator counts: {transpiled_circuit.count_ops()}")
transpiled_circuit.draw(output="mpl", fold=-1, style="clifford", idle_wires=False)

2q-depth: 188
2q-size: 281
Operator counts: OrderedDict({'sx': 548, 'rz': 380, 'cz': 281, 'measure': 8, 'x': 6})

3. Exécuter

# Sampler primitive to obtain the probability distribution
sampler = Sampler(backend)

# Turn on dynamical decoupling with sequence XpXm
sampler.options.dynamical_decoupling.enable = True
sampler.options.dynamical_decoupling.sequence_type = "XpXm"
# Enable gate twirling
sampler.options.twirling.enable_gates = True

pub = transpiled_circuit
job = sampler.run([pub], shots=1024)

result = job.result()[0]
counts = result.data["out"].get_counts()

plot_histogram(counts, figsize=(35, 5))

Nous observons quatre pics clairs à 00000000, 01000000, 10000000 et 11000000, avec quelques comptages dans d'autres chaînes de bits dus au bruit de l'ordinateur quantique. Nous allons les ignorer et ne garder que les quatre dominants en imposant un seuil : seuls les comptages au-dessus de ce seuil sont considérés comme un vrai signal au-dessus du bruit.

# Dictionary of bitstrings and their counts to keep
counts_keep = {}
# Threshold to filter
threshold = np.max(list(counts.values())) / 2

for key, value in counts.items():
    if value > threshold:
        counts_keep[key] = value

print(counts_keep)

4. Post-traiter

Pour l'algorithme de Shor, une bonne partie de l'algorithme est effectuée de manière classique. Donc, nous allons mettre le reste dans l'étape de « post-traitement », après avoir obtenu nos mesures de l'ordinateur quantique. Chacune des mesures ci-dessus peut être convertie en entiers, qui, après division par $2^m$, sont nos approximations de $\frac{k}{r}$, où $k$ est aléatoire à chaque fois.

a = 2
N = 15

FACTOR_FOUND = False
num_attempt = 0

while not FACTOR_FOUND:
    print(f"\nATTEMPT {num_attempt}:")
    # Here, we get the bitstring by iterating over outcomes
    # of a previous hardware run with multiple shots.
    # Instead, we can also perform a single-shot measurement
    # here in the loop.
    bitstring = list(counts_keep.keys())[num_attempt]
    num_attempt += 1
    # Find the phase from measurement
    decimal = int(bitstring, 2)
    phase = decimal / (2**num_control)  # phase = k / r
    print(f"Phase: theta = {phase}")

    # Guess the order from phase
    frac = Fraction(phase).limit_denominator(N)
    r = frac.denominator  # order = r
    print(f"Order of {a} modulo {N} estimated as: r = {r}")

    if phase != 0:
        # Guesses for factors are gcd(a^{r / 2} ± 1, 15)
        if r % 2 == 0:
            x = pow(a, r // 2, N) - 1
            d = gcd(x, N)
            if d > 1:
                FACTOR_FOUND = True
                print(f"*** Non-trivial factor found: {x} ***")

ATTEMPT 0:
Phase: theta = 0.0
Order of 2 modulo 15 estimated as: r = 1

ATTEMPT 1:
Phase: theta = 0.75
Order of 2 modulo 15 estimated as: r = 4
*** Non-trivial factor found: 3 ***

Conclusion

Après avoir parcouru ce module, tu seras peut-être frappé par une nouvelle admiration pour le génie de Peter Shor d'avoir inventé un algorithme aussi ingénieux. Mais espérons que tu auras également atteint un nouveau niveau de compréhension de sa simplicité trompeuse. Bien que l'algorithme puisse sembler impressionnamment (ou intimidantement) complexe, si tu le décomposes en chaque étape logique et que tu le traverses lentement, toi aussi tu seras capable d'exécuter l'algorithme de Shor.

Bien que nous soyons loin d'utiliser cet algorithme pour factoriser des nombres comme RSA1024, nos ordinateurs quantiques s'améliorent chaque jour, et une fois qu'un seuil appelé tolérance aux pannes est atteint, des algorithmes tels que ceux-ci suivront bientôt. C'est une période passionnante pour apprendre le calcul quantique !

Exercices

Concepts clés :

• Les systèmes cryptographiques modernes reposent sur la difficulté classique de factoriser de grands entiers.
• L'arithmétique modulaire — incluant les structures $\mathbb{Z}_N$ et $\mathbb{Z}_N^*$ — fournit le fondement mathématique de l'algorithme de Shor.
• Le problème de factorisation d'un entier $N$ peut être réduit au problème de trouver l'ordre d'un nombre modulo $N$.
• La recherche d'ordre quantique utilise des techniques d'estimation de phase quantique pour déterminer la période de la fonction $a^x \mod N$.
• L'algorithme de Shor consiste en un flux de travail hybride classique-quantique qui sélectionne une base, effectue la recherche d'ordre quantique, puis calcule classiquement les facteurs à partir du résultat.

Vrai/Faux :

1. V/F L'efficacité de l'algorithme de Shor menace la sécurité du chiffrement RSA.
2. V/F L'algorithme de Shor peut être exécuté efficacement sur n'importe quel ordinateur quantique actuel.
3. V/F L'algorithme de Shor utilise l'estimation de phase quantique (QPE) comme sous-routine clé.
4. V/F La partie classique de l'algorithme de Shor implique le calcul du plus grand diviseur commun (PGCD).
5. V/F L'algorithme de Shor ne fonctionne que pour factoriser des nombres pairs.
6. V/F Une exécution réussie de l'algorithme de Shor garantit toujours les facteurs corrects.

Réponse courte :

1. Pourquoi l'algorithme de Shor est-il considéré comme une menace future potentielle pour le chiffrement RSA ?
2. Pourquoi trouver la période, ou l'ordre, d'une fonction exponentielle modulaire est-il utile pour factoriser un nombre dans l'algorithme de Shor ?

Problèmes de défi :

1. De combien de qubits de contrôle $m$ avons-nous besoin pour un nombre $N$ donné que nous essayons de factoriser afin d'obtenir la précision dans le QPE nécessaire pour trouver la valeur correcte de l'ordre $r$ ?

2. En suivant la procédure que nous avons décrite ici pour factoriser 15, essaie maintenant de factoriser 21.