tutorial/3_ftqc/05_deutsch.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Deutsch algorithm（Overview）\n",
    "\n",
    "## Oracle\n",
    "Let's start with the oracle used in this algorithm.  In simple terms, it is a function that returns 0 or 1 for a given input.  \n",
    "As an example, let's consider a situation where you are buying something.   \n",
    "The output is 1 if the input can be bought at the butcher shop, and 0 if it cannot.\n",
    "\n",
    "Then,\n",
    "\n",
    "$$\n",
    "f(x) = \\begin{cases}\n",
    "   1\\ \\  (x\\ \\text{can be bought at the butcher shop})\\\\\n",
    "    0\\ \\  (x\\ \\text{can NOT be bought at the butcher shop})\n",
    "  \\end{cases}\n",
    "$$\n",
    "\n",
    "We can't buy PC at the butcher shop, but we can buy beef, so...\n",
    "\n",
    "$$\n",
    "f(\\text{PC}) = 0,\\ \\ \\ \\ f(\\text{beef}) = 1\n",
    "$$\n",
    "\n",
    "Such a function that outputs 0 or 1 depending on the input is called an oracle.\n",
    "\n",
    "In quantum computer algorithms, we use oracle to retrieve only a specific state as an answer given an input state as $x$.  \n",
    "In other words, it is a gate that extracts only a certain state."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Deutsch algorithm\n",
    "First, we explain the algorithm that Deutsch came up with.  \n",
    "The Deutsch algorithm determine the Oracle of a 1-qubit input that is either $\\lvert 0\\rangle$ or $\\lvert 1\\rangle$.\n",
    "\n",
    "When $x =\\lvert 0\\rangle$ or $\\lvert1\\rangle$, there are four possible oracles.\n",
    "\n",
    "$$\n",
    "f(x) = \\begin{cases}\n",
    "   0\\ \\  (x= \\lvert 0\\rangle)\\\\\n",
    "    0\\ \\  (x= \\lvert1\\rangle)\n",
    "  \\end{cases}\n",
    "  \\mathrm{or}\\ \n",
    "  \\begin{cases}\n",
    "   0\\ \\  (x=\\lvert 0\\rangle)\\\\\n",
    "    1\\ \\  (x=\\lvert 1\\rangle)\n",
    "  \\end{cases}\n",
    "    \\mathrm{or}\\ \n",
    "  \\begin{cases}\n",
    "   1\\ \\  (x=\\lvert 0\\rangle)\\\\\n",
    "    0\\ \\  (x=\\lvert 1\\rangle)\n",
    "  \\end{cases}\n",
    "    \\mathrm{or}\\ \n",
    "  \\begin{cases}\n",
    "   1\\ \\  (x=\\lvert 0\\rangle)\\\\\n",
    "    1\\ \\  (x=\\lvert 1\\rangle)\n",
    "  \\end{cases}\n",
    "$$\n",
    "\n",
    "Deutsch algorithm はこの $f$ が $\\lvert 0\\rangle$ と $\\lvert 1\\rangle$ で値が同じものなのか、それとも違うものなのかを判定してくれます。\n",
    "\n",
    "The Deutsch algorithm will determine if this $f$ outputs the same value for inputs $\\lvert 0\\rangle$ and $\\lvert 1\\rangle$ or not."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider a concrete circuit.\n",
    "\n",
    "<img src=\"../img/016/016_3_new.png\" width=\"40%\">\n",
    "\n",
    "$U_f$ is the Oracle.  \n",
    "For $q_0$ register, the incoming value $x$ is returned as is, and for $q_1$ register, $y\\oplus f(x)$ takes $\\rm{mod} 2$ of the sum of the incoming value $y$ and $f(x)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's check the status of each.\n",
    "\n",
    "$$\n",
    "|\\psi_1\\rangle = H|0\\rangle \\otimes H|1\\rangle = \\frac{1}{\\sqrt{2}}(\\lvert0\\rangle + \\lvert1\\rangle) \\otimes \\frac{1}{\\sqrt{2}}(\\lvert0\\rangle - \\lvert1\\rangle)\n",
    "$$\n",
    "\n",
    "We obtain\n",
    "\n",
    "$$\n",
    "|\\psi_1\\rangle = \\frac{1}{2} \\lvert0\\rangle \\otimes (\\lvert0\\rangle - \\lvert1\\rangle) + \\frac{1}{2} \\lvert1\\rangle \\otimes (\\lvert0\\rangle - \\lvert1\\rangle)\\ \\ \\ \\ \\cdots (\\star)\n",
    "$$\n",
    "\n",
    "We can see that the sign changes when the first qubit is flippeed ($\\lvert0\\rangle \\leftrightarrow \\lvert1\\rangle$).  \n",
    "In this situation, consider $\\lvert\\psi_2\\rangle$ for the four ways $f(x)$ above.\n",
    "\n",
    "Because $f(x)$ operates to first qubit,\n",
    "\n",
    "$$\n",
    "f(x)=0 \\to q_1 \\text{ do not changes.}\n",
    "$$\n",
    "\n",
    "$$\n",
    "f(x)=1 \\to q_1 \\text{ flips.}\n",
    "$$\n",
    "\n",
    "Therefore, if we look at the equation $(\\star)$\n",
    "\n",
    "$$\n",
    "f(0)=f(1) \\to \\text{the two terms have same sign}\n",
    "$$\n",
    "\n",
    "$$\n",
    "f(0)\\neq f(1) \\to \\text{the two terms have opposite sign}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then,\n",
    "\n",
    "$$\n",
    "\\begin {align}\n",
    "\\lvert \\psi_2 \\rangle &= \\begin{cases}\n",
    "\\pm \\frac{1}{2} \\lvert 0 \\rangle \\otimes (\\lvert 0\\rangle - \\lvert 1\\rangle) \\pm \\frac{1}{2} \\lvert 1 \\rangle \\otimes (\\lvert 0\\rangle - \\lvert 1\\rangle)  \\ \\  \\ \\ (f(0)= f(1)) \\\\\n",
    "\\pm \\frac{1}{2} \\lvert 0 \\rangle \\otimes (\\lvert 0\\rangle - \\lvert 1\\rangle) \\mp \\frac{1}{2} \\lvert 1 \\rangle \\otimes (\\lvert 0\\rangle - \\lvert 1\\rangle)  \\ \\  \\ \\ (f(0)\\neq f(1)) \\end{cases} \\\\\n",
    "&= \\begin{cases}\n",
    "\\pm H\\lvert 0 \\rangle \\otimes H \\lvert 1 \\rangle \\ \\  \\ \\ (f(0)= f(1)) \\\\\n",
    " \\pm H\\lvert 1 \\rangle \\otimes H \\lvert 1 \\rangle \\ \\  \\ \\ (f(0)\\neq f(1))\n",
    "\\end{cases}\n",
    "\\end {align}\n",
    "$$\n",
    "\n",
    "\n",
    "Finally, operate $H$ gate to $q_0$.  \n",
    "Then we obtain\n",
    "\n",
    "$$\n",
    "\\lvert \\psi_3 \\rangle = \\begin{cases}\n",
    "\\pm \\lvert 0\\rangle \\otimes H\\lvert 1 \\rangle\\ \\  \\ \\ (f(0)= f(1)) \\\\\n",
    "\\pm \\lvert 1\\rangle \\otimes H\\lvert 1 \\rangle\\ \\  \\ \\ (f(0)\\neq f(1))\n",
    "\\end{cases}\n",
    "$$\n",
    "\n",
    "\n",
    "The sign $\\pm$ is ignored in measurement result, so measurement to 0th qubit can determine the oracle.\n",
    "\n",
    "This is the  explanation of Deutsch algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's implement it using blueqat."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "from blueqat import Circuit\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For the input and output values of $f(x)$, four ways oracles were considered.  \n",
    "This time, we will implement each of the four ways, and the oracle will be chosen randomly by a random number.   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 191,
   "metadata": {},
   "outputs": [],
   "source": [
    "def oracle_00(c):\n",
    "    c.i[:]\n",
    "    \n",
    "def oracle_01(c):\n",
    "    c.cx[0, 1]\n",
    "    \n",
    "def oracle_10(c):\n",
    "    c.x[0]\n",
    "    c.cx[0, 1]\n",
    "    c.x[0]\n",
    "    \n",
    "def oracle_11(c):\n",
    "    c.x[1]\n",
    "    \n",
    "def oracle(c):\n",
    "    f = np.random.rand()\n",
    "    if f < 0.25:\n",
    "        oracle_00(c)\n",
    "        return \"f(0) = 0, f(1) = 0\"\n",
    "    elif f < 0.5:\n",
    "        oracle_01(c)\n",
    "        return \"f(0) = 0, f(1) = 1\"\n",
    "    elif f < 0.75:\n",
    "        oracle_10(c)\n",
    "        return \"f(0) = 1, f(1) = 0\"\n",
    "    else:\n",
    "        oracle_11(c)\n",
    "        return \"f(0) = 1, f(1) = 1\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here, using Deutsch's algorithm, we can determine the oracle with probability 1 from the measurement results."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 197,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Counter({'10': 128})\n",
      "Selected oracle: f(0) = 1, f(1) = 0\n"
     ]
    }
   ],
   "source": [
    "c = Circuit(2)\n",
    "c.x[1].h[:]\n",
    "oracle_str = oracle(c)\n",
    "c.h[0].m[0]\n",
    "res = c.run(shots = 128)\n",
    "print(res)\n",
    "print(\"Selected oracle:\", oracle_str)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If the oracle is $f(0) = f(1)$, measurement results are '00' for all samples.  \n",
    "If the oracle is $f(0) \\neq f(1)$, measurement results are '10' for all samples."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "file_extension": ".py",
  "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.11"
  },
  "mimetype": "text/x-python",
  "name": "python",
  "npconvert_exporter": "python",
  "pygments_lexer": "ipython3",
  "version": 3
 },
 "nbformat": 4,
 "nbformat_minor": 2
}