tutorial/3_ftqc/01_qft.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "NjHnSAbHrInP"
   },
   "source": [
    "# Quantum Fourier Transform\n",
    "\n",
    "The classical Fourier transform is an important tool in wave and signal analysis that breaks a function into components, each with a different frequency.\n",
    "Its discrete analogue, the Discrete Fourier transform acts on $n$ complex numbers $x_0,\\ldots,x_{N-1}$ and transforms it to another sequence of $n$ complex numbers $\\tilde x_0,\\ldots,\\tilde x_{N-1}$ via:\n",
    "\n",
    "$$\\tilde x_k = \\sum_{y=0}^{N-1}e^{-\\frac{2\\pi ikn}N} \\cdot x_k$$\n",
    "\n",
    "The quantum Fourier transform (commonly abbreviated as QFT) on $n$ qubits (with $N=2^n$), achieves an analogous effect, and is given by the following equation (for every basis state $x\\in\\{0,1\\}^n$):\n",
    "\n",
    "$$\\text{QFT}(\\lvert x\\rangle) = \\frac 1{\\sqrt N}\\sum_{y=0}^{N-1}e^{\\frac{2\\pi ixy}N}\\lvert y\\rangle\\qquad \\qquad (1)$$\n",
    "\n",
    "Here, we abuse notation and associate a bitstring $x\\in\\{0,1\\}^n$ to the integer $\\sum_{j=0}^{n-1}2^{n-1-j}x_j$.\n",
    "\n",
    "Effectively, one can think of QFT as a change of basis from the computational basis to the \"Fourier basis\".\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "oXg3hf3yAkMS"
   },
   "source": [
    "## Factorization of QFT\n",
    "\n",
    "It turns out (after some algebraic manipulations) that one is able to factorize the sum in Eq. $(1)$ into a product of pure states\n",
    "\n",
    "$$\\text{QFT}(\\lvert x\\rangle) = \\frac 1{\\sqrt N}\\left(\\vert 0\\rangle + e^{\\frac{2\\pi ix}{2^1}}\\vert 1\\rangle\\right)\\otimes \\left(\\vert 0\\rangle + e^{\\frac{2\\pi ix}{2^2}}\\vert 1\\rangle\\right)\\otimes \\cdots \\otimes \\left(\\vert 0\\rangle + e^{\\frac{2\\pi ix}{2^n}}\\vert 1\\rangle\\right).$$\n",
    "\n",
    "This formulation tells us exactly how to implement a quantum circuit achieving QFT.\n",
    "\n",
    "## Controlled Phase Rotations\n",
    "Before looking at the circuit structure though, we define the gate\n",
    "$$R_k = \\begin{pmatrix}1 & 0\\\\ 0 & e^{\\frac{2\\pi i}{2^k}}\\end{pmatrix},$$\n",
    "and recall that a controlled version of this gate will change the phase of the target qubit depending on the value of the control qubit.\n",
    "In other words, $CR_k(\\lvert 0\\rangle|x\\rangle) = |0\\rangle \\lvert x\\rangle$ and \n",
    "\n",
    "\\begin{aligned}CR_k(\\lvert 1\\rangle \\lvert x\\rangle) = \\lvert 1\\rangle\\otimes R_k(\\lvert x \\rangle) &=\\lvert 1\\rangle\\otimes R_k\\left( \\langle 0\\lvert x\\rangle \\lvert  0\\rangle + \\langle 1 \\lvert x\\rangle \\lvert 1\\rangle\\right)\n",
    " \\\\ & = \\lvert 1\\rangle\\otimes \\left( \\langle 0 \\lvert x\\rangle \\lvert  0\\rangle + \\langle 1 \\lvert x\\rangle e^{\\frac{2\\pi i}{2^k}} \\lvert 1\\rangle\\right)\\end{aligned}\n",
    "\n",
    "More compactly,\n",
    "$$CR_k(\\lvert y\\rangle \\lvert x\\rangle) = \\lvert y\\rangle \\otimes \\left( \\langle 0 \\vert x\\rangle \\lvert  0\\rangle + \\langle 1 \\vert x\\rangle e^{\\frac{2\\pi iy}{2^k}} \\lvert 1\\rangle\\right).$$\n",
    "\n",
    "Therefore, $$CR_k = \\begin{pmatrix}1 & 0 & 0 & 0\\\\ 0 & 1 & 0 & 0\\\\ 0& 0& 1 & 0\\\\ 0 & 0&0 &e^{\\frac{2\\pi i}{2^k}}\\end{pmatrix} = \\text{CPhase}\\left(\\frac{2\\pi}{2^k}\\right).$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "U1uxGVsCCi85"
   },
   "source": [
    "## Circuit Structure\n",
    "\n",
    "Now we have all the ingredients required to construct a circuit achieving QFT.\n",
    "Below is an example circuit on $n=4$ qubits:\n",
    "\n",
    "![Circuit Image](img/121_qft_ckt.png)\n",
    "\n",
    "We shall work our way through the states $\\lvert \\varphi_1\\rangle$ through $\\lvert \\varphi_4\\rangle$.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "yd5MaoRKCuWS"
   },
   "source": [
    "In $\\lvert \\varphi_1\\rangle$, let us analyze the state of the first qubit on the basis states $x_0\\in\\{0,1\\}$. Then $\\lvert x_0\\rangle$ is mapped to (let us ignore normalizations for simplifying calculations):\n",
    "+ $H$: $\\lvert 0\\rangle + e^{\\pi i x_0}\\lvert 1\\rangle$,\n",
    "+ $R_2$: $\\lvert 0\\rangle + e^{\\pi i x_0 + \\frac{2\\pi i x_1}{2^2}}\\lvert 1\\rangle$\n",
    "+ $R_3$: $\\lvert 0\\rangle + e^{\\pi i x_0 + \\frac{2\\pi i x_1}{2^2} + \\frac{2\\pi i x_2}{2^3}}\\lvert 1\\rangle$\n",
    "+ $R_4$: $\\lvert 0\\rangle + e^{\\pi i x_0 + \\frac{2\\pi i x_1}{2^2} + \\frac{2\\pi i x_2}{2^3} + \\frac{2\\pi i x_3}{2^4}}\\lvert 1\\rangle = \\lvert 0\\rangle + e^{\\frac{2\\pi i}{2^4} (8x_0 + 4x_1 + 2x_2 + x_3)}\\lvert 1\\rangle = |0\\rangle + e^{\\frac{2\\pi i x}{2^4}}\\lvert 1\\rangle$.\n",
    "\n",
    "Hence, $\\lvert \\varphi_1\\rangle = \\left(\\lvert 0\\rangle + e^{\\frac{2\\pi i x}{2^4}}\\lvert 1\\rangle\\right)\\otimes \\lvert x_1x_2x_3\\rangle$.\n",
    "\n",
    "It is now easy to see via an inductive argument that $\\lvert \\varphi_2\\rangle$ changes qubit $\\lvert x_1\\rangle$ to:\n",
    "+ $\\lvert 0\\rangle + e^{\\frac{2\\pi i}{2^3}(4x_1 + 2x_2 + x_3)}\\lvert 1\\rangle$.  \n",
    "\n",
    "However, as $e^{2\\pi ix_0} = 1$, we have $e^{\\frac{2\\pi i}{2^3}(4x_1 + 2x_2 + x_3)}=e^{\\frac{2\\pi i}{2^3}(8x_0 + 4x_1 + 2x_2 + x_3)}= e^{\\frac{2\\pi ix}{2^3}}$.\n",
    "\n",
    "So, $\\lvert \\varphi_2\\rangle = \\left(\\lvert 0\\rangle + e^{\\frac{2\\pi i x}{2^4}}\\lvert 1\\rangle\\right)\\otimes \\left(\\lvert 0\\rangle + e^{\\frac{2\\pi i x}{2^3}}\\lvert 1\\rangle\\right)\\otimes \\lvert x_2x_3\\rangle$.\n",
    "\n",
    "Continuing, we can check that $\\vert \\varphi_4 \\rangle$ gives us the reverse order of the qubits that we wanted, and hence we do a double swap to complete the circuit schematic of QFT.\n",
    "\n",
    "## Writing QFT in Blueqat-SDK"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "DmYYtTqqnbAv",
    "pycharm": {
     "is_executing": false
    }
   },
   "outputs": [],
   "source": [
    "# Install Blueqat-SDK if you haven't already!\n",
    "# !pip install blueqat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import Modules\n",
    "from blueqat import Circuit\n",
    "import math"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 51
    },
    "colab_type": "code",
    "id": "3eRpgppa_1FI",
    "outputId": "70c0f858-f1ca-48f0-f4f3-a97d489e983f",
    "pycharm": {
     "is_executing": false
    }
   },
   "outputs": [],
   "source": [
    "# Function to apply qft on a list of qubits of circuit\n",
    "def apply_qft(circuit: Circuit(), qubits):\n",
    "    num_qubits = len(qubits)\n",
    "    for i in range(num_qubits):\n",
    "        circuit.h[qubits[i]]\n",
    "        for j in range(i+1, num_qubits):\n",
    "            circuit.cphase(math.pi/(2 ** (j-i)))[qubits[j],qubits[i]] # Apply gate CR_{j-i}(qubit j, qubit i)\n",
    "    # Reverse the order of qubits at the end\n",
    "    for i in range(int(num_qubits/2)):\n",
    "        circuit.swap(qubits[i],qubits[num_qubits-i-1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Testing on a circuit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "colab_type": "text",
    "id": "JM9lexiT_034"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 2.50000000e-01+0.j        ,  2.30969883e-01-0.09567086j,\n",
       "        1.76776695e-01-0.1767767j ,  9.56708581e-02-0.23096988j,\n",
       "       -1.53080850e-17-0.25j      , -9.56708581e-02-0.23096988j,\n",
       "       -1.76776695e-01-0.1767767j , -2.30969883e-01-0.09567086j,\n",
       "       -2.50000000e-01+0.j        , -2.30969883e-01+0.09567086j,\n",
       "       -1.76776695e-01+0.1767767j , -9.56708581e-02+0.23096988j,\n",
       "        1.53080850e-17+0.25j      ,  9.56708581e-02+0.23096988j,\n",
       "        1.76776695e-01+0.1767767j ,  2.30969883e-01+0.09567086j])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = 4  # number of qubits to apply QFT on\n",
    "qc = Circuit()\n",
    "qc.x[:]  # Prepare the state |1111>\n",
    "apply_qft(qc, range(n))\n",
    "qc.run()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "qdBTsGLnDBce"
   },
   "source": [
    "The QFT only changes phases of individual qubits, and hence cannot be physically observed via measurements. Below is a visual representation of the above statevector obtained from $\\text{QFT}(|1111\\rangle)$:\n",
    "\n",
    "![Statevector](img/121_qft_statevec.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "4VAuNlz1A079",
    "outputId": "51bf7d5a-318c-4752-c1ad-3fffd388cdb5"
   },
   "source": [
    "## Applications of QFT\n",
    "\n",
    "QFT has wide applications in Algorithms design, and is the building block for many influential quantum algorithms such as Quantum Phase Estimation [[1]] , Shor's Algorithm [[2]], and the Hidden Subgroup Problem [[3]].\n",
    "\n",
    "[1]: https://en.wikipedia.org/wiki/Quantum_phase_estimation_algorithm\n",
    "[2]: https://en.wikipedia.org/wiki/Shor's_algorithm\n",
    "[3]: https://en.wikipedia.org/wiki/Hidden_subgroup_problem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "013_algo_qft.ipynb",
   "provenance": [],
   "version": "0.3.2"
  },
  "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.7"
  },
  "pycharm": {
   "stem_cell": {
    "cell_type": "raw",
    "metadata": {
     "collapsed": false
    },
    "source": []
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}