tutorial/3_ftqc/02_pea.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "NjHnSAbHrInP"
   },
   "source": [
    "# Quantum phase estimation\n",
    "\n",
    "We explain the quantum phase estimation that allows us to find the phase $\\alpha$ of its eigenvalue $\\lambda = e^{-i\\alpha}$ when the Unitary $U$ and the eigenstate $\\lvert \\psi \\rangle$ are prepared.\n",
    "\n",
    "$$\n",
    "U \\lvert \\psi \\rangle = e^{-i\\alpha} \\lvert \\psi \\rangle\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "CJhIv6UdASWQ"
   },
   "source": [
    "## Quantum circuit for quantum phase estimation\n",
    "The overall picture of the quantum phase estimation algorithm is as follows.\n",
    "\n",
    "1. Preparation of quantum states as an eigenvector.  \n",
    "2. Eigenvalues are extracted and embedded to quantum states (phase kickback).  \n",
    "3. Transform the quantum states and get an eigenvalue as measured bit string (inversed quantum Fourier transform).  \n",
    "\n",
    "\n",
    "\n",
    "```\n",
    "                         step2                   step3\n",
    "      \n",
    "|0> ----H----------------------*-------iQFT---\n",
    "|0> ----H--------------*-------|-------iQFT---\n",
    "|0> ----H--------*-----|-------|-------iQFT---\n",
    "|0> ----H--*-----|-----|-------|-------iQFT---\n",
    "                  |       |       |         |\n",
    "                  |       |       |         |\n",
    "|ψ> -------U1--U2---U4-- -U2n------------\n",
    "step1\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Phase kickback\n",
    "\n",
    "We review the phase kickback method.\n",
    "\n",
    "We introduce the controled unitary circuit for the unitary with the eigenvector $\\lvert \\psi \\rangle$ and the corresponding eigenvalue $e^{2\\pi i \\phi}$. We'll see that the eigenvalue can be embedded to the coefficient of $\\lvert 1\\rangle$ of the control bit.\n",
    "\n",
    "The eigenvalue equation for the unitary is following.\n",
    "\n",
    "$$\n",
    "U\\lvert \\psi \\rangle = e^{2\\pi i \\phi} \\lvert \\psi \\rangle\n",
    "$$\n",
    "\n",
    "Assuming the quantum state $\\lvert \\psi \\rangle$ is prepared, the phase can be extracted with the controled unitary circuit."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, from the initial state, the qubit from which you want to extract the result is put into a superposition state using an Hadamard gate.\n",
    "\n",
    "$$\n",
    "\\lvert 0 \\rangle \\lvert \\psi \\rangle \\rightarrow \\frac{\\lvert 0\\rangle + \\lvert 1 \\rangle}{\\sqrt{2}} \\lvert \\psi \\rangle = \\frac{\\lvert 0\\rangle \\lvert \\psi \\rangle + \\lvert 1 \\rangle \\lvert \\psi \\rangle}{\\sqrt{2}}\n",
    "$$\n",
    "\n",
    "Next, by introducing the controlled unitary circuit, unitary is applied only to the state the control qubit is $\\lvert 1\\rangle$.\n",
    "\n",
    "$$\n",
    "\\frac{\\lvert 0\\rangle \\lvert \\psi \\rangle + \\lvert 1 \\rangle U \\lvert \\psi \\rangle}{\\sqrt{2}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using eigenvalue equation, we can extract the eigenvalue to the coefficient.\n",
    "\n",
    "$$\n",
    "\\frac{\\lvert 0\\rangle \\lvert \\psi \\rangle + \\lvert 1 \\rangle e^{2\\pi i \\phi} \\lvert \\psi \\rangle}{\\sqrt{2}} = \\frac{\\lvert 0\\rangle \\lvert \\psi \\rangle +  e^{2\\pi i \\phi} \\lvert 1 \\rangle \\lvert \\psi \\rangle}{\\sqrt{2}} = \\frac{\\lvert 0\\rangle +  e^{2\\pi i \\phi} \\mid 1 \\rangle}{\\sqrt{2}} \\lvert \\psi \\rangle\n",
    "$$\n",
    "\n",
    "\n",
    "Next, \n",
    "\n",
    "$$\n",
    "\\frac{1}{\\sqrt{2^n}}\\sum_{k=0}^{2^n-1} e^{i2\\pi k\\phi}\\lvert k \\rangle\n",
    "$$\n",
    "\n",
    "のように、取り出したい桁に対応するkを導入すれば良いですが、これは回転角に対応しており、固有値をk回かけるということをすると、自然と対応することができます。つまり$U^k$のように同じユニタリ操作をk回実行すれば良いことになります。ということで、k回Controlled-Unitary操作を行うことで求めることができます。\n",
    "\n",
    "$$\n",
    "\\frac{\\lvert 0\\rangle +  U^k \\lvert 1 \\rangle}{\\sqrt{2}} \\lvert \\psi \\rangle = \\frac{\\lvert 0\\rangle +  e^{2\\pi i k \\phi} \\lvert 1 \\rangle}{\\sqrt{2}} \\lvert \\psi \\rangle\n",
    "$$\n",
    "\n",
    "これにより、対応する桁kに対してk回の制御付きユニタリゲートをかけることで実行が終了します。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "oXg3hf3yAkMS"
   },
   "source": [
    "## Quantum Fourier transform\n",
    "\n",
    "We also review Quantum Fourier transform.\n",
    "\n",
    "Quantum Fourier transform can transform the binary array input to a quantum state with a corresponding phase.  \n",
    "By using the inverse quantum Fourier transform, which is the inverse circuit of quantum Fourier transform, the phase transferred by the phase kickback described above can be written out as a bit string.\n",
    "\n",
    "$$\n",
    "QFT:\\lvert x \\rangle \\mapsto \\frac{1}{\\sqrt{N}}\\sum_{k=0}^{N-1} \\omega_n^{xk}\\lvert k\\rangle\n",
    "$$\n",
    "\n",
    "<!-- \n",
    "Assuming $\\omega_n = e^{\\frac{2\\pi i}{N}}$, \n",
    "\n",
    "$$\n",
    "{F_N= \n",
    "\\frac{1}{\\sqrt{N}} \n",
    "\\left[ \n",
    " \\begin{array}{rrrr} \n",
    "  1 & 1 & 1 & \\cdots &1\\\\ \n",
    "  1 & \\omega_n&\\omega_n^2&\\cdots&\\omega_n^{N-1}\\\\ \n",
    "  1 & \\omega_n^2&\\omega_n^4&\\cdots&\\omega_n^{2(N-1)}\\\\ \n",
    "  1 & \\omega_n^3&\\omega_n^6&\\cdots&\\omega_n^{3(N-1)}\\\\ \n",
    "  \\vdots&\\vdots&\\vdots&&\\vdots\\\\ \n",
    "  1 & \\omega_n^{N-1}&\\omega_n^{2(N-1)}&\\cdots&\\omega_n^{(N-1)(N-1)} \n",
    " \\end{array} \n",
    "\\right]\n",
    "}\n",
    "$$ -->\n",
    "\n",
    "When you input bit string $x_n$ to $x_1$, the output quantum state has phases corresponding to the input bit string.\n",
    "\n",
    "$$\n",
    "QFT(\\lvert x_n,x_{n-1},…,x_1 \\rangle) = \\frac{1}{\\sqrt{N}}(\\lvert 0 \\rangle + e^{2\\pi i [0.x_n]} \\lvert 1 \\rangle) \\otimes … \\otimes (\\lvert 0 \\rangle + e^{2\\pi i [0.x_1x_2…x_n]} \\lvert 1 \\rangle)\n",
    "$$\n",
    "\n",
    "$$[0.x_1x_2…] = \\frac{x_1}{2}+\\frac{x_2}{2^2}+…$$\n",
    "\n",
    "The input state (bit string) shifted by an order of magnitude is encoded to the relative phase of each qubit in the output quantum state. However, since the coefficients of $\\lvert 1\\rangle$ for each qubit are all absolute values of $1/\\sqrt{N}$, just measuring the individual qubits will produce exactly 50% 0s and 1s."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Phase kickback + inverse quantum Fourier transform"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In quantum phase estimation, we apply the phase kickback described earlier to prepare the following state.\n",
    "\n",
    "$$\n",
    "\\frac{1}{\\sqrt{2^n}}\\sum_{k=0}^{2^n-1} e^{i2\\pi k\\phi}\\lvert k \\rangle\n",
    "$$\n",
    "\n",
    "$\\phi$ is an eigenvalue of unitary, which is what we wanted to find.  \n",
    "\n",
    "If such a state can be prepared, an inverse quantum Fourier transform can be used to convert it into a quantum state $\\lvert \\phi_n,\\phi_{n-1},...,\\phi_1\\rangle$ consisting of a binary-encoded bit sequence of $\\phi$.  \n",
    "Therefore, if we perform the measurement at the end, we can extract $\\phi$.\n",
    "\n",
    "In each term, the original phase $\\phi$  is multiplied by $k$, which is the same as multiplying the eigenvalue by $k$ times.  \n",
    "Therefore, we can perform the same unitary operation $k$ times as $U^k$. In other words, it can be achieved by performing the Controlled-Unitary operation $k$ times.\n",
    "\n",
    "$$\n",
    "\\frac{\\mid 0\\rangle +  U^k \\mid 1 \\rangle}{\\sqrt{2}} \\mid \\psi \\rangle = \\frac{\\mid 0\\rangle +  e^{2\\pi i k \\phi} \\mid 1 \\rangle}{\\sqrt{2}} \\mid \\psi \\rangle\n",
    "$$\n",
    "\n",
    "Thus, we can prepare the above state by applying the corresponding $k$ times controlled unitary gate for each qubit."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Estimate the phase of the Z-gate\n",
    "\n",
    "Let's do exercize。First, let's prepare a Z-gate as a unitary.\n",
    "\n",
    "$$\n",
    "Z = \\begin{pmatrix}\n",
    "1&0\\\\\n",
    "0&-1\n",
    "\\end{pmatrix}\n",
    "$$\n",
    "\n",
    "As first, we check the answer by hand.  \n",
    "Calculate characteristic equation\n",
    "\n",
    "$$\n",
    "det\\begin{pmatrix}\n",
    "1-\\lambda&0\\\\\n",
    "0&-1-\\lambda\n",
    "\\end{pmatrix} = 0\n",
    "$$\n",
    "\n",
    "and we see that the eigenvalues are $\\lambda = 1,-1$.  \n",
    "Eigenvectors are following.\n",
    "\n",
    "$$\n",
    "\\begin{pmatrix}\n",
    "1\\\\\n",
    "0\n",
    "\\end{pmatrix},\n",
    "\\begin{pmatrix}\n",
    "0\\\\\n",
    "1\n",
    "\\end{pmatrix}\n",
    "$$\n",
    "\n",
    "Let's check it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Install blueqat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "N6OzyNAobUad"
   },
   "outputs": [],
   "source": [
    "!pip install blueqat"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Circuit overview\n",
    "\n",
    "This is an overview of the circuit.\n",
    "\n",
    "```\n",
    "|0> ----H--*--iQFT--M\n",
    "                  |\n",
    "|0> ------- Z--------\n",
    "```\n",
    "\n",
    "First, prepare two qubits, the 0th and 1st, respectively. Both qubits start in state $\\lvert 0\\rangle$.\n",
    "\n",
    "1. Prepare an eigenstate for the first qubit.  \n",
    "2. An Hadamard gate is applied to the 0th qubit to create a superposition state.\n",
    "3. Apply a CZ gate as a control unitary and kickback the phase to the 0th qubit.  \n",
    "4. Perform an inverse quantum Fourier transform, measure and extract the phase.\n",
    "\n",
    "We first prepare the eigenstate $\\lvert 0\\rangle$. In other words, we do nothing with the initial state.\n",
    "\n",
    "Then, the quantum Fourier transform of a single qubit is equivalent to an Hadamard gate.  \n",
    "(Since the Hadamard matrix is Hermitian, the inverse quantum Fourier transform in this case is also an  Hadamard gate)\n",
    "\n",
    "Thus, the implementation will look like following."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "mV6JWcmHCMY2",
    "outputId": "1d0b5e00-eff4-4ed6-c795-f6e33d045b7a"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({'00': 100})"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from blueqat import Circuit\n",
    "\n",
    "Circuit().h[0].cz[0,1].h[0].m[:].run(shots=100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "U1uxGVsCCi85"
   },
   "source": [
    "Thus $\\phi = 0.0$.\n",
    "\n",
    "The eigenvalues we seek are as follows.\n",
    "\n",
    "$$\n",
    "e^{2\\pi i \\phi} = e^{2\\pi i \\cdot 0} = e^0 = 1\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "uEO1xB4OCkcK"
   },
   "source": [
    "Next, let's set the eigenstate to be prepared as $\\lvert 1 \\rangle$.\n",
    "\n",
    "```\n",
    "|0> --H--*--iQFT--M\n",
    "               |\n",
    "|0> --X--Z--------\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "3eRpgppa_1FI",
    "outputId": "e2be355c-60b0-4b3a-8acc-aa9cecdaf9d8"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({'11': 100})"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Circuit().x[1].h[0].cz[0,1].h[0].m[:].run(shots=100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "lP9JKP_xDgai"
   },
   "source": [
    "Now $\\phi = 1/2 = 0.5$.\n",
    "\n",
    "The eigenvalues we seek are as follows.\n",
    "\n",
    "$$\n",
    "e^{2\\pi i \\cdot 0.5} = -1\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The case of estimating the phase of an X-gate\n",
    "\n",
    "An X-gate is a matrix that looks like this\n",
    "\n",
    "$$\n",
    "X = \n",
    "\\begin{pmatrix}\n",
    "0&1\\\\\n",
    "1&0\n",
    "\\end{pmatrix}\n",
    "$$\n",
    "\n",
    "We first consider the following eigenvector. The eigenvalue is 1.\n",
    "\n",
    "$$\n",
    "\\mid \\psi \\rangle = \n",
    "\\begin{pmatrix}\n",
    "1\\\\\n",
    "1\n",
    "\\end{pmatrix}\n",
    "$$\n",
    "\n",
    "The circuit is as follows\n",
    "\n",
    "```\n",
    "|0> --H--*--H--M\n",
    "         　　　　　　|\n",
    "|0> --H--X-----\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({'00': 100})"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Circuit(2).h[:].cx[0,1].h[0].m[0].run(shots=100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is $\\phi = 0.0$ and the eigenvalue is as follows.\n",
    "\n",
    "$$\n",
    "\\lambda = e^0=1\n",
    "$$\n",
    "\n",
    "Next, consider the case with following eigenvector. The eigenvalue is -1.\n",
    "\n",
    "$$\n",
    "\\mid \\psi \\rangle = \n",
    "\\begin{pmatrix}\n",
    "1\\\\\n",
    "-1\n",
    "\\end{pmatrix}\n",
    "$$\n",
    "\n",
    "\n",
    "```\n",
    "|0> --H---*--H--M\n",
    "          　　　　　　|\n",
    "|0> --HZ--X-----\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({'10': 100})"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Circuit(2).h[:].z[1].cx[0,1].h[0].m[0].run(shots=100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Thsu $\\phi = 0.5$ and the eigenvalue is as follows.\n",
    "\n",
    "$$\n",
    "\\lambda = e^{2\\pi i \\cdot0.5}=-1\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "015_algo_pea_simple.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.8.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}