Notebooks/Deutsch-Jozsa_algorithm.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Deutsch-Jozsa algorithm\n",
    "\n",
    "The [Deutsch-Jozsa algorithm](https://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm) is the classical demonstration of the quantum parallelism: the application of a function to all the quantum states in a single step. \n",
    "\n",
    "The main idea is to find if a binary function:\n",
    "$$f:Z_{2^n} \\to Z_2$$\n",
    "that is known to be *constant* (for every x the result is equal, or 0 or 1) or *balanced* (produces the same number of 0s and 1s), is constant or balanced.\n",
    "\n",
    "To compute it, the value of the function is encoded in the phase of one state as:\n",
    "$$U_f(|x>) = (-1)^{f(x)} |x>$$\n",
    "\n",
    "Where $$U_f$$ is named as *oracle*. Here, you will use a simple case:\n",
    "$$f(x) = x\\%2 $$\n",
    "\n",
    "so, using the integer or binary representation of one n-qubit state\n",
    "\n",
    "$$U_f(|00...00\\rangle)=(-1)^{f(0)}|0\\rangle= +|0\\rangle$$\n",
    "$$U_f(|00...01\\rangle)=(-1)^{f(1)}|1\\rangle=-|1\\rangle$$\n",
    "$$U_f(|00...10\\rangle)=(-1)^{f(2)}|2\\rangle= +|2\\rangle$$\n",
    "$$U_f(|00...11\\rangle)=(-1)^{f(3)}|3\\rangle=-|3\\rangle$$\n",
    "$$etc.$$\n",
    "\n",
    "The algorithm has four steps:\n",
    "\n",
    "1. Starting from a $|0\\rangle$ state of *n* qubits, apply a Walsh-Hadamard transformation to create the state $|\\Phi\\rangle=\\frac{1}{\\sqrt(2^n)}\\sum_{i=0}^{2^n-1}|i\\rangle$\n",
    "2. Apply the desired oracle.\n",
    "3. Uncompute operation 1\n",
    "4. Measure all qubits and compare with state |0>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import projectq\n",
    "from projectq.cengines import MainEngine\n",
    "from projectq.ops import H, Z, X, Measure, All"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Start the Engine and allocate an even number of qubits (by default, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "eng=MainEngine()\n",
    "qreg=eng.allocate_qureg(4)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Create a superposition of all the posible states with the number of allocated qubits, applying a Walsh-Hadamard operator. The cheat() method will print the amplitudes for all the states: |0000>,|0001>,etc."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "({0: 0, 1: 1, 2: 2, 3: 3},\n",
       " [(0.24999999999999992+0j),\n",
       "  (0.24999999999999992+0j),\n",
       "  (0.24999999999999992+0j),\n",
       "  (0.24999999999999992+0j),\n",
       "  (0.24999999999999992+0j),\n",
       "  (0.24999999999999992+0j),\n",
       "  (0.24999999999999992+0j),\n",
       "  (0.24999999999999992+0j),\n",
       "  (0.24999999999999992+0j),\n",
       "  (0.24999999999999992+0j),\n",
       "  (0.24999999999999992+0j),\n",
       "  (0.24999999999999992+0j),\n",
       "  (0.24999999999999992+0j),\n",
       "  (0.24999999999999992+0j),\n",
       "  (0.24999999999999992+0j),\n",
       "  (0.24999999999999992+0j)])"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "All(H)|qreg\n",
    "eng.flush()\n",
    "eng.backend.cheat()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To create the Oracle for the function, it is enought to compute Z applied to first qubit (qubit 0 in your quantum register), this means, for *n* qubits:\n",
    "\n",
    "$$ I^{\\otimes n-1}\\otimes Z $$\n",
    "\n",
    "For 2 qubits this operator, in matrix form, looks as:\n",
    "\n",
    "$$ I \\otimes Z = \\begin{bmatrix}1&0\\\\0&1\\end{bmatrix}\\otimes\\begin{bmatrix}1&0\\\\0&-1\\end{bmatrix}=\n",
    "\\begin{bmatrix}1&0&0&0\\\\0&-1&0&0\\\\0&0&1&0\\\\0&0&0&-1\\end{bmatrix}$$\n",
    "\n",
    "Applying it to the generated state: \n",
    "$$|\\Phi\\rangle = \\frac{1}{2}\\begin{bmatrix}1\\\\1\\\\1\\\\1\\\\\\end{bmatrix}=\\frac{1}{2}(|0\\rangle+|1\\rangle+|2\\rangle+|3\\rangle)$$\n",
    "\n",
    "yields:\n",
    "\n",
    "$$|\\phi\\rangle = \\frac{1}{2}\\begin{bmatrix}1\\\\-1\\\\1\\\\-1\\\\\\end{bmatrix}$$\n",
    "\n",
    "or, using the integer representation:\n",
    "\n",
    "$$|\\phi\\rangle = \\frac{1}{2}(|0\\rangle-|1\\rangle+|2\\rangle-|3\\rangle)$$\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "({0: 0, 1: 1, 2: 2, 3: 3},\n",
       " [(0.24999999999999992+0j),\n",
       "  (-0.24999999999999992+0j),\n",
       "  (0.24999999999999992+0j),\n",
       "  (-0.24999999999999992+0j),\n",
       "  (0.24999999999999992+0j),\n",
       "  (-0.24999999999999992+0j),\n",
       "  (0.24999999999999992+0j),\n",
       "  (-0.24999999999999992+0j),\n",
       "  (0.24999999999999992+0j),\n",
       "  (-0.24999999999999992+0j),\n",
       "  (0.24999999999999992+0j),\n",
       "  (-0.24999999999999992+0j),\n",
       "  (0.24999999999999992+0j),\n",
       "  (-0.24999999999999992+0j),\n",
       "  (0.24999999999999992+0j),\n",
       "  (-0.24999999999999992+0j)])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Z|qreg[0]\n",
    "#\n",
    "#Other oracles you can check\n",
    "#\n",
    "#X|qreg[0] #Constant\n",
    "#All(X)|qreg #Constant\n",
    "#All(Z)|qreg #balanced\n",
    "eng.flush()\n",
    "eng.backend.cheat()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Uncompute the superposition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "({0: 0, 1: 1, 2: 2, 3: 3},\n",
       " [0j,\n",
       "  (0.9999999999999993+0j),\n",
       "  0j,\n",
       "  0j,\n",
       "  0j,\n",
       "  0j,\n",
       "  0j,\n",
       "  0j,\n",
       "  0j,\n",
       "  0j,\n",
       "  0j,\n",
       "  0j,\n",
       "  0j,\n",
       "  0j,\n",
       "  0j,\n",
       "  0j])"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "All(H)|qreg\n",
    "eng.flush()\n",
    "eng.backend.cheat()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Measure the results. If it is **constant**, the result must be |0000>=|0>. If it is **balanced**, the result is different of |0>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "All(Measure) | qreg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The result is balanced\n"
     ]
    }
   ],
   "source": [
    "eng.flush()\n",
    "output=0\n",
    "for i in qreg:\n",
    "    output+=int(i)\n",
    "print(\"The result is %s\"%(\"balanced\" if output else \"constant\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you want to check that the result is 0 if is constant, substitute the gate Z in the oracle by X.\n",
    "If you want to test with another balanced function, substitute Z by All(Z), but substitute also qreg[0] by qreg"
   ]
  }
 ],
 "metadata": {
  "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.5.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}