Grover-Search-Plot.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Grover's Search Algorithm\n",
    "\n",
    "We want to find a specific item in an unsorted list of $m = 2^n$ items.\n",
    "\n",
    "Define $f(x) = 1$ `if` $x = x_0$ `else` 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import matplotlib\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "%config InlineBackend.figure_formats = {'png', 'retina'}\n",
    "\n",
    "from quantum import *\n",
    "from math import log, ceil, floor\n",
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "target: 220 (bin = 11011100)\n",
      "qubits needed: 8\n",
      "search space: 256\n",
      "optimal iterations: 12.566370614359172\n",
      "\n",
      "performed 12 iterations\n",
      "measured 220\n",
      "probability of measuring target is 99.99470%\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAuoAAAH/CAYAAAABlPgTAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAAWJQAAFiUBSVIk8AAAIABJREFUeJzs3XeUVtXBtvFr0wRBxAKWYFAsxG6UBBUbKogFFRU7IJoo\nUaNYYn1VRP3Ehr0roFgQFbGLoEQwxJ7EWLAiVqxIkBJgZn9/7JmAyFDmmZnzlOu31qwz55yZw816\n8vrebvfZO8QYkSRJkpRf6mUdQJIkSdIvWdQlSZKkPGRRlyRJkvKQRV2SJEnKQxZ1SZIkKQ9Z1CVJ\nkqQ8ZFGXJEmS8pBFXZIkScpDFnVJkiQpD1nUJUmSpDxkUZckSZLykEVdkiRJykMWdUmSJCkPWdQl\nSZKkPJRTUQ8hHBRCuD6EMCGE8J8QQnkIYVg1n9U6hDA4hPBlCGFOCGFyCOHqEEKLXDJKkiRJhahB\njr//f8AWwAzgc+A3QFzeh4QQ1gcmAi2BUcAkoANwMtA1hNAxxvhDjlklSZKkgpHr1Jd+wIYxxpWB\nP+XwnJtIJf3PMcYDYoznxBh3A64G2gGX5JhTkiRJKighxuUeAF/8g0LYBXgeuCfG2Gs5fm994ANg\ncoxx/UXuNQOmkkbp14gxzqqRsJIkSVKey4eXSTtVHJ9d9EaM8Sfgb0BTYNu6DCVJkiRlKR+KeruK\n4/tV3P+g4rhhHWSRJEmS8kI+FPWVK47Tq7hfed3VXyRJklQycl31Ja+EEGpmwr0kSZK0FDHGUJvP\nz4cR9coR85WruF95/cc6yCJJkiTlhXwYUZ9UcWxXxf3KuelVzWH/hZpayUZ1K4TgZ1fA/PwKl59d\nYfPzK2x+fnXnP/+Bjz6CDz9ccKz8/vPPq/69EKB1a9hgA1h//XQ866xaHUj/n3wo6uMqjp1DCCEu\n9L/WEMJKQEdgJvBSFuEkSZKU/2KE7777ZQmvPH77bdW/26ABrLvuz8t45ffrrQeNG//85886q1b/\nKgty1c0fAyGEBsAGwNwY48eV12OMH4cQngW6ACcANyz0axcCKwK3xBhn11VWSZIk5Z/ycvjyy1+W\n8Mrjf/5T9e82aQJt2/68hFcef/3rVNbzTU4bHoUQ9gf2rzhdk1S2PwZerLj2bYzxLxU/u27FvSkx\nxvUWeU5bYCLQCniUNB2mA7AL8B6wfYxx2jLkieDUl0Llf/4rbH5+hcvPrrD5+RU2P79fmj8fpkxZ\nfBn/+GOYM6fq323efEERX7SMr7UW1KuhtzNDSFNfavtl0lz/3WFLoBdp51AqjusBbSvOPwH+ssjv\n/OJ/jRWj6u2BAUBXYC/gS+Aa4MIYY1VLN0qSJKnAzJmTSvfiyviUKamsV6VVq19OT6k8rrZamlNe\nLHIaUc83jqgXNkcVCpufX+Hysytsfn6FrZg/v8W9vFl5XN6XNxc+rrRS3f0dqs5YGCPqkiRJEgAz\nZsCDD8KQIfDii1X/3OJe3qw8Lu7lzVJlUVfeuOCCC7KOoBz4+RUuP7vC5udX2Irh84sRxo9P5fzB\nB2HWrHS9USPYcMPFl/F8fXkz3zj1RZIkScvt00/hrrtg6NA037zSjjtCnz7Qowc0a5ZZvFrl1BdJ\nkiTlldmz4ZFH0uj5c8+l0XRIc8p794ajjkoj5qoZFnVJkiRVKUZ49VUYPBiGD4fpFWvxrbAC7L8/\nHH007LYb1K+fbc5iZFGXJEnSL0ydCvfck0bP33lnwfX27dPUlsMOg1VWyS5fKbCoS5IkCYC5c+HJ\nJ1M5f+opKCtL11u2hJ49U0HfbLNsM5YSi7okSVKJ+/e/09SWe+6B775L1+rXh333TeV8772hYcNs\nM5Yii7okSVIJ+uEHuP/+NHr++usLrm+6aSrnRx4Ja6yRXT5Z1CVJkkpGWRmMGZPK+ahRaaoLQIsW\nac55nz5pDnqo1UUHtaws6pIkSUXugw9SOb/7bvjii3QtBOjSJZXz/fd3N9B8ZFGXJEkqQjNmpJ1C\nBw+Gv/1twfX110/rnffqlXYIVf6yqEuSJBWJGGH8+DR6/uCDMGtWut60adoptE+ftHOoU1sKg0Vd\nkiSpwH36Kdx1FwwdCh9/vOD6jjumct6jBzRrllk8VZNFXZIkqQDNng2PPJJGz597Lo2mA7RuDb17\np+ktG2yQaUTlyKIuSZJUIGKEV19N886HD4fp09P1FVZIL4QefTTstltaA12Fz6IuSZKU56ZOTZsR\nDRkC77yz4Hr79mlqy2GHwSqrZJdPtcOiLkmSlIfmzoUnn0zl/Kmn0hroAC1bQs+eqaBvtlm2GVW7\nLOqSJEl55M03Uzm/5x747rt0rUED2G+/VM732gsaNsw2o+qGRV2SJCljP/wA99+fCvrrry+4vumm\nad75EUfAGmtkl0/ZsKhLkiRloKwMxoxJ5XzUqDTVBaBFizTnvE+fNAfdNc9Ll0VdkiSpDpWXp/XO\nL7gAPv88XQsBunRJ5Xz//aFx40wjKk9Y1CVJkurIa6/BiSfCyy+n8/XXT+W8Vy9YZ51ssyn/WNQl\nSZJq2fffwznnwO23p7XQ11oLrrwyTXFxaouqUi/rAJIkScWqrAxuuQU22ghuuy1tRHTaaTBpEhx+\nuCVdS+aIuiRJUi146aU0zaVyFZddd4Xrr4dNNsk2lwqHI+qSJEk16Jtv0pKK222XSnrr1jBiBIwd\na0nX8rGoS5Ik1YD58+GGG6Bdu7TkYsOGcPbZ8O670KOH01y0/Jz6IkmSlKMXX4QTTki7igLssQdc\nd12amy5VlyPqkiRJ1fTVV9CzJ+y4YyrpbdrAI4/A009b0pU7i7okSdJymjcPBg1K01zuuQdWWAHO\nPx/eeSdtWOQ0F9UEp75IkiQth3Hj4M9/hrffTufdusHVV6fNi6Sa5Ii6JEnSMvj8czj00LTM4ttv\nQ9u28MQT8NhjlnTVDou6JEnSEsydC5ddBr/5DTzwADRpAhddlMr63ntnnU7FzKkvkiRJVXj22TTN\n5f330/kBB6S56W3aZJtLpcGiLkmStIgpU+DUU2HkyHS+0UZpV9EuXbLNpdLi1BdJkqQKc+bAxRfD\nxhunkt60KQwcCP/+tyVddc8RdUmSJODJJ+Hkk+Gjj9L5IYfAlVdC69bZ5lLpsqhLkqSS9vHH0K8f\nPP54Ot9kkzTNZddds80lOfVFkiSVpNmz4YILUjF//HFYaSW46ir45z8t6coPjqhLkqSSEiM8+iic\ncgp88km6duSRcPnlsNZamUaTfsaiLkmSSsYHH8BJJ8Ezz6TzLbaAG26AHXfMNpe0OE59kSRJRW/m\nTDjnHNhss1TSV14ZrrsOXn/dkq785Yi6JEkqWjHCQw+lNdE//zxd69MnLbnYqlW22aSlsahLkqSi\n9O67aVfR555L51tvDTfeCNtum20uaVk59UWSJBWVGTPgL39J88+few5WWQVuvhleecWSrsLiiLok\nSSoKMcL998Ppp8NXX0EIcOyxcMklsPrqWaeTlp9FXZIkFbx//xtOPBHGj0/nHTqk1Vzat882l5QL\np75IkqSCNX162lX0t79NJX311eHOO2HiREu6Cp8j6pIkqeCUl8OwYXDGGfDNN1CvXhpRHzAgzUmX\nioFFXZIkFZR//COV8okT03nHjmmay1ZbZZtLqmlOfZEkSQXhhx/ghBPSlJaJE2GNNeDuu2HCBEu6\nipNFXZIk5bXycrjjDmjXDm66Ka3m0q8fvPce9OyZzqVi5NQXSZKUt159NY2iv/pqOt955zTNZbPN\nss0l1QVH1CVJUt756Sc47ri0zOKrr8Laa6c10seNs6SrdDiiLkmS8sqkSXDggfDOO9CgAZx6Kvzf\n/8FKK2WdTKpbFnVJkpQ3HnoI+vRJI+obbwwPPgibbpp1KikbTn2RJEmZmzcPTj8devRIJf2QQ+CV\nVyzpKm2OqEuSpEx99VUq5hMmpKkuV14JJ53kai6SRV2SJGVmwgQ4+GCYOjW9MDpiRNrASJJTXyRJ\nUgZihEGDoFOnVNJ32QXeeMOSLi3Moi5JkurUjBlpFP2006CsDM44A8aMSTuNSlrAqS+SJKnOvPMO\nHHBA2lV0pZXgrruge/esU0n5yRF1SZJUJ+6/H37/+1TSN9sMXnvNki4tiUVdkiTVqrlz0youhx8O\nM2fCkUfCSy/BRhtlnUzKb059kSRJtebzz9N89L//HRo2hGuvhb59XXpRWhYWdUmSVCuefx4OPRS+\n/RZat067jnbokHUqqXA49UWSJNWoGOGyy6Bz51TSd989Lb1oSZeWj0VdkiTVmOnT0wuiZ50F5eVw\n7rnwzDPQsmXWyaTC49QXSZJUI958Ew48ED78EFq0gGHDYJ99sk4lFS5H1CVJUs6GDYNtt00lfaut\n4PXXLelSrizqkiSp2v77X/jTn6BXL5g9G/r0gYkToW3brJNJhc+pL5IkqVo+/RR69IBXXoFGjeCG\nG+APf3DpRammWNQlSdJye/bZtIHR999DmzZp6cX27bNOJRUXp75IkqRlVl4OF18MXbumkt61a5qP\nbkmXal6NFPUQQusQwuAQwpchhDkhhMkhhKtDCC2W4xkhhHBICGFcCOGLEMKsEMJHIYQRIYRtayKn\nJEmqvmnTYN994bzz0nn//vDkk7DaapnGkopWiDHm9oAQ1gcmAi2BUcAkoAPQCXgP6Bhj/GEZnnMH\ncDTwXcVzvgM2BPYlTdHpFWO8dynPiAC5/p0kSdLPvfFGWnrxk09g1VXh3nvTaLpUikLFixgxxlp9\nI6MmivpooDPw5xjjjQtdvwo4Bbg1xvinpTyjDTAZmApsEWP8bqF7uwDPA5NjjOsv5TkWdUmSatid\nd8IJJ6QVXrbZJs1HX3fdrFNJ2SmIol4xmv4BiynRIYRmpOIdgTVijLOW8Jz2wCvAozHG7ou5/x8g\nxhhXXkoei7okSTVkzhw48cRU1AGOPRauvRYaN842l5S1uirquc5R71RxfHbRGzHGn4C/AU2Bpc0x\nf4tU6juEEH420y2EsBPQDBibY1ZJkrSMJk+Gjh1TSW/cGIYMgVtvtaRLdSnXot6u4vh+Ffc/qDhu\nuKSHxBjnAPsDPwHvhBBuCyFcGkIYAYwm/YvAcTlmlSRJy+Cpp9IUlzfeSBsX/f3vcNRRWaeSSk+u\nRb1yKsr0Ku5XXl+W1V/eBIYCjYE/AGcCBwGfAXctPG9dkiTVvLIyOP982HvvtMJLt25p6cWttso6\nmVSa8mId9RBCA+A54GLgdqAtsCKwDfAxcG8I4bLleF6VX/3796+Fv4EkSYXtu+9gr73goougXj24\n5BIYNQpaLPNCy1Jx6d+/f5V9sq7k+jLpFcBpwGkxxqsXc/8G4HjgTzHGW5fwnKOAwcDIGONBi9xr\nQppasxawYYxx8hKe48ukkiQtp1dfhYMOgk8/hdVXh/vvh913zzqVlL8K5WXSSRXHdlXcr5ybXtUc\n9kqV+5mNW/RGjHE28Copq//xTZKkGhJjekF0hx1SSe/QIc1Lt6RL+SHXol5ZrDuHRf47QAhhJaAj\nMBN4aSnPmVtxbFXF/ZaL/JwkScrBrFnpBdG+fWHu3LRO+vjxsM46WSeTVCmnoh5j/Ji0Ist6wAmL\n3L6QNM98WMWoOCGEBiGE34QQ2i7ys5VLLx4bQlh74RshhD1JhX82aQdUSZKUgw8/hO22g7vvhiZN\n4J574IYboFGjrJNJWlhN7EzallSgWwGPkqbDdAB2Ad4Dto8xTqv42XVJL4dOiTGut8hzRpKWaJwB\nPAJ8DWwM7EPaNKlfjPH6pWRxjrokSUvw6KPQuzdMnw4bbggPPwybb551KqmwFMTOpP97SAitgQFA\nV2A14EtS2b4wxjh9oZ9bl1TUP4kxtl3kGfWAY4GewGak0fjvSTuWXhdjXOqGRxZ1SZIWb/58OO88\nGDgwnXfvnjYxWnmJe35LWpyCKur5wqIuSdIvffMNHHYYPP98Wnpx4EA4/XSow1XmpKJSV0W9QW0+\nXJIkZevvf4cePeCLL6BVK3jgAdhll6xTSVoWebHhkSRJqlkxwvXXw047pZLesSP84x+WdKmQWNQl\nSSoyM2fCEUfASSeluen9+sG4cbD22kv/XUn5w6kvkiQVkffegwMPhLffhqZN4c474ZBDsk4lqTos\n6pIkFYmHH4Y+fWDGDPjNb2DkSNh446xTSaoup75IklTg5s9Pq7gcdFAq6QcfDK+8YkmXCp0j6pIk\nFbCpU9PUlvHjoUEDuOIKOPlkl16UioFFXZKkAvXii2npxalTYa21YMQI2GGHrFNJqilOfZEkqQA9\n8ADsumsq6TvvDG+8YUmXio1FXZKkAnP99Wmn0Xnz0hKMY8fCmmtmnUpSTbOoS5JUIGKEc89N5TxG\nGDgQrrkmzU2XVHz8P21JkgrA/PnQt29aF71+fbjjDjjqqKxTSapNFnVJkvLc7Nlw6KHw2GPQpEl6\naXSffbJOJam2WdQlScpj06bBvvumFV5WWQWeeAK23z7rVJLqgkVdkqQ89cUXsMce8Pbb0Lo1jB4N\nm2ySdSpJdcWXSSVJykOTJqWR87ffTjuMTpxoSZdKjUVdkqQ88/LLaU30Tz+F7bZL017WWSfrVJLq\nmkVdkqQ88vTTaSOj77+HvfdOa6SvumrWqSRlwaIuSVKeGDYsvTg6axb07g2PPAIrrph1KklZsahL\nkpQHrroKevVK66WfeSYMGQING2adSlKWXPVFkqQMlZenYn7llel80CA45ZRsM0nKDxZ1SZIyMm8e\nHHNMmvLSoAEMHQpHHJF1Kkn5wqIuSVIGZs6EHj3Sy6NNm8LDD6c10yWpkkVdkqQ6Vrmiy8svw+qr\nw5NPwu9/n3UqSfnGoi5JUh369NM0cj5pErRpk3Ybbdcu61SS8pGrvkiSVEfeeivtNjppEmy+edpt\n1JIuqSoWdUmS6sCLL8KOO8IXX6Tj+PGw9tpZp5KUzyzqkiTVsscfh86d4ccfYb/90nSXFi2yTiUp\n31nUJUmqRYMHQ/fuMGcO/PGP8NBD0KRJ1qkkFQKLuiRJtSBGuPTStE56WRmcdx7cemtaL12SloX/\nuJAkqYaVl6fdRa+7DkJIxxNPzDqVpEJjUZckqQbNnQu9e8Pw4dCwIdxzDxx8cNapJBUii7okSTVk\nxgw44AAYOxZWWgkeeQR22y3rVJIKlUVdkqQa8M03sNde8Prr0KoVPP00bL111qkkFTKLuiRJOZo8\nGbp0gQ8/hLZt0/KLG2yQdSpJhc5VXyRJysG//pV2G/3wQ9hqK/jb3yzpkmqGRV2SpGp64QXYaSeY\nOhU6dUrna66ZdSpJxcKiLklSNYwcCXvsAf/5Dxx0UJqT3rx51qkkFROLuiRJy+mWW1I5/+9/4fjj\n01KMK6yQdSpJxcaiLknSMooRLrwQ/vSn9P2AAXDDDVC/ftbJJBUjV32RJGkZlJWl3UVvuQXq1YOb\nb4Zjj806laRiZlGXJGkp5syBI45I89JXWAHuvx+6d886laRiZ1GXJGkJpk+H/feHv/4VVl4ZHnss\nrfQiSbXNoi5JUhW++gr23DOtlb7mmmkjoy22yDqVpFJhUZckaTE++CAtvzh5Mmy4YSrp662XdSpJ\npcRVXyRJWsTrr0PHjqmkt2+fdhu1pEuqaxZ1SZIWMnYs7LILfPstdOkC48ZBy5ZZp5JUiizqkiRV\neOAB2Gsv+OknOOwwePxxaNYs61SSSpVFXZIk4PrrUzmfNw/69YN77oFGjbJOJamUWdQlSSUtRjj3\nXDjppPT9wIEwaFDa1EiSsuSqL5KkkjV/PvTtC3feCfXrw+23Q58+WaeSpMSiLkkqSbNnw6GHpg2M\nmjSBESNgn32yTiVJC1jUJUklZ9o02HdfePFFWGUVeOIJ2H77rFNJ0s9Z1CVJJeWLL9JGRm+/Da1b\np42MNtkk61SS9Eu+KiNJKhmTJqWR87ffho03hokTLemS8pdFXZJUEl5+GXbYAT79FLbdFiZMgHXW\nyTqVJFXNoi5JKnpPPw277grff582NBo7FlZbLetUkrRkFnVJUlEbNiy9ODprFvTuDaNGQdOmWaeS\npKWzqEuSitbVV0OvXmm99DPOgCFDoGHDrFNJ0rKxqEuSitLAgXDqqen7q66Cyy6DELLNJEnLw+UZ\nJUlF56KL4PzzUzG//XY45pisE0nS8rOoS5KKRozQvz8MGJBK+pAhaV66JBUii7okqSjECOeeC5de\nCvXqpZdIDz8861SSVH0WdUlSwYsRzjwTrrgC6teHe++FQw7JOpUk5caiLkkqaDGml0avuQYaNIDh\nw+HAA7NOJUm5s6hLkgpWjHDSSXDDDWnZxQcfhP32yzqVJNUMi7okqSCVl8MJJ8Att0CjRvDww7DP\nPlmnkqSaY1GXJBWc8nI47ji44w5YYYW022jXrlmnkqSaZVGXJBWUsrK0Lvpdd0HjxvDYY9C5c9ap\nJKnmWdQlSQVj/nw46qi0qsuKK8ITT0CnTlmnkqTaYVGXJBWE+fPhyCPhgQegaVN46inYaaesU0lS\n7bGoS5Ly3rx5cNhh6YXRlVaCp5+Gjh2zTiVJtcuiLknKa3Pnps2LRo2C5s1h9GjYdtusU0lS7bOo\nS5Ly1n//CwcdlOait2gBY8ZA+/ZZp5KkulEv1weEEFqHEAaHEL4MIcwJIUwOIVwdQmhRjWftFkJ4\nJIQwteJZX4QQngkh7JlrTklSYZkzB7p3TyV91VXh+ect6ZJKS4gxVv+XQ1gfmAi0BEYBk4AOQCfg\nPaBjjPGHZXzW5cDpwGfA08B3QCtga2BsjPGsZXhGBMjl7yRJyt6sWbD//mkEffXVYexY2HLLrFNJ\nUhJCACDGGGrzz8l16stNpJL+5xjjjZUXQwhXAacAlwB/WtpDQgh/JJX0ocCxMcb5i9x3io4klYiZ\nM6FbNxg3Dlq1gueeg802yzqVJNW9ao+oV4ymfwBMjjGuv8i9ZsBUIAJrxBhnLeE5K5BG0WcCGy5a\n0pczkyPqklTAfvoJ9t4bxo+HNddM01023jjrVJL0c3U1op7LHPXKLSaeXfRGjPEn4G9AU2Bp7+Z3\nBlYHRgIxhLB3COHMEMLJIQTf65ekEvGf/0DXrqmkr702/PWvlnRJpS2XKSXtKo7vV3H/A1IJ3xB4\nfgnP+V3F8b/AP4FNF74ZQhgPHBRj/K76USVJ+Wz69FTSX3oJWrdO01422CDrVJKUrVxG1FeuOE6v\n4n7l9aWt/tKq4vgXoAzYAWgGbEEard8JeLD6MSVJ+WzaNNh991TSf/1reOEFS7okQQ0sz1gDKjPM\nA/aNMU6MMc6KMb4FdAc+B3Z2GowkFZ/vv4fddoPXXoP11kvTXtq2zTqVJOWHXIp65Yj5ylXcr7z+\n41KeU3n/HzHGTxe+EWOcDYyuOP0dyyiEUOVX//79l/UxkqRa9O23qaT/4x9pBP2FF6BNm6xTSVLS\nv3//KvtkXclljvqkimO7Ku5vWHGsag77os+pqtBXXm+yjLlc9UWS8tw336SS/tZbsNFGaXWXX/0q\n61SStED//v2rHOCtq7Key4j6uIpj57BI2hDCSkBH0pKLLy3lOc+RlnHcZNHnVKhcPXdyDlklSXli\n6lTYZZdU0jfeOK3uYkmXpF+qdlGPMX5MetlzPeCERW5fCKwIDKuYvkIIoUEI4TchhLaLPOdT4HGg\nDXDywvdCCF2APYBpwDPVzSpJyg9ffplK+rvvpk2Mxo2DtdbKOpUk5adqb3gEUFG6J5JWbnmUNI2l\nA7AL8B6wfYxxWsXPrgt8DEyJMa63yHN+VfGcdUgj7P8k/QvA/qSVYA6NMT6yDHnc8EiS8tRnn8Gu\nu8KHH8IWW8DYsdCyZdapJGn51dWGRzkVdYAQQmtgANAVWA34EngEuDDGOH2hn1uXVNQ/iTH+4p3+\nEMLqwPnAvsBapJdVJwCXxhhfW8YsFnVJykNTpkCnTjB5Mvz2tzBmDKy2WtapJKl6Cqao5xOLuiTl\nn8mTU0mfMgXat4dnn4VVVsk6lSRVX10V9XxYR12SVKQ+/BB23jmV9A4d0ki6JV2Slo1FXZJUK95/\nP5X0zz6Djh3TSHqLpe1VLUn6H4u6JKnGvftuKulffgk77QTPPAPNm2edSpIKi0VdklSj3n47LcE4\ndWqam/7UU9CsWdapJKnwWNQlSTXmzTdTSf/mG+jcGZ54Apo2zTqVJBUmi7okqUb84x9pBP2776Br\nV3jsMVhxxaxTSVLhsqhLknL22mtpM6MffoC994ZRo6Bx46xTSVJhs6hLknLy8suw++7w44+w334w\nciSssELWqSSp8FnUJUnVNnFimos+fToceCA8+CA0apR1KkkqDhZ1SVK1TJgAe+wBM2bAIYfA/fdD\nw4ZZp5Kk4mFRlyQtt7/+Nb0w+tNPcMQRcM89lnRJqmkWdUnSchk7FvbaC2bNgt694a67oEGDrFNJ\nUvGxqEuSltno0dCtG8yeDcccA4MHQ/36WaeSpOJkUZckLZMnn4R994U5c6BvX7jtNqjn/xeRpFrj\nP2IlSUv12GPQvTvMnQsnngg33WRJl6Ta5j9mJUlLNHJkWnpx3jzo1w+uuw5CyDqVJBU/i7okqUoj\nRsDBB8P8+fCXv8CgQZZ0SaorFnVJ0mLddx8cdhiUlcE558Bll1nSJakuWdQlSb8wbBj07Anl5XD+\n+XDxxZZ0SaprFnVJ0s8MHpzWRy8vhwED4MILLemSlAW3qJAk/c9tt8Fxx6XvL70Uzjor2zySVMos\n6pIkIC25eMIJ6fsrr4TTTss2jySVOqe+SJK47roFJf2aayzpkpQPLOqSVOKuugpOPjl9f8MNC76X\nJGXLqS+SVMIuvxzOPDN9f+utcOyx2eaRJC3giLoklaiBA1NJDwHuuMOSLkn5xhF1SSpBl16aNjEK\nIS3HeNRRWSeSJC3KEXVJKjH/7/8tKOlDhljSJSlfWdQlqYRcfDGce+6Ckt67d9aJJElVsahLUom4\n6CI477xU0ocOtaRLUr6zqEtSCRgwAM4/P5X0u+6CXr2yTiRJWhqLuiQVuQsvhAsugHr14O67oWfP\nrBNJkpaFq75IUhHr3z8V9cqSfsQRWSeSJC0ri7okFamFS/qwYXD44VknkiQtD4u6JBWZGFNJHzAg\nlfR77oHk9oJDAAAgAElEQVTDDss6lSRpeVnUJamIxJjmo190USrp994Lhx6adSpJUnVY1CWpSMSY\nVna5+GKoXz+V9EMOyTqVJKm6LOqSVARihP/7v7TraP36cN99cPDBWaeSJOXCoi5JBS7GtNvopZem\nkn7//dCjR9apJEm5sqhLUgGLEc45BwYOtKRLUrGxqEtSgYoRzj4bLrsslfThw+Ggg7JOJUmqKRZ1\nSSpAMcJZZ8Hll0ODBqmkH3hg1qkkSTXJoi5JBSZGOPNMuOKKVNJHjIDu3bNOJUmqaRZ1SSogMcIZ\nZ8CVV1rSJanYWdQlqUDECH/5C1x1VSrpDz4I+++fdSpJUm2xqEtSAYgRTjsNrr4aGjZMJX2//bJO\nJUmqTRZ1ScpzMcKpp8I116SS/tBDsO++WaeSJNU2i7ok5bEY4ZRT4NprU0l/+GHo1i3rVJKkulAv\n6wCSpMWzpEtSaXNEXZLyUIzQrx9cdx00apRK+j77ZJ1KklSXLOqSlGdihJNPhuuvTyX9kUdgr72y\nTiVJqmsWdUnKIzHCSSfBDTdY0iWp1FnUJSlPxAh//jPceCOssEIq6XvumXUqSVJWLOqSlAfKy+HE\nE+Hmm1NJHzUKunbNOpUkKUsWdUnKWHk5nHAC3HJLKumPPgp77JF1KklS1izqkpSh8nI4/ni49VZL\nuiTp5yzqkpSR8nL405/gttugceNU0rt0yTqVJClfWNQlKQPl5dC3L9x+eyrpjz0GnTtnnUqSlE8s\n6pJUx8rL4bjj4I47Ukl//HHYffesU0mS8k29rANIUilZuKQ3aQJPPGFJlyQtniPqklRHysvh2GPh\nzjsXlPRdd806lSQpX1nUJakOlJfDH/4AQ4ZY0iVJy8aiLkm1rKwslfShQ1NJf/JJ6NQp61SSpHxn\nUZekWlRWBsccA3fdBSuumEr6LrtknUqSVAgs6pJUS8rK4Oij4e67U0l/6inYeeesU0mSCoVFXZJq\nQVkZ9OkDw4ZZ0iVJ1ePyjJJUwxYu6U2bwtNPW9IlScvPEXVJqkFlZXDUUXDPPQtK+o47Zp1KklSI\nLOqSVEPKyqB3b7j3XmjWLJX0HXbIOpUkqVBZ1CWpBsyfn0r6ffelkv7MM9CxY9apJEmFzKIuSTma\nPx969YL777ekS5JqjkVdknIwfz707AnDh8NKK6WSvv32WaeSJBUDi7okVdP8+XDkkfDAA6mkjx4N\n222XdSpJUrGwqEtSNcyfD0ccASNGWNIlSbUj53XUQwitQwiDQwhfhhDmhBAmhxCuDiG0yOGZR4YQ\nyiu+jsk1oyTVpHnz4PDDU0lv3hyefdaSLkmqeTmNqIcQ1gcmAi2BUcAkoANwMtA1hNAxxvjDcj5z\nHeAG4CegGRBzyShJNamypD/00IKS3qFD1qkkScUo1xH1m0gl/c8xxgNijOfEGHcDrgbaAZcsz8NC\nCAEYAnwL3JJjNkmqUfPmwWGHpZK+8sowZowlXZJUe6pd1CtG0zsDk2OMNy5y+wJgFnBkCGHF5Xjs\nSUAnoE/F70tSXqgs6Q8/vKCk//73WaeSJBWzXEbUO1Ucn130RozxJ+BvQFNg22V5WAhhY2AgcE2M\n8cUccklSjZo3Dw499Ocl/Xe/yzqVJKnY5VLU21Uc36/i/gcVxw2X9qAQQgNgGPAJcE4OmSSpRs2d\nC4ccAiNHQosWMHasJV2SVDdyeZl05Yrj9CruV15fltVfzge2AjrGGP+bQyZJqjGzZ0OPHvDkkwtK\n+jbbZJ1KklQqMl9HPYTQATgbuCLG+HLWeSQJYMYM2G8/GDcOVlstre6y9dZZp5IklZJcpr5Ujpiv\nXMX9yus/VvWAiikvdwPvkV5AXeyPLW+wEEKVX/3791/ex0kqMdOmQefOqaSvtRa88IIlXZJKTf/+\n/avsk3UlxFi9ZcorNiK6Hbgtxth3MfdHk1aF2S3GOK6KZ7QAlnWd9WtjjKcsJVMEqO7fSZK+/hq6\ndIE334Q2beC552D99bNOJUnKJ5VlPcZYq609l6kvleW7cwghxIXacQhhJaAjMBN4aQnPmAPcyeI3\nNdoG+C0wgTTiPjGHrJK0VJ99BrvvDu+/D+3apTnprVtnnUqSVKqqXdRjjB+HEJ4FugAnkHYTrXQh\nsCJwS4xxNvxvmssGwNwY48cVz5gD/HFxzw8h9CcV9btijIOrm1OSlsWHH6aSPmUKbLllmpPeqlXW\nqSRJpSzXl0mPJ410XxdC2A2YBHQAdiGNgp+70M+2Bt4BpgDr5fjnSlKNeeutNCd96lTYdlt46ilY\nZZWsU0mSSl0uL5NSMTLeHhhKKuinkkr4NcC2McZpi/u1ZX38cvysJFXLa6/Bzjunkr7rrmkzI0u6\nJCkfVPtl0nzky6SSlseECbD33mkpxn32gQcfhMaNs04lScp3dfUyaU4j6pJUqEaPhj32SCW9cudR\nS7okKZ9Y1CWVnJEjoVu3tPPoMcfAvfdCw4ZZp5Ik6ecs6pJKyrBhcPDBMG8e9OsHt98O9etnnUqS\npF+yqEsqGTffDL16QVkZnHceDBoEdbjBnCRJy8WiLqkkXH45HH/8gu8HDLCkS5LyW67rqEtSXosx\njZ5fckkq5jfdBH37Zp1KkqSls6hLKlrl5XDKKXDddWke+tChcOSRWaeSJGnZWNQlFaWyMjj2WBg8\nGBo1guHDoXv3rFNJkrTsLOqSis7cudCzJ4wYAU2awKhR0KVL1qkkSVo+FnVJRWX2bOjRA558Epo3\nT8cddsg6lSRJy8+iLqlozJgB++0H48bBaqul3Ue32SbrVJIkVY9FXVJRmDYN9twTXn4Z1loLxoyB\nTTfNOpUkSdVnUZdU8L7+Os1Bf/NNaNMGnnsO1l8/61SSJOXGoi6poH32Gey+O7z/PrRrB2PHQuvW\nWaeSJCl37kwqqWB9+CHsuGMq6VtuCePHW9IlScXDoi6pIL31VirpU6bAttumF0hbtco6lSRJNcei\nLqngvPYa7LwzTJ0Ku+6aXhxdZZWsU0mSVLMs6pIKyoQJqZz/8APss09aJ71Zs6xTSZJU8yzqkgrG\n6NGwxx5pvfRDDoGRI6Fx46xTSZJUOyzqkgrCyJHQrVvaefSYY+Dee6Fhw6xTSZJUeyzqkvLesGFw\n8MEwbx706we33w7162edSpKk2mVRl5TXbr4ZevWCsjI47zwYNAhCyDqVJEm1z6IuKW9dfjkcf/yC\n7wcMsKRLkkqHO5NKyjsxptHzSy5Jxfymm6Bv36xTSZJUtyzqkvJKeTmccgpcd12ahz50KBx5ZNap\nJEmqexZ1SXmjrAyOPRYGD4ZGjWD4cOjePetUkiRlw6IuKS/MnQs9e8KIEdCkCYwaBV26ZJ1KkqTs\nWNQlZW72bOjRI+0y2rx5Ou6wQ9apJEnKlkVdUqZmzID99oNx42C11dLuo9tsk3UqSZKyZ1GXlJlp\n02DPPeHll2GttWDMGNh006xTSZKUHyzqkjLx9ddpDvqbb0KbNvDcc7D++lmnkiQpf1jUJdW5zz6D\n3XeH99+Hdu1g7Fho3TrrVJIk5Rd3JpVUpz78EHbcMZX0LbeE8eMt6ZIkLY5FXVKdeeutVNKnTIFt\nt00vkLZqlXUqSZLyk0VdUp147TXYeWeYOhV23TW9OLrKKlmnkiQpf1nUJdW6CRNSOf/hB9hnn7RO\nerNmWaeSJCm/WdQl1arRo2GPPdJ66YccAiNHQuPGWaeSJCn/WdQl1ZqRI6Fbt7Tz6DHHwL33QsOG\nWaeSJKkwWNQl1Yphw+Dgg2HePOjXD26/HerXzzqVJEmFw6IuqcbdfDP06gVlZXDeeTBoEISQdSpJ\nkgqLRV1SjbriCjj++PT95ZfDgAGWdEmSqsOdSSXViBjh/PPh4otTMb/pJujbN+tUkiQVLou6pJyV\nl8Mpp8B116V56EOHwpFHZp1KkqTCZlGXlJP58+G442DwYGjUCIYPh+7ds04lSVLhs6hLqrYff0xr\noz/7LDRpAqNGQZcuWaeSJKk4WNQlVctHH6VdRidNgpYtU0nffvusU0mSVDxc9UXSchs/Hjp0SCV9\n003hlVcs6ZIk1TSLuqTlMmQI7L47fP897LUXTJwI666bdSpJkoqPRV3SMikvhzPPhKOPXrDb6GOP\nQfPmWSeTJKk4OUdd0lL99FNabvHRR6FBA7jxRjj22KxTSZJU3Czqkpbos8+gWzf417+gRQt4+GHY\nddesU0mSVPws6pKq9MorsN9+MHUqbLghPPEEbLRR1qkkSSoNzlGXtFgPPAA775xK+q67wksvWdIl\nSapLFnVJPxMjXHghHHoozJmT5qI/8wysumrWySRJKi1OfZH0P7Nnp1Vdhg+HevXgqqvg5JMhhKyT\nSZJUeizqkoA0xWX//eHll2GlleD++2HvvbNOJUlS6bKoS+Jf/0oru3z2GbRpk14a3WyzrFNJklTa\nnKMulbjHHoOOHVNJ3377tNKLJV2SpOxZ1KUSFSNccUWa7jJzJhxxBDz3HLRqlXUySZIEFnWpJM2d\nC3/4A5xxRirsl1wCw4ZB48ZZJ5MkSZWcoy6VmO+/hwMPhBdegCZN4O674aCDsk4lSZIWZVGXSsik\nSbDPPvDRR7D22vDoo9C+fdapJEnS4jj1RSoRY8bAttumkr711umlUUu6JEn5y6IulYCbboI994Tp\n0+GAA2D8ePjVr7JOJUmSlsSiLhWx+fPhz3+GE06AsjI45xx48EFo2jTrZJIkaWmcoy4VqenT4ZBD\nYPRoaNQI7rgDevbMOpUkSVpWFnWpCH38cXpp9N13oWVLeOSRtKmRJEkqHE59kYrMhAnw+9+nkr7p\npumlUUu6JEmFx6IuFZGhQ2G33dJa6XvuCRMnwrrrZp1KkiRVh0VdKgLl5XDWWdCnD8ybB/36wWOP\nQfPmWSeTJEnV5Rx1qcD99FN6SXTUKGjQAG64AY47LutUkiQpVxZ1qYB99hnsuy/885/QogU89FCa\n+iJJkgqfRV0qUK++mkr61Kmw4Ybw+OPQrl3WqSRJUk1xjrpUgEaMgJ12SiW9Uyd46SVLuiRJxcai\nLhWQGGHAgLSR0Zw58Mc/pg2NVl0162SSJKmm1UhRDyG0DiEMDiF8GUKYE0KYHEK4OoTQYhl/f9UQ\nwh9CCI+EED4MIcwKIfwYQpgQQjg6hBBqIqdUyGbPhiOOgAsugBBg0CC49VZo2DDrZJIkqTaEGGNu\nDwhhfWAi0BIYBUwCOgCdgPeAjjHGH5byjL7ATcCXwDjgU2BN4ABgZeDhGGOPZcgSAXL9O0n5ZupU\n2H9/ePllaNYMhg+HvffOOpUkSaWpcgw5xlirg8k1UdRHA52BP8cYb1zo+lXAKcCtMcY/LeUZnYAV\nY4xPLnJ9DeAVYB3goBjjyKU8x6KuovPmm7DPPmmFlzZt0kujm2+edSpJkkpXQRT1itH0D4DJMcb1\nF7nXDJgKRGCNGOOsav4ZZwOXANfHGE9eys9a1FVUHn8cDjsMZs6E7bZLa6W3apV1KkmSSltdFfVc\n56h3qjg+u+iNGONPwN+ApsC2OfwZ8xc5SkUvRrjqKthvv1TSjzgCnn/eki5JUinJtahXLgj3fhX3\nP6g4blidh4cQGgC9Kk6fqc4zpEIzd25azeX001Nhv/hiGDYMGjfOOpkkSapLuW54tHLFcXoV9yuv\nL9PqL4sxENgUeDLGOKaaz5AKxvffw4EHwgsvQJMmcPfdcNBBWaeSJElZyNt11EMIJwGnAu8CPZfz\nd6v86t+/f23ElXI2aRJ06JBK+lprwfjxlnRJkrLSv3//KvtkXcl1RL1yxHzlKu5XXv9xeR4aQjgR\nuAZ4G9gtxrhcv+/LpCo0Y8emUj59Ovz2t/DYY9C6ddapJEkqXf37969ygLeuynquI+qTKo5VbV5e\nOTe9qjnsvxBC6AdcB/wb6BRj/Kb68aT8d/PN0LVrKukHHAATJljSJUlS7kV9XMWx86K7h4YQVgI6\nAjOBl5blYSGEM4FBwD9IJf27HPNJeWv+fDjpJDj+eCgrg3POgQcfhKZNs04mSZLyQU5FPcb4MWlp\nxvWAExa5fSGwIjAsxjgb0iouIYTfhBDaLvqsEMJ5wKXAa6TpLkvczVQqZNOnp02Mrr8eGjVKL41e\ncgnUy9u3RiRJUl2riZ1J2wITgVbAo6TpMB2AXYD3gO1jjNMqfnZd4GNgSoxxvYWe0RsYApQB1wP/\nWcwfNTnGeNdSsrjhkfLexx9Dt27wzjuw+urwyCOwww5Zp5IkScuqrjY8yvVlUmKMH4cQ2gMDgK7A\nXsCXpJdBL4wxLm7pxkWb9LoVx3pAvyr+qL8CSyzqUr6bMCHNQ//uO9h007Tz6HrrLf33JElS6cl5\nRD2fOKKufHbXXWkjo3nzYM89YfhwaN4861SSJGl51dWIujNipVo2dy6ccQYcdVQq6SefnJZftKRL\nkqQlyXnqi6Sq/fvf0KsX/POfUL8+3HgjHHdc1qkkSVIhcERdqgVlZTBwIGyzTSrp660H48ZZ0iVJ\n0rJzRF2qYe+/D717w0sVuwf07QtXXAHNmmWbS5IkFRZH1KUaUl6e1kXfaqtU0n/1K3jmmbTzqCVd\nkiQtL0fUpRowZQocfTQ8/3w679kTrr0WVlkl21ySJKlwOaIu5SBGGDwYNt88lfSWLeHhh9NOo5Z0\nSZKUC0fUpWr66is49lh44ol03r073HILtGqVbS5JklQcHFGXquGBB2CzzVJJX3llGDYsjaRb0iVJ\nUk1xRF1aDt99ByecACNGpPM99oA77oDWrbPNJUmSio8j6tIyevzxNIo+YgQ0bQq33gpPP21JlyRJ\ntcMRdWkppk+Hfv1g6NB0vtNOMGQItG2baSxJklTkHFGXluC559KKLkOHwgorwKBBaYdRS7okSapt\njqhLizFzJpx5Jtx4Yzr/3e/grrtg442zzSVJkkqHI+rSIiZOTLuL3ngjNGgAF12UrlnSJUlSXXJE\nXaowZw5ccAFceSWUl6cpL3ffnUq7JElSXXNEXQLeeAPat4fLL0/nZ58Nr75qSZckSdlxRF0lbd48\nuPTSNL1l/nzYcMM0F3277bJOJkmSSp1FXSXrnXegd2947bV0ftJJqbSvuGK2uSRJksCpLypBZWVw\n1VWw9dappLdpA88/D9dea0mXJEn5wxF1lZSPPoKjjoIXX0znxxyT1kZv3jzTWJIkSb/giLpKQoxw\n882wxRappK+5JjzxBNxxhyVdkiTlJ0fUVfQ++yyNnI8Zk84POwyuvx5WWy3bXJIkSUviiLqKVoxp\nHfTNN08lfbXVYMQIuO8+S7okScp/jqirKH39NfTtC6NGpfNu3eC229KUF0mSpELgiLqKzsMPw2ab\npZLevDkMGQKPPmpJlyRJhcURdRWNadPgxBPT1BaA3XaDwYPh17/ONpckSVJ1OKKuovD002kU/b77\n0lroN94Izz5rSZckSYXLEXUVtBkz4LTT4Pbb03nHjjB0KGywQaaxJEmScuaIugrWX/+a1kW//XZo\n1AguvxxeeMGSLkmSioMj6io4s2fD2WfDtdem8623TsswbrpptrkkSZJqkiPqKigvvwy//W0q6fXr\nwwUXwEsvWdIlSVLxcURdBWHuXLjwQhg4EMrLYZNN0ij6NttknUySJKl2WNSV9/71L+jVC958E0KA\n00+Hiy6Cxo2zTiZJklR7LOrKW/PnpxdE+/eHefOgbVu46y7YYYesk0mSJNU+i7ry0nvvQe/eaU46\nwPHHw2WXQbNm2eaSJEmqK75MqrxSXp5eFN1qq1TSW7dOGxfdeKMlXZIklRZH1JU3PvkE+vRJ66ND\nGlG/5hpo0SLLVJIkSdlwRF2ZmzUrFfLNN08lvVUrGDUq7TBqSZckSaXKEXVlZvp0uOkmuPpq+Pbb\ndO2gg+Dmm2H11bPNJkmSlDWLuurcd9+lEfQbbkhlHaB9ezjvPOjWLS3BKEmSVOos6qozX3wBV14J\nt92WprsA7LILnHMO7L67BV2SJGlhFnXVuo8+SuuhDx2adhgF2HvvVNC33z7TaJIkSXnLoq5a89Zb\nMHAg3H9/WnYxBOjRIxX0rbbKOp0kSVJ+s6irxr36Kvy//5dWbgFo0AB69YKzzoJ27bLNJkmSVCgs\n6qoRMcL48XDJJTBmTLq2wgrwhz/AX/4Cbdpkm0+SJKnQWNSVkxjh6adTQZ84MV1r1gyOPx5OOQXW\nXDPbfJIkSYXKoq5qKSuDkSPTFJd//jNdW3VVOPlkOPHE9L0kSZKqz6Ku5TJvHtx7b3pJ9L330rU1\n14TTT4fjjkuj6ZIkScqdRV3LZPZsGDw4LbP46afp2rrrwplnwlFHQePGWaaTJEkqPhZ1LdGMGXDz\nzTBoEHz9dbr2m9/A2WfDYYdBw4bZ5pMkSSpWFnUt1vffw3XXpa8ff0zXfvtbOPdc6N4d6tXLNp8k\nSVKxs6jrZ776Cq66Cm65BWbOTNd22CEV9D32SJsWSZIkqfZZ1AXA5Mlp/vmQIfDf/6ZrXbumXUR3\n3DHbbJIkSaXIol7i3n0XLr0U7rsvLbkIcMABqaBvs0222SRJkkqZRb1EvfFGWgN95Mi0aVH9+tCz\nJ5x1FmyySdbpJEmSZFEvMRMmpIL+zDPpvFEjOPpoOOMMWG+9bLNJkiRpAYt6CYgRRo9OBX3ChHSt\naVPo2xdOPRXWXjvbfJIkSfoli3oRKy+HUaNSQX/99XStRQs46aT0tdpq2eaTJElS1SzqRWjePBg+\nPL0k+u676VqrVnDaaWkUvXnzbPNJkiRp6SzqRWTOHBg6FC67DD75JF1bZ500//yYY6BJkyzTSZIk\naXlY1IvATz/BrbemjYq++ipd22ijtILLEUekF0YlSZJUWCzqBWzaNLj+erj2Wvjhh3Rtyy3TGugH\nHpiWXJQkSVJhsqgXoK+/hkGD4Kab0mg6wHbbwbnnwl57QQjZ5pMkSVLuLOoFZMoUuOIKuPPONB8d\nYPfdU0HfeWcLuiRJUjGxqOexGOGdd9LmRKNHw7hxMH9+urfffmmKy+9/n21GSZIk1Q6Lep754QcY\nOzYV89Gj4YsvFtyrVw8OPzy9JLr55tlllCRJUu2zqGesrAxeeWVBMX/llbRRUaU11oAuXaBrV+jc\nGVq2zC6rJEmS6o5FPQOff76gmI8ZAz/+uOBew4Zpvvkee6SvLbZII+mSJEkqLRb1OjBnDowfv6Cc\nv/32z+9vsMGCYt6pEzRrlk1OSZIk/f/27j3YqrKM4/j3l5RJGo4EZmpxkdBqKESHggYBh8AuamVp\njWWZWU0pWjpON8Muo9U4NplWU1mkTtFFZLqoFAKaTHbx0pVCASWJCpFMbqY8/fG+233O7mwOe+/D\nXmsdfp+ZM2v2etd5eZh3ztrPetd7KQ8n6ntABKxcWU/Mly2rr9ICKRGfObOenI8dW1ioZmZmZlZS\nTtQHyObNsGRJSsxvvhnWretdPnFiPTGfMsW7hZqZmZnZrjlRb9OTT8Jvf1tfOvHOO9O5mhEj0iTQ\n2bPT8eCDi4vVzMzMzKrHiXoL1q/vPQl006Z62ZAhMG1avdd84kRPAjUzMzOz9nWcSko6TNI1ktZL\n2i5pjaQrJB1YRD0DaceOtKb5hRem1VcOPRTOPBMWLEhJ+ujR8N73wsKF8PDDsHx52oRo0iQn6e2Y\nN29e0SFYB9x+1eW2qza3X7W5/WxXFBHt/7I0FlgBjABuBFYCk4EZwF+AqRGxqXkNA15PALT7f4qA\nVavqw1mWLYOtW+vlQ4emVVlmz07rmh9xBEht/VPWB0ltt50Vz+1XXW67anP7VZvbr5qUE8CI2KOZ\nYKdDX64mJdfnRMRVtZOSLgfOBz4DvK+L9bTs0Ufrk0BvuQXWru1dPmFCPTGfOhX23XdPRGFmZmZm\n1lvbPeq5F3wVsCYixjaU7Q9sAAI4OCK29lHFgNaTr++3R33nTrjrrnpivmJF70mgw4enHUDnzEmT\nQA85ZFf/og0k9ypUm9uvutx21eb2qza3XzVVoUd9Rj4ubiyIiMck3QHMAl4O3NqFeprasAEWL06J\n+eLFsHFjvWyffVJP+Zw5qef86KPTOTMzMzOzInWSqI/Px782KV9FSrDHsesEe6Dqecrjj8Mdd9TX\nNL/33t7lz39+PTGfORMOLGy6qpmZmZlZ3zpJ1Ifl47+blNfO95cGD1Q9TznoINiypf55v/1g+vT6\n0onjx3sSqJmZmZmV26BcR33Llt5Z+LZtcNNN6cfKTX6CqjS3X3W57arN7Vdtbj9rppPVvms93cOa\nlNfOb+5SPWZmZmZmg0YnPeor83F8k/Jx+dhs7PlA17PHZ96amZmZmXVLJ8szjgHuA9YAR0SPiiQd\nAPydtKziyIjYtqfrMTMzMzMbTNoe+hIRq0lLKo4G3t9QfAkwFLi2llxLGiLpyJyYt12PmZmZmdne\noO0edXiqN3wFMBJYRBrGMhmYDvwFmBIRj+RrRwGrgQciYnS79ZiZmZmZ7Q06StQBJB0GfBKYAwwH\n1gMLgUsi4t89rhtFStTXRsSYdusxMzMzM9sbdJyom5mZmZnZwOtkeUYzMzMzM9tDnKibmZmZmZXQ\noEjUJR0m6RpJ6yVtl7RG0hWSDiw6NmtO0kGSzpK0UNJ9krZK2izpdklnylu1VYqk0yXtzD/vKjoe\n65+k4/Pf34Z873xI0s2STig6NmtOyamSluY22yrpfknfk/TyouMzkHSKpCvz99mj+b54bT+/M0XS\nTyVtym16r6S5kgZFrlYlrbSfpHGSLpJ0q6R1knbke+qNkqZ3GksnGx6VgqSxpBVjRgA3Ul8xZi4w\nR9LUiNhUYIjW3JuBq0kTh5cCDwLPBd4AfB04AXhTYdHZbpN0OPAl4DFgf9LeB1Zikj4HXACsI907\nN5JW3joaOA64qbjorB9fA84ktVmt7cYBJwFvlPT2iLi+wPgMPgZMAP4D/A04kl3cFyWdBPwQ2Aos\nADYBJwJXAFNJ35fWPa2036dI7fNH4MektjuS1H4nSpobEVe2G0jlJ5NKugWYBZwTEVf1OH85cD7w\n1eH67pgAAAadSURBVIh4X1HxWXOSZgBDI+InDecPBn4FHA6cEhE3FBGf7Z785uNnwAtIKzVdAJwV\nEdcUGpg1JendwFeBbwFnR8QTDeVDGs9ZOUh6AWmDwA3AhIjY2KNsOnArsCYixhYTocFTbbEuIu6X\ndBypM+q6iHh7H9c+m7Tx4wHA1Ii4K5/fl9SerwDeEhELuhX/3q7F9jsDuCci7m04P4303RjAqIjY\n0E4slX6dknvTZ5FuSlc1FH+C9GR6uqShXQ/O+hURSxuT9Hz+H8BX8sfjuhuVteFcYAbwTtLfnJVY\n/vL/DPAAfSTpAE7SS21EPt7ZM0kHiIhlpLdaz+l2UNZbRCyLiPvzx/6GcZ5CarPv1pL0XMcOUs8u\ngDscu6iV9ouI+Y1Jej5/G7AceAYwpd1YKp2ok5IDSDub9hIRjwF3AM8CPGavep5oOFoJSToKuAz4\nQkT8ouh4bLfMIiUFNwAh6TV5fOVcj2+uhD+QetMnSxresyD34O0P/LyIwKxtM/Px5j7KbgO2Aa+Q\n9PTuhWQD5L8Nx5ZVfYz6+Hz8a5PyVaQvpXGk10dWAZKGALXXS33duKwEcjtdC6wFPlJsNNaCY/Nx\nB3AP8OKehZJuIw0529j4i1a8iNgu6WTgOuBPkhYBDwNjgdeROq7eU2CI1rqmuUxEPClpDXAUMIa0\nW7tVQB6mdjywhfTA1Zaq96gPy8dmO5fWznv1l2q5jJQ8/CQiflZ0MNbUxcDLgHfkV7RWDSPz8ULg\nSeCVpF7YCaQkbxrw/WJCs930O9L8gmcCZwEXkYZPrAPm+yGrcoaRxjHvKpcRzmUqIw8xvJ407GVe\nRDRr235VPVG3QUbSucAHgT8Dbys4HGtC0mTgw8DnI+LOouOxltTu+/8FToyIFRGxNSL+ALyetMLB\ncR4GU075TdYS4NOk1V/GAEOBScBq4HpJny0uQrO9m6R9SG+bp5DmHVzeSX1VT9RrTyjDmpTXzm/u\nQizWIUkfAL5AWuJoRkS43UooJwrfJr2C/USzy7oXkbWo9nd1d0Q82LMgIrYBt+SPx2JldDppFZAb\nIuKCiFgbEdsj4m7Sg9ZDwIckjS40SmtFrcfcuUzF5ST9OtIbrgWkv9eOVD1RX5mP45uUj8vHZmPY\nrSQknQd8Efg9KUn/Z8EhWXP7k/62XgRs77HJ0U7ScBiAr+VzVxQWpTVTu282+9Kvnd+vC7FY647J\nx6WNBflB69ek7/aXdTMo60ht3Pn/5TK5Y2Q06Q3Y6m4GZa3Jk32/A5xKGvby1ojY2Wm9VZ9MWrtR\nzZKk6LEovKQDSJsEbAF+WURwtnskXQRcCtwNzPIGVaW3HfgGfW/+MAmYCNxO+vJZ0cW4bPcsIbXd\nixrvm9lL8nFNd8Oy3fR4Po5sUj6i4TorvyXAW4E5wHcbyqaRHpqXR0TbK4fYniXpGcD3SJsczY+I\ndw5U3ZXuUY+I1aTJT6OB9zcUX0Iat3dt7mWwEpL0cVKS/hvgeCfp5Zdfs787Is5u/AF+lC+bn895\nUmLJ5OEuPyJtUDW3Z5mkVwGzgUfwiktlVVt68WxJz+tZIOkEUgfVNvyQXCU/IO0ue5qkSbWTkp5J\nmosA8OUiArP+5YmjC0lJ+tdJuwYPXP2DYGfSMaQb0khgEem17mRgOqlHb0pEPFJYgNZU3s3rm6SV\nJ64EHu3jsjURMb+rgVnbJM0jDX/xzqQlJulQ0n3zcFJv3j2kDo+TSX+Pp0XEwuIitF2RdAOprf5D\nShD+QVq+77WktyXndbJluXUuL6F5cv74XOBVpKErtf0m/hURF/a4/iRSwr6d1Kv+CCnxeyHw/Yg4\ntUuhG621n6RvAmeQHraublLl0ohY3k4sVR/6QkSslnQM8EnSa6NXA+tJkxIv6WRJHNvjRuXj04Dz\nmlyzDHCiXh1B30NirEQi4qHcc3cxKRmYRprQtgi4NCJ+U2R81q9TgLNJK2O9nvT2+GHgx8AXI8Ib\nHhXvpaT9QGr3wyA9DI/Jn9eSlkhNhRGL8lb1HwXeSFp6cxVwPmn+lnVXK+03KpcPpz5Pq6cAdpJ2\nKW1Z5XvUzczMzMwGo0qPUTczMzMzG6ycqJuZmZmZlZATdTMzMzOzEnKibmZmZmZWQk7UzczMzMxK\nyIm6mZmZmVkJOVE3MzMzMyshJ+pmZmZmZiXkRN3MzMzMrIScqJuZmZmZlZATdTMzMzOzEnKibmZm\nZmZWQk7UzczMzMxKyIm6mZmZmVkJOVE3MzMzMyshJ+pmZmZmZiXkRN3MzMzMrIT+ByOev7rlMHg2\nAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x10d3c5ba8>"
      ]
     },
     "metadata": {
      "image/png": {
       "height": 255,
       "width": 373
      }
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "def grovers_plot(func, qubits, N=None, iterations=None):    \n",
    "    if N is None:\n",
    "        N = 2 ** qubits\n",
    "\n",
    "    # input: |00...0> (length n)\n",
    "    # output: |0>\n",
    "    state = Q(kron(*(zero for _ in range(qubits)), zero))\n",
    "\n",
    "    # Apply HX to the output register.\n",
    "    state = state.apply_gate(X, 0)\n",
    "    state = state.apply_gate(H, 0)\n",
    "\n",
    "    # Apply H^n to the input register.\n",
    "    # input register: qubits 1 to n\n",
    "    input_H = kron(*(H for _ in range(qubits)), I)\n",
    "    state = state.apply_unitary(input_H)\n",
    "\n",
    "    # First, we'll compute the diffusion operator.\n",
    "    # this definition of D (the diffusion matrix aka. inversion about the mean)\n",
    "    # is given in Grover's original paper\n",
    "    P = 1/N * np.ones((N, N))\n",
    "    D = -np.eye(N) + 2*P\n",
    "    # I assume we leave the output register untouched (hence the final I)\n",
    "    D = kron(D, I)\n",
    "    \n",
    "    # initalize list of probabilities. Probability is 0 after 0th iteration\n",
    "    y_data = [0]\n",
    "    \n",
    "    if iterations is None:\n",
    "        # the exact number of iterations to reach optimal probability\n",
    "        # Should be (pi/4)*sqrt(N) iterations (Mermin, chapter 4)\n",
    "        opt_iters = (np.pi/4) * sqrt(N).real\n",
    "        # take the floor\n",
    "        iterations = floor(opt_iters)\n",
    "\n",
    "    # Now we perform the Grover iteration.\n",
    "    for iteration in range(iterations):\n",
    "        state = state.apply_func(func)\n",
    "        state = state.apply_unitary(D)\n",
    "        amplitudes = to_row(state.state)\n",
    "        probs = [(abs(a) ** 2).real for a in amplitudes]\n",
    "        target_prob = sum(p for idx, p in enumerate(probs) if func(idx >> 1) == 1)\n",
    "        y_data.append(target_prob)\n",
    "    \n",
    "    print('\\nperformed {} iterations'.format(iterations))\n",
    "    print('measured', state.measure()>>1)\n",
    "    print('probability of measuring target is {:.5f}%'.format(100*y_data[-1]))\n",
    "    \n",
    "    plt.plot(range(iterations+1), y_data)\n",
    "    plt.xlim(0, iterations)\n",
    "\n",
    "target = 220\n",
    "    \n",
    "def func(x):\n",
    "    # This func is the Black Box Predicate (ie. the Oracle).\n",
    "    return 1 if x == target else 0\n",
    "    # This oracle also allows the search space to contain multiple matches.\n",
    "    # For example:\n",
    "    #   return 1 if x % 33 == 0 else 0\n",
    "    # \n",
    "    # In this case, the number of iterations (R) changes. To be specific:\n",
    "    #   R = (pi * arcsin(sqrt(M / N))) / 4\n",
    "    # where M is the number of matches in the search space of size N.\n",
    "    # (see 'Is Quantum Search Practical?' pg 24)\n",
    "    # Since Grover's Search is periodic after the optimal number of iterations,\n",
    "    # this adjustment is important.\n",
    "\n",
    "qubits = ceil(log(target, 2))\n",
    "space_size = 2 ** qubits\n",
    "iters = (np.pi/4) * sqrt(space_size).real\n",
    "print('target: {0} (bin = {0:b})'.format(target))\n",
    "print('qubits needed:', qubits)\n",
    "print('search space:', space_size)\n",
    "print('optimal iterations:', iters)\n",
    "grovers_plot(func, qubits=8)"
   ]
  }
 ],
 "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}