content/ex2/ex2-fr.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercice 2 - Algorithme de Shor\n",
    "## Contexte historique\n",
    "\n",
    "En informatique, nous mesurons souvent les performances d'un algorithme en fonction de sa croissance avec la taille du problème d'entrée. Par exemple, l'addition a un algorithme qui croît linéairement avec la taille des nombres que nous ajoutons. Il existe certains problèmes informatiques pour lesquels les meilleurs algorithmes dont nous disposons augmentent _exponentiellement_ avec la taille de l'entrée, ce qui signifie que les entrées de taille relativement modeste sont trop grandes pour être résolues avec n'importe quel ordinateur sur terre. Nous en sommes tellement sûrs qu'une grande partie de la sécurité d'Internet dépend du fait que certains problèmes sont insolubles.\n",
    "\n",
    "En 1994, Peter Shor a montré qu'il est possible de factoriser efficacement un nombre dans ses nombres premiers sur un ordinateur quantique.[1] C'est une grande nouvelle, car le meilleur algorithme classique que nous connaissons est l'un de ces algorithmes qui croît de façon exponentielle. Et en fait, le [cryptage RSA](https://en.wikipedia.org/wiki/RSA_(cryptosystem)) repose sur le fait que la factorisation de nombres suffisamment grands est infaisable. Pour factoriser des nombres entiers trop grands pour nos ordinateurs classiques actuels, il faudra des millions de qubits et de portes, et ces circuits sont beaucoup trop gros pour fonctionner avec succès sur les ordinateurs quantiques d'aujourd'hui.\n",
    "\n",
    "Alors, comment Lieven M.K. Vandersypen, Matthias Steffen, Gregory Breyta, Costantino S. Yannoni, Mark H. Sherwood et Isaac L. Chuang parviennent à factoriser 15 sur un ordinateur quantique, depuis 2001 ?![2]\n",
    "\n",
    "La difficulté de créer des circuits pour l'algorithme de Shor est de créer le circuit qui calcule un $ay \\bmod N$ contrôlé. Bien que nous sachions créer ces circuits en utilisant un nombre polynomial de portes, celles-ci sont encore trop grandes pour les ordinateurs d'aujourd'hui. Heureusement, si nous connaissons a priori quelques informations sur le problème, alors nous pouvons parfois « tricher » et créer des circuits plus efficaces.\n",
    "\n",
    "Pour exécuter ce circuit sur le matériel dont ils disposaient, les auteurs de l'article ci-dessus ont trouvé un circuit très simple qui a effectué $7y \\bmod 15$. Cela a rendu le circuit suffisamment petit pour fonctionner sur leur matériel. À la fin de cet exercice, vous aurez créé un circuit pour $35y \\bmod N$ qui peut être utilisé dans l'algorithme de Shor et peut fonctionner sur `ibmq_santiago`.\n",
    "\n",
    "Si vous voulez comprendre ce qui se passe dans cet exercice, vous devriez consulter la [page Qiskit Textbook sur l'algorithme de Shor](https://qiskit.org/textbook/ch-algorithms/shor.html), mais si c'est trop impliqué pour vous, vous pouvez terminer l'exercice sans cela.\n",
    "\n",
    "### Les références\n",
    "1. Shor, Peter W. \"Algorithms for quantum computation: discrete logarithms and factoring.\" Proceedings 35th annual symposium on foundations of computer science. Ieee, 1994.\n",
    "2. Vandersypen, Lieven MK, et al. \"Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance.\" Nature 414.6866 (2001): 883-887."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# tl;dr : algorithme de Shor\n",
    "\n",
    "Il existe un algorithme appelé [_quantum phase estimation_](https://qiskit.org/textbook/ch-algorithms/quantum-phase-estimation.html) qui nous indique la phase qu'une porte introduit dans un certain type d'état. Par exemple, les entrées de l'algorithme d'estimation de phase pourraient être l'état $|1\\rangle$ et la porte $Z$. Si la $Z$-gate agit sur l'état $|1\\rangle$, on retrouve le même état avec une phase globale ajoutée de $\\pi$ :\n",
    "\n",
    "$$\n",
    "Z|1\\rangle = -|1\\rangle = e^{i\\pi} |1\\rangle\n",
    "$$\n",
    "\n",
    "Et l'algorithme d'estimation de phase quantique pourrait résoudre ce problème pour nous. Vous pouvez voir un autre exemple [ici](https://qiskit.org/textbook/ch-algorithms/quantum-phase-estimation.html#2.-Example:-T-gate-).\n",
    "\n",
    "Shor a montré que si nous faisons une estimation de phase sur une porte, $U$, qui a le comportement $U|y\\rangle = |a y\\bmod N\\rangle$, nous pouvons rapidement obtenir des informations sur les facteurs de $N$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Le problème\n",
    "\n",
    "Dans cet exercice, nous allons factoriser 35 en effectuant une estimation de phase sur un circuit qui implémente $13y \\bmod 35$. L'exercice consiste à créer un circuit qui fait cela, et qui est également assez petit pour fonctionner sur `ibmq_santiago` ! Ce n'est pas une tâche facile, donc la première chose que nous allons faire est de tricher.\n",
    "\n",
    "Un détail de l'algorithme de Shor est que notre circuit n'a besoin de travailler que sur des états que nous pouvons atteindre en appliquant $U$ à l'état de départ $|1\\rangle$. C'est à dire. nous pouvons utiliser _any_ circuit qui a le comportement :\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "U|1\\rangle &= |13\\rangle \\\\\n",
    "UU|1\\rangle &= |29\\rangle \\\\\n",
    "UUU|1\\rangle &= |27\\rangle \\\\\n",
    "UUUU|1\\rangle &= |1\\rangle \\\\\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "Alors, comment pouvons-nous rendre cela plus facile pour nous? Comme nous n'avons besoin que de transformer correctement 4 états différents, nous pouvons les encoder sur deux qubits. Pour cet exercice, nous choisirons de mapper les états de base de calcul à 2 qubits aux nombres comme suit :\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "|1\\rangle &\\rightarrow |00\\rangle \\\\\n",
    "|13\\rangle &\\rightarrow |01\\rangle \\\\\n",
    "|29\\rangle &\\rightarrow |10\\rangle \\\\\n",
    "|27\\rangle &\\rightarrow |11\\rangle \\\\\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "Pourquoi est-ce de la « tricherie » ? Eh bien, pour tirer parti de cette optimisation, nous devons connaître tous les états que $U$ va affecter, ce qui signifie que nous devons calculer $ay \\bmod N$ jusqu'à ce que nous revenions à 1, et cela signifie que nous connaissons le période de $a^x \\bmod N$ et peut donc obtenir les facteurs de $N$. Une optimisation comme celle-ci, dans laquelle nous utilisons des informations qui nous indiqueraient la valeur $r$, ne va évidemment pas s'adapter à des problèmes que les ordinateurs classiques ne peuvent pas résoudre.\n",
    "\n",
    "Mais le but de cet exercice est juste de vérifier que l'algorithme de Shor fonctionne bien comme prévu, et nous n'allons pas nous inquiéter du fait que nous avons triché pour obtenir un circuit pour $U$.\n",
    "\n",
    "<div id='u-definition'></div>\n",
    "<div class=\"alert alert-block alert-success\">\n",
    "\n",
    "**Exercice 2a :** Créez un circuit ($U$) qui effectue la transformation :\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "U|00\\rangle &= |01\\rangle \\\\\n",
    "U|01\\rangle &= |10\\rangle \\\\\n",
    "U|10\\rangle &= |11\\rangle \\\\\n",
    "U|11\\rangle &= |00\\rangle \\\\\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "et est contrôlé par un autre qubit. Le circuit agira sur un registre cible à 2 qubits nommé « cible » et sera contrôlé par un autre registre à un seul qubit nommé « contrôle ». Vous devez affecter votre circuit fini à la variable '`cu`'.\n",
    "    \n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit import QuantumCircuit\n",
    "from qiskit import QuantumRegister, QuantumCircuit\n",
    "c = QuantumRegister(1, 'control')\n",
    "t = QuantumRegister(2, 'target')\n",
    "cu = QuantumCircuit(c, t, name=\"Controlled 13^x mod 35\")\n",
    "\n",
    "# ECRIVEZ VOTRE CODE ENTRE CES LIGNES - COMMENCER\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# ÉCRIVEZ VOTRE CODE ENTRE CES LIGNES - FIN\n",
    "\n",
    "cu.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et exécutez la cellule ci-dessous pour vérifier votre réponse :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Traceback \u001b[1;36m(most recent call last)\u001b[0m:\n",
      "\u001b[1;36m  File \u001b[1;32m\"<ipython-input-1-51e031b65df6>\"\u001b[1;36m, line \u001b[1;32m3\u001b[1;36m, in \u001b[1;35m<module>\u001b[1;36m\u001b[0m\n",
      "\u001b[1;33m    grade_ex2a(cu)\u001b[0m\n",
      "\u001b[1;31mNameError\u001b[0m\u001b[1;31m:\u001b[0m name 'cu' is not defined\n",
      "\n",
      "Use %tb to get the full traceback.\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "\n",
       "<style>\n",
       ".button {\n",
       "  border: none;\n",
       "  color: white;\n",
       "  padding: 4px 8px;\n",
       "  text-align: center;\n",
       "  text-decoration: none;\n",
       "  display: inline-block;\n",
       "  font-size: 12px;\n",
       "  margin: 4px 2px;\n",
       "  transition-duration: 0.2s;\n",
       "  cursor: pointer;\n",
       "}\n",
       ".iqx-button {\n",
       "  background-color: #0f62fe; \n",
       "  color: white; \n",
       "}\n",
       ".iqx-button:hover {\n",
       "  background-color: #0043ce;\n",
       "  color: white;\n",
       "}\n",
       "</style>\n",
       "<a href=\"https://stackoverflow.com/search?q=NameError: name 'cu' is not defined\" target='_blank'><button class='button iqx-button'>Search for solution online</button></a>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Vérifiez votre réponse en utilisant le code suivant\n",
    "from qc_grader import grade_ex2a\n",
    "grade_ex2a(cu)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Toutes nos félicitations! Vous avez terminé la partie difficile.\n",
    "\n",
    "Nous lisons la sortie de l'algorithme d'estimation de phase en mesurant les qubits, nous devrons donc nous assurer que notre registre de « comptage » contient suffisamment de qubits pour lire $r$. Dans notre cas, $r = 4$, ce qui signifie que nous n'avons besoin que de $\\log_2(4) = 2$ qubits (en trichant encore car nous connaissons $r$ à l'avance), mais comme Santiago a 5 qubits, et nous n'avons utilisé que 2 pour le registre \"cible\", nous utiliserons les 3 qubits restants comme registre de comptage.\n",
    "\n",
    "Pour faire une estimation de phase sur $U$, nous devons créer des circuits qui effectuent $U^{2^x}$ ($U$ répétés $2^x$ fois) pour chaque qubit (d'indice $x$) dans notre registre de $n$ compter les qubits. Dans notre cas, cela signifie que nous avons besoin de trois circuits qui implémentent :\n",
    "\n",
    "$$U, \\; U^2, \\; \\text{et} \\; U^4 $$\n",
    "\n",
    "L'étape suivante consiste donc à créer un circuit qui effectue $U^2$ (c'est-à-dire un circuit équivalent à appliquer $U$ deux fois).\n",
    "\n",
    "<div class=\"alert alert-block alert-success\">\n",
    "\n",
    "**Exercice 2b :** Créez un circuit ($U^2$) qui effectue la transformation :\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "U|00\\rangle &= |10\\rangle \\\\\n",
    "U|01\\rangle &= |11\\rangle \\\\\n",
    "U|10\\rangle &= |00\\rangle \\\\\n",
    "U|11\\rangle &= |01\\rangle \\\\\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "et est contrôlé par un autre qubit. Le circuit agira sur un registre cible à 2 qubits nommé « cible » et sera contrôlé par un autre registre à un seul qubit nommé « contrôle ». Vous devez affecter votre circuit fini à la variable '`cu2`'.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "c = QuantumRegister(1, 'control')\n",
    "t = QuantumRegister(2, 'target')\n",
    "cu2 = QuantumCircuit(c, t)\n",
    "\n",
    "# ECRIVEZ VOTRE CODE ENTRE CES LIGNES - COMMENCER\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# ÉCRIVEZ VOTRE CODE ENTRE CES LIGNES - FIN\n",
    "\n",
    "cu2.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et vous pouvez vérifier votre réponse ci-dessous :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Vérifiez votre réponse en utilisant le code suivant\n",
    "from qc_grader import grade_ex2b\n",
    "grade_ex2b(cu2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Enfin, nous avons également besoin d'un circuit qui équivaut à appliquer $U$ quatre fois (c'est-à-dire que nous avons besoin du circuit $U^4$).\n",
    "\n",
    "<div class=\"alert alert-block alert-success\">\n",
    "    \n",
    "**Exercice 2c :** Créez un circuit ($U^4$) qui effectue la transformation :\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "U|00\\rangle &= |00\\rangle \\\\\n",
    "U|01\\rangle &= |01\\rangle \\\\\n",
    "U|10\\rangle &= |10\\rangle \\\\\n",
    "U|11\\rangle &= |11\\rangle \\\\\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "et est contrôlé par un autre qubit. Le circuit agira sur un registre cible à 2 qubits nommé « cible » et sera contrôlé par un autre registre à un seul qubit nommé « contrôle ». Vous devez affecter votre circuit fini à la variable '`cu4`'. _Indice : La meilleure solution est très simple._\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Traceback \u001b[1;36m(most recent call last)\u001b[0m:\n",
      "\u001b[1;36m  File \u001b[1;32m\"<ipython-input-3-7cf52742833d>\"\u001b[1;36m, line \u001b[1;32m1\u001b[1;36m, in \u001b[1;35m<module>\u001b[1;36m\u001b[0m\n",
      "\u001b[1;33m    c = QuantumRegister(1, 'control')\u001b[0m\n",
      "\u001b[1;31mNameError\u001b[0m\u001b[1;31m:\u001b[0m name 'QuantumRegister' is not defined\n",
      "\n",
      "Use %tb to get the full traceback.\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "\n",
       "<style>\n",
       ".button {\n",
       "  border: none;\n",
       "  color: white;\n",
       "  padding: 4px 8px;\n",
       "  text-align: center;\n",
       "  text-decoration: none;\n",
       "  display: inline-block;\n",
       "  font-size: 12px;\n",
       "  margin: 4px 2px;\n",
       "  transition-duration: 0.2s;\n",
       "  cursor: pointer;\n",
       "}\n",
       ".iqx-button {\n",
       "  background-color: #0f62fe; \n",
       "  color: white; \n",
       "}\n",
       ".iqx-button:hover {\n",
       "  background-color: #0043ce;\n",
       "  color: white;\n",
       "}\n",
       "</style>\n",
       "<a href=\"https://stackoverflow.com/search?q=NameError: name 'QuantumRegister' is not defined\" target='_blank'><button class='button iqx-button'>Search for solution online</button></a>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "c = QuantumRegister(1, 'control')\n",
    "t = QuantumRegister(2, 'target')\n",
    "cu4 = QuantumCircuit(c, t)\n",
    "\n",
    "# ÉCRIVEZ VOTRE CODE ENTRE CES LIGNES - COMMENCER\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# ÉCRIVEZ VOTRE CODE ENTRE CES LIGNES - FIN\n",
    "\n",
    "cu4.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vous pouvez vérifier votre réponse en utilisant le code ci-dessous :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Traceback \u001b[1;36m(most recent call last)\u001b[0m:\n",
      "\u001b[1;36m  File \u001b[1;32m\"<ipython-input-4-576cbbc7571f>\"\u001b[1;36m, line \u001b[1;32m3\u001b[1;36m, in \u001b[1;35m<module>\u001b[1;36m\u001b[0m\n",
      "\u001b[1;33m    grade_ex2c(cu4)\u001b[0m\n",
      "\u001b[1;31mNameError\u001b[0m\u001b[1;31m:\u001b[0m name 'cu4' is not defined\n",
      "\n",
      "Use %tb to get the full traceback.\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "\n",
       "<style>\n",
       ".button {\n",
       "  border: none;\n",
       "  color: white;\n",
       "  padding: 4px 8px;\n",
       "  text-align: center;\n",
       "  text-decoration: none;\n",
       "  display: inline-block;\n",
       "  font-size: 12px;\n",
       "  margin: 4px 2px;\n",
       "  transition-duration: 0.2s;\n",
       "  cursor: pointer;\n",
       "}\n",
       ".iqx-button {\n",
       "  background-color: #0f62fe; \n",
       "  color: white; \n",
       "}\n",
       ".iqx-button:hover {\n",
       "  background-color: #0043ce;\n",
       "  color: white;\n",
       "}\n",
       "</style>\n",
       "<a href=\"https://stackoverflow.com/search?q=NameError: name 'cu4' is not defined\" target='_blank'><button class='button iqx-button'>Search for solution online</button></a>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Vérifiez votre réponse en utilisant le code suivant\n",
    "from qc_grader import grade_ex2c\n",
    "grade_ex2c(cu4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-success\">\n",
    "\n",
    "**Exercice 2 final :** Maintenant que nous avons contrôlé $U$, $U^2$ et $U^4$, nous pouvons combiner cela dans un circuit qui exécute la partie quantique de l'algorithme de Shor.\n",
    "\n",
    "La partie initialisation est simple : nous devons mettre le registre de comptage dans l'état $|{+}{+}{+}\\rangle$ (ce que nous pouvons faire avec trois portes H) et nous avons besoin que le registre cible soit dans l'état $|1\\rangle$ (que nous avons mappé à l'état de base de calcul $|00\\rangle$, nous n'avons donc rien à faire ici). Nous ferons tout cela pour vous.\n",
    "\n",
    "_Votre_ tâche consiste à créer un circuit qui exécute les $U$ contrôlés, qui seront utilisés entre l'initialisation et la transformée de Fourier quantique inverse. Plus formellement, on veut un circuit :\n",
    "\n",
    "\n",
    "$$\n",
    "CU_{c_0 t}CU^2_{c_1 t}CU^4_{c_2 t}\n",
    "$$\n",
    "\n",
    "Où $c_0$, $c_1$ et $c_2$ sont les trois qubits dans le registre 'comptage', $t$ est le registre 'cible' et $U$ est comme <a href=\"#u-definition\"> défini dans la première partie de cet exercice</a>. Dans cette notation, $CU_{a b}$ signifie que $CU$ est contrôlé par $a$ et agit sur $b$. Une solution simple consiste à simplement combiner les circuits `cu`, `cu2` et `cu4` que vous avez créés ci-dessus, mais vous trouverez très probablement un circuit plus efficace qui a le même comportement !\n",
    "    \n",
    "</div>\n",
    "<div class=\"alert alert-block alert-danger\">\n",
    "    \n",
    "Votre circuit ne peut contenir que des [CNOTs](https://qiskit.org/documentation/stubs/qiskit.circuit.library.CXGate.html) et un seul qubit [U-gates](https://qiskit.org/documentation/stubs/qiskit.circuit.library.UGate.html). Votre score sera le nombre de CNOTs que vous utilisez (moins c'est mieux), car les portes multi-qubit sont généralement beaucoup plus difficiles à réaliser sur le matériel que les portes à qubit unique. Si vous rencontrez des difficultés avec cette exigence, nous avons inclus une ligne de code à côté de la soumission qui convertira votre circuit sous cette forme, bien que vous feriez probablement mieux à la main.\n",
    "    \n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Code pour combiner vos solutions précédentes dans votre soumission finale\n",
    "cqr = QuantumRegister(3, 'control')\n",
    "tqr = QuantumRegister(2, 'target')\n",
    "cux = QuantumCircuit(cqr, tqr)\n",
    "solutions = [cu, cu2, cu4]\n",
    "for i in range(3):\n",
    "    cux = cux.compose(solutions[i], [cqr[i], tqr[0], tqr[1]])\n",
    "cux.draw('mpl')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Vérifiez votre réponse en utilisant le code suivant\n",
    "from qc_grader import grade_ex2_final\n",
    "# Décommentez les deux lignes ci-dessous si vous devez convertir votre circuit en CNOTs et en portes à qubit unique\n",
    "#from qiskit import transpile\n",
    "#cux = transpile(cux, basis_gates=['cx','u'])\n",
    "grade_ex2_final(cux)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une fois que vous êtes satisfait du circuit, vous pouvez le soumettre ci-dessous :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Soumettez votre réponse. Vous pouvez soumettre à nouveau à tout moment.\n",
    "from qc_grader import submit_ex2_final\n",
    "submit_ex2_final(cux)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Toutes nos félicitations! Vous avez terminé l'exercice. Lisez la suite pour voir votre circuit utilisé pour le facteur 35 et voir comment il fonctionne.\n",
    "\n",
    "## Utilisation de votre circuit pour factoriser 35\n",
    "\n",
    "La cellule de code ci-dessous prend votre soumission pour l'exercice et l'utilise pour créer un circuit qui nous donnera $\\tfrac{s}{r}$, où $s$ est un entier aléatoire entre $0$ et $r-1$, et $r$ est la période de la fonction $f(x) = 13^x \\bmod 35$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit.circuit.library import QFT\n",
    "from qiskit import ClassicalRegister\n",
    "# Créer l'objet circuit\n",
    "cr = ClassicalRegister(3)\n",
    "shor_circuit = QuantumCircuit(cqr, tqr, cr)\n",
    "\n",
    "# Initialiser les qubits\n",
    "shor_circuit.h(cqr)\n",
    "\n",
    "# Ajoutez votre circuit\n",
    "shor_circuit = shor_circuit.compose(cux)\n",
    "\n",
    "# Effectuer le QFT inverse et extraire la sortie\n",
    "shor_circuit.append(QFT(3, inverse=True), cqr)\n",
    "shor_circuit.measure(cqr, cr)\n",
    "shor_circuit.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Transpilons ce circuit et voyons quelle est sa taille et combien de CNOTs il utilise :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "from qiskit import Aer, transpile, assemble\n",
    "from qiskit.visualization import plot_histogram\n",
    "qasm_sim = Aer.get_backend('aer_simulator')\n",
    "tqc = transpile(shor_circuit, basis_gates=['u', 'cx'], optimization_level=3)\n",
    "print(f\"circuit depth: {tqc.depth()}\")\n",
    "print(f\"Circuit contains {tqc.count_ops()['cx']} CNOTs\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et voyons ce que nous obtenons :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "counts = qasm_sim.run(tqc).result().get_counts()\n",
    "plot_histogram(counts)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En supposant que tout a fonctionné correctement, nous devrions voir une probabilité égale de mesurer les nombres 0$, 2$, 4$ et 8$. En effet, l'estimation de phase nous donne $2^n \\cdot \\tfrac{s}{r}$, où $n$ est le nombre de qubits dans notre registre de comptage (ici $n = 3$, $s$ est un entier aléatoire entre $0$ et $r-1$, et $r$ est le nombre que nous essayons de calculer). Convertissons-les en fractions qui nous disent $s/r$ (c'est quelque chose que nous pouvons facilement calculer classiquement) :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from fractions import Fraction\n",
    "n = 3  # n est le nombre de qubits dans notre registre de \"comptage\"\n",
    "# Parcourez chaque chaîne de mesure\n",
    "for measurement in counts.keys():\n",
    "    # Convertissez la chaîne binaire en 'int' et divisez par 2^n\n",
    "    decimal = int(measurement, 2)/2**n\n",
    "    # Utilisez l'algorithme des fractions continues pour convertir en forme a/b\n",
    "    print(Fraction(decimal).limit_denominator())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous pouvons voir que le dénominateur de certains des résultats nous dira la bonne réponse $r = 4$. On peut vérifier $r = 4$ rapidement :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "13**4 % 35"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Alors, comment pouvons-nous en tirer les facteurs ? Il y a alors une forte probabilité que le plus grand commun diviseur de $N$ et soit $a^{r/2}-1$ soit $a^{r/2}+1$ soit un facteur de $N$, et le le plus grand diviseur commun est aussi quelque chose que nous pouvons facilement calculer de manière classique."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import gcd # Greatest common divisor\n",
    "for x in [-1, 1]:\n",
    "    print(f\"Guessed factor: {gcd(13**(4//2)+x, 35)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous n'avons besoin que de trouver un facteur et pouvons l'utiliser pour diviser $N$ pour trouver l'autre facteur. Mais dans ce cas, _both_ $a^{r/2}-1$ ou $a^{r/2}+1$ nous donnent les facteurs de $35$. Nous pouvons à nouveau vérifier que cela est correct :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "7*5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exécution sur `ibmq_santiago`\n",
    "\n",
    "Nous avons promis que cela fonctionnerait sur Santiago, nous allons donc vous montrer ici comment faire cela. Dans cet exemple, nous utiliserons un appareil Santiago simulé pour plus de commodité, mais vous pouvez le remplacer par l'appareil réel si vous le souhaitez :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Traceback \u001b[1;36m(most recent call last)\u001b[0m:\n",
      "\u001b[1;36m  File \u001b[1;32m\"<ipython-input-5-08c7db1515f3>\"\u001b[1;36m, line \u001b[1;32m15\u001b[1;36m, in \u001b[1;35m<module>\u001b[1;36m\u001b[0m\n",
      "\u001b[1;33m    tqc = transpile(shor_circuit, santiago, optimization_level=3)\u001b[0m\n",
      "\u001b[1;31mNameError\u001b[0m\u001b[1;31m:\u001b[0m name 'transpile' is not defined\n",
      "\n",
      "Use %tb to get the full traceback.\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "\n",
       "<style>\n",
       ".button {\n",
       "  border: none;\n",
       "  color: white;\n",
       "  padding: 4px 8px;\n",
       "  text-align: center;\n",
       "  text-decoration: none;\n",
       "  display: inline-block;\n",
       "  font-size: 12px;\n",
       "  margin: 4px 2px;\n",
       "  transition-duration: 0.2s;\n",
       "  cursor: pointer;\n",
       "}\n",
       ".iqx-button {\n",
       "  background-color: #0f62fe; \n",
       "  color: white; \n",
       "}\n",
       ".iqx-button:hover {\n",
       "  background-color: #0043ce;\n",
       "  color: white;\n",
       "}\n",
       "</style>\n",
       "<a href=\"https://stackoverflow.com/search?q=NameError: name 'transpile' is not defined\" target='_blank'><button class='button iqx-button'>Search for solution online</button></a>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from qiskit.test.mock import FakeSantiago\n",
    "from qiskit import assemble\n",
    "from qiskit.visualization import plot_histogram\n",
    "santiago = FakeSantiago()\n",
    "real_device = False\n",
    "\n",
    "# Décommentez ce bloc de code pour qu'il s'exécute sur l'appareil réel\n",
    "#from qiskit import IBMQ\n",
    "#IBMQ.load_account()\n",
    "#provider = IBMQ.get_provider(hub='ibm-q', group='open', project='main')\n",
    "#santiago = provider.get_backend('ibmq_santiago')\n",
    "#real_device = True\n",
    "\n",
    "# Nous devons transpiler pour Santiago\n",
    "tqc = transpile(shor_circuit, santiago, optimization_level=3)\n",
    "\n",
    "if not real_device:\n",
    "    tqc = assemble(tqc)\n",
    "\n",
    "# Exécutez le circuit et imprimez les comptes\n",
    "counts = santiago.run(tqc).result().get_counts()\n",
    "plot_histogram(counts)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Si votre score était suffisamment bas, vous devriez voir que nous avons une forte probabilité de mesurer $0$, $2$, $4$ ou $8$ comme nous l'avons vu avec la simulation parfaite. Vous verrez des résultats supplémentaires en raison d'inexactitudes dans le processeur et d'éléments indésirables interagissant avec nos qubits. Ce \"bruit\" s'aggrave à mesure que notre circuit est long, car un temps de calcul plus long signifie plus de temps pour les interactions indésirables, et plus de portes signifie plus d'erreurs potentielles. C'est pourquoi nous avons dû tricher pour créer le plus petit circuit possible.\n",
    "\n",
    "Dans un avenir proche, nos systèmes quantiques s'amélioreront suffisamment pour que nous puissions commencer à utiliser des techniques d'atténuation des erreurs plus avancées pour surmonter ces problèmes, ce qui signifie que nous pourrons exécuter des circuits suffisamment grands pour [exécuter l'algorithme de Shor sans tricher](https://arxiv.org/pdf/quant-ph/0205095.pdf)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Additional information\n",
    "\n",
    "**Created by:** Frank Harkins\n",
    "\n",
    "**Version:** 1.0.0"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  },
  "nbdime-conflicts": {
   "local_diff": [
    {
     "diff": [
      {
       "diff": [
        {
         "key": 0,
         "length": 1,
         "op": "removerange"
        }
       ],
       "key": "version",
       "op": "patch"
      }
     ],
     "key": "language_info",
     "op": "patch"
    }
   ],
   "remote_diff": [
    {
     "diff": [
      {
       "diff": [
        {
         "diff": [
          {
           "key": 4,
           "op": "addrange",
           "valuelist": "8"
          },
          {
           "key": 4,
           "length": 1,
           "op": "removerange"
          }
         ],
         "key": 0,
         "op": "patch"
        }
       ],
       "key": "version",
       "op": "patch"
      }
     ],
     "key": "language_info",
     "op": "patch"
    }
   ]
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}