content/ex2/ex2-es.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "XWNLHnfAwUAS"
   },
   "source": [
    "# Ejercicio 2 - Algoritmo de Shor\n",
    "## Contexto histórico\n",
    "\n",
    "En computación, frecuentemente medimos el desempeño de un algoritmo por cómo crece el problema con el tamaño de la entrada. Por ejemplo, para la adición el algoritmo crece linealmente con el tamaño de los números a sumar. Hay algunos problemas de cómputo para los cuales los mejores algoritmos crecen _exponencialmente_ con el tamaño de la entrada, y esto significa que entradas de tamaño relativalemente modesto son demasiado grandes para ser tratadas por cualquier computadora en la Tierra. Estamos tan seguros de esto, que mucha de la seguridad de internet depende de la falta de solución a ciertos problemas. \n",
    "\n",
    "En 1994, Peter Shor demostró que es posible descomponer un número en sus factores primos de manera eficaz en una computadora cuántica.[1]  Estas son buenas noticias, ya que el mejor algoritmo clásico que conocemos es uno de esos algoritmos que crecen exponencialmente. De hecho, el sistema criptográfico [RSA](https://es.wikipedia.org/wiki/RSA) está basado en la inviabilidad de factorizar números lo suficientemente grandes. Factorizar números enteros muy grandes con las computadoras clásicas actuales requeriría millones de cúbits y de compuertas, y estos circuitos son excesivamente grandes para ejecutarse con éxito en las computadoras cuánticas de hoy en día. \n",
    "\n",
    "¡¿Cómo hicieron Lieven M.K. Vandersypen, Matthias Steffen, Gregory Breyta, Costantino S. Yannoni, Mark H. Sherwood e Isaac L. Chuang para factorizar el número 15 en una computadora cuántica, ya hace bastante tiempo, en 2001?![2]\n",
    "\n",
    "La dificultad de recrear el algoritmo de Shor consiste en crear el circuito que calcula $ay \\bmod N$. Si bien conocemos cómo crear estos circuitos usando un número polinomial de compuertas, estos circuitos son demasiado largos para las computadoras de hoy en día. Afortunadamente, si a priori tenemos una información sobre el problema, entonces podemos, a veces, 'hacer trampa' y crear un circuito más eficiente.\n",
    "\n",
    "Para la ejecución de este circuito en el hardware que tenían disponible en la época, los autores del artículo de arriba encontraron un circuito muy simple que lleva a cabo $7y \\bmod 15$. Esto hace al circuito lo suficientemente pequeño para ejecutarlo en su hardware. Una vez llegado al final de este ejercicio, ya habrás creado un circuito para $35y \\bmod N$ que puede ser usado en el algoritmo de Shor y que puede ejecutarse en `ibmq_santiago`.\n",
    "\n",
    "Si quieres entender de qué va el ejercicio, deberías revisar [la página del libro de texto de Qiskit sobre el algoritmo de Shor](https://qiskit.org/textbook/ch-algorithms/shor.html), pero si esto implica mucho esfuerzo para ti, puedes completar este ejercicio sin leerla.\n",
    "\n",
    "### Referencias\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",
    "1. 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": {
    "id": "3R-BKlSewUAX"
   },
   "source": [
    "## Vayamos al grano, el algoritmo de Shor\n",
    "Existe un algoritmo llamado [_estimación cuántica de la fase_](https://qiskit.org/textbook/ch-algorithms/quantum-phase-estimation.html) que nos dice cuál es la fase que una compuerta introduce a un cierto tipo de estado. Por ejemplo, las entradas para el algoritmo para estimar la fase podrían ser el estado $|1\\rangle$ y $Z$ la compuerta. Si la compuerta $Z$ actúa sobre el estado $|1\\rangle$, obtenemos el mismo estado de vuelta con una fase global de  $\\pi$\n",
    "\n",
    "$$\n",
    "Z|1\\rangle = -|1\\rangle = e^{i\\pi} |1\\rangle\n",
    "$$\n",
    "\n",
    "y el algoritmo cuántico de estimación de la fase podría hacer el trabajo por nosotros. Ver otro ejemplo [aquí](https://qiskit.org/textbook/ch-algorithms/quantum-phase-estimation.html#2.-Example:-T-gate-).\n",
    "\n",
    "Shor demostró que si estimamos la fase de una compuerta $U$, que se comporta como $U|y\\rangle = |a y\\bmod N\\rangle$, podemos rápidamente obtener información sobre los factores primos de $N$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "zVq7fn1ywUAY"
   },
   "source": [
    "## El problema\n",
    "\n",
    "En este ejercicio, factorizaremos 35 a través de una estimación de fase en un circuito que implementa $13y \\bmod 35$. El ejercicio consiste en crear el circuito que hace esto y  ¡que sea lo suficientemente pequeño para ejecutarse en `ibmq_santiago`! Esta no es una tarea fácil, así que la primera cosa que vamos a hacer es hacer trampa.\n",
    "\n",
    "Un detalle a saber sobre el algoritmo de Shor es que solo necesitamos en nuestro circuito los estados que podemos alcanzar a través de aplicaciones sucesivas de $U$ sobre el estado de partida $|1\\rangle$, i.e. podemos usar _cualquier_ circuito con el comportamiento siguiente:\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",
    "¿Cómo hacer esto más fácil para nosotros? Visto que solo necesitamos transformar 4 estados diferentes de manera correcta, podemos codificarlos en dos cúbits. Para este ejercicio, elegimos representar estos números en la base computacional a dos cúbits de la manera siguiente:\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",
    "¿Por qué esto es \"hacer trampa\"? Bueno, para tomar ventaja de la optimización, necesitamos conocer todos los estados que van a ser afectados por $U$, lo que significa que tenemos que calcular $ay \\bmod N$ hasta que regresemos a 1, y esto significa que ya conocemos el período de $a^x \\bmod N$ y por lo tanto ya podemos extraer los factores primos de $N$. Cualquier optimización como esta, en la que usamos información que nos puede decir el valor de $r$, no es escalable para problemas que una computadora clásica no puede resolver.\n",
    "\n",
    "Pero el propósito de este ejercicio es justamente el de verificar que el algoritmo de Shor sí funciona como previsto, y no nos vamos a preocupar por el hecho de que hicimos trampa para obtener el circuito para $U$.\n",
    "\n",
    "\n",
    "<div id='u-definition'></div>\n",
    "<div class=\"alert alert-block alert-success\">\n",
    "\n",
    "**Ejercicio 2a:** Crear un circuito ($U$) que lleve a cabo la transformación:\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",
    "y que esté controlado por otro cúbit. El circuito deberá actuar sobre un registro objetivo de 2 cúbits llamado 'target', y estará controlado por otro registro de un único cúbit llamado 'control'. Deberás asignar tu circuito final a la variable '`cu`'.\n",
    "    \n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "jdZIrQEEwUAb",
    "scrolled": true
   },
   "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",
    "# ESCRIBE TU CÓDIGO ENTRE ESTAS LÍNEAS- INICIO\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# ESCRIBE TU CÓDIGO ENTRE ESTAS LÍNEAS - FIN\n",
    "\n",
    "cu.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "BM0ixg8CwUAc"
   },
   "source": [
    "y ejecuta la celda siguiente para verificar tu respuesta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "ON-13rxhwUAd",
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Verifica tu respuesta usando el siguiente código\n",
    "from qc_grader import grade_ex2a\n",
    "grade_ex2a(cu)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "1amzkrGNwUAe"
   },
   "source": [
    "¡Felicidades! Ya completaste la parte difícil. \n",
    "\n",
    "Midiendo los cúbits podemos leer la salida del algoritmo de estimación de la fase, así que tenemos que asegurarnos que nuestro registro de 'conteo', contiene suficientes cúbits para leer $r$. En nuestro caso, $r=4$, lo que significa que solo neecesitamos $\\log_2(4) = 2$ cúbits (de nuevo haciendo trampa ya que conocemos $r$ de antemano), pero ya que Santiago tiene 5 cúbits, y solo utilisamos 2 para el registro 'target', utilizaremos los restantes 3 cúbits como nuestro registro de conteo.\n",
    "\n",
    "Para hacer la estimación de fase sobre $U$, necesitamos crear un circuito que lleva a cabo  $U^{2^x}$ ($U$ repetida $2^x$ veces) para cada cúbit (con índice $x$) en nuestro registro de conteo de $n$ cúbits. En nuestro caso esto significa que necesitamos 3 circuitos que implementen:\n",
    "\n",
    "$$ U, \\; U^2, \\; \\text{y} \\; U^4 $$\n",
    "\n",
    "Así que el paso siguiente consiste en crear el circuito que lleva a cabo $U^2$ (i.e. un circuito equivalente a aplicar $U$ dos veces).\n",
    "\n",
    "<div class=\"alert alert-block alert-success\">\n",
    "\n",
    "**Ejercicio 2b:** Crear un circuito ($U^2$) que lleve a cabo la transformación:\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",
    "y que esté controlado por otro cúbit. El circuito deberá actuar sobre un registro objetivo de 2 cúbits llamado 'target', y estará controlado por otro registro de un único cúbit llamado 'control'. Deberás asignar tu circuito final a la variable '`cu2`'.\n",
    "\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "C-rgmNZ9wUAe",
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "c = QuantumRegister(1, 'control')\n",
    "t = QuantumRegister(2, 'target')\n",
    "cu2 = QuantumCircuit(c, t)\n",
    "\n",
    "# ESCRIBE TU CÓDIGO ENTRE ESTAS LÍNEAS- INICIO\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# ESCRIBE TU CÓDIGO ENTRE ESTAS LÍNEAS - FIN\n",
    "\n",
    "cu2.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "t9yk_CzvwUAf"
   },
   "source": [
    "y puedes verificar tu respuesta de la manera siguiente:\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "WNvolLaiwUAg",
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Verifica tu respuesta usando el siguiente código\n",
    "from qc_grader import grade_ex2b\n",
    "grade_ex2b(cu2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "0r9ZAxfqwUAh"
   },
   "source": [
    "Finalmente, necesitamos también un circuito que sea equivalente a aplicar $U$ cuatro veces (i.e. necesitas el circuito $U^4$). \n",
    "\n",
    "<div class=\"alert alert-block alert-success\">\n",
    "    \n",
    "**Ejercicio 2c:** Crear un circuito ($U^4$) que lleve a cabo la transformación:\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",
    "y que esté controlado por otro cúbit. El circuito deberá actuar sobre un registro objetivo de 2 cúbits llamado 'target', y estará controlado por otro registro de un único cúbit llamado 'control'. Deberás asignar tu circuito final a la variable '`cu4`'. _Pista: La mejor solución es la más simple._\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "6W1lVCdtwUAi",
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "c = QuantumRegister(1, 'control')\n",
    "t = QuantumRegister(2, 'target')\n",
    "cu4 = QuantumCircuit(c, t)\n",
    "\n",
    "# ESCRIBE TU CÓDIGO ENTRE ESTAS LÍNEAS- INICIO\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# ESCRIBE TU CÓDIGO ENTRE ESTAS LÍNEAS - FIN\n",
    "\n",
    "\n",
    "cu4.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "C9f-mm4bwUAi"
   },
   "source": [
    "y puedes verificar tu respuesta de la manera siguiente:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "h1HhoUoHwUAj",
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Verifica tu respuesta usando el siguiente código\n",
    "from qc_grader import grade_ex2c\n",
    "grade_ex2c(cu4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "rlKrjm6OwUAj"
   },
   "source": [
    "<div class=\"alert alert-block alert-success\">\n",
    "\n",
    "**Ejercicio 2 - ejercicio final:** Ahora que tenemos la versión controlada de  $U$, $U^2$ y $U^4$, podemos combinarlas en un circuito que lleva a cabo la parte cuántica del algoritmo de Shor.\n",
    "\n",
    "La preparación de los cúbits es fácil: necesitamos poner el registro de conteo en el estado $|{+}{+}{+}\\rangle$ (que podemos obtener con tres compuertas H) y necesitamos que el registro 'target' esté en el estado $|1\\rangle$ (el cual representamos con el estado $|00\\rangle$ de la base computacional, así que no necesitamos hacer nada). Toda esta preparación la haremos por ti.\n",
    "\n",
    "_Tu_ tarea es crear un circuito que lleve a cabo las compuertas controladas de $U$s, que serán usadas entre la preparación y la transformada de Fourier cuántica inversa. Formalemente, queremos un circuito:\n",
    "\n",
    "\n",
    "$$\n",
    "CU_{c_0 t}CU^2_{c_1 t}CU^4_{c_2 t}\n",
    "$$\n",
    "\n",
    "dónde $c_0$, $c_1$ y $c_2$ son tres cúbits en el registro de conteo, $t$ es el registro 'target' y $U$ está <a href=\"#u-definition\">definida en la primera parte del ejercicio</a>. En esta notación, $CU_{a b}$ indica que $CU$ está controlada por $a$ y actúa sobre $b$. Una solución fácil a este problema es combinar los circuitos `cu`, `cu2` y `cu4` que creaste arriba, pero muy probablemente encontrarás un circuito más eficiente con el mismo comportamiento.\n",
    "\n",
    "    \n",
    "</div>\n",
    "<div class=\"alert alert-block alert-danger\">\n",
    "\n",
    "Tu circuito solo puede contener [CNOTs](https://qiskit.org/documentation/stubs/qiskit.circuit.library.CXGate.html) y [compuertas-U](https://qiskit.org/documentation/stubs/qiskit.circuit.library.UGate.html) a un solo cúbit. Tu puntaje es igual al número de CNOTs que utilizaste (mientras menos mejor), ya que las compuertas a varios cúbits son usualmente mucho más difíciles de llevar a cabo en el hardware en comparación con las compuertas a un cúbit. Si se te dificulta este último requisito, hemos incluido una línea de código cerca de la verificación que escribirá tu circuito con estas condiciones, aunque es posible que hacerlo mejor manualmente.  \n",
    "    \n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "8KBjWMphwUAk",
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Código para combinar tus soluciones previas en tu respuesta final\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": {
    "id": "GRwEcjGdwUAk",
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Verifica tu respuesta usando el código siguiente\n",
    "from qc_grader import grade_ex2_final\n",
    "# Descomenta las dos líneas de abajo si necesitas convertir tu circuito en CNOTs y en compuertas a un cúbit\n",
    "#from qiskit import transpile\n",
    "#cux = transpile(cux, basis_gates=['cx','u'])\n",
    "grade_ex2_final(cux)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "a3zRMFAHwUAl"
   },
   "source": [
    "Una vez satisfecho/a con el circuito, puedes enviar tu respuesta a continuación: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "0Tj9gLMvwUAl",
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Envía tu respuesta. Puedes volver a envíar tu respuesta en cualquier momento.\n",
    "from qc_grader import submit_ex2_final\n",
    "submit_ex2_final(cux)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "WyHcuSPowUAm"
   },
   "source": [
    "¡Felicidades! Haz terminado el ejercicio. Continúa la lectura para que veas el uso de tu circuito para factorizar 35, y ver su desempeño.\n",
    "\n",
    "## Usando tu circuito para factorizar 35\n",
    "\n",
    "La celda de código siguiente recupera el circuito que enviaste en el ejercicio y lo utiliza para crear un circuito que nos dará $\\tfrac{s}{r}$, dónde $s$ es un entero tomado aleatoriamente entre $0$ and $r-1$, y $r$ es el período de la función $$f(x) = 13^x \\bmod 35.$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "hGrsWjZewUAm",
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "from qiskit.circuit.library import QFT\n",
    "from qiskit import ClassicalRegister\n",
    "# Crea un objeto tipo circuito\n",
    "cr = ClassicalRegister(3)\n",
    "shor_circuit = QuantumCircuit(cqr, tqr, cr)\n",
    "\n",
    "# Prepara los cúbits\n",
    "shor_circuit.h(cqr)\n",
    "\n",
    "# Añade tu circuito\n",
    "shor_circuit = shor_circuit.compose(cux)\n",
    "\n",
    "# Calcula la transformada cuántica de Fourier inversa y extrae la salida\n",
    "shor_circuit.append(QFT(3, inverse=True), cqr)\n",
    "shor_circuit.measure(cqr, cr)\n",
    "shor_circuit.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "e_aLBvqewUAn"
   },
   "source": [
    "Transpilemos el circuito y veamos que tan grande es y cuantas CNOTs utiliza:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "pn0pBZ5bwUAn",
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "from qiskit import Aer, transpile\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\"profundidad del circuito: {tqc.depth()}\")\n",
    "print(f\"el circuito contiene {tqc.count_ops()['cx']} CNOTs\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "mGWje-cPwUAo"
   },
   "source": [
    "Y veamos qué obtenemos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "B93b11JkwUAo",
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "counts = qasm_sim.run(tqc).result().get_counts()\n",
    "plot_histogram(counts)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "pXmaGh0twUAo"
   },
   "source": [
    "Suponiendo que todo ha funcionado correctamente, deberíamos ver probabilidades iguales para medir los números $0$, $2$, $4$, $8$. Esto se debe a que la estimación de la fase nos da $2^n \\cdot \\tfrac{s}{r}$, donde $n$ es el número de cúbits en nuestro registro de conteo (aquí $n=3$, $s$ is un número aleatorio entre  $0$ y $r-1$, y $r$ es un número que estamos intentando calcular). Convirtamos esto en fracciones de $s/r$ (esto es algo que es fácil de calcular clásicamente):\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "fHAH8DiawUAp",
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "from fractions import Fraction\n",
    "n = 3  # n es el número de cúbits en el registro de conteo\n",
    "# Bucle sobre cada valor de la medida\n",
    "for measurement in counts.keys():\n",
    "    # Convierte el código binario tipo string en 'int', y divide por 2^n\n",
    "    decimal = int(measurement, 2)/2**n\n",
    "    # Usando el algoritmos de fracciones continuas lo convertimos en la forma a/b\n",
    "    print(Fraction(decimal).limit_denominator())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "uy3urqXywUAq"
   },
   "source": [
    "Podemos ver que el denominador de algunos resultados nos dirá cúal es la respuesta correcta $r = 4$. Podemos verificar $r=4$ rápidamente:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "PqBfGh89wUAq",
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "13**4 % 35"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "miO5bwzOwUAr"
   },
   "source": [
    "¿Pero de aquí cómo obtenemos los factores primos?  Existe así una alta probabilidad que el máximo común divisior de $N$, $a^{r/2}-1$ o $a^{r/2}+1$, sea un factor de $N$, y el máximo común divisor también se puede calcular clásicamente.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "wBH6GdkpwUAr",
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "from math import gcd # máximo común divisor\n",
    "for x in [-1, 1]:\n",
    "    print(f\"Valor estimado: {gcd(13**(4//2)+x, 35)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "dSBWMHpGwUAr"
   },
   "source": [
    "Solo necesitamos conseguir un factor, y podemos usarlo para dividir $N$ para conseguir el otro factor. Pero en este caso, _ambos_  $a^{r/2}-1$ y $a^{r/2}+1$ son factores de $35$. De nuevo, verifiquemos que esto es correcto:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "BAWbIROSwUAr",
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "7*5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "xTqcyHuJwUAr"
   },
   "source": [
    "## Ejecución en `ibmq_santiago`\n",
    "\n",
    "Como prometido este algoritmo se puede ejecutar en Santiago, así que aquí te mostraremos como hacer eso. En este ejemplo, usamos un simulador del dispositivo Santiago por conveniencia, pero si prefieres puedes cambiar esto por el verdadero dispositivo:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "8EEMJQ6xwUAr",
    "scrolled": true
   },
   "outputs": [],
   "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",
    "## Descomenta este bloque de código para la ejecución del algoritmo en el verdadero dispositivo\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",
    "# Necesitamos transpilar para enviar a Santiago\n",
    "tqc = transpile(shor_circuit, santiago, optimization_level=3)\n",
    "\n",
    "if not real_device:\n",
    "    tqc = assemble(tqc)\n",
    "\n",
    "# Ejecuta el circuito e imprime los resultados\n",
    "counts = santiago.run(tqc).result().get_counts()\n",
    "plot_histogram(counts)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "baOMoUr3wUAs"
   },
   "source": [
    "Si tu puntaje fue lo suficientemente bajo, deberías ver una alta probabilidad de medir $0$, $2$, $4$ or $8$ como vimos en la simulación perfecta. Verás otros resultados adicionales debido a imperfecciones en el procesador y cosas indeseadas que interactúan con nuestros cúbits. Este 'ruido' se vuelve mucho peor mientras es más largo el circuito, ya que más tiempo de cómputo le da más tiempo a las interacciones indeseadas, y más compuertas significa mayor potencial a errores. Es por esto que necesitamos hacer trampa para crear un circuito lo más pequeño posible. \n",
    "\n",
    "En el futuro cercano, nuestro sistema cuántico va mejorar lo suficiente de modo que podremos usar técnicas avanzadas de mitigación de errores para sobrepasar estos problemas, lo que significará que podremos ejecutar circuitos lo suficientemente grandes para [llevar a cabo el algoritmo Shor sin hacer trampa](https://arxiv.org/pdf/quant-ph/0205095.pdf).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "--gtCw0LwUAs"
   },
   "source": [
    "## Información\n",
    "\n",
    "**Created by:** Frank Harkins\n",
    "\n",
    "**Latin-American Spanish translation:** Mauricio Gómez Viloria, Manuel Morgado\n",
    "\n",
    "**Version:** 1.0.0"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "ex2-es.ipynb",
   "provenance": [],
   "toc_visible": true
  },
  "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
}