lab-QFT.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "907cf7f3-48c5-4237-9d4c-a967923a6600",
   "metadata": {},
   "source": [
    "## 01. Qiskit basics\n",
    "\n",
    "If the instructions presented in the `README.md` file were correctly followed, **Qiskit** should be correctly installed. The following code will initialize **Qiskit**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5fe0f878-5572-49ff-b52e-22656bcb7011",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from qiskit import QuantumCircuit, transpile, Aer\n",
    "from qiskit.tools.visualization import plot_histogram, plot_state_city"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ab258753-d163-4059-a1d0-d2df98e31b8f",
   "metadata": {},
   "source": [
    "Let's start by generating a quantum circuit with only **two** qubits. To do this, we can use the `QuantumCircuit()` function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1a2a5869-9302-4ff1-b6a1-299af9b4c696",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Generate a quantum circuit with 2 qubits\n",
    "circuit = QuantumCircuit(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c4dc1a6d-d1d5-4192-a431-9e04ac843dab",
   "metadata": {},
   "source": [
    "Obviously, the current circuit doesn't do anything yet.\n",
    "\n",
    "It is worth mentioning that both qubits were initialized with the $\\vert 0\\rangle$ value: $\\begin{cases}\\vert q_0\\rangle = \\vert 0\\rangle\\\\\\vert q_1\\rangle = \\vert 0\\rangle\\end{cases}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "990aa6eb-460d-47dd-a04f-8812d6373d69",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Visualize the (empty) circuit\n",
    "circuit.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a443c618-d636-4b7f-a118-036863660b0e",
   "metadata": {},
   "source": [
    "Let's now generate the third **Bell state**.\n",
    "\n",
    "Can you recall the formula for this state? If not, here it is: $\\vert \\Psi^+\\rangle = \\dfrac{\\vert 01\\rangle + \\vert 10\\rangle}{\\sqrt{2}}$\n",
    "\n",
    "How can this be obtained? First, transform the $\\vert q_0\\rangle$ ket into $\\vert +\\rangle$ using a **Hadamard** gate and the $\\vert q_1\\rangle$ ket into $\\vert 1\\rangle$ using a **Pauli X (NOT)** gate:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4035da94-3af5-43c0-90eb-7d8113691684",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Apply H gate on q0\n",
    "circuit.h(0)\n",
    "circuit.x(1)\n",
    "circuit.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b4ab22c0-a009-4d45-a73d-558c62a72e4f",
   "metadata": {},
   "source": [
    "We are currently looking at $\\frac{1}{\\sqrt{2}}\\big(\\vert 0\\rangle + \\vert 1 \\rangle\\big) \\otimes \\vert 1\\rangle$. By applying one last operation, a **controlled NOT (CNOT)** gate between these two kets, we will finally achieve our Bell state:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "845ed042-d3d0-44bf-a392-3987e3fb7d4c",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "circuit.cx(0, 1)\n",
    "circuit.measure_all()\n",
    "circuit.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a6b24db6-b53d-480c-b9b1-7d6179e1965f",
   "metadata": {},
   "source": [
    "As you can tell, we have introduced the measurement operation as well.\n",
    "\n",
    "**Q:** What results do we expect to get when we run the simulation?\n",
    "    \n",
    "**A:** Since $\\vert \\Psi^+\\rangle = \\dfrac{\\vert 01\\rangle + \\vert 10\\rangle}{\\sqrt{2}}$, we expect about 50% of the results to be $\\vert 01\\rangle$ and the rest of them to be $\\vert 10\\rangle$.\n",
    "\n",
    "Let's now run the simulation and check if our prediction was correct:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "24f852f1-887e-40aa-8183-55b53691f38c",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "simulator = Aer.get_backend('aer_simulator')\n",
    "circ = transpile(circuit, simulator)\n",
    "result = simulator.run(circ).result()\n",
    "counts = result.get_counts(circ)\n",
    "plot_histogram(counts, title='Bell-State counts')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d0b30779-ebaf-46d2-92fb-2c11ba213274",
   "metadata": {},
   "source": [
    "We were close, weren't we?\n",
    "\n",
    "Now try to implement the circuit that is responsible for the second Bell state, $\\vert \\Phi^-\\rangle = \\dfrac{\\vert 00\\rangle - \\vert 11\\rangle}{\\sqrt{2}}$\n",
    "\n",
    "**Hint:** Start with the $\\vert 10\\rangle$ state."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "81452ba8-7010-4d5d-8042-65c39546a431",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Generate a quantum circuit with 2 qubits\n",
    "circuit = QuantumCircuit(2)\n",
    "\n",
    "# TODO - Implement the logic behind the second Bell state\n",
    "\n",
    "# Visualize the circuit (with measurements enabled)\n",
    "circuit.measure_all()\n",
    "circuit.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5dfd8ed9-65e4-4258-8208-895e5e822235",
   "metadata": {},
   "source": [
    "When ready, check that your simulation correctly outputs the expected measurements:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a99d5556-7beb-4bad-9326-d5f8fa57e338",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "simulator = Aer.get_backend('aer_simulator')\n",
    "circ = transpile(circuit, simulator)\n",
    "result = simulator.run(circ).result()\n",
    "counts = result.get_counts(circ)\n",
    "plot_histogram(counts, title='Bell-State counts')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b1376153-e98b-4081-8c7d-58a2d291cf90",
   "metadata": {},
   "source": [
    "## 02. Swaps and phase shifts\n",
    "\n",
    "Let's say we have two qubits, $\\vert q_0\\rangle$ and $\\vert q_1\\rangle$. How can we swap their values? Informally, how can we accomplish $\\vert q_0\\rangle\\leftrightarrow\\vert q_1\\rangle$?\n",
    "\n",
    "It turns out that this operation can be performed using three **CNOT** gates, written in the following configuration:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "833a49a5-7016-4c91-928f-e61191805a6e",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Generate a quantum circuit with 2 qubits\n",
    "circuit = QuantumCircuit(2)\n",
    "\n",
    "# Insert the CNOT gates\n",
    "circuit.cx(0, 1)\n",
    "circuit.cx(1, 0)\n",
    "circuit.cx(0, 1)\n",
    "\n",
    "# Visualize the circuit\n",
    "circuit.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aac29121-64b1-430e-9230-e243336bcea0",
   "metadata": {},
   "source": [
    "Let's verify this circuit's correctness for $\\vert 01\\rangle$ (we expect it to get converted into $\\vert 10\\rangle$):\n",
    "\n",
    "1. Since $\\vert q_0\\rangle$ is, at this point, $\\vert 0\\rangle$, the first CNOT gate **will not** be activated;\n",
    "2. However, $\\vert q_1\\rangle=\\vert 1\\rangle$, so the second CNOT gate **will** open and update $\\vert q_0\\rangle$ to $X\\vert q_0\\rangle=\\vert 1\\rangle$;\n",
    "3. Finally, since $q_0\\rangle$ is now $\\vert 1\\rangle$, the last CNOT gate **will** also open, converting $\\vert q_1\\rangle$ into $X\\vert q_1\\rangle=\\vert 0\\rangle$.\n",
    "\n",
    "So, indeed, we obtained $\\vert q_0q_1\\rangle\\rightarrow\\vert q_1q_0\\rangle$.\n",
    "\n",
    "**Q:** Can you work out a similar reasoning for $\\vert 11\\rangle$?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1fecd1e3-07d6-4bc1-886d-6296673e0d16",
   "metadata": {},
   "source": [
    "This operation is used extensively throughout the quantum world, so a simplified notation can be used instead:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "46483672-b275-4df3-856c-756bfe15f64f",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Generate a quantum circuit with 2 qubits\n",
    "circuit = QuantumCircuit(2)\n",
    "\n",
    "# Swap the qubits\n",
    "circuit.swap(0, 1)\n",
    "\n",
    "# Visualize the circuit\n",
    "circuit.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c283ab13-eff5-4026-9812-44f927d7af2e",
   "metadata": {},
   "source": [
    "Moving on to phase shifts - these are operations that map the basis states $\\vert 0\\rangle\\rightarrow\\vert 0\\rangle$ and $\\vert 1\\rangle\\rightarrow e^{i\\varphi}\\vert1\\rangle$. Presented in matrix form, the shifts can be written as:\n",
    "\n",
    "$$P(\\varphi)=\\begin{bmatrix}1 & 0\\\\0 & e^{i\\varphi} \\end{bmatrix}$$\n",
    "\n",
    "If we were to compute the probabilities of measuring $\\vert 0\\rangle$ or $\\vert 1\\rangle$ for a given qubit, we would soon realize that they **remain unchanged**. However, the phase shift, as the name suggests, modifies the phase of the quantum state. This is equivalent to tracing a rotation along the Z axis on the **Bloch sphere** by $\\varphi$ radians.\n",
    "\n",
    "For now, this might seem insignificant. However, we will disprove this in the following subsections. Until then, let's see how does such an operation look like in Qiskit:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3b4a5c78-5030-4903-8447-436aa5f31f43",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Generate a quantum circuit with 1 qubit\n",
    "circuit = QuantumCircuit(1)\n",
    "\n",
    "# Rotate the qubit by pi/4 radians\n",
    "pi = 3.14159265359\n",
    "circuit.p(pi/4, 0)\n",
    "\n",
    "# Visualize the circuit\n",
    "circuit.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a59c578-3f17-4114-af1f-37d1dbbf874d",
   "metadata": {},
   "source": [
    "Another version of this transform is the **controlled phase shift (CP)** gate. As you are accustomed by now, the controlled version takes two qubits as input and modifies the second one based on the $\\vert 1\\rangle$ component of the first one.\n",
    "\n",
    "Another way to put it is using the matrix notation:\n",
    "\n",
    "$$CP(\\varphi) = \\begin{bmatrix}1 & 0 & 0 & 0\\\\ 0 & 1 & 0 & 0\\\\ 0 & 0 & 1 & 0\\\\0 & 0 & 0 & e^{i\\varphi} \\end{bmatrix}$$\n",
    "\n",
    "Let's check it out in Qiskit:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "27f6d172-af3c-48e1-ab4c-d7be4eaaebac",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Generate a quantum circuit with 1 qubit\n",
    "circuit = QuantumCircuit(2)\n",
    "\n",
    "# Rotate the qubit by pi/4 radians\n",
    "pi = 3.14159265359\n",
    "circuit.cp(pi/4, 0, 1)\n",
    "\n",
    "# Visualize the circuit\n",
    "circuit.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9adccc72-45ce-4af7-bcf4-f95b656e0d9e",
   "metadata": {},
   "source": [
    "## 03. Quantum Fourier Transform (QFT)\n",
    "\n",
    "We are now ready to learn about one of the most important algorithms in the whole quantum realm - the notorious **Quantum Fourier Transform (QFT)**.\n",
    "\n",
    "The algorithm was initially discovered in **June 1994** internally, in an IBM Research Division, by an American mathematician, **Don Coppersmith**. This procedure provided a breakthrough for the famous **Shor** algorithm (developed later that year).\n",
    "\n",
    "In this section, we will discuss how the transform really works and how it can be useful."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "61846902-2fd4-4b4c-9665-607b882adaac",
   "metadata": {},
   "source": [
    "The purpose of the QFT is to map a given ket $\\vert X\\rangle=\\sum_{j=0}^{N-1}x_j\\vert j\\rangle$ to another vector, $\\vert Y\\rangle=\\sum_{k=0}^{N-1}y_k\\vert k\\rangle$, such that the following formula holds true:\n",
    "\n",
    "$$\\boxed{y_k=\\frac{1}{\\sqrt{N}}\\sum_{j=0}^{N-1}x_j\\cdot\\omega_N^{jk}}\\,,\\text{ where } \\omega_N^{jk}=\\exp\\left(2\\pi i\\cdot\\frac{jk}{N}\\right)$$\n",
    "\n",
    "Equivalently, the formula above can be expressed as:\n",
    "\n",
    "$$\\vert j\\rangle\\rightarrow\\frac{1}{\\sqrt{N}}\\sum_{k=0}^{N-1}\\omega_N^{jk}\\vert k\\rangle$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b268d80a-d3a3-4268-9763-e8f981e1b975",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Intuition\n",
    "\n",
    "We will work towards building a **visual intuition** instead of only applying the math concepts.\n",
    "\n",
    "First of all, we can think about the QFT as a black box that gets a **state in the computational basis** as an input ($\\vert x\\rangle$) and spits out (outputs) a **state in the Fourier basis** ($\\vert \\tilde x\\rangle$). Since this operation is valid in the quantum realm, we can be sure that there exists a **unitary transformation**, let's say $QFT$, that can convert between those two basis:\n",
    "\n",
    "$$QFT\\vert x\\rangle = \\vert \\tilde x\\rangle$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "380d27a4-8b10-4b8b-bdb6-4254002adc4f",
   "metadata": {},
   "source": [
    "Qiskit actually [provides a great visualization](https://learn.qiskit.org/course/ch-algorithms/quantum-fourier-transform) of how _counting_ in the computational basis state affects the Fourier state.\n",
    "\n",
    "Let's start by showing the computational basis output - pay attention to the frequency with which different qubits change:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f14e8bb5-9453-442f-9257-1ded352dc7ce",
   "metadata": {},
   "source": [
    "![image.png](https://learn.qiskit.org/content/v2/ch-algorithms/images/zbasis-counting.gif)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "adcf2c2b-086b-4305-8485-9cb98b694159",
   "metadata": {},
   "source": [
    "_Note: the least significant (qu)bit is on the left_\n",
    "\n",
    "As you can see from the representation above, the leftmost qubit filps on each increment, the next flips on every 2 increments, the third with every 4 increments and so on.\n",
    "\n",
    "Now take a look at the Fourier basis; in this case, we store numbers using different quantifiable rotations around the Z-axis:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8853bf2b-cbd1-44ca-807e-e0b2aa84b869",
   "metadata": {},
   "source": [
    "![image.png](https://learn.qiskit.org/content/v2/ch-algorithms/images/fourierbasis-counting.gif)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "71c56e38-0089-4733-8334-44edc9de484d",
   "metadata": {},
   "source": [
    "This time, each qubit starts from the $\\vert +\\rangle$ state and gets rotated according to the following formula when a number $x$ is stored:\n",
    "\n",
    "$$\\frac{x}{2^{n-k}}\\cdot 2\\pi \\text{ radians}$$\n",
    "\n",
    "For example, the leftmost qubit (so $k=0$) will get rotated $\\frac{x}{2^{n}}=\\frac{x}{2^{4}}=\\frac{x}{16}$ full turns in order to store the value $x$, while the rightmost qubit ($k=3$) will simply flip, since $\\frac{x}{2^1}=\\frac{x}{2}$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b172bac-2911-45be-a99b-f80645f2c735",
   "metadata": {},
   "source": [
    "### The math\n",
    "\n",
    "Consider the $\\vert x\\rangle = \\vert x_1\\dots x_n\\rangle$ state, where $\\vert x_1\\rangle$ denotes the most significant bit. We know that $\\vert x\\rangle = \\vert x_1\\dots x_n\\rangle\\in\\big\\{\\vert 0_1\\dots 0_n\\rangle, \\vert 0_1\\dots 1_n\\rangle,\\dots,\\vert 1_1\\dots 1_n\\rangle\\big\\}$, so it might be useful to consider the total number of possible kets as well, $N=2^n$.\n",
    "\n",
    "The following formula can be derived (and should be trusted as-is) for the QFT operator:\n",
    "\n",
    "$$QFT_N\\vert x\\rangle = \\frac{1}{\\sqrt{N}}\\sum_{y=0}^{N-1}\\omega_N^{xy}\\cdot\\vert y\\rangle$$\n",
    "\n",
    "Since we know that $\\omega_N^{xy}=\\exp\\left(2\\pi i\\cdot\\frac{xi}{N}\\right)$ and $N=2^n$, we can reformulate:\n",
    "\n",
    "$$QFT_N\\vert x\\rangle = \\frac{1}{\\sqrt{N}}\\sum_{y=0}^{N-1}\\exp\\left(2\\pi i\\cdot\\frac{xy}{2^n}\\right)\\cdot\\vert y\\rangle$$\n",
    "\n",
    "Rewriting $y$ in fractional binary notation (**please note that we think of $y$ as a number, do not confuse it with $\\vert y\\rangle$**), that is $\\frac{y}{2^n}=\\sum_{k=1}^n\\frac{y_k}{2^k}$, would yield:\n",
    "\n",
    "$$QFT_N\\vert x\\rangle = \\frac{1}{\\sqrt{N}}\\sum_{y=0}^{N-1}\\exp\\left(2\\pi i\\cdot x\\sum_{k=1}^n\\frac{y_k}{2^k}\\right)\\cdot\\vert y\\rangle$$\n",
    "\n",
    "We now want to expand the exponential of a sum into a product of exponentials:\n",
    "\n",
    "$$QFT_N\\vert x\\rangle = \\frac{1}{\\sqrt{N}}\\sum_{y=0}^{N-1}\\prod_{k=1}^n\\exp\\left(2\\pi i\\cdot x\\frac{y_k}{2^k}\\right)\\cdot\\vert y\\rangle$$\n",
    "\n",
    "Finally, this equation can be rearranged as a tensor product:\n",
    "\n",
    "$$QFT_N\\vert x\\rangle = \\frac{1}{\\sqrt{N}}\\bigotimes_{k=1}^{n}\\left[\\vert0\\rangle + \\exp\\left(2\\pi i\\cdot \\frac{x}{2^k}\\right)\\vert 1\\rangle\\right]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5a022e13-f6ad-4e64-bd0f-12ec8688c406",
   "metadata": {},
   "source": [
    "### Implementation notes\n",
    "\n",
    "Let's consider the $\\vert x_1\\rangle$ ket. When the **Hadamard** gate is applied on it, the result is fairly obvious. However, the same result can be rewritten in the context of phase shifting - this can be achieved using the following formula:\n",
    "\n",
    "$$H\\vert x_1\\dots x_n\\rangle=\\frac{1}{\\sqrt{2}}\\left[\\vert0\\rangle + \\exp\\left(2\\pi i\\cdot \\frac{x_1}{2^k}\\right)\\vert 1\\rangle\\right]\\otimes\\vert x_2x_3\\dots x_n\\rangle$$\n",
    "\n",
    "Remember the $CP$ gate? Let's _rebrand it_ into something that is more useful in the current context. Thus, let's define $CROT_k$:\n",
    "\n",
    "$$CROT_k = CP\\left(\\exp\\left(\\frac{2\\pi i}{2^k}\\right)\\right) = \\begin{bmatrix}1 & 0 & 0 & 0\\\\ 0 & 1 & 0 & 0\\\\ 0 & 0 & 1 & 0\\\\0 & 0 & 0 & \\exp\\left(\\frac{2\\pi i}{2^k}\\right) \\end{bmatrix}$$\n",
    "\n",
    "When **deactivated**, so for $\\vert 0 x_j\\rangle$, the gate **does nothing**: $CROT_k\\vert 0 x_j\\rangle = \\vert 0 x_j\\rangle$. However, when **active**, the gate will modify the phase, as it was explained before, meaning that $CROT_k\\vert 1 x_j\\rangle = \\exp\\left(\\frac{2\\pi i}{2}\\right)\\vert 1 x_j\\rangle$.\n",
    "\n",
    "In the previous context of $H\\vert x_1\\dots x_n\\rangle$, applying the $CP_2$ gate with control in qubit $2$ would only modify the phase of the $\\vert 1\\rangle$ ket:\n",
    "\n",
    "$$\\frac{1}{\\sqrt{2}}\\left[\\vert0\\rangle + \\exp\\left(\\frac{2\\pi i x_1}{2}+\\frac{2\\pi i x_2}{2^2}\\right)\\vert 1\\rangle\\right]\\otimes\\vert x_2x_3\\dots x_n\\rangle$$\n",
    "\n",
    "This can continue by applying the $CP_3$ gate with control in qubit $3$, the $CP_4$ gate with control in qubit $4$ and so on, until $CP_n$ is reached:\n",
    "\n",
    "$$\\frac{1}{\\sqrt{2}}\\left[\\vert0\\rangle + \\exp\\left(\\frac{2\\pi i x_1}{2}+\\dots+\\frac{2\\pi i x_n}{2^n}\\right)\\vert 1\\rangle\\right]\\otimes\\vert x_2x_3\\dots x_n\\rangle$$\n",
    "\n",
    "However, since we know that $x=2^0x_n+\\dots+2^{n-1}x_1$, the last equation can simply be rewritten as:\n",
    "\n",
    "$$\\frac{1}{\\sqrt{2}}\\left[\\vert0\\rangle + \\exp\\left(\\frac{2\\pi i x}{2^n}\\right)\\vert 1\\rangle\\right]\\otimes\\vert x_2x_3\\dots x_n\\rangle$$\n",
    "\n",
    "Finally, doing this for all kets would result in the **QFT** formula already provided above."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "145a7fdc-34a8-4cf0-8927-ac8bd8a90064",
   "metadata": {},
   "source": [
    "### The implementation (3 qubits)\n",
    "\n",
    "Let's start with a blank canvas containing 3 qubits:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9f86217e-7081-4099-9627-06285b1a5e1b",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Generate a quantum circuit with 3 qubits\n",
    "pi = 3.14159265359\n",
    "circuit = QuantumCircuit(3)\n",
    "\n",
    "# Visualize the (empty) circuit\n",
    "circuit.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "702ea93f-5fb1-4bb9-a4e2-a5e4eeab50a4",
   "metadata": {},
   "source": [
    "Since Qiskit's least significant bit has the lowest index (in other words, 0), the circuit must be **mirrored horizontally** in the end.\n",
    "\n",
    "Until then, we can add the first part of the algorithm, containing the Hadamard gate for $\\vert q_2\\rangle$ and the $CP$ gates with control in $\\vert q_1\\rangle$ and $\\vert q_0\\rangle$ (again, don't forget that our reasoning must be flipped horizontally):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0febe038-48c7-44f7-a6a5-31bff2d75179",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Add the Hadamard gate\n",
    "circuit.h(2)\n",
    "\n",
    "# Add the CP gates\n",
    "circuit.cp(pi/2, 1, 2)\n",
    "circuit.cp(pi/4, 0, 2)\n",
    "\n",
    "# Visualize the circuit (add barrier for visibility)\n",
    "circuit.barrier()\n",
    "circuit.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5b520957-b619-44ec-b3cf-516a1aff637a",
   "metadata": {},
   "source": [
    "Next, we can repeat the same logic for the $\\vert q_1\\rangle$ ket:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "58b8821b-3472-44b3-96cc-461e12e99c9b",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Add the Hadamard gate\n",
    "circuit.h(1)\n",
    "\n",
    "# Add the CP gate\n",
    "circuit.cp(pi/2, 0, 1)\n",
    "\n",
    "# Visualize the circuit (add barrier for visibility)\n",
    "circuit.barrier()\n",
    "circuit.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8776556e-e0cb-469d-bff1-893154435c76",
   "metadata": {},
   "source": [
    "One last Hadamard gate shall be applied. In the end, as we've already established, the circuit must be flipped horizontally - in this case, $\\vert q_0\\rangle$ and $\\vert q_2\\rangle$ must be swapped:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ba8dbe61-cb62-437f-9177-ceec65c460a9",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Add the Hadamard gate (add barrier for visibility)\n",
    "circuit.h(0)\n",
    "circuit.barrier()\n",
    "\n",
    "# Swap q0 and q2\n",
    "circuit.swap(0, 2)\n",
    "\n",
    "# Visualize the circuit\n",
    "circuit.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "48521b58-a772-45cf-8fd4-09664e0d37ad",
   "metadata": {},
   "source": [
    "Obviously, the code can be generalized for $n$ qubits. This is your task:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d4df616c-43c4-4a6b-9092-701233072f44",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Generate the circuit for the i-th qubit, qi (i = 0..n-1)\n",
    "def generate_qft_block(circuit, i):    \n",
    "    # TODO - Add Hadamard gate\n",
    "    \n",
    "    # TODO - Add CP gates (start with the following loop)\n",
    "    # for j in range(i-1, -1, -1):\n",
    "        \n",
    "\n",
    "    # Add barrier for visibility and return\n",
    "    circuit.barrier()\n",
    "    return circuit\n",
    "    \n",
    "# Generate the whole circuit\n",
    "def generate_qft(circuit, n):\n",
    "    # TODO - Loop through all possible n values (n-1 -> 0) and\n",
    "    #        call generate_qft_block\n",
    "    \n",
    "    # TODO - Finally, add swaps\n",
    "    \n",
    "    # Return the circuit\n",
    "    return circuit\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e37dde2-9712-4bc9-9d14-02a9c861dc53",
   "metadata": {},
   "source": [
    "To test your code, you can try to run the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5e6592c6-1619-4072-ada9-752496c915ef",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Generate a quantum circuit with n qubits\n",
    "n = 4\n",
    "circuit = QuantumCircuit(n)\n",
    "generate_qft(circuit, n)\n",
    "\n",
    "# Visualize the (empty) circuit\n",
    "circuit.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9319b8f0-bb7d-44ba-bfb0-636b0e780853",
   "metadata": {},
   "source": [
    "## Bibliography\n",
    "\n",
    "Our sources of inspiration are explained bellow:\n",
    "\n",
    "1. [**IBM Research Report** - An Approximate Fourier Transform Useful in Quantum Factoring](https://arxiv.org/pdf/quant-ph/0201067.pdf);\n",
    "2. [**Qiskit learn** - Quantum Fourier Transform](https://learn.qiskit.org/course/ch-algorithms/quantum-fourier-transform);"
   ]
  }
 ],
 "metadata": {
  "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.10.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}