{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "cb7fff0a",
   "metadata": {},
   "source": [
    "# Quantum information and quantum computing - Problem set 08\n",
    "\n",
    "### _Problem 1_ : Code Grover's search algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "77a52647",
   "metadata": {},
   "source": [
    "In this notebook we are going to see a simple implementation of the Grover algorithm on a database of dimension $N=8$ possibile data, so using $n=3$ qubits.\n",
    "\n",
    "Between all the possibile state $|xyz\\rangle$ , let's consider $|110 \\rangle$ and $|101 \\rangle$ as the solutions of our problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6e62c1a2",
   "metadata": {},
   "outputs": [],
   "source": [
    "#initialization\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "import math\n",
    "\n",
    "# importing Qiskit\n",
    "from qiskit_aer import QasmSimulator\n",
    "from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c5e32a24",
   "metadata": {},
   "source": [
    "##### Creating the oracle\n",
    "\n",
    "The first thing to make is a oracle function, that adds a phase to the states that are solution of our search problems. Considering $f(x)=1$ iff $x$ is a solution of the problem, the unitary has the form\n",
    "\n",
    "\\begin{equation}\n",
    "U |x\\rangle_{n} = (-1)^{f(x)}|x\\rangle_{n}\n",
    "\\end{equation}\n",
    "\n",
    "\n",
    "In our case the oracle function is easy to make: we have to control if the first qubit (the last, for qiskit order) is $1$ and then perform a Z gate on second and third qubit.\n",
    "\n",
    "Note that, since we already know the solutions, we can construct the oracle without the ancilla qubit."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c58d51ac",
   "metadata": {},
   "outputs": [],
   "source": [
    "def oracle_gate(circuit):\n",
    "    ## TO DO: Create the oracle function\n",
    "    \n",
    "    circuit.barrier() # Barriers are added to divide the different parts of the circuits\n",
    "    return circuit"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3d6cfad3",
   "metadata": {},
   "source": [
    "##### Creating the Grover gate \n",
    "\n",
    "Now we want to add the Grover gate. Remember that it is made of three parts:\n",
    "\n",
    "- Apply Hadamard gates on all qubits\n",
    "- Apply a phase shift to all the $|x \\rangle_{n}$ except $|0\\rangle_{n}$\n",
    "- Apply again Hadamard to all the qubits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "01207567",
   "metadata": {},
   "outputs": [],
   "source": [
    "def grover_gate(circuit):\n",
    "    \n",
    "    ## TO DO: Create Grover gate\n",
    "    \n",
    "    # Hadamard\n",
    "        \n",
    "    # To add a phase at all the solutions except |0>, we create a set of \n",
    "    # transformations that only |0> won't trigger\n",
    "    \n",
    "    #Hadamard again\n",
    "   \n",
    "    \n",
    "    circuit.barrier()\n",
    "    return circuit\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2113672c",
   "metadata": {},
   "source": [
    "##### Construct the circuit\n",
    "\n",
    "We can now assemble the Grover circuit for our problem. \n",
    "\n",
    "1) As a first thing, apply the Hadamard:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b26621d5",
   "metadata": {},
   "outputs": [],
   "source": [
    "grover= QuantumCircuit(3,3)\n",
    "\n",
    "for i in range(3):\n",
    "    grover.h(i)\n",
    "\n",
    "grover.barrier()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2fe69a17",
   "metadata": {},
   "source": [
    "2) Append to the circuit the oracle gate and the Grover gate. \n",
    "- How many time do I have to apply the Grover gate?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "56881d15",
   "metadata": {},
   "source": [
    "... and don't forget to measure!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "086174be",
   "metadata": {},
   "source": [
    "3) Print the circuit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "391ac930",
   "metadata": {},
   "outputs": [],
   "source": [
    "# We can simply print the circuit \n",
    "#print(grover)\n",
    "\n",
    "# Or draw it just like in IBM Quantum Experience\n",
    "# to do this, install pylatexenc with 'pip install pylatexenc'\n",
    "# and then use the draw function\n",
    "\n",
    "grover.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3821f374",
   "metadata": {},
   "source": [
    "##### Run the algorithm on QASM\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a952dca2",
   "metadata": {},
   "outputs": [],
   "source": [
    "backend = QasmSimulator()\n",
    "results = backend.run(grover, backend=backend, shots=2048).result()\n",
    "answer = results.get_counts()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "03f5e4be",
   "metadata": {},
   "source": [
    "##### Visualize the results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3112a8df",
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.suptitle(\"Results of Grover's algorithm\")\n",
    "plt.bar(answer.keys(), answer.values(), color='royalblue')\n",
    "plt.show()\n",
    "\n",
    "print(answer)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b44045c4",
   "metadata": {},
   "source": [
    "If you did everything well, in this case you should have only the solutions of the problem as outcome of the measurements.\n",
    "\n",
    "In general, the aim of the Grover's algorithm is to get as close as possibile to the superposition of the solutions, in order to have statistically the right answers."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e0025991",
   "metadata": {},
   "source": [
    "### _Extra_ : Run with noise model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "35b40dce",
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit_aer.noise import NoiseModel\n",
    "from qiskit.providers.fake_provider import GenericBackendV2\n",
    "\n",
    "fake_backend = GenericBackendV2(num_qubits=3)\n",
    "noise_model = NoiseModel.from_backend(fake_backend)\n",
    "shots = 2048 \n",
    "\n",
    "results = fake_backend.run(grover, backend=fake_backend, shots=shots,noise_model = noise_model).result()\n",
    "answer = results.get_counts()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "79afa3a8",
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.suptitle(\"Results of Grover's algorithm\")\n",
    "plt.bar(answer.keys(), answer.values(), color='royalblue')\n",
    "plt.show()\n",
    "\n",
    "print(answer)"
   ]
  }
 ],
 "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
}