Algorithme de Shor

Pour ce module Qiskit in Classrooms, les étudiants doivent disposer d'un environnement de Python travail sur lequel les paquets suivants sont installés :

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

Pour configurer et installer les paquets ci-dessus, consultez le guide d'installation de Qiskit. Pour pouvoir exécuter des tâches sur de véritables ordinateurs quantiques, les étudiants devront créer un compte en IBM Quantum® suivant les étapes décrites dans le guide « Créer votre IBM Cloud compte ».

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

# 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 1990s, l'enthousiasme grandissait autour du potentiel des ordinateurs quantiques pour résoudre des problèmes difficiles à traiter par les ordinateurs classiques. Quelques informaticiens talentueux avaient mis au point des algorithmes qui démontraient la puissance de l'informatique quantique pour certains problèmes de niche artificiels, mais personne n'avait trouvé une seule « application révolutionnaire » de l'informatique quantique qui allait assurément révolutionner le domaine. C'était le cas jusqu'en 1994, lorsque Peter Shor a mis au point ce qui est aujourd'hui appelé l'algorithme de Shor pour factoriser les 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é Internet s'appuyaient sur cette difficulté. Shor a trouvé un moyen de déterminer ces facteurs de manière exponentiellement plus efficace en transférant certaines des étapes les plus difficiles à un ordinateur quantique théorique futur.

Dans ce module, nous allons explorer l'algorithme de Shor. Tout d'abord, nous allons donner un peu plus de contexte à l'algorithme, en formalisant le problème qu'il résout et en expliquant sa pertinence pour la cybersécurité. Ensuite, nous présenterons une introduction aux mathématiques modulaires et à leur application au problème de factorisation, en montrant comment la factorisation se réduit à un autre problème appelé « recherche d'ordre » Nous montrerons comment la transformée de Fourier quantique et l'estimation de phase quantique, que nous avons apprises 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 allons exécuter l'algorithme de Shor sur un véritable ordinateur quantique! Gardez toutefois à l'esprit que cet algorithme ne sera vraiment utile que lorsque nous disposerons d'un ordinateur quantique puissant et tolérant aux pannes, ce qui ne sera pas le cas avant plusieurs années. Nous allons donc simplement factoriser un petit nombre pour montrer comment fonctionne l'algorithme.

Le problème de l'affacturage

Le but du problème de factorisation est de trouver les facteurs premiers d'un nombre $N$. Pour certains nombres $N$, c'est assez facile. Par exemple, si $N$ est pair, l'un de ses facteurs premiers sera 2. Si $N$ est une puissance première, c'est-à-dire $N=p^k$ pour un certain nombre premier $p$, il est également assez facile de trouver $p$ : il suffit d'approximer la racine $k^{\text{th}}$ de $N$ et de rechercher les nombres premiers proches qui pourraient être $p$.

Cependant, les ordinateurs classiques rencontrent des difficultés lorsque $N$ est impair et n'est pas une puissance première. C'est le cas traité par l'algorithme de Shor. L'algorithme trouve deux facteurs $p$ et $q$ tels que $N=pq$. Il peut être appliqué de manière récursive 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 systèmes cryptographiques ont été conçus en se basant sur le fait qu'il est difficile de factoriser de grands nombres, notamment celui couramment utilisé aujourd'hui, appelé RSA. Dans le RSA, une clé publique est créée en multipliant deux grands nombres premiers entre eux pour obtenir $N = p\cdot q$. Ensuite, n'importe qui peut utiliser cette clé publique pour crypter 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 serait capable de déterminer ce que sont $p$ $q$ et et de déchiffrer le cryptage. Mais ce n'est pas le cas. C'est un problème réputé difficile. En fait, les facteurs premiers d'un nombre appelé RSA1024, qui comporte 1024 chiffres binaires et 309 chiffres décimaux, n'ont toujours pas été trouvés, malgré une récompense de 100 000 dollars offerte pour sa factorisation dès 1991.

Solution de Shor

En 1994, Peter Shor s'est rendu compte 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 passer en revue quelques notions élémentaires d'arithmétique modulaire, puis nous verrons comment les utiliser pour factoriser $N$.

Arithmétique modulaire

L'arithmétique modulaire est un système de comptage cyclique, ce qui signifie que le comptage commence de manière habituelle, avec les nombres entiers 0, 1, 2, etc., à un certain moment, après une période donnée $N$, le décompte recommence. Voyons comment cela fonctionne à l'aide d'un exemple. Supposons que notre période soit 5. Ensuite, pendant que nous comptons, là où nous arriverions normalement à 5, nous recommençons à 0 :

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

En effet, dans le monde « modulo-5 », 5 équivaut à 0. Nous disons que $5\bmod 5 \ = 0$. En fait, tous les multiples de 5 seront équivalents à $0\bmod 5$.

Vérifiez votre compréhension

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

Vous partez pour un long voyage en train transcontinental à 8 heures du matin. Le trajet en train dure 60 heures. Quelle heure est-il quand vous arrivez?

• Réponse

  La période est de 24, puisqu'il y a 24 heures dans une journée. Ainsi, ce problème peut être écrit en arithmétique modulaire comme suit :

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

  Vous arriveriez donc à destination à 20 h, soit 8 heures du soir.

$\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, lorsque nous comptions 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\}$. Nous pouvons 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. Il s'agit du sous-ensemble des nombres tels $\mathbb{Z}_N$ que le plus grand commun diviseur entre chaque élément et $N$ est 1, de sorte que chaque élément est « coprime » avec $N$. Si l'on prend l'ensemble de ces nombres avec l'opération de multiplication modulaire, on obtient un autre objet mathématique, appelé groupe. Nous appelons ce groupe $\mathbb{Z}_N^*$. Il s'avère qu'avec $\mathbb{Z}_N^*$ (et les groupes finis en général), si nous choisissons un élément quelconque et que nous multiplions $a$ $a \in \mathbb{Z}_N^*$ par lui-même à plusieurs reprises, nous obtiendrons toujours le nombre $1$. Le nombre minimum 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 les nombres ci-dessous.

Vérifiez votre compréhension

Qu'est-ce que c'est $\mathbb{Z}_{15}^*$?

• Réponse

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

  Nous avons exclu les numéros suivants :

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

Quel est l'ordre de chacun des éléments dans $\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}$$

  Notez que, même si nous avons réussi à trouver l'ordre des nombres dans $\mathbb{Z}_{15}^*$, ce n'est PAS une tâche facile en général, pour des plus grands $N$. 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 au fur et à mesure que nous avancerons dans le reste du cahier.

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

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

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

Comment le fait de trouver nous $x$ aide-t-il à trouver les facteurs $p$ et $q$? Examinons maintenant cet argument. 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$. Ainsi, pour un certain entier $l$,

$x^2 - 1 = l N$

Nous pouvons 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 se divise pas $x+1$ exactement par ou $x-1$. Ainsi, les deux facteurs de $N$, $p$ et, $q$ doivent chacun se diviser par $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 nous calculons les plus grands diviseurs communs (PDC) entre $N$ et et $x-1$ $x+1$, cela nous donnera les facteurs $p$ et $q$. Le calcul du PDC entre deux nombres est une tâche classique facile qui peut être accomplie, par exemple, à l'aide de l'algorithme d'Euclide.

Vérifiez votre compréhension

Il peut être difficile de comprendre chaque étape du raisonnement ci-dessus, alors essayez de l'appliquer à un exemple. Utilisez $N=15$ et $x=11$. Vérifiez d'abord que $x^2 \equiv 1 \text{mod}(N)$ et $x \not\equiv \pm 1 \bmod N$. Continuez ensuite à vérifier chaque étape. Enfin, calculez $\text{GCD}(11\pm1,15)$ et vérifiez qu'il s'agit bien des facteurs de $15$.

• Réponse

  $11^2 = 121$, qui est $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, nous savons que $(x+1)(x-1) = l N$ pour certains entiers $l$. Cela se vérifie lorsque nous substituons $x$ et $N$ : $(12)(10) = l 15$ lorsque $l = 8$. $\checkmark$

  Maintenant, nous devons calculer $\text{GCD}(12,15)$ et $\text{GCD}(10,15)$.

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

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

L'algorithme

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

1. Choisissez un nombre entier aléatoire Choisissez un nombre entier aléatoire $a$ tel que $1 < a < N$.

• Calculer $\text{GCD}(a, N)$ de manière classique.
  • Si $\text{GCD}(a, N) > 1$, vous avez déjà trouvé un facteur. Arrêtez.
  • Sinon, continuez.

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

3. Vérifiez si la commande est paire.

• Si $r$ est impair, revenez à l'étape 1 et choisissez un nouveau $a$.
• Si $r$ est pair, passez à l'étape 4.

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

• Vérifiez que $x \not\equiv 1 \pmod N$ et $x \not\equiv -1 \pmod N$.
  • Si $x \equiv \pm 1 \pmod N$, revenez à l'étape 1 et choisissez un nouveau $a$.
• Sinon, calculez les pgcd pour extraire les facteurs :

Ce seront des facteurs non triviaux de $N$.

5. Facteur récursivement si nécessaire

• Si $p$ et/ou ne $q$ sont pas premiers, appliquez l'algorithme de manière récursive pour les factoriser complètement.
• Une fois tous les facteurs premiers déterminés, le calcul est terminé.

Sur la base de cette procédure, on pourrait se demander pourquoi un ordinateur quantique est nécessaire pour accomplir cette tâche. C'est nécessaire car l'étape 2, qui consiste à trouver l'ordre de $a$ modulo $N$, est classiquement un problème très difficile. La complexité augmente de manière 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, qui consiste à trouver le PGCD de deux nombres entiers, est en fait assez facile à réaliser de manière classique. Ainsi, la seule étape qui nécessite réellement la puissance d'un ordinateur quantique est celle de la recherche d'ordre. Nous disons que le problème de factorisation « se réduit » au problème de recherche d'ordre.

La partie difficile : trouver la commande

Nous allons maintenant voir comment utiliser un ordinateur quantique pour trouver des solutions. Tout d'abord, clarifions ce que nous entendons par « ordre » Bien sûr, je vous ai déjà expliqué ce que signifie mathématiquement cet ordre : c'est le premier entier non nul $r$ tel que $a^r = 1 \pmod N.$ Mais voyons si nous pouvons acquérir un peu plus d'intuition pour ce concept.

Pour suffisamment petit $N$, nous pouvons simplement déterminer l'ordre en calculant chaque puissance de $a$, en prenant le module $N$ de ce nombre, puis en s'arrêtant lorsque nous trouvons la puissance $r$ qui satisfait $a^r = 1 \text{mod}(N)$. C'est ce que nous avons fait avec notre exemple, $N=15$, ci-dessus. Examinons quelques graphiques représentant ces puissances modulaires pour certaines valeurs échantillons de $a$ et $N$ :

Vous remarquez quelque chose? Ce sont des fonctions périodiques! Et l'ordre $r$ est le même que la période! Ainsi, la recherche d'ordre équivaut à la recherche de période.

Les ordinateurs quantiques sont particulièrement adaptés à la recherche de la période des fonctions. Pour cela, nous pouvons utiliser une sous-routine algorithmique appelée « estimation de phase quantique ». Nous avons abordé le QPE et son rapport avec la transformée de Fourier quantique dans le module précédent. Pour un rappel détaillé, consultez le module QFT ou la leçon de John Watrous sur l'estimation de phase quantique dans son cours sur les algorithmes quantiques. Nous allons maintenant passer en revue les grandes lignes de la procédure :

Dans l'estimation de phase quantique (QPE), nous partons d'un opérateur unitaire $U$ et d'un état propre de cet opérateur unitaire $|\psi\rangle$. Ensuite, nous utilisons la 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 équivaut à trouver la valeur de $\theta$ dans la fonction périodique. Le circuit ressemble à ceci :

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

Dans l'algorithme de Shor, nous utilisons le 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-qubits, 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 $|0010\rangle$ qubits, car quatre qubits sont nécessaires pour coder des nombres allant jusqu'à 15. (Si ce concept vous est inconnu, consultez le module d'introduction Qiskit dans les salles de classe pour rafraîchir vos connaissances sur le codage binaire des états quantiques.)

Maintenant, nous devons déterminer un état propre de cet opérateur unitaire. Si nous avons commencé dans l'état $|1\rangle$, nous pouvons voir que chaque application successive de $U$ multipliera l'état de notre registre par $a \pmod N$, et après $r$ applications, nous arriverons à $|1\rangle$ nouveau à l'état. Par exemple avec $a = 3$ et $N = 35$ :

Ainsi, 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 tous des états propres de $M_a$. (Il existe d'autres états propres que ceux-ci. Mais nous ne nous intéressons qu'à ceux qui répondent à la forme ci-dessus.)

Vérifiez votre compréhension

Trouvez 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 qui ont été cyclés ci-dessus, avec différentes 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 ayons réussi à initialiser l'état de notre 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 dans un instant). 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}$. Nous pourrons ensuite déterminer l'ordre $r$ à l'aide de l'équation simple suivante :

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

Mais n'oubliez pas que j'ai dit que le QPE fournit des estimations$\theta_j$ — il ne nous donne pas une valeur exacte. Nous avons besoin d'une estimation suffisamment précise pour différencier et $r$ $r+1$. Plus nous disposons de qubits de contrôle $m$, meilleure sera l'estimation. Dans les problèmes à la fin de la leçon, vous devrez déterminer le minimum $m$ nécessaire pour factoriser un nombre $N$.

Maintenant, nous devons résoudre un problème. Toutes les explications ci-dessus sur la manière de trouver $r$ commencent 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 la $r$ valeur de. La logique 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$, nous pouvons préparer l'état initial dans l'état $n$ à -qubits correspondant à $|1\rangle$ en binaire (comme dans ) $|000...01\rangle$. Bien que cet état ne soit manifestement pas un état propre de $M_a$, il s'agit d'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érifiez votre compréhension

Vérifiez que $|1\rangle$ est équivalent à la superposition des états propres que vous avez trouvés pour $N=15$ et $a=2$ dans la question précédente.

• Réponse

  Les quatre états propres étaient les suivants :

  $$\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$? Étant donné que l'état initial est une superposition de tous les états propres de la forme indiquée ci-dessus, l'algorithme QPE estime simultanément chacun des $\theta_k$ correspondant à ces états propres. Ainsi, la mesure des qubits $m$ 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 choisies au hasard. Si nous répétons ce circuit plusieurs fois et obtenons plusieurs échantillons avec différentes valeurs de $k$, nous pourrons rapidement en déduire $r$.

Implémenter dans Qiskit

Comme nous l'avons mentionné précédemment, notre matériel n'est pas encore capable de traiter des nombres aussi grands que RSA1024. Nous allons simplement factoriser un petit nombre pour montrer comment fonctionne l'algorithme. Pour cette démonstration, nous utiliserons une version simplifiée du code présenté dans le tutoriel sur l'algorithme de Shor. Si vous souhaitez obtenir plus de détails, veuillez consulter le tutoriel.

Nous exécuterons l'algorithme à l'aide de notre infrastructure standard pour résoudre les problèmes quantiques, appelée infrastructure Qiskit patterns. Cela comprend quatre étapes :

1. Mappage de votre problème sur un circuit quantique
2. Optimiser le circuit pour qu'il puisse être exécuté sur du matériel quantique
3. Exécutez votre circuit sur l'ordinateur quantique
4. Post-traiter les mesures

1. Carte

Factorisons $N=15$, en choisissant $a=2$ comme notre entier coprime.

Tout d'abord, nous devons construire le circuit qui mettra en œuvre l'unité de multiplication modulaire. $M_a$ C'est en fait la partie la plus délicate de toute la mise en œuvre, qui peut s'avérer très coûteuse en termes de calcul, selon la manière dont elle est réalisée. Pour cela, nous allons tricher un peu : nous savons que nous commençons dans l'état $|1\rangle$, et d'après une question posée précédemment,

Nous allons donc construire une unité qui effectue les opérations correctes sur ces quatre états, mais qui laisse tous les autres états inchangés. C'est de la triche, car 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 étaient inconnus, nous ne serions pas en mesure de le faire.

Vérifiez votre compréhension

Grâce à votre connaissance de la manière dont $M_2$ l'opérateur transforme les états ci-dessus, construisez l'opérateur à partir d'une série de portes SWAP, qui échangent les états de deux qubits. (Astuce : écrire chaque état $|i\rangle$ en binaire vous 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 à l'aide d'un simple SWAP. $M_2|0001\rangle$ est obtenu en échangeant les états des qubits $0$ et $1$. $M_2|0010\rangle$ est obtenu en échangeant les états des qubits $1$ et $2$. Et ainsi de suite. Nous pouvons donc décomposer la $M_2$ matrice en la série suivante de portes SWAP :

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

  En gardant à l'esprit que les opérateurs agissent de droite à gauche, vérifions que cela produit 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 désormais coder le circuit équivalent à cet opérateur dans Qiskit.

Tout d'abord, nous importons les paquets 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)

Output:

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

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)

Output:

Nous avons maintenant notre porte $U$ contrôlée. Mais pour exécuter l'algorithme d'estimation de phase quantique, nous aurons besoin de contrôlé $U^2$, contrôlé $U^4$, jusqu'à contrôlé $U^{2^{m-1}}$, 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 des $m=8$ qubits de contrôle pour notre procédure d'estimation de phase. Nous avons donc besoin de :

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)

Output:

[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 supérieurs) sont équivalents à l'identité. Il suffit donc de construire 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 plus grands $N$ ou différents choix de $a$, vous ne pouvez pas ignorer la construction des puissances supérieures. C'est l'une des raisons pour lesquelles cet exemple est considéré comme un exemple simplifié : les petits nombres permettent des raccourcis qui ne fonctionneraient pas dans des cas plus complexes.

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)

Output:

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

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)

Output:

Maintenant, nous pouvons rassembler tous ces éléments pour trouver l'ordre de $2\bmod 15$ à l'aide d'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)

Output:

2. Optimiser

Maintenant que nous avons cartographié notre circuit, l'étape suivante consiste à l'optimiser pour qu'il puisse fonctionner sur un ordinateur quantique particulier. Nous devons d'abord charger le backend.

service = QiskitRuntimeService()

backend = service.backend("ibm_marrakesh")

Si vous ne disposez pas de temps sur votre compte ou si vous souhaitez utiliser un simulateur pour une raison quelconque, vous pouvez 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)

Output:

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))

Output:

Nous observons quatre pics distincts à 00000000, 01000000, 10000000 et 11000000, avec quelques comptages dans d'autres chaînes de bits dus au bruit dans l'ordinateur quantique. Nous allons ignorer ces derniers et ne conserver que les quatre dominants en imposant un seuil : seuls les comptes supérieurs à ce seuil sont considérés comme un véritable 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-traitement

Pour l'algorithme de Shor, une grande partie de l'algorithme est exécutée de manière classique. Nous mettrons donc le reste dans l'étape de « post-traitement », après avoir obtenu nos mesures à partir de l'ordinateur quantique. Chacune des mesures ci-dessus peut être convertie en nombres entiers qui, après division par $2^m$, constituent nos approximations pour $\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} ***")

Output:

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 suivi ce module, vous serez peut-être frappé par une nouvelle admiration pour le génie de Peter Shor, qui a su imaginer un algorithme aussi ingénieux. Mais j'espère que vous avez également atteint un nouveau niveau de compréhension de sa simplicité trompeuse. Même si l'algorithme peut sembler incroyablement (voire intimidant) complexe, si vous le décomposez en étapes logiques et que vous le parcourez lentement, vous serez vous aussi capable d'exécuter l'algorithme de Shor.

Même si nous sommes encore loin d'utiliser cet algorithme pour factoriser des nombres tels que RSA1024, nos ordinateurs quantiques s'améliorent chaque jour, et une fois qu'un seuil appelé tolérance aux pannes sera atteint, des algorithmes tels que ceux-ci suivront rapidement. C'est une période passionnante pour découvrir l'informatique quantique!

Incidents

Concepts essentiels :

• Les systèmes cryptographiques modernes reposent sur la difficulté classique de factoriser de grands nombres entiers.
• L'arithmétique modulaire — y compris les structures $\mathbb{Z}_N$ et $\mathbb{Z}_N^*$ — fournit les bases mathématiques de l'algorithme de Shor.
• Le problème de la factorisation d'un entier $N$ peut être réduit au problème de la recherche de 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 une recherche d'ordre quantique, puis calcule de manière classique les facteurs à partir du résultat.

Vrai/Faux :

1. Vrai ou faux : L'efficacité de l'algorithme de Shor menace la sécurité du cryptage RSA.
2. Vrai ou faux : l'algorithme de Shor peut être exécuté efficacement sur n'importe quel ordinateur quantique moderne.
3. Vrai ou faux? L'algorithme de Shor utilise l'estimation de phase quantique (QPE) comme sous-programme clé.
4. Vrai ou faux : La partie classique de l'algorithme de Shor consiste à calculer le plus grand commun diviseur (PGCD).
5. Vrai ou faux : l'algorithme de Shor ne fonctionne que pour la factorisation des nombres pairs.
6. Vrai ou faux : 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 potentielle pour le cryptage RSA?
2. Pourquoi est-il utile de déterminer la période, ou l'ordre, d'une fonction exponentielle modulaire pour factoriser un nombre dans l'algorithme de Shor?

Problèmes difficiles :

1. Combien de qubits de contrôle $m$ faut-il 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, essayez maintenant de factoriser 21.