Cours d'informatique quantique – Mathématiques et théorie pour débutants

1. Introduction et Structure du Cours [0]

1. L'informatique quantique utilise la mécanique quantique pour traiter l'information. [0]
2. Ce cours vise à fournir une base solide sur le sujet. [1]
3. Il est divisé en deux sections principales : les mathématiques de base et la mécanique quantique. [2]
4. Le cours expliquera la puissance des ordinateurs quantiques et leur impact technologique. [3]
5. Michael de Quantum Source a créé ce cours. [4]
6. Il évite les analogies, se concentrant sur le fonctionnement réel des ordinateurs quantiques. [7]

2. Structure Détaillée du Cours [8]

2.1. Section Mathématique et Qubits [9]

1. La première section couvre les mathématiques de base nécessaires. [9]
   1. Introduction aux nombres complexes. [9]
   2. Bases de l'algèbre linéaire. [9]
2. La section suivante explore la représentation mathématique des qubits. [9]
   1. Opérations sur un qubit unique et leurs propriétés. [10]
3. La troisième section traite des multi-qubits et de leurs opérations. [11]
   1. Exploration des phénomènes quantiques étranges. [12]
   2. Intrication quantique (quantum entanglement). [12]
   3. Phase kickback. [12]

2.2. Algorithmes Quantiques [13]

1. La section finale utilise les connaissances acquises pour analyser les algorithmes quantiques. [13]
2. Cette analyse démontre la nature révolutionnaire de la technologie quantique. [14]

3. Nombres Imaginaires et Complexes [15]

3.1. Définition des Nombres Imaginaires [15]

1. Commençons par les racines carrées des nombres. [15]
2. Si $x^2=4$, alors $x=\pm 2$. [16]
3. Si $x^2=-4$, cela nécessite les nombres imaginaires. [17]
4. On définit $i$ comme la racine carrée de -1. [18]
5. $\sqrt{-4}$ peut alors s'écrire $\pm 2i$. [18]
6. Un nombre imaginaire contient un facteur de $\sqrt{-1}$. [19]

3.2. Nombres Complexes et Opérations [20]

1. Un nombre complexe est la somme d'un nombre réel et d'un nombre imaginaire. [21]
2. La forme standard est $a+iB$. [22]
   1. $A$ est la partie réelle. [22]
   2. $B$ est la partie imaginaire. [22]
3. L'addition et la soustraction se font en combinant les parties réelles et imaginaires. [24]
4. La multiplication nécessite de se souvenir que $i^2=-1$. [26]
5. Le conjugué complexe s'obtient en inversant le signe de la partie imaginaire. [27]
   1. Il est noté par un astérisque (*). [28]
6. Propriété clé : multiplier un nombre complexe par son conjugué donne toujours un nombre réel. [30]

3.3. Représentation Graphique des Complexes [32]

1. Un nombre complexe peut être vu comme un vecteur sur un plan. [32]
   1. L'axe horizontal est l'axe Réel. [32]
   2. L'axe vertical est l'axe Imaginaire. [32]
2. La magnitude est la distance du nombre complexe à l'origine. [34]
   1. Elle est calculée par le théorème de Pythagore : $\sqrt{a^2+b^2}$. [35]
3. Une autre représentation utilise la magnitude ($r$) et l'angle ($\theta$). [38]
   1. Ceci est appelé la forme polaire : $r(\cos \theta +i\sin \theta )$. [39]
   2. L'angle $\theta$ est trouvé par $\arctan (B/A)$. [40]
4. Il existe une troisième forme, la forme exponentielle : $r{e}^{i\theta }$. [42]
5. En informatique quantique, on utilise presque exclusivement la forme exponentielle. [44]
   1. Changer $\theta$ fait tourner autour d'un cercle unité. [45]

4. Introduction aux Matrices et Opérations [47]

4.1. Définition et Opérations de Base [47]

1. Une matrice est un arrangement bidimensionnel de nombres. [47]
2. Une matrice $M\times N$ a $M$ lignes et $N$ colonnes. [49]
3. L'addition et la soustraction nécessitent des dimensions identiques. [51]
4. On peut multiplier une matrice par un scalaire. [55]
   1. Chaque élément de la matrice est multiplié par le scalaire. [56]
5. La multiplication matricielle implique un produit scalaire entre les lignes de la première matrice et les colonnes de la seconde. [57]
6. La multiplication est possible seulement si les colonnes de la première égalent les lignes de la seconde. [60]

4.2. Vecteurs et Transformations Matricielle [62]

1. Une matrice $N\times 1$ est appelée un vecteur colonne. [62]
2. Les états quantiques sont représentés par des vecteurs colonnes. [64]
3. Multiplier une matrice par un vecteur colonne donne un autre vecteur colonne. [65]
   1. Intuitivement, la matrice transforme le vecteur. [66]
4. La matrice identité est diagonale avec des uns (le reste est zéro). [69]
   1. Multiplier par elle redonne la matrice originale. [71]
5. Une matrice possède une inverse (notée $A^{-1}$) qui, multipliée par $A$, donne l'identité. [73]
   1. Graphiquement, appliquer $A$ puis $A^{-1}$ ramène au point initial. [75]
6. On peut prendre le conjugué complexe d'une matrice (signe de tous les éléments imaginaires inversé). [77]

4.3. Transposée, Dagger et Types de Matrices [81]

1. La transposée ($T$) échange les lignes et les colonnes d'une matrice. [81]
2. Le dagger ($†$) combine la transposée et le conjugué complexe. [83]
3. Deux types de matrices sont utilisées pour les opérations quantiques : [84]
   1. Matrices Unitaires ($U$) : $U{U}^{†}=I$. [85]
   2. Géométriquement, elles conservent la longueur du vecteur (rotation/flip). [87]
   3. Matrices Hermitiennes ($H$) : $H=H^{†}$. [89]
4. Quand une transformation étire ou comprime un vecteur sans changer sa direction, on a : [92]
   1. Le vecteur est un vecteur propre (eigenvector). [93]
   2. Le facteur d'étirement/compression est une valeur propre (eigenvalue). [93]
5. Exemple : Pour la matrice $\left(\begin{array}{cc}2& 0\\ 1& 2\end{array}\right)$ et le vecteur $\left(\begin{array}{c}0\\ 3\end{array}\right)$, le résultat est $\left(\begin{array}{c}0\\ 6\end{array}\right)$. [95]
   1. On factorise $2\times \left(\begin{array}{c}0\\ 3\end{array}\right)$, donc la valeur propre est 2. [96]

5. Qubits et Représentation Quantique [98]

5.1. Qubits vs Bits Classiques [98]

1. Les ordinateurs classiques utilisent des zéros et des uns binaires. [98]
2. Les ordinateurs quantiques utilisent des qubits (bits quantiques). [99]
   1. Un qubit peut être zéro et un en même temps. [99]
3. Physiquement, un qubit est une particule en deux états distincts (ex: polarisation d'un photon). [103]
4. Les états $|0⟩$ et $|1⟩$ sont définis comme les vecteurs colonnes $\left(\begin{array}{c}1\\ 0\end{array}\right)$ et $\left(\begin{array}{c}0\\ 1\end{array}\right)$. [104]
5. Les crochets de Dirac ($|\dots ⟩$) sont la notation utilisée. [105]

5.2. Superposition et Mesure [106]

1. La superposition signifie qu'une particule est dans deux états simultanément. [106]
2. Un qubit en superposition est à la fois $|0⟩$ et $|1⟩$. [108]
3. Mathématiquement, un qubit est un vecteur colonne $\left(\begin{array}{c}\alpha \\ \beta \end{array}\right)$. [110]
   1. $\alpha$ indique la proportion de l'état $|0⟩$. [111]
   2. $\beta$ indique la proportion de l'état $|1⟩$. [111]
4. La mesure change l'état du système à l'état mesuré. [116]
   1. Si mesuré, un qubit en superposition s'effondre (collapses) en $|0⟩$ ou $|1⟩$. [119]
5. Les amplitudes ($\alpha ,\beta$) déterminent la probabilité de mesure. [124]
   1. Probabilité de mesurer $|0⟩$ est $|\alpha {|}^2$. [125]
   2. Probabilité de mesurer $|1⟩$ est $|\beta {|}^2$. [125]
6. La somme des probabilités doit être égale à un ($|\alpha {|}^2+|\beta {|}^2=1$). [129]
7. La notation de Dirac est la manière conventionnelle d'écrire les états quantiques. [133]
   1. Les vecteurs $\left(\begin{array}{c}\alpha \\ \beta \end{array}\right)$ deviennent $\alpha |0⟩+\beta |1⟩$. [134]
   2. Les crochets $|\dots ⟩$ sont appelés Kets. [138]

5.3. Représentation sur la Sphère de Bloch [142]

1. Un qubit peut être représenté graphiquement sur la Sphère de Bloch. [142]
   1. Le pôle Nord est l'état $|0⟩$. [143]
   2. Le pôle Sud est l'état $|1⟩$. [143]
2. La position verticale détermine la probabilité de mesure. [146]
   1. Plus haut, plus de chance de mesurer $|0⟩$. [151]
3. La rotation autour de la sphère est appelée la phase. [149]

6. Opérations sur les Qubits : Portes Quantiques [155]

6.1. Portes à Qubit Unique (X, Y, Z) [155]

1. Les portes quantiques changent les états des qubits. [155]
2. Les portes simples courantes sont les portes X, Y, et Z. [156]
3. La Porte X (NOT) inverse le qubit (ex: $|0⟩\to |1⟩$). [158]
   1. Elle fait tourner le qubit de $180^{\circ }$ ($\pi$ radians) autour de l'axe X. [161]
4. La Porte Y fait tourner le qubit de $\pi$ radians autour de l'axe Y. [164]
5. La Porte Z fait tourner le qubit de $\pi$ radians autour de l'axe Z. [165]
6. Appliquer la même porte deux fois les annule ; elles sont donc leurs propres inverses. [166]
7. Appliquer une porte se fait par multiplication matricielle avec le vecteur colonne du qubit. [171]
8. Pour appliquer une porte $U$ en notation de Dirac : [173]
   1. La première colonne de la matrice $U$ montre où $|0⟩$ est transformé. [174]
   2. La deuxième colonne montre où $|1⟩$ est transformé. [174]
9. La Porte Z change $|1⟩$ en $-|1⟩$, mais ne change pas les probabilités de mesure. [181]

6.2. Phase et Rotation sur l'Axe Z [182]

1. La rotation autour de l'axe Z est appelée la phase. [184]
2. La phase est représentée mathématiquement par les nombres complexes en forme exponentielle. [188]
3. La multiplication de l'état $|1⟩$ par $e^{i\theta }$ fait tourner le qubit de $\theta$ autour de l'axe Z. [199]
4. Il existe deux types de phase : [200]
   1. Phase globale : Multiplie l'entier qubit ; elle est physiquement non pertinente. [201]
   2. Phase relative : Multiplie seulement l'amplitude de l'état $|1⟩$ ; elle est extrêmement importante. [201]
5. La phase relative ne change pas les probabilités de mesure. [206]

6.3. États Équatoriaux et Porte Hadamard [211]

1. Les états sur l'équateur de la Sphère de Bloch sont des raccourcis pour des états courants. [212]
   1. Ils ont tous une chance égale d'être mesurés $|0⟩$ ou $|1⟩$ (0.5). [215]
2. Définitions des états équatoriaux : [216]
   1. État Plus ($|+⟩$) : $\frac{1}{\sqrt{2}}(|0⟩+|1⟩)$. [216]
   2. État Moins ($|-⟩$) : $\frac{1}{\sqrt{2}}(|0⟩-|1⟩)$ (phase relative de -1). [217]
   3. État $i$ ($|i⟩$) : Phase relative de $i$. [219]
   4. État $-i$ ($|-i⟩$) : Phase relative de $-i$. [219]
3. La Porte Hadamard ($H$) est la matrice la plus importante. [220]
   1. Elle transforme $|0⟩$ en $|+⟩$. [222]
   2. Elle transforme $|1⟩$ en $|-⟩$. [222]
   3. Elle est son propre inverse ($HH=I$). [224]
4. La porte Hadamard montre que la phase est cruciale pour les algorithmes. [226]

6.4. Portes de Phase et Produits Tensoriels [230]

1. Nouvelles portes ajoutant une phase relative : [231]
   1. Porte S : Ajoute une phase relative de $\pi /2$ radians. [232]
   2. Porte T : Ajoute une phase relative de $\pi /4$ radians. [233]
2. Les conjugués transposés ($S^{†},T^{†}$) sont les inverses de ces portes. [234]
3. Pour plusieurs qubits, on utilise le produit tensoriel ($\otimes$). [238]
   1. Deux qubits $|0⟩$ sont représentés par $|00⟩$. [239]
   2. Deux qubits en superposition donnent quatre états possibles (ex: $|00⟩,|01⟩,|10⟩,|11⟩$). [242]
4. La mesure fonctionne de manière similaire, mais les probabilités s'appliquent aux combinaisons. [244]
5. Pour appliquer une porte à un qubit spécifique, on utilise un circuit quantique. [250]
   1. Les lignes verticales représentent les qubits. [252]
   2. Les boîtes sont les portes, appliquées de gauche à droite (ordre temporel). [254]

7. Portes Multi-Qubits et Intrication [266]

7.1. Portes Contrôlées [266]

1. La porte multi-qubits la plus courante est la CNOT (Controlled-X). [267]
   1. Elle agit sur un contrôle et une cible. [270]
   2. Elle applique une porte X à la cible si le contrôle est $|1⟩$. [271]
2. La Porte Toffoli est similaire, mais possède deux qubits de contrôle. [274]
3. On peut créer des versions contrôlées d'autres portes (Y, Z, S, T, Hadamard). [278]
   1. Elles appliquent la porte si le contrôle est $|1⟩$. [278]
4. Pour mesurer un seul qubit dans un système multi-qubits : [281]
   1. On somme les probabilités de tous les états où ce qubit est dans l'état désiré. [281]

7.2. Effondrement et Normalisation [282]

1. Si on mesure un qubit, l'état entier s'effondre. [284]
2. On retire tous les états de superposition incompatibles avec la mesure. [286]
3. Les probabilités restantes doivent être normalisées (multipliées par une constante $A$) pour sommer à un. [287]

7.3. Intrication Quantique [295]

1. L'intrication est observée lorsque la mesure d'un qubit détermine immédiatement l'état de l'autre. [301]
2. Un état est intriqué s'il ne peut être factorisé en produits tensoriels d'états de qubits uniques. [304]
3. Deux types d'états intriqués existent : [307]
   1. Maximale : Mesurer un qubit révèle l'état des autres (ex: les États de Bell $\Phi ,\Psi$). [308]
   2. Partielle : La mesure d'un qubit affecte les probabilités ou la phase des autres. [311]

7.4. Phase Kickback [313]

1. Le phénomène de phase kickback se produit si la cible ($V$) est un état propre de la porte ($U$). [314]
2. Si $U|V⟩=e^{i\theta }|V⟩$, alors la porte contrôlée applique la phase $e^{i\theta }$ au qubit de contrôle. [320]
3. Le vecteur cible $V$ reste inchangé. [322]
4. Ce phénomène est utilisé dans certains algorithmes quantiques. [324]

8. Codage Superdense et Réversibilité [325]

8.1. Codage Superdense (Superdense Coding) [325]

1. Ce protocole permet d'envoyer deux bits classiques avec un seul qubit. [326]
2. Alice et Bob commencent avec deux qubits maximaleent intriqués (un état de Bell). [329]
3. Alice effectue une opération sur son qubit selon les deux bits à envoyer (00, 01, 10, ou 11). [333]
4. Alice envoie son qubit à Bob. [334]
5. Bob applique ensuite une CNOT (contrôle : son qubit initial) puis un Hadamard sur son qubit initial. [340]
6. Bob mesure les deux qubits pour obtenir les deux bits originaux d'Alice. [343]

8.2. Opérations Classiques et Réversibilité [346]

1. Les opérations classiques principales sont AND, OR, NOT, et XOR (ou exclusif). [347]
2. La réversibilité signifie que l'on peut déterminer l'entrée à partir de la sortie $F(x)$. [361]
   1. L'opération OR n'est pas réversible (plusieurs entrées donnent la même sortie 1). [362]
3. Pour rendre une porte classique réversible, on ajoute un bit d'entrée $C$. [364]
   1. La sortie devient $X$ et $C\oplus F(X)$. [365]
4. Toutes les opérations quantiques (sauf la mesure) doivent être réversibles. [370]
   1. Ceci est requis car elles doivent être unitaires. [371]

9. Application des Fonctions Quantiques [375]

9.1. Fonctions Quantiques Réversibles [375]

1. Pour appliquer une fonction $F$ sur un ordinateur quantique, elle doit être réversible. [376]
2. La technique est similaire à la réversibilité classique : on utilise $X$ et $Y$ (registres d'entrée/sortie). [377]
3. La fonction quantique standard est : entrée $(X,Y)\to (X,Y\oplus F(X))$. [378]
4. Si on initialise $Y$ à $|0⟩$, alors $0\oplus F(X)=F(X)$. [379]
   1. On obtient l'état $(X,F(X))$, permettant de requêter la fonction. [382]
5. Si l'on utilise l'état de sortie $|-⟩$ (phase Oracle), on obtient : [385]
   1. L'état final est $-1^{F(X)}|X-⟩$. [397]
   2. La différence entre $F(X)=0$ et $F(X)=1$ est seulement une phase globale de $-1$. [395]

9.2. Théorème de Non-Clonage [400]

1. Le théorème de non-clonage stipule qu'on ne peut pas copier un état quantique inconnu. [401]
2. Si l'état est $S=\alpha |0⟩+\beta |1⟩$, on ne peut le copier sans connaître $\alpha$ et $\beta$. [401]
3. On peut copier des états dont on connaît les amplitudes (ex: $|0⟩$ ou $|1⟩$). [403]

10. Algorithme de Deutsch (1 Qubit) [404]

10.1. Le Problème Classique vs Quantique [405]

1. Problème : Déterminer si une fonction $F$ à 1 bit est constante ou équilibrée (balanced). [405]
   1. Constante : $F(0)=F(1)$. [411]
   2. Équilibrée : $F(0)\ne F(1)$. [413]
2. Solution classique : Nécessite deux requêtes ($F(0)$ puis $F(1)$). [417]
3. L'Algorithme de Deutsch résout ce problème en une seule requête quantique. [420]

10.2. Circuit de Deutsch [421]

1. Le circuit utilise deux qubits initialisés à $|00⟩$. [423]
2. Étape 1 : Initialisation à $|0⟩\otimes |-⟩$ (ou $|+⟩\otimes |-⟩$ après Hadamard). [424]
3. Étape 2 : Application de l'Oracle de Phase $U_F$. [427]
   1. Si $F(0)=F(1)$ (constant), l'état devient $|+⟩$. [432]
   2. Si $F(0)\ne F(1)$ (équilibré), l'état devient $|-⟩$. [437]
4. Étape 3 : Application d'un Hadamard au premier qubit. [439]
   1. Si état initial était $|+⟩$, il devient $|0⟩$. [440]
   2. Si état initial était $|-⟩$, il devient $|1⟩$. [440]
5. Mesure : Si on mesure $|0⟩$, $F$ est constante. Si on mesure $|1⟩$, $F$ est équilibrée. [441]

11. Algorithme de Deutsch-Jozsa (N Qubits) [445]

1. L'algorithme généralise celui de Deutsch pour une fonction prenant $N$ bits en entrée. [445]
2. Classiquement, cela prend jusqu'à $2^{N-1}+1$ requêtes dans le pire des cas. [452]
3. Quantiquement, il ne faut qu'une seule requête de la fonction. [457]
4. Le circuit est similaire, mais utilise $N$ qubits d'entrée en superposition. [458]

11.1. Identités Clés de l'Algorithme [459]

1. Étape 1 : Initialisation à $|0{⟩}^{\otimes N}\otimes |-⟩$. [461]
2. Étape 2 : Application de $N$ portes Hadamard sur les $N$ qubits d'entrée. [462]
   1. Identité clé : Hadamard sur $|0{⟩}^{\otimes N}$ donne une superposition uniforme de tous les états $X$. [473]
3. Étape 3 : Application de l'Oracle de Phase $U_F$. [478]
   1. L'état devient $\frac{1}{2^{N/2}}{\sum }_X(-1{)}^{F(X)}|X⟩$. [481]
4. Étape 4 : Application d'un Hadamard sur chacun des $N$ qubits. [483]
   1. Une identité importante est dérivée pour le Hadamard sur un état $X$ arbitraire. [495]

11.2. Conclusion de Deutsch-Jozsa [498]

1. On analyse l'amplitude de l'état tout-zéro ($|0{⟩}^{\otimes N}$). [498]
2. Si $F$ est constante, l'amplitude de $|0{⟩}^{\otimes N}$ est $\pm 1$ (probabilité de mesure = 1). [506]
3. Si $F$ est équilibrée, l'amplitude de $|0{⟩}^{\otimes N}$ est zéro (probabilité de mesure = 0). [510]
4. Résultat : Mesurer $|0{⟩}^{\otimes N}$ signifie que $F$ est constante ; mesurer autre chose signifie qu'elle est équilibrée. [515]

12. Algorithme de Bernstein-Vazirani [519]

1. Problème : Trouver une chaîne secrète $S$ de longueur $N$. [520]
   1. La fonction est $F(X)=X\cdot S(\mathrm{mod}2)$ (produit scalaire). [520]
2. Classiquement, il faut $N$ requêtes pour trouver chaque bit de $S$. [524]
3. Quantiquement, il ne faut qu'une seule requête. [525]
4. Le circuit est identique à Deutsch-Jozsa, mais l'Oracle utilise l'état $|-⟩$ comme cible. [526]
5. Après les deux séries d'Hadamard, la probabilité de mesurer l'état $S$ est un. [547]
6. Le schéma général (Hadamard, Oracle, Hadamard) est fréquent dans les algorithmes quantiques. [551]

13. Transformée de Fourier Quantique (QFT) [553]

1. La QFT est utilisée dans de nombreux algorithmes, y compris l'algorithme de Shor. [553]
2. Intuition sur la Sphère de Bloch : [555]
   1. L'entrée est un nombre $J$ encodé en binaire sur les qubits. [557]
   2. La sortie encode $J$ dans la phase relative des qubits en superposition uniforme. [559]
3. La rotation de chaque qubit est déterminée par $J$ et sa position. [562]
   1. Le qubit de droite tourne de $J/2^N\times 2\pi$ radians. [564]
4. La QFT est définie par une formule impliquant une somme et des exponentielles complexes. [594]
5. Il existe une QFT inverse qui défait la transformation. [595]

14. Estimation de Phase Quantique (QPE) [597]

1. L'algorithme QPE trouve la valeur propre ($e^{i\theta }$) d'un vecteur propre ($V$) d'une matrice ($U$). [597]
2. $U|V⟩=e^{i\theta }|V⟩$. QPE trouve $e^{i\theta }$ avec une certaine précision. [599]
3. Le circuit QPE utilise deux registres : un pour stocker la phase estimée ($M$ zéros) et un pour le vecteur propre $V$. [601]
4. Des portes $U^{2^k}$ sont appliquées au vecteur $V$ avec le $k$-ième qubit de phase comme contrôle. [603]
5. Le phase kickback applique une phase $e^{i{2}^k\theta }$ au qubit de contrôle. [609]
6. Après ces étapes, le premier registre contient un état proportionnel à $J$, où $\theta =2\pi J$. [617]
7. Appliquer la QFT inverse au premier registre permet de mesurer $J$ avec $M$ bits de précision. [623]
8. Avec $J$, on trouve $\theta$ puis la valeur propre $e^{i\theta }$. [625]

15. Algorithme de Shor (Factorisation) [626]

15.1. Objectif et Théorie des Nombres [626]

1. L'algorithme de Shor trouve les facteurs premiers ($P, Q$) d'un grand nombre $N=PQ$. [627]
2. Il utilise une combinaison d'étapes classiques et quantiques. [631]
3. Étape classique 1 : Choisir $A$ tel que $\text{PGCD}(A,N)=1$. [632]
4. Réduction : Le problème se réduit à trouver la période ($R$) de l'exponentiation modulaire $A^x(\mathrm{mod}N)$. [636]
5. La période $R$ est trouvée lorsque $A^R\equiv 1(\mathrm{mod}N)$. [641]
6. Si $R$ est trouvé, les facteurs $P$ et $Q$ sont trouvés via $\text{PGCD}(A^{R/2}\pm 1,N)$. [643]

15.2. Application de QPE à Shor [645]

1. On construit une porte $U$ qui transforme $|X⟩$ en $|X\cdot A(\mathrm{mod}N)⟩$. [645]
2. L'état $|1⟩$ est un vecteur propre de $U$, avec la valeur propre $e^{2\pi iS/R}$. [653]
3. On construit l'état $\frac{1}{\sqrt{R}}{\sum }_{s=0}^{R-1}|U^s⟩$, qui est une superposition des états $|U^s⟩$. [660]
4. On utilise l'algorithme QPE sur cet état pour estimer la valeur propre $e^{2\pi iS/R}$. [663]
5. Le résultat mesuré $J$ est une approximation de $S/R$. [665]

15.3. Estimation de R et Factorisation [666]

1. On utilise la technique des fractions continues pour estimer $S$ et $R$ à partir de $J$. [667]
2. On choisit l'approximation dont le dénominateur est inférieur à $N$ (car $R<N$). [671]
3. Une fois $R$ estimé, on calcule $\text{PGCD}(A^{R/2}-1,N)$ et $\text{PGCD}(A^{R/2}+1,N)$. [675]
4. Ces deux PGCD ont une forte probabilité de donner les facteurs $P$ et $Q$. [677]
5. Exemple : Pour $N=15$, choisir $A=7$. La période $R=4$. [681]
6. Les PGCD donnent $\text{PGCD}(48,15)=3$ et $\text{PGCD}(50,15)=5$. [686]