lab4_ex1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![image](resources/qgss-header.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lab 4: Shor's Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this lab, you will implement a quantum program to factor the number 15. In order to do this, you will write `Qiskit` code for Shor's algorithm following the material presented in lecture 4.\n",
    "\n",
    "You might find the following chapters of the Qiskit Textbook useful:\n",
    "- **Shor's algorithm**: https://qiskit.org/textbook/ch-algorithms/shor.html\n",
    "- **Quantum phase estimation**: https://qiskit.org/textbook/ch-algorithms/quantum-phase-estimation.html\n",
    "- **Quantum Fourier transform**: https://qiskit.org/textbook/ch-algorithms/quantum-fourier-transform.html\n",
    "\n",
    "Remember, to run a cell in Jupyter notebooks, you press `Shift` + `Return/Enter` on your keyboard."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Installing necessary packages"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before we begin, you will need to install some prerequisites into your environment. Run the cell below to complete these installations. At the end, the cell outputs will be cleared."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "!pip install -U -r grading_tools/requirements.txt\n",
    "\n",
    "from IPython.display import clear_output\n",
    "clear_output()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Review of Shor's Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![image](resources/shor_circuit.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You might recall from lecture 4 that Shor's algorithm can be used to factor numbers $N$ that are products of the form \n",
    "\n",
    "$$N = pq$$\n",
    "\n",
    "where $p$ and $q$ are prime numbers. This is done in four main steps, similar to the implementation of quantum phase estimation. In this case, we will use two registers of qubits. The first register will have $n$ qubits, and will contain the measurement qubits. The second register will have $m$ qubits, and will be the eigenstate for quantum phase estimation. \n",
    "\n",
    "1. First, we begin by initializing our qubits. We create a superposition of all $2^n$ computational basis states on the $n$ measurement qubits by applying a Hadamard ($H$) gate on each qubit starting off in the state $\\vert0\\rangle^{\\otimes n}$. We also initialize the $m$ target qubits in the state $\\vert1\\rangle$. Here, the exponent $\\otimes n$ means that we have a tensor product of the states of $n$ qubits.\n",
    "\n",
    "2. Second, we apply the unitary operator $U$ with various powers onto the target qubits by controlling it with each of the different measurement qubits. The unitary operator in this case implements modular exponentiation. The schematic above shows the ordering and respective powers.\n",
    "\n",
    "3. Third, we apply an inverse quantum Fourier transform on the $n$ measurement qubits.\n",
    "\n",
    "4. Finally, we measure the first $n$ qubits.\n",
    "\n",
    "After the measurement outcomes are determined, we will need to do additional classical post-processing in order to determine the factors or to decide to run the program again.\n",
    "\n",
    "\n",
    "# Graded Exercise 1: Implementing Shor's Algorithm\n",
    "\n",
    "In this lab, we will implement Shor's algorithm and use it to factor 15 into 3 and 5."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. Initializing the qubits\n",
    "\n",
    "We will need to initialize our qubits as described above by applying a Hadamard gate on each of the $n$ measurement qubits. We will also set the target qubits to $\\vert1\\rangle$, since that is the eigenstate onto which the unitary operator $U$ will be applied. Here, $\\vert1\\rangle$ is initialized by applying an $X$ gate on the last qubit.\n",
    "\n",
    "We have created a function below called `initialize_qubits` which takes in three arguments. The first argument is the quantum circuit onto which the gates will be applied. The second argument, `n`, is the number of measurement qubits. The third argument, `m`, is the number of target qubits for the unitary operator."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [],
   "source": [
    "def initialize_qubits(given_circuit, n, m):\n",
    "    \n",
    "    ### WRITE YOUR CODE BETWEEN THESE LINES - START\n",
    "    given_circuit.h(range(n))\n",
    "    given_circuit.x(n+m-1)\n",
    "    ### WRITE YOUR CODE BETWEEN THESE LINES - END"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. Modular exponentiation\n",
    "\n",
    "We have created a function called `a_x_mod15` below which takes in two arguments, `a` and `x`, and implements the unitary operator $$U = a^x \\text{ mod } 15$$\n",
    "\n",
    "**You do not need to modify this function.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit import QuantumCircuit\n",
    "\n",
    "def a_x_mod15(a, x):\n",
    "    if a not in [2,7,8,11,13]:\n",
    "        raise ValueError(\"'a' must be 2,7,8,11 or 13\")\n",
    "    U = QuantumCircuit(4)        \n",
    "    for iteration in range(x):\n",
    "        if a in [2,13]:\n",
    "            U.swap(0,1)\n",
    "            U.swap(1,2)\n",
    "            U.swap(2,3)\n",
    "        if a in [7,8]:\n",
    "            U.swap(2,3)\n",
    "            U.swap(1,2)\n",
    "            U.swap(0,1)\n",
    "        if a == 11:\n",
    "            U.swap(1,3)\n",
    "            U.swap(0,2)\n",
    "        if a in [7,11,13]:\n",
    "            for q in range(4):\n",
    "                U.x(q)\n",
    "    U = U.to_gate()\n",
    "    U.name = \"%i^%i mod 15\" % (a, x)\n",
    "    c_U = U.control()\n",
    "    return c_U"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the function `a_x_mod15` creates a 4-qubit unitary controlled by an additional fifth qubit. In order to use this gate, you will need to append it to your quantum circuit using `Qiskit`'s `circuit.append()` function by passing in the five qubits in a list containing the control qubit first, followed by the four target qubits.\n",
    "\n",
    "Below, we have created a function called `modular_exponentiation` which takes in four arguments. The first argument, `given_circuit`, is the circuit onto which modular exponentiation will be applied. The next two arguments, `n` and `m`, are the numbers of measurement and target qubits. The schematic above for Shor's algorithm will be useful here. The last argument, `a`, is the base of the modular exponentiation. You will need to call the function `a_x_mod15` as needed in the function below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [],
   "source": [
    "def modular_exponentiation(given_circuit, n, m, a):\n",
    "    \n",
    "    ### WRITE YOUR CODE BETWEEN THESE LINES - START\n",
    "    for q in range(n):\n",
    "        given_circuit.append(a_x_mod15(a, 2**q),\n",
    "                            [q] + [n+i for i in range(m)])\n",
    "    ### WRITE YOUR CODE BETWEEN THESE LINES - END\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. Implementing the inverse quantum Fourier transform\n",
    "\n",
    "The last step before measuring the first $n$ qubits is the implementation of the inverse quantum Fourier transform. As with `lab3`, you can either implement it on your own or use `Qiskit`'s circuit library.\n",
    "\n",
    "The function `apply_iqft` takes two arguments. The first argument, `given_circuit`, contains the qubits onto which the inverse quantum Fourier transform will be applied. The second argument, `measurement_qubits`, contains the list of qubits onto which the inverse quantum Fourier transform will be applied."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit.circuit.library import QFT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {},
   "outputs": [],
   "source": [
    "def apply_iqft(given_circuit, measurement_qubits):\n",
    "    \n",
    "    ### WRITE YOUR CODE BETWEEN THESE LINES - START\n",
    "    given_circuit.append(QFT(len(measurement_qubits),do_swaps=False,inverse=True, name='iqft'), measurement_qubits)\n",
    "\n",
    "    ### WRITE YOUR CODE BETWEEN THESE LINES - END"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4. Putting it all together\n",
    "\n",
    "Finally, we combine the functions to construct the quantum program that implements Shor's algorithm.\n",
    "\n",
    "The next lines of code put everything together. **You do not need to modify anything below, but you will need to run the cell to submit your solution.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit import QuantumCircuit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"word-wrap: normal;white-space: pre;background: #fff0;line-height: 1.1;font-family: &quot;Courier New&quot;,Courier,monospace\">     ┌───┐ ░                                                              ░ »\n",
       "q_0: ┤ H ├─░────────■─────────────────────────────────────────────────────░─»\n",
       "     ├───┤ ░        │                                                     ░ »\n",
       "q_1: ┤ H ├─░────────┼──────────────■──────────────────────────────────────░─»\n",
       "     ├───┤ ░        │              │                                      ░ »\n",
       "q_2: ┤ H ├─░────────┼──────────────┼──────────────■───────────────────────░─»\n",
       "     ├───┤ ░        │              │              │                       ░ »\n",
       "q_3: ┤ H ├─░────────┼──────────────┼──────────────┼──────────────■────────░─»\n",
       "     └───┘ ░ ┌─────┴┼──────┐┌─────┴┼──────┐┌─────┴┼──────┐┌─────┴┼──────┐ ░ »\n",
       "q_4: ──────░─┤0     │      ├┤0     │      ├┤0     │      ├┤0     │      ├─░─»\n",
       "           ░ │             ││             ││             ││             │ ░ »\n",
       "q_5: ──────░─┤1            ├┤1            ├┤1            ├┤1            ├─░─»\n",
       "           ░ │  7^1 mod 15 ││  7^2 mod 15 ││  7^4 mod 15 ││  7^8 mod 15 │ ░ »\n",
       "q_6: ──────░─┤2            ├┤2            ├┤2            ├┤2            ├─░─»\n",
       "     ┌───┐ ░ │             ││             ││             ││             │ ░ »\n",
       "q_7: ┤ X ├─░─┤3            ├┤3            ├┤3            ├┤3            ├─░─»\n",
       "     └───┘ ░ └─────────────┘└─────────────┘└─────────────┘└─────────────┘ ░ »\n",
       "c_0: ═══════════════════════════════════════════════════════════════════════»\n",
       "                                                                            »\n",
       "c_1: ═══════════════════════════════════════════════════════════════════════»\n",
       "                                                                            »\n",
       "c_2: ═══════════════════════════════════════════════════════════════════════»\n",
       "                                                                            »\n",
       "c_3: ═══════════════════════════════════════════════════════════════════════»\n",
       "                                                                            »\n",
       "«     ┌───────┐┌─┐         \n",
       "«q_0: ┤0      ├┤M├─────────\n",
       "«     │       │└╥┘┌─┐      \n",
       "«q_1: ┤1      ├─╫─┤M├──────\n",
       "«     │  iqft │ ║ └╥┘┌─┐   \n",
       "«q_2: ┤2      ├─╫──╫─┤M├───\n",
       "«     │       │ ║  ║ └╥┘┌─┐\n",
       "«q_3: ┤3      ├─╫──╫──╫─┤M├\n",
       "«     └───────┘ ║  ║  ║ └╥┘\n",
       "«q_4: ──────────╫──╫──╫──╫─\n",
       "«               ║  ║  ║  ║ \n",
       "«q_5: ──────────╫──╫──╫──╫─\n",
       "«               ║  ║  ║  ║ \n",
       "«q_6: ──────────╫──╫──╫──╫─\n",
       "«               ║  ║  ║  ║ \n",
       "«q_7: ──────────╫──╫──╫──╫─\n",
       "«               ║  ║  ║  ║ \n",
       "«c_0: ══════════╩══╬══╬══╬═\n",
       "«                  ║  ║  ║ \n",
       "«c_1: ═════════════╩══╬══╬═\n",
       "«                     ║  ║ \n",
       "«c_2: ════════════════╩══╬═\n",
       "«                        ║ \n",
       "«c_3: ═══════════════════╩═\n",
       "«                          </pre>"
      ],
      "text/plain": [
       "     ┌───┐ ░                                                              ░ »\n",
       "q_0: ┤ H ├─░────────■─────────────────────────────────────────────────────░─»\n",
       "     ├───┤ ░        │                                                     ░ »\n",
       "q_1: ┤ H ├─░────────┼──────────────■──────────────────────────────────────░─»\n",
       "     ├───┤ ░        │              │                                      ░ »\n",
       "q_2: ┤ H ├─░────────┼──────────────┼──────────────■───────────────────────░─»\n",
       "     ├───┤ ░        │              │              │                       ░ »\n",
       "q_3: ┤ H ├─░────────┼──────────────┼──────────────┼──────────────■────────░─»\n",
       "     └───┘ ░ ┌─────┴┼──────┐┌─────┴┼──────┐┌─────┴┼──────┐┌─────┴┼──────┐ ░ »\n",
       "q_4: ──────░─┤0     │      ├┤0     │      ├┤0     │      ├┤0     │      ├─░─»\n",
       "           ░ │             ││             ││             ││             │ ░ »\n",
       "q_5: ──────░─┤1            ├┤1            ├┤1            ├┤1            ├─░─»\n",
       "           ░ │  7^1 mod 15 ││  7^2 mod 15 ││  7^4 mod 15 ││  7^8 mod 15 │ ░ »\n",
       "q_6: ──────░─┤2            ├┤2            ├┤2            ├┤2            ├─░─»\n",
       "     ┌───┐ ░ │             ││             ││             ││             │ ░ »\n",
       "q_7: ┤ X ├─░─┤3            ├┤3            ├┤3            ├┤3            ├─░─»\n",
       "     └───┘ ░ └─────────────┘└─────────────┘└─────────────┘└─────────────┘ ░ »\n",
       "c_0: ═══════════════════════════════════════════════════════════════════════»\n",
       "                                                                            »\n",
       "c_1: ═══════════════════════════════════════════════════════════════════════»\n",
       "                                                                            »\n",
       "c_2: ═══════════════════════════════════════════════════════════════════════»\n",
       "                                                                            »\n",
       "c_3: ═══════════════════════════════════════════════════════════════════════»\n",
       "                                                                            »\n",
       "«     ┌───────┐┌─┐         \n",
       "«q_0: ┤0      ├┤M├─────────\n",
       "«     │       │└╥┘┌─┐      \n",
       "«q_1: ┤1      ├─╫─┤M├──────\n",
       "«     │  iqft │ ║ └╥┘┌─┐   \n",
       "«q_2: ┤2      ├─╫──╫─┤M├───\n",
       "«     │       │ ║  ║ └╥┘┌─┐\n",
       "«q_3: ┤3      ├─╫──╫──╫─┤M├\n",
       "«     └───────┘ ║  ║  ║ └╥┘\n",
       "«q_4: ──────────╫──╫──╫──╫─\n",
       "«               ║  ║  ║  ║ \n",
       "«q_5: ──────────╫──╫──╫──╫─\n",
       "«               ║  ║  ║  ║ \n",
       "«q_6: ──────────╫──╫──╫──╫─\n",
       "«               ║  ║  ║  ║ \n",
       "«q_7: ──────────╫──╫──╫──╫─\n",
       "«               ║  ║  ║  ║ \n",
       "«c_0: ══════════╩══╬══╬══╬═\n",
       "«                  ║  ║  ║ \n",
       "«c_1: ═════════════╩══╬══╬═\n",
       "«                     ║  ║ \n",
       "«c_2: ════════════════╩══╬═\n",
       "«                        ║ \n",
       "«c_3: ═══════════════════╩═\n",
       "«                          "
      ]
     },
     "execution_count": 146,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def shor_program(n, m, a):\n",
    "    \n",
    "    # set up quantum circuit\n",
    "    shor = QuantumCircuit(n+m, n)\n",
    "    \n",
    "    # initialize the qubits\n",
    "    initialize_qubits(shor, n, m)\n",
    "    shor.barrier()\n",
    "\n",
    "    # apply modular exponentiation\n",
    "    modular_exponentiation(shor, n, m, a)\n",
    "    shor.barrier()\n",
    "\n",
    "    # apply inverse QFT\n",
    "    apply_iqft(shor, range(n))\n",
    "\n",
    "    # measure the first n qubits\n",
    "    shor.measure(range(n), range(n))\n",
    "    \n",
    "    return shor\n",
    "    \n",
    "n = 4; m = 4; a = 7\n",
    "mycircuit = shor_program(n, m, a)\n",
    "mycircuit.draw(output='text')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's it! In order to run your quantum circuit and get the measurement outcomes, you simply need to run `Qiskit`'s `execute` function as follows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAc0AAAFLCAYAAAC0rNfYAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3de7xVdZ3/8ddH0MwfkAppclFEUkdNFE+jFop4q7TMzLw0XZwuppmOY16nspxGq6lMy7Ea07yVmjamlpo5BnghDUjyNmIDaChCII5YCQKf3x9rHzoczsG14Zyz1zn79Xw89sO9v2uddT6br2e/91rru74rMhNJkvTaNmh0AZIk9RaGpiRJJRmakiSVZGhKklSSoSlJUkmGpiRJJfVvdAGNNGTIkBw5cmSjy5AkVci0adMWZuYbO1rW1KE5cuRIpk6d2ugyJEkVEhFPd7bMw7OSJJVkaEqSVJKhKUlSSYamJEklGZqSJJVkaEqSVJKhKUlSSYamJEklGZqSJJVkaEqSVJKhKUlSSYamJEklGZqSJJVkaEqSVJKhKUlSSYamJEklGZqSJJVkaEqSVJKhKUlSSYamJEklGZqSJJVkaEqSVJKhKdXceeed7LDDDowePZqvfvWrayy/8MIL2Wmnndh111054IADePrpp1ct69evH7vtthu77bYbhx122Kr2ffbZZ1X70KFDOfzww3vkvUjqHv0bXYBUBStWrOCkk07iV7/6FcOHD+etb30rhx12GDvttNOqdXbffXemTp3KJptswne/+13OPPNMbrjhBgBe//rX8/DDD6+x3XvvvXfV8/e///28973v7f43I6nbuKcpAQ899BCjR49m1KhRbLTRRhxzzDHccsstq60zYcIENtlkEwD22msv5s6dW3r7S5Ys4Z577nFPU+rlDE0JePbZZxkxYsSq18OHD+fZZ5/tdP3LL7+cd73rXatev/LKK7S0tLDXXnvxs5/9bI31b775Zg444AAGDRrUtYVL6lEenpWAzFyjLSI6XPfaa69l6tSpTJo0aVXbM888w9ChQ5k1axb7778/b3nLW9huu+1WLb/uuuv4xCc+0fWFS+pR7mlKFHuWf/zjH1e9njt3LkOHDl1jvbvvvpvzzz+fW2+9lde97nWr2lvXHTVqFPvttx+/+93vVi1btGgRDz30EIceemg3vgNJPcHQlIC3vvWtPPXUU8yePZtly5Zx/fXXrzYKFuB3v/sdn/rUp7j11lvZYostVrUvXryYpUuXArBw4ULuv//+1QYQ3Xjjjbz73e9m44037pk3I6nbGJoN0h2XN8yePZs999yTN7/5zRx99NEsW7asR95LX9C/f38uueQS3vGOd/B3f/d3HHXUUey8886ce+653HrrrQCcccYZvPzyy3zgAx9Y7d/+iSeeoKWlhTFjxjBhwgTOPvvs1ULz+uuv59hjj23I+5LUtaKjcznNoqWlJadOndrjv3fFihVsv/32q13ecN111632QfvrX/+aPffcc9XlDRMnTlx1ecOAAQN4+eWX19juUUcdxRFHHMExxxzDCSecwJgxYzjxxBN77H1JUl8QEdMys6WjZe5pNkB3XN6Qmdxzzz0ceeSRAHz0ox/tcBSnJK2v9TlSBvDSSy8xbNgwPvOZzwDFJVmtR8922203hgwZwqmnntoj76VehmYDdMflDYsWLWLTTTelf//+pbYp9RZd/QENsGzZMo4//ni23357dtxxR3760592+/voK1onArnjjjt4/PHHue6663j88cdXW6d1IpDf//73HHnkkZx55pmrLf/CF77A+PHjV70eOHAgDz/88KrHNttswxFHHNEj76deXnLSAN1xeUNH1/91tk2pt1jfmZpgzQ9ogPPPP58tttiCmTNnsnLlSl544YUee0+9XdsjZcCqI2Vt+2TChAmrnu+1115ce+21q15PmzaN+fPn8853vpOOTo899dRTLFiwgH322acb38W6c0+zAbrj8oYhQ4bw4osvsnz58rVuU+pN1vdURusH9MEHH7zaz1xxxRWcc845AGywwQYMGTKkm99J37E+R8pWrlzJZz/7Wb7+9a93uv51113H0UcfXdkv/YZmA3TH5Q0RwYQJE7jpppsAuOqqq5znVL1ed3xAv/jii0CxBzp27Fg+8IEPMH/+/G6ovm9alyNlZ5xxBgCXXnophxxyyGp92l7VR5sbmg3QXZc3fO1rX+PCCy9k9OjRLFq0iI9//OMNe49SV+iOD+jly5czd+5c3v72tzN9+nT23ntvTj/99K4vvo9anyNlU6ZM4ZJLLmHkyJGcfvrpXH311Zx99tmrfmbGjBksX76cPfbYo/vfyLrKzKZ97LHHHimpuh544IE8+OCDV72+4IIL8oILLlhjvV/96le544475vz581e1ffCDH8wRI0bkNttsk4MHD86BAwfmWWedlStXrsxNNtkkV6xYkZmZzzzzTO60007d/2b6iFdffTW33XbbnDVrVi5dujR33XXXfPTRR1dbZ/r06Tlq1KicOXNmp9v54Q9/mCeddNJqbWeddVaee+653VJ3PYCp2UluOBBIUmW1PZUxbNgwrr/+en784x+vtk7rqYw777xztVMZP/rRj1Y9v/LKK5k6deqq0bfvec97mDhxIvvvvz///d//vdogFq1d2yNlK1as4GMf+9iqI2UtLS0cdthhqx0pA9h6661XHUVbm5/85Cfcfvvt3f0W1ouTGzRgcgNJ5d1+++2ceuqpqz6gP/e5z632AX3ggQfyyCOPsNVWWwEdf0C3huYll1wCwNNPP82HP/xhXnzxRd74xjfywx/+kK233rrH35uqaW2TGxiahqYkqQ1nBJIkqQsYmpIkleRAIPVJn7yo0RV0ncuqOQWn1JTc05QkqSRDU5KkkgxNSZJKMjQlSSrJ0JQkqSRDU5KkkrzkpAt4eYMkNQf3NCVJKsk9TUlqYh4pq4+hKanH+AGt3q7HD89GxKcjYnZEvBIR0yJin7Wse0RE3BURf4qIJRHxYEQctpb1j42IjIifd0/1kqRm1qOhGRFHAxcDFwC7Aw8Ad0REZzeyGw/cAxxaW/924OaOgjYiRgFfB+7thtIlSerxPc3TgCsz87LMfCIzTwbmASd2tHJm/lNmfjUzH8rMP2TmecA04PC260XEhsB1wOeAWd37FiRJzarHQjMiNgL2AO5qt+gu4G11bGogsLhd2/nAnMy8at0rlCRp7XpyINAQoB8wv137fODAMhuIiJOA4cA1bdoOBo4Gdiu5jeOB4wGGDh3KxIkTARg1ahQDBw5kxowZAAwePJidd96ZyZMnA9C/f3/GjRvH9OnTeemllwBoaWlh/vz5wHZlfnWv0Prvscsuu7B06VKeeuopAEaMGMGWW27J1KlTARg0aBBjx47lvvvuY/ny5QDsu+++PPbYYyxatAiAMWPGsGTJEmbNKnb+R44cyeabb8706dMB2GyzzRgzZgyTJk0iM4kIxo8fz4wZM1i8uPheNHbsWF544QXmzJkDlO+nvmTKlCksXboUgHHjxjFz5kwWLFgA9L5+6ktXubX+rQwYMICWlpZe20/Q2dmx3mfevHk8+eSTAAwbNozhw4fz4IMPAvX109pEZnbjW2jziyKGAs8C+2bmvW3avwgcm5k7vsbPv58iLI/JzFtrbUOA3wMfzMyJtbYrgSGZ+e7XqqmlpSVb/6ddH44IrB77pJrsl+qxT9YUEdMys6WjZT25p7kQWAG8qV37Fqy597maNoH5kdbArNkF2Aq4OyJa2zao/cxyYOfMfHL9S5ckqQePlWTmMopBPAe1W3QQxSjaDkXEUcC1wHGZeVO7xb8F3kJxaLb1cSvFCNrdgNldUrwkSfT85AYXAtdExEPA/cAJwFDgewARcTVAZn6k9voYij3M04HJEdG6l7osM1/IzD8Dj7b9BRHxItA/M1drlyRpffVoaGbmDRExGPg8xWHVR4FDMvPp2irtz0ifQFHjRbVHq0nAft1brSRJq+vxafQy81Lg0k6W7be21yW3f9y61CVJ0mvpO+O/JUnqZoamJEklGZqSJJVkaEqSVJKhKUlSSYamJEklGZqSJJVkaEqSVJKhKUlSSYamJEklGZqSJJVkaEqSVJKhKUlSSYamJEklGZqSJJVkaEqSVJKhKUlSSYamJEklGZqSJJVkaEqSVJKhKUlSSYamJEklGZqSJJVkaEqSVJKhKUlSSYamJEklGZqSJJVkaEqSVJKhKUlSSXWFZkQcFREHt3l9bkTMjYhfRsRWXV+eJEnVUe+e5pdan0TEWOBfgG8DGwLf7LqyJEmqnv51rr8N8GTt+fuAn2Xmv0fEXcAvu7QySZIqpt49zVeAgbXnBwB3157/X5t2SZL6pHr3NO8FvhkR9wEtwJG19u2BP3ZlYZIkVU29e5qfAZZRhOUJmflcrf1deHhWktTH1bWnmZlzgfd00H5ql1UkSVJF1X2dZkRsHBFHRsRZEbFprW27iNi868uTJKk66trTjIjRFIN/BgCbAjcCLwIn1l5/oqsLlCSpKurd07wIuAvYEvhrm/ZbgQldVZQkSVVU7+jZtwF7ZeaKiGjb/gwwtMuqkiSpgtZl7tkNO2jbmuJaTUmS+qx6Q/Mu4LQ2rzMiBgHnAb/osqokSaqgeg/Pngb8OiKeBDYGbgBGA/OBo7q4NkmSKqXe6zSfi4jdgGOBsRR7qv8J/Cgz/7rWH5YkqZerd0+TWjheUXtIktQ0XjM0I+II4LbMfLX2vFOZ+V9dVpkkSRVTZk/zJuBNwILa884k0K8ripIkqYpeMzQzc4OOnkuS1GzqCsGI2Dci1gjaiOgXEft2XVmSJFVPvXuOvwY6mph909oySZL6rHpDMyjOXbY3GPjz+pcjSVJ1lbrkJCJurT1N4NqIWNpmcT9gF+CBLq5NkqRKKXud5qLafwNYzOp3OFkG3Adc1oV1SZJUOaVCMzP/ESAi5gDfyEwPxUqSmk690+id112FSJJUdWVmBPo9MD4zF0fEI3Q8EAiAzNy1K4uTJKlKyuxp/hRoHfizthmBJEnq08rMCHReR88lSWo2TosnSVJJrxmaEfFIRPy+zKPML4yIT0fE7Ih4JSKmRcQ+a1l3q4j4cUT8T0SsiIgrO1lvUER8OyKei4ilEfGHiPCm2JKkLlX2LiddIiKOBi4GPk1xbeengTsiYqfMfKaDH3kdsBD4KnB8J9vcELiL4vrRo4C5wHD+dh5WkqQuUdc5zS5wGnBlZrZOhHByRLwTOBE4p4PfPQc4BSAijuxkm/8IbAHsm5nLam1zurBmSZKAHjynGREbAXtQ7BW2dRfwtvXY9OHA/cB3IuL5iHg8Ir5U2wOVJKnL9OR1mkMo5qmd3659PnBgiVo7MwrYH/gxcCgwEvgPYABw+npsV5Kk1TTiOs32odvZnVPK2gBYAHwyM1cA0yJiMPCtiDgjM1fbdkQcT+386NChQ5k4cSIAo0aNYuDAgcyYMQOAwYMHs/POOzN58mQA+vfvz7hx45g+fTovvfQSAC0tLcyfPx/Ybj3Kr5bWf49ddtmFpUuX8tRTTwEwYsQIttxyS6ZOnQrAoEGDGDt2LPfddx/Lly8HYN999+Wxxx5j0aJiquIxY8awZMkSZs2aBcDIkSPZfPPNmT59OgCbbbYZY8aMYdKkSWQmEcH48eOZMWMGixcvBmDs2LG88MILzJkzByjfT33JlClTWLq0+BMcN24cM2fOZMGCBUDv66e+NGC/9W9lwIABtLS09Np+gq279x+qB82bN48nn3wSgGHDhjF8+HAefPBBoL5+WptolyndpnZ49i/AsZl5Y5v2/wB2yczxr/HzPwcWZuZx7donAa9m5oFt2vYBJgNbZOafOttmS0tLtv5Puz4+edF6b6IyLju10RV0DfukmuyX6rFP1hQR0zKzpaNl6/S1LyK2i4h31x6ldrNqg3SmAQe1W3QQ63dbsfuB0RHR9r1sTxHQC9dju5IkraauCdtrhz0vBw4DVv6tOX4OfCwzF3X6w4ULgWsi4iGKsDsBGAp8r7ahqwEy8yNtfudutaeDgJW118sy8/Fa+3eBzwAXR8QlFOc0zwMubX9oVpKk9VFXaAI/AEYD+wAP1tr2pAiuy4Aj1vbDmXlDLXg/D2wFPAockplP11bp6OD679q9fg/wNEU4kpl/jIiDKQL5YeB54Arg3+p5Y5IkvZZ6Q/MdwAGZOaVN2/0R8Sng7jIbyMxLgUs7WbZfB21RYpu/Yf0uW5Ek6TXVe07zT0BHN6D+C/Bah2YlSerV6g3NfwUuiohhrQ2159+sLZMkqc8qM7lB+wkNtgXmRMSztdfDgFcoprL7QZdXKElSRfTohO2SJPVmPT1huyRJvVbfmdNKkqRuVldoRsRGEXFeRMys3UR6RdtHdxUpSVIV1Lun+WXgoxSjZVcCZ1DcUWQRxQ2lJUnqs+oNzaOAEzLz+8AK4JbMPAX4ImvOKStJUp9Sb2huCbTO+foysGnt+Z3AwV1VlCRJVVRvaD5DMcE6wB8optUD2Bv4a1cVJUlSFdUbmjcDB9SeXwycFxGzgStxYgNJUh9X14TtmXlOm+c3RcRcionSZ2bmz7u6OEmSqqTeu5yspnZ3kd90US2SJFVa3ZMbRMTYiLg6IqbWHtdExNjuKE6SpCqpd3KDfwB+S3ED6dtrjy2BhyLiQ11fniRJ1VHv4dnzgS9k5gVtGyPiHODfgGu7qjBJkqqm3sOzbwR+0kH7jRS3BpMkqc+qNzR/DezXQft+wKT1LUaSpCorcxPqI9q8vAP4SkS08LdRs3sBRwBf6vLqJEmqkHW9CfXxtUdb3wEuXe+KJEmqqDI3ofaem5Ik4U2oJUkqbV0mNzg0IiZHxMKI+FNETIqIQ7qjOEmSqqTeyQ0+QTFp+/8CZwFnA7OBmyPiY11fniRJ1VHv5AZnAadl5iVt2i6PiGkUAXpFl1UmSVLF1Ht4dmuKG063dwewzfqXI0lSda3LTagP6qD9YODp9S9HkqTqqvfw7DeA79TuavIAkMA44MPAyV1cmyRJlVLvTai/HxELgM9SzAIE8ARwVGbe0tXFSZJUJaVDMyL6UxyGnZyZN3dfSZIkVVPpc5qZuRz4L2Bg95UjSVJ11TsQaAYwujsKkSSp6uoNzS8B34yIwyNiRERs3vbRDfVJklQZ9Y6e/UXtv/9FMXK2VdRe9+uKoiRJqqJ6Q3NCt1QhSVIvUCo0I2IT4OvA4cCGwN3AKZm5sBtrkySpUsqe0zwPOI7i8Ox1FLMCfbebapIkqZLKHp49Avh4Zl4PEBE/Au6PiH6ZuaLbqpMkqULK7mmOAO5tfZGZDwHLgaHdUZQkSVVUNjT7AcvatS2n/oFEkiT1WmVDL4BrI2Jpm7aNgcsi4i+tDZl5WFcWJ0lSlZQNzas6aLu2KwuRJKnqSoVmZv5jdxciSVLV1TuNniRJTcvQlCSpJENTkqSSDE1JkkoyNCVJKsnQlCSpJENTkqSSDE1JkkoyNCVJKsnQlCSpJENTkqSSDE1JkkoyNCVJKsnQlCSpJENTkqSSDE1Jkkrq8dCMiE9HxOyIeCUipkXEPq+x/vjaeq9ExKyIOKHd8n4R8eU225wdEf8WEaVusC1JUlk9GpoRcTRwMXABsDvwAHBHRGzdyfrbArfX1tsd+ArwnYh4f5vVzgJOAk4BdgT+qfb6nG56G5KkJtXTe2OnAVdm5mW11ydHxDuBE+k45E4AnsvMk2uvn4iIPYHTgZ/W2t4G3JaZt9Vez4mIW4E9u+UdSJKaVo/taUbERsAewF3tFt1FEXwd2buD9X8JtETEhrXX9wETImLH2u/ZCdifYg9VkqQu05N7mkOAfsD8du3zgQM7+Zk3AXd3sH7/2vbmAV8DBgKPR8SK2rLzM/PSjjYYEccDxwMMHTqUiRMnAjBq1CgGDhzIjBkzABg8eDA777wzkydPBqB///6MGzeO6dOn89JLLwHQ0tLC/Pnzge3KvP9eofXfY5dddmHp0qU89dRTAIwYMYItt9ySqVOnAjBo0CDGjh3Lfffdx/LlywHYd999eeyxx1i0aBEAY8aMYcmSJcyaNQuAkSNHsvnmmzN9+nQANttsM8aMGcOkSZPITCKC8ePHM2PGDBYvXgzA2LFjeeGFF5gzZw5Qvp/6kilTprB06VIAxo0bx8yZM1mwYAHQ+/qpL409bP1bGTBgAC0tLb22n6DDs2O90rx583jyyScBGDZsGMOHD+fBBx8E6uuntYnM7Ma30OYXRQwFngX2zcx727R/ETg2M3fs4GdmAtdk5pfbtI0HJgJbZebzEXEM8HXgDOAxYDeK86ZnZObla6uppaUlW/+nXR+fvGi9N1EZl53a6Aq6hn1STfZL9dgna4qIaZnZ0tGyntzTXAisoNh7bGsL1tz7bPV8J+svBxbVXn8d+EZmXl97/UhEbENxjnStoSlJUj167FhJZi4DpgEHtVt0EMXo2I5MYc1DtwcBUzPz1drrTSjCuK0V9KXjQJKkSujp0bMXAtdExEPA/RSjY4cC3wOIiKsBMvMjtfW/B3wmIi4Cvg+8HTgOOLbNNm8Dzo6I2RSHZ3enGKV7dXe/GUlSc+nR0MzMGyJiMPB5YCvgUeCQzHy6tsrW7dafHRGHAN+iuCzlOeCUzPxpm9VOBr4MXEpx6HYecBnwr935XiRJzafHZ82pjWrtcGRrZu7XQdskYOxatrcEOLX2kCSp23jeT5KkkgxNSZJKMjQlSSrJ0JQkqSRDU5KkkgxNSZJKMjQlSSrJ0JQkqSRDU5KkkgxNSZJKMjQlSSrJ0JQkqSRDU5KkkgxNSZJKMjQlSSrJ0JQkqSRDU5KkkgxNSZJKMjQlSSrJ0JQkqSRDU5KkkgxNSZJKMjQlSSrJ0JQkqSRDU5KkkgxNSZJKMjQlSSrJ0JQkqSRDU5KkkgxNSZJKMjQlSSrJ0JQkqSRDU5KkkgxNSZJKMjQlSSrJ0JQkqSRDU5KkkgxNSZJKMjQlSSrJ0JQkqSRDU5KkkgxNSZJKMjQlSSrJ0JQkqSRDU5KkkgxNSZJKMjQlSSrJ0JQkqSRDU5KkkgxNSZJKMjQlSSrJ0JQkqSRDU5KkkgxNSZJKMjQlSSrJ0JQkqSRDU5KkkgxNSZJKMjQlSSqpx0MzIj4dEbMj4pWImBYR+7zG+uNr670SEbMi4oT13aYkSeuiR0MzIo4GLgYuAHYHHgDuiIitO1l/W+D22nq7A18BvhMR71/XbUqStK56ek/zNODKzLwsM5/IzJOBecCJnax/AvBcZp5cW/8y4Crg9PXYpiRJ66THQjMiNgL2AO5qt+gu4G2d/NjeHaz/S6AlIjZcx21KkrROenJPcwjQD5jfrn0+8KZOfuZNnazfv7a9ddmmJEnrpH8Dfme2ex0dtL3W+q3tsZZ1OtxmRBwPHF97+XJEPLnWaqtjCLCwu3/JD/65u39Dn9Pt/WKf1M2/lWrqTX8r23S2oCdDcyGwgjX3ALdgzT3FVs93sv5yYBFFONa1zcz8T+A/S1ddERExNTNbGl2HVme/VI99Uk19pV967PBsZi4DpgEHtVt0EMWI145MAQ7sYP2pmfnqOm5TkqR10tOHZy8EromIh4D7KUbHDgW+BxARVwNk5kdq638P+ExEXAR8H3g7cBxwbNltSpLUVXo0NDPzhogYDHwe2Ap4FDgkM5+urbJ1u/VnR8QhwLcoLiF5DjglM39axzb7il53SLlJ2C/VY59UU5/ol8hc2xgcSZLUyrlnJUkqydCUJKkkQ1OSpJIMzV4iIqLNc/tN6kS7v5VY27pSvfzw7SUyM2tz7ZKZK1vb/VBoHL+8VFPtb2VQ6/NG1yOIiH6NrqGrOHq2F4iINwFHAmOBHYDfADdm5m8aWpiAVV9cou2XmbbL/ODuORExmuI67gnASIoJUm4D7snMBbV17JMGaf2i2Zv/VgzNXiAifgGMBp6guFb1bcAuwB+ArwLXZOaKxlXYfCLiJOAx4MHM/Gub9g0odnD8w2qAiJgEDATupZhKc39gHMW0mxcD38zMFb3lA7oviIjzgenAXZm5pE17P2Blb+sHQ7PiImJ/4AZg98ycGxEbA6+jCM3jgAOASzLzwsZV2VwiYhwwGbgPeAZ4CJiUmTParPM64EzgB5k5ryGFNpmImAD8BHhzZr7Ypn0Y8AmKGzXcApzsl8ye0eZvZQbwMvAgcFtmTmqzzuuBrwHfyMxnGlJoHQzNiouILwH7Zub+HSwbBJwMnFNbZ3oPl9eUIuJbwJ7A3RSHzLek+ECYSTGV4+Ra2xRgUGa+3KBSm0pEnE5xGmNCZv61tieTrYcCI+JDwH8A78vMexpYatOIiH8H3krxxX+X2mNTiqMAEykOnW9CccrpDW33RKvK0Ky42je1m4EPZ+adHSzvD9wO3JGZ3+rp+ppRRFwDLM7MU2qDs/anuEnA7hSHBucDOwKzM7P9zQTUTSJiJ2AScGpm/qhN+6pDsRFxC/BwZn6xQWU2lYi4guKLy8drpy7GAntTBOmbKe6HvC3w28w8pHGVlteI+2mqPtOAO4BLIuJy4JfAk5n559ryAcBOOEF9T/oaMAJW3b3nTuDOiNiC4nD5O4BRwCkNq7A5PQlcDXw7IsYDPwN+k5kvwKoBdWOBaxpXYtP5F4ovkK2Df6YCUyPiDRR9MYFi3vBLGlZhndzT7AUiYgTFIdgDgcUU59DmU9xLdG9gh8zcoXEVNp+I6J+Zy2vfnjegGNDQehjwPcC1mfmGhhbZhGrnkk8GDgM2BuZS/M38H8Uh9ddn5tjGVdjc2g+Uq/2tXJeZAxpbWXmGZi8SEbsCH6IYPduf4tzAFODCzHykkbXpb5eeADdRnMtsfy9Y9ZCI2BF4N7AbsDnFjervBr6bmbMbWZsKtQC9FNg8M49qdD1lGZoVVfvGvCtwBLAE+D3Fzbefry3fAZgDLOttQ7Z7qzZ98j6KPZfHKC77eSYz/xIRG2Tmytp55jdk5qIGltt0agN/NsjMV9u1vzEz/9Sgsppa+8FYnSwf2Ha0c9UZmhUVEd+mCMx5FN+URwLPU5yn+fc+eL/QyuugT7ahuG72ZuDizJzVwPKaVkTskZnT2rVtRPFh/WonP6Zu1Emf9MrrMttzGrAKqo0CPCWKBlMAAASISURBVA74GPDOzNyO4vDSd4BDgP+JiE85hV7P6aRPtqI4vHQY8FhEHB81jau0uUTEm4HfRsSjEXFhROwOxQCtzHy11h0bRcTft05Dqe61lj5ZUZviMCJiw97aJ4ZmNR1OMSz+rsxcVBt08qfM/Gpmbgt8C/hnig9t9YwyfXIasFVv/ybdyxwL/C/wK2Av4OcR8ZuIODMiRtT64o0U1wFu0cA6m0mZPtmCXtonhmY1PQFsVZtHk9oozf612YAALgP+AnygUQU2IfukmnaguE75a8AnKS5xeJRiwNyUiLgN+D7wRGbObViVzaVP94nXaVbTZGA5xTe0c4FbMnNprY3MnF07P/BKA2tsNvZJxdQGXP0C2KY2QO55isPkt1F8cO8B7EsxS9AnG1ZoE2mGPnEgUEVFxFCKQ35vobjW7EHg17XnJwEfBEa2meRA3cw+qbaI2LCDkbNHUFwCNCAz/9KYyppXX+wTQ7PCImIwcChwMMUMMzsAm1FMFfb9zLy+geU1JfukOlov8emgvT/QOujkG0BLZu7X4wU2oWboE0OzYiJiOMVtwAD+DDwO/JXiA3oAxXmzha1Tg6n72SfV1KZfAlhJMb3k822WB/Be4NnM/G1jqmwuzdAnhmaFRMSJFJc0jKH4IJ4F/JHibgA3ZeYfG1ddc7JPqqldv/yZYpKJuRQzZN2SmU82sLym1Cx94ujZiqgd9ruA4n5/W1EM1b6CYqDJ8cAPa9cKtn5bUzezT6qpg37ZG7iKYs/mo8B32vRLv0bV2UyaqU/c06yIiDgZ+FBm7tnBsnHAV4BhwN9n5sKerq8Z2SfVZL9UTzP1iXua1bEMGBgRu0Axz2nrbBmZeR/wDxSXMxzcuBKbjn1STfZL9TRNnxia1XETxaGMUyNiYGYuzcxlUdwJgMx8BngRGN7IIpuMfVJN9kv1NE2fGJoVUDsf9gLFzVgPAp6LiMsjYo/a8q0j4kMU1wf+pHGVNg/7pJrsl+pptj7xnGaFRMSmwNYU98t8H/D22qLnKb7gXJ2ZX2pMdc3JPqkm+6V6mqVPDM0Gi4gtgA8DnwUWUlz/9yJwL8WMMxsC2wG/BJ5yMvDuZ59Uk/1SPc3YJ4Zmg0XElcDOwG0Uhzg2pziMsT2wAPh8Zj7YsAKbkH1STfZL9TRjnxiaDVQ7F7AEOCQzJ7dp25rimsCPU8w6c1RmTm9YoU3EPqkm+6V6mrVPHAjUWDsBsymGawPFreYz8+nMvAF4D8WhDm831XPsk2qyX6qnKfvE0GysWRSHML4VEW9uHZ7dqnbrqauAdzWiuCZln1ST/VI9TdknhmYDZeZfgc8BrweuBj4SESMi4v8BRMQmwHiKG7iqB9gn1WS/VE+z9onnNCugNovGF4DDKCY6ngL8CTgQmAd8IjMfaVyFzcc+qSb7pXqarU8MzQqpDd8+FDicYsqpR4EbM/N/GlpYE7NPqsl+qZ5m6RNDs6Kik5u5qnHsk2qyX6qnL/eJoSlJUkkOBJIkqSRDU5KkkgxNSZJKMjQlSSrJ0JQkqSRDU5KkkgxNSZJK+v/iHZRe+YirRgAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 504x360 with 1 Axes>"
      ]
     },
     "execution_count": 147,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from qiskit import Aer, execute\n",
    "simulator = Aer.get_backend('qasm_simulator')\n",
    "counts = execute(mycircuit, backend=simulator, shots=1000).result().get_counts(mycircuit)\n",
    "from qiskit.visualization import plot_histogram\n",
    "plot_histogram(counts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 148,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Measured 0\n",
      "Measured 4\n",
      "Measured 12\n",
      "Measured 8\n"
     ]
    }
   ],
   "source": [
    "for measured_value in counts:\n",
    "    print(f\"Measured {int(measured_value[::-1], 2)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can then follow the classical post-processing details described in lecture 4 to obtain the factors from the measurement outcomes. If you did everything correctly, you should have only measured 0, 4, 8 and 12.\n",
    "\n",
    "#### Classical post-processing\n",
    "\n",
    "Recall that in order to factor the number $N = pq$, we used a number $a$ coprime with $N$ and computed the period of $a^x \\text{ mod } N$.\n",
    "\n",
    "We will use the sequence of steps outlined in lecture 4 to guess the factors of $N$ using the measurement outcomes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Measured 0\n",
      "(1, 15)\n",
      "Measured 4\n",
      "(5, 3)\n",
      "Measured 12\n",
      "(5, 3)\n",
      "Measured 8\n",
      "(1, 15)\n"
     ]
    }
   ],
   "source": [
    "from math import gcd\n",
    "\n",
    "for measured_value in counts:\n",
    "    measured_value_decimal = int(measured_value[::-1], 2)\n",
    "    print(f\"Measured {measured_value_decimal}\")\n",
    "    \n",
    "    if measured_value_decimal % 2 != 0:\n",
    "        print(\"Failed. Measured value is not an even number\")\n",
    "        continue\n",
    "    x = int((a ** (measured_value_decimal/2)) % 15)\n",
    "    if (x + 1) % 15 == 0:\n",
    "        print(\"Failed. x + 1 = 0 (mod N) where x = a^(r/2) (mod N)\")\n",
    "        continue\n",
    "    guesses = gcd(x + 1, 15), gcd(x - 1, 15)\n",
    "    print(guesses)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### That's it!\n",
    "\n",
    "You can grade your solution by running the cell below after filling in your name and email address. **Always provide the same name and email as the one you used during registration to ensure consistency.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 150,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Grading...\n",
      "lab4/ex1 - 🎉 Correct\n",
      "🎊 Hurray! You have a new correct answer! Let's submit it.\n",
      "Submitting the answers for lab4...\n",
      "📝 Our records, so far, are:\n",
      "Correct answers: lab1:ex1, lab2:ex1, lab3:ex1, lab4:ex1\n"
     ]
    }
   ],
   "source": [
    "name = 'First Last'\n",
    "email = 'first.last@domain.com'\n",
    "\n",
    "### Do not change the lines below\n",
    "from grading_tools import grade\n",
    "from qiskit import transpile\n",
    "mycircuit_t = transpile(mycircuit, basis_gates = ['u1', 'u2', 'u3', 'cx'])\n",
    "grade(answer=mycircuit_t, name=name, email=email, labid='lab4', exerciseid='ex1')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Additional reading\n",
    "\n",
    "- The first experimental demonstration of Shor's algorithm was completed by researchers at IBM and Stanford in 2001 using an experimental platform called nuclear magnetic resonance. You can find the paper here: https://www.nature.com/articles/414883a\n",
    "- For additional details on the method of continued fractions, you may refer to this page (https://riliu.math.ncsu.edu/437/notes3se4.html) or any standard reference such as Mermin's Quantum Computer Science text."
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}