{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c19b0e9c",
   "metadata": {},
   "source": [
    "# Quantum information and quantum computing - Problem set 07\n",
    "\n",
    "### _Problem 1_ : Shor's algorithm for factoring 15"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2dae867e",
   "metadata": {},
   "source": [
    "In this notebook we are going to see how to implement a simple circuit of 6 qubits to factorize $N = 15$ using Python and the Qiskit quantum library provided by IBM"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6c3572d1",
   "metadata": {},
   "outputs": [],
   "source": [
    "# First, import all the useful methods\n",
    "\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt   \n",
    "import math\n",
    "\n",
    "from qiskit_aer import QasmSimulator\n",
    "from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "04389db2",
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit_ibm_runtime import QiskitRuntimeService\n",
    "\n",
    "# Save your credentials on disk.\n",
    "# QiskitRuntimeService.save_account(channel='ibm_quantum', token=<IBM Quantum API key>)\n",
    "\n",
    "service = QiskitRuntimeService(\n",
    "    channel='ibm_quantum',\n",
    "    instance='ibm-q/open/main',\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b673d97e",
   "metadata": {},
   "source": [
    "We will surely need the circuit for $\\text{QFT}^\\dagger$, so we will create a function to do it"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9109b479",
   "metadata": {},
   "outputs": [],
   "source": [
    "def qft_dagger(circ, n):\n",
    "    # TO DO: a function that takes a circuit as input\n",
    "    # and appends the inverse QFT to it\n",
    "    \n",
    "    # Don't forget the Swaps!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e3d69f76",
   "metadata": {},
   "source": [
    "Suppose now we have already made the first three steps in the Shor's algorithm and we obtained the random number $y=4$. We have that\n",
    "\n",
    "\\begin{equation*}\n",
    "\\text{gcd}(y,15) = 1\n",
    "\\end{equation*}\n",
    "\n",
    "so we can proceed with the order-finding algorithm.\n",
    "\n",
    "#### Build the circuit\n",
    "First, we have to build the circuit. For this, we will assume that the possibile period for $y=4$ is a $2$-qubit number. This assumption is justified since we expect a small number.\n",
    "\n",
    "Therefore, together with the $4$ qubits useful to represent the number from $0$ to $15$, we need a $6$-qubits circuit."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5fdff415",
   "metadata": {},
   "outputs": [],
   "source": [
    "## The initial circuit is given\n",
    "\n",
    "# Construct the different register\n",
    "\n",
    "first_register   = QuantumRegister(2,name=\"a\")\n",
    "second_register  = QuantumRegister(4,name=\"s\")\n",
    "classic_register = ClassicalRegister(2, name=\"c\")\n",
    "\n",
    "# Put together the circuit\n",
    "shor_circ = QuantumCircuit(first_register,second_register,classic_register)\n",
    "\n",
    "\n",
    "# In the first register , create the superposition of all the possible states\n",
    "\n",
    "shor_circ.h(first_register[0])\n",
    "shor_circ.h(first_register[1])\n",
    "\n",
    "# And prepare the state |1>_L in the second register\n",
    "\n",
    "shor_circ.x(second_register[0])\n",
    "\n",
    "print(shor_circ)\n",
    "\n",
    "# Or, with pylatexenc installed\n",
    "#shor_circ.draw(\"mpl\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5c25856e",
   "metadata": {},
   "source": [
    "Now we need the circuit for modular exponentiation. Usually this step is the bottleneck for Shor's algorithm, since we have to apply the c-$U^{2^n}$ gates. In this case, we will contruct directly a unitary that performs\n",
    "\n",
    "\\begin{equation*}\n",
    "U | z \\rangle_{2}|1\\rangle_{4} = | z \\rangle_{2} |4^z(\\text{mod}15)\\rangle_{4}\n",
    "\\end{equation*}\n",
    "\n",
    "\n",
    "This can be constructed simply by looking at the possible outcome of this operation\n",
    "\n",
    "| z | 4^z(mod15) |\n",
    "|---|------------|\n",
    "| 0 | 1          |\n",
    "| 1 | 4          |\n",
    "| 2 | 1          |\n",
    "| 3 | 4          |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "05d2d655",
   "metadata": {},
   "outputs": [],
   "source": [
    "# TO DO: create a circuit to perform U|z>|1> as indicated above \n",
    "\n",
    "print(shor_circ)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "45aea06d",
   "metadata": {},
   "source": [
    "- **Bonus question**: what if $y=11$?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c0a8c793",
   "metadata": {},
   "source": [
    "Then we can apply the $\\text{QFT}^\\dagger$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b0d3f3a5",
   "metadata": {},
   "outputs": [],
   "source": [
    "qft_dagger(shor_circ,2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "68603180",
   "metadata": {},
   "source": [
    "and measure the first two qubits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "608906c1",
   "metadata": {},
   "outputs": [],
   "source": [
    "## Add measurements of the first register at the end\n",
    "shor_circ.measure(first_register[0],classic_register[0])\n",
    "shor_circ.measure(first_register[1],classic_register[1]) "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "56d6b2d6",
   "metadata": {},
   "source": [
    "The whole circuit looks like:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3fdef2b4",
   "metadata": {},
   "outputs": [],
   "source": [
    "## Print the final circuit\n",
    "\n",
    "#print(shor_circ)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f11ac7c9",
   "metadata": {},
   "source": [
    "#### Run the circuit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5eaa8ee9",
   "metadata": {},
   "outputs": [],
   "source": [
    "backend = QasmSimulator()\n",
    "shots = 2048 # it is interesting seeing a single shot, since statistically we will get all the answers\n",
    "results = backend.run(shor_circ, backend=backend, shots=shots).result()\n",
    "answer = results.get_counts()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e01f6807",
   "metadata": {},
   "source": [
    "#### Print the results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "41f3f133",
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.suptitle(\"Results of order finding algorithm\")\n",
    "plt.bar(answer.keys(), answer.values(), color='royalblue')\n",
    "plt.show()\n",
    "\n",
    "print(answer)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "afac9285",
   "metadata": {},
   "source": [
    "#### Continue the algorithm\n",
    "\n",
    "Answer the following questions:\n",
    "- What are the results of our circuit?\n",
    "- What we have to do next? Do we need the continuous fraction algorithm?\n",
    "- What is the final answer that we get?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8d7a2814",
   "metadata": {},
   "source": [
    "### _Extra_ : using a NoiseModel of a real quantum device\n",
    "\n",
    "We can also make our simulation more similar to the real use case by importing noise models from IBM quantum devices. This is done by importing the NoiseModel function from Qiskit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e10d541e",
   "metadata": {},
   "outputs": [],
   "source": [
    "##Noise Model\n",
    "from qiskit_aer.noise import NoiseModel\n",
    "from qiskit.providers.fake_provider import GenericBackendV2\n",
    "fake_backend = GenericBackendV2(num_qubits=6)\n",
    "\n",
    "noise_model = NoiseModel.from_backend(fake_backend)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "519968b2",
   "metadata": {},
   "outputs": [],
   "source": [
    "shots = 2048\n",
    "results = fake_backend.run(shor_circ, backend=fake_backend, shots=shots,noise_model = noise_model).result()\n",
    "answer = results.get_counts()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c6fc6875",
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.suptitle(\"Results of order finding algorithm\")\n",
    "plt.bar(answer.keys(), answer.values(), color='royalblue')\n",
    "plt.show()\n",
    "\n",
    "print(answer)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b15eb555",
   "metadata": {},
   "source": [
    "Here you can see how adding the noise model showed some contribution to results different from the previous ones, generated by noise (as an example, readout error that can shift bits)."
   ]
  }
 ],
 "metadata": {
  "jupytext": {
   "formats": "ipynb,md"
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.12.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}