tutorial/3_ftqc/05_deutsch-jozsa.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Deutsch-Jozsa algorithm\n",
    "\n",
    "We explain the Deutsch-Jozsa algorithm, a generalization of the Deutsch algorithm.  \n",
    "For function $f$, which can take $2^n$ kinds of inputs (00...000 to 11...111), we assume that one of the following conditions holds.\n",
    "\n",
    "1.  $f(x)$ is same for all inputs,\n",
    "namely, $f(x)=0$ for all $x$ or $f(x)=1$ for all $x$.\n",
    "\n",
    "2. $f(x)$ is different in half of the inputs,\n",
    "namely, $f(x)=0$ for $2^{n-1}$ of inputs $x$, and $f(x)=1$ for others.\n",
    "\n",
    "This algorithm determines whether Oracle is 1\\. or 2\\. above.\n",
    "\n",
    "The circuit is here.\n",
    "\n",
    "<img src=\"../img/101_img.png\" width=\"60%\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It has $n$ qubits $\\lvert 0\\rangle$ and 1qubit $\\lvert 1\\rangle$ as  initial states.\n",
    "\n",
    "Now let's check the states.\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "\\lvert \\psi_1\\rangle &= \\biggl(\\otimes^n H\\lvert 0\\rangle \\biggr)\\otimes H \\lvert 1\\rangle \\\\\n",
    "&= \\frac{1}{ \\sqrt{2^{n+1}} } \\sum^{2^n}_{x\\in \\{ 0, 1 \\}^n} \\bigl( \\lvert x\\rangle \\otimes (\\lvert 0\\rangle - \\lvert 1\\rangle) \\bigr) \\\\\n",
    "&= \\frac{1}{ \\sqrt{2^{n+1}} } \\sum^{2^n}_{x\\in \\{ 0, 1 \\}^n} \\lvert x\\rangle \\otimes \\lvert 0\\rangle - \\frac{1}{ \\sqrt{2^{n+1}} } \\sum^{2^n}_{x\\in \\{ 0, 1 \\}^n} \\lvert x\\rangle \\otimes \\lvert 1\\rangle \\\\\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "\n",
    "For the $n$ th qubit, you can see that swapping $\\lvert 0\\rangle$ and $\\lvert 1\\rangle$ changes the overall sign."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, consider $\\psi_2$.  \n",
    "Because $f(x)$ operates to $n$ th qubit,\n",
    "\n",
    "$$\n",
    "f(x) = 0 \\to n\\text{ th qubit is NOT be flipped.}\n",
    "$$\n",
    "$$\n",
    "f(x) = 1 \\to n\\text{ th qubit is flipped.}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dividing the summation by $f(x) = 0 \\text{ or } 1$ for each term,\n",
    "\n",
    "$$\n",
    "\\frac{1}{ \\sqrt{2^{n+1}} } \\sum^{2^n}_{x\\in \\{ 0, 1 \\}^n} \\lvert x\\rangle \\otimes \\lvert 0\\rangle \\xrightarrow{U_f} \\frac{1}{ \\sqrt{2^{n+1}} } \\sum_{f(x)=0} \\lvert x\\rangle \\otimes \\lvert 0\\rangle + \\frac{1}{ \\sqrt{2^{n+1}} } \\sum_{f(x)=1} \\lvert x\\rangle \\otimes \\lvert 1\\rangle\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\frac{1}{ \\sqrt{2^{n+1}} } \\sum^{2^n}_{x\\in \\{ 0, 1 \\}^n} \\lvert x\\rangle \\otimes \\lvert 1\\rangle \\xrightarrow{U_f} \\frac{1}{ \\sqrt{2^{n+1}} } \\sum_{f(x)=0} \\lvert x\\rangle \\otimes \\lvert 1\\rangle + \\frac{1}{ \\sqrt{2^{n+1}} } \\sum_{f(x)=1} \\lvert x\\rangle \\otimes \\lvert 0\\rangle\n",
    "$$\n",
    "\n",
    "We can see that $n$ th qubit is flipped when $f(x)=1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Therefore,\n",
    "\n",
    "$$\n",
    "\\lvert \\psi_2\\rangle = \\frac{1}{\\sqrt{2^n}} \\biggl( \\sum_{f(x)=0}\\lvert x\\rangle - \\sum_{f(x)=1}\\lvert x\\rangle \\biggr) \\otimes \\frac{1}{\\sqrt{2}} (\\lvert 0\\rangle - \\lvert 1\\rangle)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the case \"1.$f(x)$ is same for all inputs\", each of terms for $f(x)=0$ or $f(x)=1$ vanish.  \n",
    "So,\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "\\lvert \\psi_2 \\rangle &= \\pm \\frac{1}{ \\sqrt{2^{n}} } \\sum^{2^n}_{x\\in \\{ 0, 1 \\}^n} \\lvert x\\rangle \\otimes \\frac{1}{\\sqrt{2}} (\\lvert 0\\rangle - \\lvert 1\\rangle) \\\\\n",
    "&= \\pm \\biggl( \\otimes^{n} H \\lvert 0\\rangle \\biggr) \\otimes H \\lvert 1\\rangle\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "As a consequence, $\\lvert \\psi_3 \\rangle$ is\n",
    "\n",
    "$$\n",
    "\\lvert \\psi_3 \\rangle = \\pm \\lvert 00...00 \\rangle \\otimes H\\lvert 1 \\rangle\n",
    "$$\n",
    "\n",
    "In this case, the measurmet results from the $0$ th to $n$ th qubits will all be \"0\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the case \"2.$f(x)$ is different in half of the inputs\", because the signs are different for $f(x)$,\n",
    "\n",
    "$$\n",
    "\\lvert \\psi_2 \\rangle = \\frac{1}{ \\sqrt{2^{n}} } \\sum^{2^n}_{x\\in \\{ 0, 1 \\}^n} (-1)^{f(x)} \\lvert x\\rangle \\otimes \\frac{1}{\\sqrt{2}} (\\lvert 0\\rangle - \\lvert 1\\rangle)\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "\\lvert \\psi_3 \\rangle &= \\frac{1}{ \\sqrt{2^{n}} } \\sum^{2^n}_{x\\in \\{ 0, 1 \\}^n} (-1)^{f(x)} (\\otimes^nH) \\lvert x\\rangle \\otimes \\frac{1}{\\sqrt{2}} (\\lvert 0\\rangle - \\lvert 1\\rangle) \\\\\n",
    "&= \\frac{1}{ 2^{n} } \\sum^{2^n}_{x\\in \\{ 0, 1 \\}^n} (-1)^{f(x)} \\bigl( \\sum^{2^n-1}_{y=0}(-1)^{x\\cdot y}\\lvert y \\rangle \\bigr) \\otimes \\frac{1}{\\sqrt{2}} (\\lvert 0\\rangle - \\lvert 1\\rangle)\n",
    "\\end{align}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, consider the probability $\\rm{Pr}(0)$ that all the measurements results from the $0$ th to the $n$ th qubits are \"0\".  \n",
    "It is squared absolute value of the amplitude of state $\\lvert y \\rangle\\ (y=0)$.  \n",
    "\n",
    "Because $x\\cdot y=0$ when $y=0$,\n",
    "\n",
    "$$\n",
    "\\mathrm{Pr}(0) = \\biggl| \\frac{1}{2^n} \\sum^{2^n}_{x\\in \\{ 0, 1 \\}^n} (-1)^{f(x)} \\biggr|^2\n",
    "$$\n",
    "\n",
    "If $f(x)$ is different in half of the inputs, all the terms cancel each other out, so $\\mathrm{Pr}(0) =0$.  \n",
    "Therefore, the result of measuring up to $n$ th qubits from the $0$ th will never be all \"0\".  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "From the above, we can determine the oracle by whether the results of measuring the qubits up to the ($n-1$) th bit are all $0$ or not."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's implement this in blueqat."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from blueqat import Circuit\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's implement oracle for case 1\\. and 2\\., respectively.\n",
    "\n",
    "In the case 1\\., we invert the $n$ th qubit regardless of the qubits up to the ($n-1$) th.\n",
    "\n",
    "In the case 2\\., we prepare $n$ $CX$ gates such that each qubit up to the ($n-1$) th qubit is a control bit and all target bits are the $n$ th qubit.    \n",
    "In this case, the $n$ th qubit is inverted for half of the possible values of the qubits up to the ($n-1$) th qubit, while remains unchanged for the other half."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def oracle_1(c):\n",
    "    n = c.n_qubits\n",
    "    c.x[n-1]\n",
    "    \n",
    "def oracle_2(c):\n",
    "    n = c.n_qubits\n",
    "    for i in range(n-1):\n",
    "        c.cx[i, n-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following is the main body of the algorithm.    \n",
    "まず、オラクルが 1\\. と2\\. のどちらであるかを乱数で決めます。これが求めたい正解となります。  \n",
    "First, set the oracles 1\\. or 2\\. by random number. This will be the correct answer we want to find.  \n",
    "\n",
    "Next, use the Deutsch-Jozsa algorithm to determine the oracle.  \n",
    "\n",
    "Finally, check if the result of the discrimination and the oracle selected by a random number in advance match."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Oracle: f(x) = 1 for all x.\n",
      "Results of quantum circuit: Counter({'00001': 1000})\n",
      "OK\n"
     ]
    }
   ],
   "source": [
    "n = 4\n",
    "\n",
    "c = Circuit(n + 1)\n",
    "c.x[n].h[:]\n",
    "\n",
    "if np.random.rand() > 0.5:\n",
    "    oracle_1(c)\n",
    "    oracle = \"f(x) = 1 for all x.\"\n",
    "else:\n",
    "    oracle_2(c)\n",
    "    oracle = \"f(x) = 0 for half x and f(x) = 1 for others.\"\n",
    "\n",
    "c.h[:]\n",
    "res = c.m[:].run(shots = 1000)\n",
    "\n",
    "print(\"Oracle:\", oracle)\n",
    "print(\"Results of quantum circuit:\", res)\n",
    "\n",
    "if [arr[:n] for arr in res.keys()] == ['0'*n] and oracle == \"f(x) = 1 for all x.\":\n",
    "    print(\"OK\")\n",
    "elif [arr[:n] for arr in res.keys()] != ['0'*n] and oracle == \"f(x) = 0 for half x and f(x) = 1 for others.\":\n",
    "    print(\"OK\")\n",
    "else:\n",
    "    print(\"incorrect\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we determined the oracle using the Deutsch-Jozsa algorithm."
   ]
  },
  {
   "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
}