{ "cells": [ { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "In this notebook, we implement the Deutsch-Jozsa algorithm using Qiskit. Recall that the algorithm is figuring out whether a given binary function\n", "$$\n", "f \\colon \\{0,1\\}^n \\rightarrow \\{0,1\\}\n", "$$\n", "is balanced or constant. So let us first choose a reasonably simple function f and implement the corresponding oracle. Basically the easiest choice is probably $n = 2$ and\n", "$$\n", "f(x_0, x_1) = x_0 \\oplus x_1\n", "$$\n", "What is the oracle $U_f$? The oracle is specified by\n", "$$\n", "U_f |x \\rangle |y \\rangle = |x \\rangle |y \\oplus f(x) \\rangle\n", "$$\n", "So the third qubit is inverted if f is equal to one and left unchanged otherwise. Using the definition of f, we see that the third qubit is inverted if the first two qubits are different and left unchanged if they are equal.\n", "This is easily implemented using two CNOT gates" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": true }, "outputs": [], "source": [ "from qiskit import QuantumRegister, QuantumCircuit, ClassicalRegister\n", "from qiskit.tools.visualization import matplotlib_circuit_drawer as drawer\n", "from qiskit.tools.visualization import plot_histogram\n", "from qiskit import Aer\n", "from qiskit import compile, execute\n", "from qiskit import IBMQ\n", "import numpy as np\n", "%matplotlib inline\n", "my_style = {'cregbundle': True}" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": true }, "outputs": [], "source": [ "#####################################\n", "# Create the oracle. We assume that #\n", "# our quantum register has three #\n", "# qubits. #\n", "#####################################\n", "def createOracleBalanced(q,c):\n", " circuit = QuantumCircuit(q,c)\n", " circuit.cx(q[0], q[2])\n", " circuit.cx(q[1], q[2])\n", " circuit.barrier(q)\n", " return circuit\n", "\n", "\n", "\n", "#####################################\n", "# Create a constant oracle #\n", "#####################################\n", "def createOracleConstant(q,c):\n", " circuit = QuantumCircuit(q,c)\n", " circuit.x(q[2])\n", " circuit.barrier(q)\n", " return circuit" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAPEAAADRCAYAAAAdZ1Q/AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAFmBJREFUeJzt3X9M1Pf9B/DnB2qHU47jh4iF3llp\n3Te6r/Y8+ZKmDrq2KP2Knkq1zaIdscZETTYjo5C52c5fObTrQrJuGbUFW6FfyVwHRoPWlpEV9VqL\nYG2TricKtboCRrgTrD/uXt8/nJeigCCf43NveT6SS7z3vX2/nyhPPp/73AGaiAiISFlhRgcgoqFh\niYkUxxITKY4lJlIcS0ykOJaYSHEsMZHiWGIixbHERIpjiYkUxxITKY4lJlIcS0ykOJaYSHEsMZHi\nWGIixbHERIpjiYkUxxITKY4lJlIcS0ykOJaYSHEsMZHiWGIixbHERIpjiYkUxxITKY4lJlIcS0yk\nOJaYSHEsMZHiWGIixbHERIpjiYkUxxITKY4lJlLciCpxaWkpnnjiiQHPt9vtOHDgQPACKaqrqwvv\nvvsuXnvtNezcuRMdHR1GRxrRRlSJb+Xz+ZCXl4dx48YhMjIS2dnZaG9vDzzucDhQVVVlYMLQIiLY\ntm0bJkyYgJ/97GfIzc1FTk4OEhISUFBQAJ/PZ3TEEWlEl9jpdKKyshIulwtnz54FACxbtizwOEvc\n08aNG5Gfnw+v19tj/MqVKygsLMSqVasMSjbCSQjYvXu3JCcny5gxYyQjI0PWrVsnzz77rO77lJSU\nSHp6euC+xWKRHTt2BO673W4BIGfOnAmMWa1WOXbsmO5ZVHPu3DkJDw8XAP3eGhoajI464hh+JN65\ncydyc3NRVlYGr9eLrKwsFBUVwWazDWodp9OJadOmDXh+R0cHWlpaYLfbA2PJyckwmUxobGwMjDkc\nDlRWVg4qy72otLT0jqfLmqbhjTfeGKZEdJOhJe7u7sa6detQXFyM1NRUaJqGFStWwOfzBUq8a9cu\nPPbYY3jsscdQU1PT51oFBQU4ceLEgPe+eUoYFRXVY9xsNsPj8QTuz507F/v27RvMh3VPcrvdCA8P\nv+O8U6dODUMa+r77jNy8trYWfr8fzzzzTGCsra0NAGCz2dDR0YFXX30VR48exaVLl/D000+jvr4e\nYWFD/9oTGRkJAOjs7Owx3tHRAZPJFLjf3NwMi8Uy5P3uRNO0oO8RbCKC6urqe+JjCTUi0udjhh6J\nW1tbER8f32OsvLwc48ePR0JCAlwuF9LT0xEREYG4uDg88MADOHPmjC57m81mWCwW1NfXB8aamprg\n8Xh6nJZXVVXB4XDosmd/RCSkb4cOHRrQx/H2228bnvVevPXH0BJPmTIFbrcbtbW1uHr1KsrLy+F0\nOgOn0hcuXEB0dHRgfnR0NC5cuKDb/itXrkRhYSFOnz4Nj8eD/Px8zJkzBxMnTgRw4/XQmpoaZGVl\n6banqp588klMmzatz7Og8PBwPPDAA1i8ePEwJyNDS5ySkoL169dj0aJFSEpKgsvlQmpqaqDEsbGx\nuHjxYmB+R0cHYmNje11r69atmDp16qD2LygowLx585CSkoLExET4fD7s2rUr8PjBgwdhs9kQFxd3\nFx/dvUXTNOzduzfwBe7WMsfGxuLAgQOIiIgwIN0IJyHGarVKRUWFiIhcvHhRbDabfPfdd3LhwgWZ\nPn26+Hy+u1771peY7iQnJ0e2b99+1/vdizwej/zxj3+UGTNmSEJCggCQwsJCaW9vNzraiGXoha1b\neTweNDc3B47EZrMZa9euDbxV8ve//70uF7UGymq18vTwFpGRkVizZg3WrFkD4MYR+qWXXjI41cim\nidzhWfMwOnz4MDIzM9HZ2RmUK5wNDQ1oaGhATk6O7muPVJqm3fHCCwVXSJWY1MMSG8/wd2wR0dCw\nxESKY4mJFMcSEymOJSZSHEtMpDiWmEhxLDGR4lhiIsWxxESKY4mJFMcSEymOJSZSHEtMpDiWmEhx\nLDGR4lhiIsWxxESKY4mJFMcSEymOJSZSHEtMpDiWmEhxLDGR4lhiIsWxxESKY4mJFMcSEymOJSZS\nHEtMpDiWmEhxLDGNKCJyz/0+5RFV4tLSUjzxxBMDnm+323HgwIHgBaJhISKoqKhAWloaRo0ahVGj\nRmHWrFnYvXv3PVHoEVXiW/l8PuTl5WHcuHGIjIxEdnY22tvbA487HA5UVVUZmJCGyu/348UXX8Rz\nzz2Huro6+Hw++Hw+HDlyBM8//zyWL18Ov99vdMwhGdEldjqdqKyshMvlwtmzZwEAy5YtCzzOEqvv\nz3/+M0pKSgCgR1lv/rm0tBSvv/66Idl0IyFg9+7dkpycLGPGjJGMjAxZt26dPPvss7rvU1JSIunp\n6YH7FotFduzYEbjvdrsFgJw5cyYwZrVa5dixY7pnuVeEyKdQr3w+nyQnJ4umaQKg15umaTJp0iTx\n+XxGx71rhh+Jd+7cidzcXJSVlcHr9SIrKwtFRUWw2WyDWsfpdGLatGkDnt/R0YGWlhbY7fbAWHJy\nMkwmExobGwNjDocDlZWVg8pCoeH06dM4depUv897RQRNTU1oamoaxmQ6M/IrSFdXl8TExMj+/ft7\njAEIjD311FMSFxcnmzZtGvJ+3z8St7S0CABpamrqMcdiscg777wTuH/gwAGZMWPGkPe+E/RxpOCN\nN6D/mt4HA9XW1sLv9+OZZ54JjLW1tQFA4EhcWlqKQ4cOBZ6z6iUyMhIA0NnZ2WO8o6MDJpMpcL+5\nuRkWi0XXvXsjil4l1TQtZLN3dXUhPj4e3d3d/c774Q9/iG+//RZjx44dpmT6MvR0urW1FfHx8T3G\nysvLMX78eCQkJAAAkpKSgrK32WyGxWJBfX19YKypqQkej6fHaXlVVRUcDkdQMlBwjRkzBjk5OdA0\nrc85YWFh+PnPf65sgQGDSzxlyhS43W7U1tbi6tWrKC8vh9PpHPTz4bu1cuVKFBYW4vTp0/B4PMjP\nz8ecOXMwceJEADe+ktfU1CArK2tY8pD+NmzYAIvFgrCw2z/Vw8LCkJSUhA0bNhiQTD+GljglJQXr\n16/HokWLkJSUBJfLhdTU1Lsq8datWzF16tRB/Z2CggLMmzcPKSkpSExMhM/nw65duwKPHzx4EDab\nDXFxcYPOQ6Fh/PjxOHz4MObPn9+jyGFhYZg/fz6OHDkSOOtTVtCv2AyS1WqVioqKHmMlJSW6X9ga\niJycHNm+ffuQ972XheCnUJ9aWlpkz549AkBaWlqMjqMbQy9s3crj8aC5ubnHkXj58uVwuVy4cuUK\nXC4X9u7dO2x5rFYrFi9ePGz7UXA9+OCDePDBBwN/vldoIqFzafHw4cPIzMxEZ2dnvxcj7lZDQwMa\nGhqQk5Oj+9ojVShfne6Lipn7E1IlJvWoWAgVM/fH8HdsEdHQsMREimOJiRTHEhMpjiUmUhxLTKQ4\nlphIcSwxkeJYYiLFscREimOJiRTHEhMpjiUmUhxLTKQ4lphIcSwxkeJYYiLFscREimOJiRTHEhMp\njiUmUhxLTKQ4lphIcSwxkeJYYiLFhdTvYqLQ5/F4cPz4cZw8eRJdXV0AgEOHDmHGjBmIiYkxOF3v\n/H4//vWvf6G+vh7nzp0DAJSVlcFut2Py5Mm9/tpTpRj3u9xIJf/4xz8kOztbwsPDBcBtN03TJDMz\nU/bu3St+v9/ouCIi0tbWJps2bZKkpKReMwOQpKQk2bRpk7S1tRkd966xxNSvCxcuyNKlSwWAxMTE\nyLp162Tfvn3yzTffyKVLlwSAHDx4UNavXy8TJkwQADJ37lz55ptvDM1dUVEhcXFxAkCefvpp2bFj\nhzQ2NkpnZ6cAkMbGRnnzzTclIyNDAEhcXJzs3r3b0Mx3iyWmPjU1NcmkSZPkvvvukw0bNkh3d/dt\nc75/Mnf16lX5wx/+IKNHj5b4+HhpaGgYzrgiIuL3++Wll14SADJz5kxpbGy8bc6tJ6AnTpyQlJQU\nASC/+tWvQuZMYqBYYupVW1ubPPTQQxIdHS2HDx/uc15vz8i++OILSUpKkri4ODl16lQwY97md7/7\nnQCQVatWybVr13qd01vma9euyerVqwWAvPLKK8GOqSuWmHq1ZMkSGTVqlBw9erTfeX1dVvnyyy8l\nKipK0tLSxOfzBSPibY4cOSJhYWGydOnSfo+mfWX2+/3ywgsviKZp/X7hCjUjqsQlJSWSnp4+4Pkz\nZsyQ6urq4AUKUdXV1QJANm/efMe5/V0bfeuttwSAvPnmm3rG65Xf75cf//jHYrFYpLOzs9+5/WXu\n7OwUi8UiU6dOVea0WvFr60Pj8/mQl5eHcePGITIyEtnZ2Whvbw887nA4UFVVZWBCYxQVFWHChAnI\ny8sb0jo5OTmYPn06ioqKgv5LvWtqanDy5Els2rQJJpPprtcxmUzYvHkzPv/8c3z44Yc6JgyeEV1i\np9OJyspKuFwunD17FgCwbNmywOMjscT//ve/UV1djRUrVuD+++8f0lqapmHVqlU4ceIEGhoadErY\nu9LSUsTExGDJkiVDXmvx4sWIjY1FSUmJDsmCLyRKXFFRgYcffhhjx47F7NmzkZubi8WLFwd93+Li\nYuTn52PSpEmIiorCtm3bUF1djebmZgDA9OnTER4ejk8//TToWULFJ598AhHB7NmzdVnv5joff/yx\nLuv15ejRo0hLS0NERMSQ14qIiEBaWhpcLpcOyYLP8BLv3LkTubm5KCsrg9frRVZWFoqKimCz2Qa1\njtPpxLRp0wY8v6OjAy0tLbDb7YGx5ORkmEwmNDY2BsYcDgcqKysHlUVlJ06cAAA8+uijuqw3ceJE\nmM3mHv+mert8+TK++uqrQX/O9GfGjBlwu92Bd6WFMkNL3N3djXXr1qG4uBipqanQNA0rVqyAz+eD\nzWbDqVOnkJaWhp/85CeYNWsWjh071udaBQUFgU/AgfB6vQCAqKioHuNmsxkejydwf+7cudi3b98g\nPzJ1eb1ejBo1CmPHjtVlPU3TEB0dHfj3DoabRYuOjtZtzZtrqVBiQ69O79+/X8xmc4+xM2fOCAA5\nf/68tLe3S3t7u4iIfP755zJr1qwh7ff9q9MXL14UAHL8+PEec0wmk1RWVgbuFxcXy4IFC4a070Cg\nj7cF8sYb0H9NDT0St7a2Ij4+vsdYeXk5xo8fj4SEBMTGxiI2NhYA8IMf/ADh4eG67W02m2GxWFBf\nXx8Ya2pqgsfj6XFaXlVVBYfDodu+fZEbL/cZfisrKwMANDQ0DGj+nbK3tbUBALZv3x7U3BMmTMCy\nZct0ySwieOGFF5CQkAC/32/4/8nNzH0xtMRTpkyB2+1GbW0trl69ivLycjidztue2/h8PvziF79A\nQUGBrvuvXLkShYWFOH36NDweD/Lz8zFnzhxMnDgRwI1TqZqaGmRlZem6byibOXMmAOCf//ynLut9\n9NFHANDj2kMwzJw5Ex999JEuL2WJCOrq6mC326Fpmg7pgsvQEqekpGD9+vVYtGgRkpKS4HK5kJqa\n2qPEIoLly5cjKysLmZmZfa61detWTJ06dVD7FxQUYN68eUhJSUFiYiJ8Ph927doVePzgwYOw2WyI\ni4sb/AenqEceeQTTp0/HG2+8oUshiouLMWHCBMyaNUuHdH1bsmQJTp8+rctruzU1NTh16hSee+45\nHZINAwkxVqtVKioqAvfXrFkjGzdu1GXtwb5jKycnR7Zv367L3ir5y1/+IgBkz549d5zb36dQXV2d\naJomL7/8so7penf58mUZN26cPP7443d8m2d/mX0+n8yaNUtiY2Pl8uXLescMipAq8c1vE/vqq69E\nRKSmpkZGjRol6enpkp6eLgsXLhzS+oMt8csvvyxnzpwZ0p4qunr1qthsNomPj5dvv/2237l9FcLr\n9crkyZPFarWKx+MJRszblJaWCgB59dVX+53XX4lfe+01ASAlJSU6pwuekCpxXV2dREZGBu09q8eP\nH1fqP8dIjY2NMnr0aHn00Uf7/Yb53grh9XrlySeflPDwcPnggw+CGbMHv98vCxYskLCwMCkrK+tz\nXl8lfvfddyUsLEzmz5+vzPumRUKsxBRaqqurJSIiQiwWi7z//vu9zrm1EB9//LFMmTJFwsLC5J13\n3hmOmD1cunRJ0tPTRdM0+eUvfyldXV23zbk1c1dXl6xdu1Y0TZO0tDS5dOnScMXVBUtM/XK5XDJ5\n8mQBIJmZmVJZWdnj9BiAdHV1yfvvvy/Z2dkSFhYmiYmJcuDAAcMyd3d3y5o1awSAJCYmysaNG8Xt\ndgeOrgDE7/eL2+2WzZs3B358z+rVq3stfahjiemOuru7ZePGjYEfv6Npmjz88MNit9sFQODnbsXE\nxEheXp5cvHjR6MgicuPngt388TsAJDo6Wmw2W+DPN8czMjKkpqbG6Lh3TRPR4XUEGhGuXbuGDz74\nAJ988gk+++wzdHV1Yf/+/fjtb3+LmTNnIiMjA6NHjzY65m3cbjc+/PBDfPrppzh//jz27t2LlStX\nwm6346c//SkeeeQRoyMOCUtMpDjDv4uJiIaGJSZSHEtMpDiWmEhxLDGR4lhiIsWxxESKY4mJFMcS\nEymOJSZSHEtMpDiWmEhxLDGR4lhiIsWxxESKY4mJFMcSEymOJSZSHEtMpLj7jA5Aw2f27NlobW2F\nz+fDj370I7z11lswmUxGx6Ih4g/KG0E6OzsDv1R97dq1MJvNeOWVV4wNRUPG0+kR5GaB/X4/vvvu\nOyV+bSfdGUs8wixcuBDx8fH48ssvkZuba3Qc0gFLPMK89957OHfuHJKSkvDXv/7V6DikA5Z4BLr/\n/vvx/PPP47333jM6CumAJR4hvF4vzp8/D+DGc+KqqipMnTrV4FSkB77ENEJ4vV44HA5cuXIFfr8f\nqamp+M1vfmN0LNIBX2IitJxrRWy0CWNGRxgdhe4CT6f/w+fzIS8vD+PGjUNkZCSys7PR3t5udKyg\nu37dh7K/v4//q/rA6Ch0l1ji/3A6naisrITL5cLZs2cBAMuWLTM4VfAd++xLdHq7kPY/042OQndJ\nuRLX1dXhqaeegslkgtlsxuLFi3VZt7i4GPn5+Zg0aRKioqKwbds2VFdXo7m5WZf1Q9H16z7UHDkO\na+J4PDwx0eg4dJeUKvGePXuwcOFCrF69Gq2trfj666+xYsWKXuc6nU5MmzZtQOt2dHSgpaUFdrs9\nMJacnAyTyYTGxkZdsoeim0fhpx+3891bClPmwlZXVxesVit27NiBBQsW6Lr2119/DYvFgqamJjz0\n0EOBcavVii1btmDp0qW67tebgsLioO9B6nLmr+zzMWVeYqqtrYWmaXA4HLqvHRkZCeDGNwh8X0dH\nx7B9l09//0nBcPT4F/j7wY/w4pL/xSMPJQ3r3qQvZU6n29vbER0dHZTTPrPZDIvFgvr6+sBYU1MT\nPB7PgE/JVcLnwvcWZU6nT548CZvNhr/97W+YO3cuPB4PXC4X5syZo8v6W7Zswdtvv43q6mrExsbi\nxRdfhNfrRXV1tS7r3wlPp6k//Z6piUJKS0tl8uTJMmbMGElISJBf//rXfc7dsmWLTJkyZcBrX79+\nXXJzcyU2NlbGjh0rCxculLa2Nj1ih5Rr167L1td3yZ/e+bv4/X6j45AOlDkSkz74XPjeo8yFLdLH\nf//XJIgInwvfQ3gkJlKcMleniah3LDGR4lhiIsWxxESKY4mJFMcSEymOJSZSHEtMpDiWmEhxLDGR\n4lhiIsWxxESKY4mJFMcSEymOJSZSHEtMpDiWmEhxLDGR4lhiIsWxxESKY4mJFMcSEymOJSZS3P8D\nqukNVbKk3KEAAAAASUVORK5CYII=\n", "text/plain": [ "