{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# IQC 2024/25 - Practical\n", "\n", "## Setup\n", "\n", "Install a clean Python environment and required modules: \n", "\n", "```bash\n", "python -m venv .venv\n", ".venv/bin/pip install pennylane matplotlib\n", "```\n", "\n", "Use `.venv/bin/python` as the Python kernel. \n", "\n", "Run imports below to test your environment. " ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "from matplotlib import pyplot as plt\n", "import numpy as np\n", "import pennylane as pl" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Part 1 – Classical Random Walk\n", "\n", "The random walk is a procedure, where at every time step an imaginary particle at given position has a random chance to move to next or previous position. The simplest example uses an unbiased coin to determine which direction to take. The goal of this exercise is for you to familiarise yourselves with the classical case before we move on to the quantum version. \n", "\n", "A very simple implementation of the random walk is given below. It simulates the position of the particle after *n* steps. Repeated calls can sample from different end positions. The probability $p$ can be modified for a biased coin. " ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAiwAAAGdCAYAAAAxCSikAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjkuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8hTgPZAAAACXBIWXMAAA9hAAAPYQGoP6dpAAAwU0lEQVR4nO3df1iVdZ7/8RdgnCMVWJIcNRJNEw2CxCSYJqersx0ado2mJWK60si1rY2ypYtJzKDJabEaSTfZcd0rra7GdLymyE2Glk7R1IA6Io7LZE61GaYd0PoKRQUGn+8fXR07eTQP/uADPh/XdV/B537fd+/P9UF5eZ/7PifMGGMEAABgsfD+bgAAAOCHEFgAAID1CCwAAMB6BBYAAGA9AgsAALAegQUAAFiPwAIAAKxHYAEAANYb0t8NnAi9vb3au3evzj77bIWFhfV3OwAA4BgYY/TZZ59p1KhRCg8/+jWUQRFY9u7dq/j4+P5uAwAA9MHu3bt1/vnnH7VmUASWs88+W9I3E46Oju7nbgAAwLHo6OhQfHy8//f40QyKwPLty0DR0dEEFgAABphjuZ2Dm24BAID1CCwAAMB6BBYAAGA9AgsAALAegQUAAFiPwAIAAKxHYAEAANYjsAAAAOv1KbBUVlYqISFBTqdT6enp2rx581Hr161bp8TERDmdTiUnJ6u6ujpg/+eff67CwkKdf/75Gjp0qCZPnqzly5f3pTUAADAIhRxY1q5dq6KiIpWVlWnr1q1KSUmRx+NRW1tb0Pr6+nrl5+dr9uzZampqUk5OjnJyctTc3OyvKSoqUk1NjZ577jnt2LFD9957rwoLC7V+/fq+zwwAAAwaYcYYE8oB6enpuuyyy7Rs2TJJ33xScnx8vO6++27NmzfvsPq8vDx1dnbq5Zdf9o9dfvnlSk1N9V9FSUpKUl5enh588EF/TVpamq699lr96le/+sGeOjo6FBMTo/b2dt6aHwCAASKU398hXWHp7u5WY2Oj3G73oROEh8vtdquhoSHoMQ0NDQH1kuTxeALqMzMztX79eu3Zs0fGGL3++uv629/+pmuuuSboObu6utTR0RGwAQCAwSukwLJ//3719PQoLi4uYDwuLk4+ny/oMT6f7wfrn3zySU2ePFnnn3++IiMjlZWVpcrKSl155ZVBz1leXq6YmBj/Fh8fH8o0AADAAGPFU0JPPvmkNm7cqPXr16uxsVGLFy/WXXfdpVdffTVofUlJidrb2/3b7t27T3HHAADgVBoSSnFsbKwiIiLU2toaMN7a2iqXyxX0GJfLddT6L7/8UvPnz9eLL76o7OxsSdIll1yibdu26de//vVhLydJksPhkMPhCKV1AANUwrwN/q93Lcrux04A9KeQrrBERkYqLS1NXq/XP9bb2yuv16uMjIygx2RkZATUS1Jtba2//uDBgzp48KDCwwNbiYiIUG9vbyjtAQCAQSqkKyzSN48gz5o1S1OnTtW0adO0ZMkSdXZ2qqCgQJI0c+ZMjR49WuXl5ZKkuXPnavr06Vq8eLGys7O1Zs0abdmyRStWrJAkRUdHa/r06SouLtbQoUM1ZswYvfHGG3r22WdVUVFxAqcKAAAGqpADS15envbt26fS0lL5fD6lpqaqpqbGf2NtS0tLwNWSzMxMrV69WgsWLND8+fM1YcIEVVVVKSkpyV+zZs0alZSU6Oabb9ann36qMWPG6JFHHtEdd9xxAqYIAAAGupDfh8VGvA8LMHhxDwsweJ2092EBAADoDwQWAABgPQILgAEnYd6GgJeKAAx+BBYAAGA9AgsAALAegQWAVXi5B0AwBBYAAGA9AgsAALAegQUAAFiPwAIAAKxHYAEAANYjsAAAAOsRWAAAgPUILAAAwHoEFgAAYD0CCwAAsB6BBQAAWI/AAgAArEdgAQAA1hvS3w0AwPH67qc771qU3Y+dADhZuMICAACsxxUWAP2GKyMAjhVXWAAAgPUILAAAwHoEFgAAYD0CCwAAsB6BBQAAWI/AAgAArEdgAQAA1iOwAAAA6xFYAACA9QgsAADAegQWAABgvT4FlsrKSiUkJMjpdCo9PV2bN28+av26deuUmJgop9Op5ORkVVdXB+wPCwsLuj3++ON9aQ8AAAwyIQeWtWvXqqioSGVlZdq6datSUlLk8XjU1tYWtL6+vl75+fmaPXu2mpqalJOTo5ycHDU3N/trPv7444Bt5cqVCgsL0w033ND3mQEAgEEj5MBSUVGhOXPmqKCgQJMnT9by5csVFRWllStXBq1funSpsrKyVFxcrEmTJmnhwoWaMmWKli1b5q9xuVwB20svvaSrrrpK48aN6/vMAADAoBFSYOnu7lZjY6PcbvehE4SHy+12q6GhIegxDQ0NAfWS5PF4jljf2tqqDRs2aPbs2Ufso6urSx0dHQEbAAAYvEIKLPv371dPT4/i4uICxuPi4uTz+YIe4/P5Qqp/5plndPbZZ+tnP/vZEfsoLy9XTEyMf4uPjw9lGgAAYICx7imhlStX6uabb5bT6TxiTUlJidrb2/3b7t27T2GHAADgVBsSSnFsbKwiIiLU2toaMN7a2iqXyxX0GJfLdcz1b775pnbu3Km1a9cetQ+HwyGHwxFK6wAAYAAL6QpLZGSk0tLS5PV6/WO9vb3yer3KyMgIekxGRkZAvSTV1tYGrX/qqaeUlpamlJSUUNoCAACDXEhXWCSpqKhIs2bN0tSpUzVt2jQtWbJEnZ2dKigokCTNnDlTo0ePVnl5uSRp7ty5mj59uhYvXqzs7GytWbNGW7Zs0YoVKwLO29HRoXXr1mnx4sUnYFoAAGAwCTmw5OXlad++fSotLZXP51Nqaqpqamr8N9a2tLQoPPzQhZvMzEytXr1aCxYs0Pz58zVhwgRVVVUpKSkp4Lxr1qyRMUb5+fnHOSUAADDYhBxYJKmwsFCFhYVB99XV1R02lpubq9zc3KOe8/bbb9ftt9/el3YAAMAgZ91TQgAAAN9HYAEAANYjsAAAAOsRWAAAgPUILAAGpYR5G5Qwb0N/twHgBCGwAAAA6xFYAACA9QgsAE4ZXqYB0FcEFgAAYD0CCwAAsB6BBQAAWI/AAgAArEdgAQAA1iOwAAAA6xFYAACA9QgsAADAegQWAABgPQILAACwHoEFAABYj8ACAACsR2ABAADWI7AAAADrEVgAAID1CCwAAMB6BBYAAGA9AgsAALAegQUAAFiPwAIAAKxHYAEAANYjsAAAAOsRWAAAgPUILAAAwHoEFgAAYL0+BZbKykolJCTI6XQqPT1dmzdvPmr9unXrlJiYKKfTqeTkZFVXVx9Ws2PHDs2YMUMxMTE688wzddlll6mlpaUv7QEAgEEm5MCydu1aFRUVqaysTFu3blVKSoo8Ho/a2tqC1tfX1ys/P1+zZ89WU1OTcnJylJOTo+bmZn/N+++/ryuuuEKJiYmqq6vT9u3b9eCDD8rpdPZ9ZgAAYNAIObBUVFRozpw5Kigo0OTJk7V8+XJFRUVp5cqVQeuXLl2qrKwsFRcXa9KkSVq4cKGmTJmiZcuW+WseeOAB/fSnP9Vjjz2mSy+9VBdeeKFmzJihESNG9H1mAABg0AgpsHR3d6uxsVFut/vQCcLD5Xa71dDQEPSYhoaGgHpJ8ng8/vre3l5t2LBBF110kTwej0aMGKH09HRVVVUdsY+uri51dHQEbAAAYPAKKbDs379fPT09iouLCxiPi4uTz+cLeozP5ztqfVtbmz7//HMtWrRIWVlZ+p//+R9df/31+tnPfqY33ngj6DnLy8sVExPj3+Lj40OZBgAAGGD6/Smh3t5eSdJ1112nf/3Xf1VqaqrmzZunv//7v9fy5cuDHlNSUqL29nb/tnv37lPZMgAAOMWGhFIcGxuriIgItba2Boy3trbK5XIFPcblch21PjY2VkOGDNHkyZMDaiZNmqS33nor6DkdDoccDkcorQMAgAEspCsskZGRSktLk9fr9Y/19vbK6/UqIyMj6DEZGRkB9ZJUW1vrr4+MjNRll12mnTt3BtT87W9/05gxY0JpDwAADFIhXWGRpKKiIs2aNUtTp07VtGnTtGTJEnV2dqqgoECSNHPmTI0ePVrl5eWSpLlz52r69OlavHixsrOztWbNGm3ZskUrVqzwn7O4uFh5eXm68sorddVVV6mmpkb//d//rbq6uhMzSwAAMKCFHFjy8vK0b98+lZaWyufzKTU1VTU1Nf4ba1taWhQefujCTWZmplavXq0FCxZo/vz5mjBhgqqqqpSUlOSvuf7667V8+XKVl5frnnvu0cSJE/X73/9eV1xxxQmYIgAAGOhCDiySVFhYqMLCwqD7gl0Vyc3NVW5u7lHPedttt+m2227rSzsAAGCQ6/enhAAAAH4IgQUAAFivTy8JAcBAkzBvg//rXYuy+7ETAH1BYAFwUhAQAJxIvCQEAACsR2ABAADWI7AAAADrEVgAAID1CCwAAMB6BBYAAGA9AgsAALAegQUAAFiPwAIAAKxHYAEAANYjsAAAAOsRWAAAgPUILAAAwHoEFgAAYD0CCwAAsB6BBQAAWI/AAgAArEdgAQAA1iOwAAAA6xFYAACA9QgsAADAegQWAABgPQILAACwHoEFAABYj8ACAACsR2ABAADWI7AAAADrEVgAAID1CCwAAMB6BBYAAGC9PgWWyspKJSQkyOl0Kj09XZs3bz5q/bp165SYmCin06nk5GRVV1cH7L/11lsVFhYWsGVlZfWlNQAAMAiFHFjWrl2roqIilZWVaevWrUpJSZHH41FbW1vQ+vr6euXn52v27NlqampSTk6OcnJy1NzcHFCXlZWljz/+2L89//zzfZsRAAAYdEIOLBUVFZozZ44KCgo0efJkLV++XFFRUVq5cmXQ+qVLlyorK0vFxcWaNGmSFi5cqClTpmjZsmUBdQ6HQy6Xy7+dc845fZsRAAAYdEIKLN3d3WpsbJTb7T50gvBwud1uNTQ0BD2moaEhoF6SPB7PYfV1dXUaMWKEJk6cqDvvvFOffPLJEfvo6upSR0dHwAYAAAavkALL/v371dPTo7i4uIDxuLg4+Xy+oMf4fL4frM/KytKzzz4rr9erRx99VG+88YauvfZa9fT0BD1neXm5YmJi/Ft8fHwo0wAAAAPMkP5uQJJuuukm/9fJycm65JJLdOGFF6qurk5XX331YfUlJSUqKiryf9/R0UFoAQBgEAvpCktsbKwiIiLU2toaMN7a2iqXyxX0GJfLFVK9JI0bN06xsbF67733gu53OByKjo4O2AAAwOAVUmCJjIxUWlqavF6vf6y3t1der1cZGRlBj8nIyAiol6Ta2toj1kvSRx99pE8++UQjR44MpT0AADBIhfyUUFFRkf7rv/5LzzzzjHbs2KE777xTnZ2dKigokCTNnDlTJSUl/vq5c+eqpqZGixcv1jvvvKOHHnpIW7ZsUWFhoSTp888/V3FxsTZu3Khdu3bJ6/Xquuuu0/jx4+XxeE7QNAEAwEAW8j0seXl52rdvn0pLS+Xz+ZSamqqamhr/jbUtLS0KDz+UgzIzM7V69WotWLBA8+fP14QJE1RVVaWkpCRJUkREhLZv365nnnlGBw4c0KhRo3TNNddo4cKFcjgcJ2iaAABgIOvTTbeFhYX+KyTfV1dXd9hYbm6ucnNzg9YPHTpUr7zySl/aAAAApwk+SwgAAFiPwALghEiYt0EJ8zb0dxsABikCC4DTFiELGDgILAAAwHoEFgAAYD0CCwAAsB6BBQAAWI/AAgAArEdgAQAA1iOwAAAA6xFYAACA9QgsAADAegQWAABgPQILAACwHoEFAABYj8ACAACsR2ABAADWI7AAAADrEVgAAID1CCwAAMB6BBYAAGA9AgsAALAegQUAAFiPwAIAAKxHYAEAANYjsAAAAOsRWAAAgPUILAAAwHoEFgAAYD0CCwAAsB6BBQAAWI/AAgAArEdgAQAA1utTYKmsrFRCQoKcTqfS09O1efPmo9avW7dOiYmJcjqdSk5OVnV19RFr77jjDoWFhWnJkiV9aQ0AAAxCIQeWtWvXqqioSGVlZdq6datSUlLk8XjU1tYWtL6+vl75+fmaPXu2mpqalJOTo5ycHDU3Nx9W++KLL2rjxo0aNWpU6DMBAACDVsiBpaKiQnPmzFFBQYEmT56s5cuXKyoqSitXrgxav3TpUmVlZam4uFiTJk3SwoULNWXKFC1btiygbs+ePbr77rv129/+VmeccUbfZgMAAAalkAJLd3e3Ghsb5Xa7D50gPFxut1sNDQ1Bj2loaAiolySPxxNQ39vbq1tuuUXFxcW6+OKLf7CPrq4udXR0BGwAAGDwCimw7N+/Xz09PYqLiwsYj4uLk8/nC3qMz+f7wfpHH31UQ4YM0T333HNMfZSXlysmJsa/xcfHhzINAAAwwPT7U0KNjY1aunSpnn76aYWFhR3TMSUlJWpvb/dvu3fvPsldAgCA/jQklOLY2FhFRESotbU1YLy1tVUulyvoMS6X66j1b775ptra2nTBBRf49/f09Oi+++7TkiVLtGvXrsPO6XA45HA4QmkdwAmUMG+D/+tdi7L7sRMAp4uQrrBERkYqLS1NXq/XP9bb2yuv16uMjIygx2RkZATUS1Jtba2//pZbbtH27du1bds2/zZq1CgVFxfrlVdeCXU+AABgEArpCoskFRUVadasWZo6daqmTZumJUuWqLOzUwUFBZKkmTNnavTo0SovL5ckzZ07V9OnT9fixYuVnZ2tNWvWaMuWLVqxYoUkafjw4Ro+fHjA/+OMM86Qy+XSxIkTj3d+AABgEAg5sOTl5Wnfvn0qLS2Vz+dTamqqampq/DfWtrS0KDz80IWbzMxMrV69WgsWLND8+fM1YcIEVVVVKSkp6cTNAgAADGohBxZJKiwsVGFhYdB9dXV1h43l5uYqNzf3mM8f7L4VADjZuDcHsFe/PyUEAADwQwgsAADAegQWAABgPQILAACwHoEFAABYj8ACAACsR2ABAADWI7AAAADrEVgAAID1CCwAAMB6BBYAAGA9AgsAALAegQUAAFiPwAIAAKxHYAEAANYjsAAAAOsRWAAAgPUILAAAwHoEFgAAYD0CCwAAsB6BBQAAWI/AAgAArEdgAQAA1iOwAAAA6xFYAACA9QgsAADAegQWAABgPQILAACwHoEFAABYj8ACAACsR2ABAADWI7AAAADrEVgAAID1+hRYKisrlZCQIKfTqfT0dG3evPmo9evWrVNiYqKcTqeSk5NVXV0dsP+hhx5SYmKizjzzTJ1zzjlyu93atGlTX1oDAACDUMiBZe3atSoqKlJZWZm2bt2qlJQUeTwetbW1Ba2vr69Xfn6+Zs+eraamJuXk5CgnJ0fNzc3+mosuukjLli3T//7v/+qtt95SQkKCrrnmGu3bt6/vMwMAAINGyIGloqJCc+bMUUFBgSZPnqzly5crKipKK1euDFq/dOlSZWVlqbi4WJMmTdLChQs1ZcoULVu2zF/z85//XG63W+PGjdPFF1+siooKdXR0aPv27X2fGYATJmHeBiXM29DfbQA4jYUUWLq7u9XY2Ci3233oBOHhcrvdamhoCHpMQ0NDQL0keTyeI9Z3d3drxYoViomJUUpKStCarq4udXR0BGwAAGDwCimw7N+/Xz09PYqLiwsYj4uLk8/nC3qMz+c7pvqXX35ZZ511lpxOp5544gnV1tYqNjY26DnLy8sVExPj3+Lj40OZBgAAGGCseUroqquu0rZt21RfX6+srCzdeOONR7wvpqSkRO3t7f5t9+7dp7hbAABwKoUUWGJjYxUREaHW1taA8dbWVrlcrqDHuFyuY6o/88wzNX78eF1++eV66qmnNGTIED311FNBz+lwOBQdHR2wAQCAwSukwBIZGam0tDR5vV7/WG9vr7xerzIyMoIek5GREVAvSbW1tUes/+55u7q6QmkPAAAMUkNCPaCoqEizZs3S1KlTNW3aNC1ZskSdnZ0qKCiQJM2cOVOjR49WeXm5JGnu3LmaPn26Fi9erOzsbK1Zs0ZbtmzRihUrJEmdnZ165JFHNGPGDI0cOVL79+9XZWWl9uzZo9zc3BM4VQAI3bdPR+1alN3PnQCnt5ADS15envbt26fS0lL5fD6lpqaqpqbGf2NtS0uLwsMPXbjJzMzU6tWrtWDBAs2fP18TJkxQVVWVkpKSJEkRERF655139Mwzz2j//v0aPny4LrvsMr355pu6+OKLT9A0AQDAQBZyYJGkwsJCFRYWBt1XV1d32Fhubu4Rr5Y4nU698MILfWkDAACcJqx5SggAAOBICCwAAMB6BBYAAGA9AgsAALAegQUAAFiPwAIAAKxHYAEAANYjsAAAAOsRWAAAgPUILAAAwHoEFgAAYD0CCwAAsB6BBQAAWI/AAgAArEdgAQAA1iOwAAAA6xFYAACA9QgsAADAegQWAABgPQILAACwHoEFAABYj8ACAACsR2ABAADWI7AAAADrEVgAAID1CCwAAMB6Q/q7AQB2SZi3wf/1rkXZ/dgJABzCFRYAAGA9AgsAhCBh3oaAq1AATg0CCwAAsB6BBQAAWI/AAgAArEdgAQAA1iOwAAAA6/UpsFRWViohIUFOp1Pp6enavHnzUevXrVunxMREOZ1OJScnq7q62r/v4MGDuv/++5WcnKwzzzxTo0aN0syZM7V3796+tAYAAAahkAPL2rVrVVRUpLKyMm3dulUpKSnyeDxqa2sLWl9fX6/8/HzNnj1bTU1NysnJUU5OjpqbmyVJX3zxhbZu3aoHH3xQW7du1QsvvKCdO3dqxowZxzczAAAwaIQcWCoqKjRnzhwVFBRo8uTJWr58uaKiorRy5cqg9UuXLlVWVpaKi4s1adIkLVy4UFOmTNGyZcskSTExMaqtrdWNN96oiRMn6vLLL9eyZcvU2NiolpaW45sdAAAYFEIKLN3d3WpsbJTb7T50gvBwud1uNTQ0BD2moaEhoF6SPB7PEeslqb29XWFhYRo2bFjQ/V1dXero6AjYAADA4BVSYNm/f796enoUFxcXMB4XFyefzxf0GJ/PF1L9V199pfvvv1/5+fmKjo4OWlNeXq6YmBj/Fh8fH8o0AADAAGPVU0IHDx7UjTfeKGOMfvOb3xyxrqSkRO3t7f5t9+7dp7BLAABwqoX0ac2xsbGKiIhQa2trwHhra6tcLlfQY1wu1zHVfxtWPvzwQ7322mtHvLoiSQ6HQw6HI5TWAQDAABbSFZbIyEilpaXJ6/X6x3p7e+X1epWRkRH0mIyMjIB6SaqtrQ2o/zasvPvuu3r11Vc1fPjwUNoCAACDXEhXWCSpqKhIs2bN0tSpUzVt2jQtWbJEnZ2dKigokCTNnDlTo0ePVnl5uSRp7ty5mj59uhYvXqzs7GytWbNGW7Zs0YoVKyR9E1b+8R//UVu3btXLL7+snp4e//0t5557riIjI0/UXAEAwAAVcmDJy8vTvn37VFpaKp/Pp9TUVNXU1PhvrG1paVF4+KELN5mZmVq9erUWLFig+fPna8KECaqqqlJSUpIkac+ePVq/fr0kKTU1NeD/9frrr+snP/lJH6cGAAAGi5ADiyQVFhaqsLAw6L66urrDxnJzc5Wbmxu0PiEhQcaYvrQBAABOE1Y9JQQAABAMgQUAAFiPwAIAAKxHYAEAANYjsAAAAOsRWAAAgPUILAAAwHoEFgAAYD0CCwAAsB6BBQAAWI/AApzmEuZtUMK8Df3dBgAcFYEFAABYj8ACAMeJq1TAyUdgAQAA1iOwAAAA6xFYAACA9QgsAADAegQWAABgPQILAACwHoEFAABYj8ACAACsR2ABAADWI7AAAADrEVgAAID1CCwAAMB6BBYAAGA9AgsAALAegQUAAFiPwAIAAKxHYAEAANYjsAAAAOsN6e8GAJw6CfM2+L/etSi7HzsBgNBwhQUAAFivT4GlsrJSCQkJcjqdSk9P1+bNm49av27dOiUmJsrpdCo5OVnV1dUB+1944QVdc801Gj58uMLCwrRt27a+tAUAAAapkAPL2rVrVVRUpLKyMm3dulUpKSnyeDxqa2sLWl9fX6/8/HzNnj1bTU1NysnJUU5Ojpqbm/01nZ2duuKKK/Too4/2fSYAAGDQCjmwVFRUaM6cOSooKNDkyZO1fPlyRUVFaeXKlUHrly5dqqysLBUXF2vSpElauHChpkyZomXLlvlrbrnlFpWWlsrtdvd9JgAAYNAKKbB0d3ersbExIFiEh4fL7XaroaEh6DENDQ2HBRGPx3PE+mPR1dWljo6OgA0AbJEwb0PADc4Ajl9IgWX//v3q6elRXFxcwHhcXJx8Pl/QY3w+X0j1x6K8vFwxMTH+LT4+vs/nAgAA9huQTwmVlJSovb3dv+3evbu/WwIAACdRSO/DEhsbq4iICLW2tgaMt7a2yuVyBT3G5XKFVH8sHA6HHA5Hn48HAAADS0hXWCIjI5WWliav1+sf6+3tldfrVUZGRtBjMjIyAuolqba29oj1AAAA3xfyO90WFRVp1qxZmjp1qqZNm6YlS5aos7NTBQUFkqSZM2dq9OjRKi8vlyTNnTtX06dP1+LFi5Wdna01a9Zoy5YtWrFihf+cn376qVpaWrR3715J0s6dOyV9c3XmeK7EAACAwSHkwJKXl6d9+/aptLRUPp9Pqampqqmp8d9Y29LSovDwQxduMjMztXr1ai1YsEDz58/XhAkTVFVVpaSkJH/N+vXr/YFHkm666SZJUllZmR566KG+zg0AAAwSffosocLCQhUWFgbdV1dXd9hYbm6ucnNzj3i+W2+9VbfeemtfWgEAAKeBAfmUEAAAOL0QWAAAgPUILAAAwHoEFgAAYD0CCwAAsB6BBQBOAT4QETg+BBYAAGA9AgswiPGvegCDBYEFAABYj8ACAACsR2ABAADWI7AAAADrEVgAAID1CCwAAMB6BBYAAGA9AgsAALAegQUAAFiPwAIA/YB3IQZCQ2ABBhF+CQIYrAgsAADAegQWAABgPQILAACwHoEFAABYj8ACAACsR2ABAADWI7AAgCV4LB04MgILMEDxyw3A6YTAAgAArEdgAQAA1iOwAAAA6xFYgAGCe1YAnM4ILABgKUIqcAiBBQAAWK9PgaWyslIJCQlyOp1KT0/X5s2bj1q/bt06JSYmyul0Kjk5WdXV1QH7jTEqLS3VyJEjNXToULndbr377rt9aQ0YFPiXNY6Enw2crkIOLGvXrlVRUZHKysq0detWpaSkyOPxqK2tLWh9fX298vPzNXv2bDU1NSknJ0c5OTlqbm721zz22GP693//dy1fvlybNm3SmWeeKY/Ho6+++qrvMwMAAINGyIGloqJCc+bMUUFBgSZPnqzly5crKipKK1euDFq/dOlSZWVlqbi4WJMmTdLChQs1ZcoULVu2TNI3V1eWLFmiBQsW6LrrrtMll1yiZ599Vnv37lVVVdVxTQ4YKPhXM/qKnx2cLoaEUtzd3a3GxkaVlJT4x8LDw+V2u9XQ0BD0mIaGBhUVFQWMeTwefxj54IMP5PP55Ha7/ftjYmKUnp6uhoYG3XTTTYeds6urS11dXf7v29vbJUkdHR2hTAfoF0llr0iSmn/p8Y/1dn0h6dDP8Pe/P1E1335PzfHXnOi1OZE1wX7GABt9+3NrjPnhYhOCPXv2GEmmvr4+YLy4uNhMmzYt6DFnnHGGWb16dcBYZWWlGTFihDHGmD/96U9Gktm7d29ATW5urrnxxhuDnrOsrMxIYmNjY2NjYxsE2+7du38wg4R0hcUWJSUlAVdtent79emnn2r48OEKCws74f+/jo4OxcfHa/fu3YqOjj7h5+9vzG9gY34D32CfI/Mb2E7m/Iwx+uyzzzRq1KgfrA0psMTGxioiIkKtra0B462trXK5XEGPcblcR63/9r+tra0aOXJkQE1qamrQczocDjkcjoCxYcOGhTKVPomOjh6UP4zfYn4DG/Mb+Ab7HJnfwHay5hcTE3NMdSHddBsZGam0tDR5vV7/WG9vr7xerzIyMoIek5GREVAvSbW1tf76sWPHyuVyBdR0dHRo06ZNRzwnAAA4vYT8klBRUZFmzZqlqVOnatq0aVqyZIk6OztVUFAgSZo5c6ZGjx6t8vJySdLcuXM1ffp0LV68WNnZ2VqzZo22bNmiFStWSJLCwsJ077336le/+pUmTJigsWPH6sEHH9SoUaOUk5Nz4mYKAAAGrJADS15envbt26fS0lL5fD6lpqaqpqZGcXFxkqSWlhaFhx+6cJOZmanVq1drwYIFmj9/viZMmKCqqiolJSX5a37xi1+os7NTt99+uw4cOKArrrhCNTU1cjqdJ2CKx8/hcKisrOywl6EGC+Y3sDG/gW+wz5H5DWy2zC/MmGN5lggAAKD/8FlCAADAegQWAABgPQILAACwHoEFAABYj8DyPY888ogyMzMVFRV1xDeja2lpUXZ2tqKiojRixAgVFxfr66+/Dqipq6vTlClT5HA4NH78eD399NMnv/kQ1dXVKSwsLOj25z//WZK0a9euoPs3btzYz90fm4SEhMN6X7RoUUDN9u3b9eMf/1hOp1Px8fF67LHH+qnb0OzatUuzZ8/W2LFjNXToUF144YUqKytTd3d3QM1AXj9JqqysVEJCgpxOp9LT07V58+b+bqlPysvLddlll+nss8/WiBEjlJOTo507dwbU/OQnPzlsre64445+6jg0Dz300GG9JyYm+vd/9dVXuuuuuzR8+HCdddZZuuGGGw57U1GbBfu7JCwsTHfddZekgbd2f/zjH/UP//APGjVqlMLCwg77sGFjjEpLSzVy5EgNHTpUbrdb7777bkDNp59+qptvvlnR0dEaNmyYZs+erc8///zkNf2Db95/miktLTUVFRWmqKjIxMTEHLb/66+/NklJScbtdpumpiZTXV1tYmNjTUlJib/m//7v/0xUVJQpKioyb7/9tnnyySdNRESEqampOYUz+WFdXV3m448/Dtj+6Z/+yYwdO9b09vYaY4z54IMPjCTz6quvBtR1d3f3c/fHZsyYMebhhx8O6P3zzz/3729vbzdxcXHm5ptvNs3Nzeb55583Q4cONf/5n//Zj10fmz/84Q/m1ltvNa+88op5//33zUsvvWRGjBhh7rvvPn/NQF+/NWvWmMjISLNy5Urz17/+1cyZM8cMGzbMtLa29ndrIfN4PGbVqlWmubnZbNu2zfz0pz81F1xwQcDP4/Tp082cOXMC1qq9vb0fuz52ZWVl5uKLLw7ofd++ff79d9xxh4mPjzder9ds2bLFXH755SYzM7MfOw5NW1tbwNxqa2uNJPP6668bYwbe2lVXV5sHHnjAvPDCC0aSefHFFwP2L1q0yMTExJiqqirzl7/8xcyYMcOMHTvWfPnll/6arKwsk5KSYjZu3GjefPNNM378eJOfn3/SeiawHMGqVauCBpbq6moTHh5ufD6ff+w3v/mNiY6ONl1dXcYYY37xi1+Yiy++OOC4vLw84/F4TmrPx6u7u9ucd9555uGHH/aPffsLr6mpqf8aOw5jxowxTzzxxBH3/8d//Ic555xz/GtnjDH333+/mThx4ino7sR77LHHzNixY/3fD/T1mzZtmrnrrrv83/f09JhRo0aZ8vLyfuzqxGhrazOSzBtvvOEfmz59upk7d27/NXUcysrKTEpKStB9Bw4cMGeccYZZt26df2zHjh1GkmloaDhFHZ5Yc+fONRdeeKH/H3cDee2+H1h6e3uNy+Uyjz/+uH/swIEDxuFwmOeff94YY8zbb79tJJk///nP/po//OEPJiwszOzZs+ek9MlLQiFqaGhQcnKy/43yJMnj8aijo0N//etf/TVutzvgOI/Ho4aGhlPaa6jWr1+vTz75xP+uxd81Y8YMjRgxQldccYXWr1/fD9313aJFizR8+HBdeumlevzxxwNevmtoaNCVV16pyMhI/5jH49HOnTv1//7f/+uPdo9Le3u7zj333MPGB+L6dXd3q7GxMeDPUnh4uNxut/V/lo5Fe3u7JB22Xr/97W8VGxurpKQklZSU6IsvvuiP9vrk3Xff1ahRozRu3DjdfPPNamlpkSQ1Njbq4MGDAWuZmJioCy64YECuZXd3t5577jnddtttAR+4O5DX7rs++OAD+Xy+gPWKiYlRenq6f70aGho0bNgwTZ061V/jdrsVHh6uTZs2nZS+BuSnNfcnn88XEFYk+b/3+XxHreno6NCXX36poUOHnppmQ/TUU0/J4/Ho/PPP94+dddZZWrx4sX70ox8pPDxcv//975WTk6OqqirNmDGjH7s9Nvfcc4+mTJmic889V/X19SopKdHHH3+siooKSd+s1dixYwOO+e56nnPOOae8575677339OSTT+rXv/61f2wgr9/+/fvV09MT9M/SO++8009dnRi9vb2699579aMf/SjgXb9//vOfa8yYMRo1apS2b9+u+++/Xzt37tQLL7zQj90em/T0dD399NOaOHGiPv74Y/3yl7/Uj3/8YzU3N8vn8ykyMvKw+wLj4uL8f28OJFVVVTpw4IBuvfVW/9hAXrvv+3ZNgv3Z++7vuREjRgTsHzJkiM4999yTtqanRWCZN2+eHn300aPW7NixI+AGsYGsL/P96KOP9Morr+h3v/tdQF1sbKyKior831922WXau3evHn/88X77hRfK/L7b+yWXXKLIyEj98z//s8rLy/v9baaPpC/rt2fPHmVlZSk3N1dz5szxj9u4fpDuuusuNTc366233goYv/322/1fJycna+TIkbr66qv1/vvv68ILLzzVbYbk2muv9X99ySWXKD09XWPGjNHvfvc7a/+R1ldPPfWUrr32Wo0aNco/NpDXbqA4LQLLfffdF5CEgxk3btwxncvlch32lMK3d7q7XC7/f79/93tra6uio6NPyR/cvsx31apVGj58+DH9EktPT1dtbe3xtHhcjmc909PT9fXXX2vXrl2aOHHiEddKOrSep1qo89u7d6+uuuoqZWZm+j9U9Gj6e/2OVWxsrCIiIoKuT3+tzYlQWFiol19+WX/84x8DrmYGk56eLumbq2cD7ZfesGHDdNFFF+m9997T3/3d36m7u1sHDhwIuMoyENfyww8/1KuvvvqDV04G8tp9uyatra0aOXKkf7y1tVWpqan+mra2toDjvv76a3366acnbU1Pi8By3nnn6bzzzjsh58rIyNAjjzyitrY2/+Ww2tpaRUdHa/Lkyf6a6urqgONqa2uVkZFxQnr4IaHO1xijVatWaebMmTrjjDN+sH7btm0BP8Sn2vGs57Zt2xQeHu5fu4yMDD3wwAM6ePCgf+61tbWaOHFiv70cFMr89uzZo6uuukppaWlatWpVwAePHkl/r9+xioyMVFpamrxer/+T23t7e+X1elVYWNi/zfWBMUZ33323XnzxRdXV1R32UmQw27Ztk6QBsV7f9/nnn+v999/XLbfcorS0NJ1xxhnyer264YYbJEk7d+5US0vLKft78URZtWqVRowYoezs7KPWDeS1Gzt2rFwul7xerz+gdHR0aNOmTbrzzjslffN354EDB9TY2Ki0tDRJ0muvvabe3l5/WDvhTsqtvAPYhx9+aJqamswvf/lLc9ZZZ5mmpibT1NRkPvvsM2PMocear7nmGrNt2zZTU1NjzjvvvKCPNRcXF5sdO3aYyspKKx9r/tarr75qJJkdO3Yctu/pp582q1evNjt27DA7duwwjzzyiAkPDzcrV67sh05DU19fb5544gmzbds28/7775vnnnvOnHfeeWbmzJn+mgMHDpi4uDhzyy23mObmZrNmzRoTFRU1IB5r/uijj8z48ePN1VdfbT766KOAxym/NZDXz5hvHmt2OBzm6aefNm+//ba5/fbbzbBhwwKe0hso7rzzThMTE2Pq6uoC1uqLL74wxhjz3nvvmYcffths2bLFfPDBB+all14y48aNM1deeWU/d35s7rvvPlNXV2c++OAD86c//cm43W4TGxtr2trajDHfPNZ8wQUXmNdee81s2bLFZGRkmIyMjH7uOjQ9PT3mggsuMPfff3/A+EBcu88++8z/+02SqaioME1NTebDDz80xnzzWPOwYcPMSy+9ZLZv326uu+66oI81X3rppWbTpk3mrbfeMhMmTOCx5lNp1qxZRtJh27fP2htjzK5du8y1115rhg4damJjY819991nDh48GHCe119/3aSmpprIyEgzbtw4s2rVqlM7kRDk5+cf8f0Qnn76aTNp0iQTFRVloqOjzbRp0wIeTbRZY2OjSU9PNzExMcbpdJpJkyaZf/u3fzNfffVVQN1f/vIXc8UVVxiHw2FGjx5tFi1a1E8dh2bVqlVBf1a/+++Qgbx+33ryySfNBRdcYCIjI820adPMxo0b+7ulPjnSWn37d0NLS4u58sorzbnnnmscDocZP368KS4utvq9PL4rLy/PjBw50kRGRprRo0ebvLw889577/n3f/nll+Zf/uVfzDnnnGOioqLM9ddfHxCuB4JXXnnFSDI7d+4MGB+Ia/f6668H/XmcNWuWMeabR5sffPBBExcXZxwOh7n66qsPm/cnn3xi8vPzzVlnnWWio6NNQUGB/x/3J0OYMcacnGs3AAAAJwbvwwIAAKxHYAEAANYjsAAAAOsRWAAAgPUILAAAwHoEFgAAYD0CCwAAsB6BBQAAWI/AAgAArEdgAQAA1iOwAAAA6xFYAACA9f4/rtwme8gjOuoAAAAASUVORK5CYII=", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "def random_walk(T, start = 0, p = .5):\n", " # Create a random sequence of 1 and -1 values. \n", " steps = np.random.choice([1, -1], T, p = [p, 1 - p])\n", " return np.sum(steps)\n", "\n", "N_STEPS = 100\n", "N_SAMPLES = 100000\n", "walks = [random_walk(N_STEPS) for _ in range(N_SAMPLES)]\n", "plt.hist(walks, bins = 2 * N_STEPS + 1, density = True, range = (-N_STEPS - .5, N_STEPS + .5))\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The walk above can reach any point in space. As in practice the size of the quantum register is finite, it is useful to add **boundary conditions** to the problem. In such a case, the particle is contained in a box of $n$ positions, from $0$ to $n - 1$, and start at position $\\lfloor n / 2 \\rfloor$. If the position exceeds the range of the box, the particle moves to the other side, i.e. from $0$ to $n - 1$, and from $n - 1$ to $0$. This can be visualised as if the particle was moving on a ring with first and last position connected. " ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAiwAAAGdCAYAAAAxCSikAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjkuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8hTgPZAAAACXBIWXMAAA9hAAAPYQGoP6dpAAAsNUlEQVR4nO3dfVScdX7//xc3gTFRUMOGSWIMiWIIQqAhgpP6NWszJ4OlNaNbRNZjEGk82rCbLFtqSCO4ze4huoUmCmdpWlP1dCMprUZXU3ZxVlLdjGa5yYm0JqueKFmTgaBHUDSQA9fvD4+T35jJzSAJH8bn45zrCNe8ryvv9/kkx9e55rpmIizLsgQAAGCwyIluAAAA4FwILAAAwHgEFgAAYDwCCwAAMB6BBQAAGI/AAgAAjEdgAQAAxiOwAAAA40VPdAPjYXR0VEePHtVll12miIiIiW4HAACcB8uy9Omnn2rWrFmKjDz7NZSwCCxHjx7VnDlzJroNAAAwBkeOHNFVV1111pqwCCyXXXaZpC8HjouLm+BuAADA+RgYGNCcOXP8/x8/m7AILF+9DRQXF0dgAQBgkjmf2zm46RYAABiPwAIAAIxHYAEAAMYjsAAAAOMRWAAAgPEILAAAwHgEFgAAYDwCCwAAMB6BBQAAGI/AAgAAjEdgAQAAxiOwAAAA440psNTX1yspKUk2m005OTnat2/fWeubmpqUkpIim82m9PR07d69O+D1zz77TKWlpbrqqqt0ySWXKDU1VQ0NDWNpDQAAhKGQA8vOnTtVVlamqqoqdXR0KCMjQy6XS729vUHr9+7dq8LCQpWUlKizs1Nut1tut1tdXV3+mrKyMjU3N+vf//3f9fbbb2vdunUqLS3Viy++OPbJAABA2IiwLMsK5YCcnBzdcMMNqqurkySNjo5qzpw5+sEPfqD169efVl9QUKDBwUG99NJL/n033nijMjMz/VdR0tLSVFBQoIcffthfk5WVpVtvvVU//elPz9nTwMCA4uPj1d/fr7i4uFDGATAJJK1/OaT69zfnXaBOAIynUP7/HdIVluHhYbW3t8vpdJ46QWSknE6nvF5v0GO8Xm9AvSS5XK6A+qVLl+rFF1/Uhx9+KMuy9Oqrr+oPf/iDVqxYEfScQ0NDGhgYCNgAAED4Cimw9PX1aWRkRImJiQH7ExMT5fP5gh7j8/nOWf/EE08oNTVVV111lWJiYpSbm6v6+nrdfPPNQc9ZXV2t+Ph4/zZnzpxQxgAAAJOMEU8JPfHEE3rjjTf04osvqr29XTU1NVqzZo1eeeWVoPUVFRXq7+/3b0eOHLnIHQMAgIspOpTihIQERUVFqaenJ2B/T0+P7HZ70GPsdvtZ67/44gtt2LBBzz//vPLyvnzfedGiRdq/f7/+8R//8bS3kyQpNjZWsbGxobQOAAAmsZACS0xMjLKysuTxeOR2uyV9edOtx+NRaWlp0GMcDoc8Ho/WrVvn39fS0iKHwyFJOnnypE6ePKnIyMCLPVFRURodHQ2lPQATLJSbY7kxFkAoQgos0pePIBcVFWnJkiXKzs7Wli1bNDg4qOLiYknSqlWrNHv2bFVXV0uS1q5dq2XLlqmmpkZ5eXlqbGxUW1ubtm3bJkmKi4vTsmXLVF5erksuuURz587Vnj179Mwzz6i2tnYcRwUAAJNVyIGloKBAx48fV2VlpXw+nzIzM9Xc3Oy/sba7uzvgasnSpUu1Y8cObdy4URs2bFBycrJ27dqltLQ0f01jY6MqKip099136+OPP9bcuXP1s5/9TA888MA4jAgAACa7kD+HxUR8Dgtghgv1lhCfwwKEpwv2OSwAAAATgcACAACMR2ABAADGI7AAAADjEVgAAIDxCCwAAMB4BBYAAGC8kD84DgDCCV8nAEwOXGEBAADGI7AAAADjEVgAAIDxCCwAAMB4BBYAAGA8AgsAADAegQUAABiPwAIAAIzHB8cBwAXCh9IB44crLAAAwHgEFgAAYDwCCwAAMB6BBQAAGI/AAgAAjEdgAQAAxiOwAAAA4xFYAACA8QgsAADAeAQWAABgPAILAAAwHt8lBHzLhPL9NhLfcQPADFxhAQAAxiOwAAAA4xFYAACA8cYUWOrr65WUlCSbzaacnBzt27fvrPVNTU1KSUmRzWZTenq6du/eHfB6RERE0O3nP//5WNoDAABhJuTAsnPnTpWVlamqqkodHR3KyMiQy+VSb29v0Pq9e/eqsLBQJSUl6uzslNvtltvtVldXl7/m2LFjAdv27dsVERGh733ve2OfDAAAhI2QA0ttba1Wr16t4uJipaamqqGhQVOnTtX27duD1m/dulW5ubkqLy/XwoULtWnTJi1evFh1dXX+GrvdHrC98MILuuWWWzR//vyxTwYAAMJGSIFleHhY7e3tcjqdp04QGSmn0ymv1xv0GK/XG1AvSS6X64z1PT09evnll1VSUhJKawAAIIyF9DksfX19GhkZUWJiYsD+xMREHTx4MOgxPp8vaL3P5wta//TTT+uyyy7THXfcccY+hoaGNDQ05P99YGDgfEcAAACTkHFPCW3fvl133323bDbbGWuqq6sVHx/v3+bMmXMROwQAABdbSIElISFBUVFR6unpCdjf09Mju90e9Bi73X7e9a+99poOHTqkv/7rvz5rHxUVFerv7/dvR44cCWUMAAAwyYQUWGJiYpSVlSWPx+PfNzo6Ko/HI4fDEfQYh8MRUC9JLS0tQeuffPJJZWVlKSMj46x9xMbGKi4uLmADAADhK+TvEiorK1NRUZGWLFmi7OxsbdmyRYODgyouLpYkrVq1SrNnz1Z1dbUkae3atVq2bJlqamqUl5enxsZGtbW1adu2bQHnHRgYUFNTk2pqasZhLAAAEE5CDiwFBQU6fvy4Kisr5fP5lJmZqebmZv+Ntd3d3YqMPHXhZunSpdqxY4c2btyoDRs2KDk5Wbt27VJaWlrAeRsbG2VZlgoLC7/hSAAAINyM6duaS0tLVVpaGvS11tbW0/bl5+crPz//rOe8//77df/994+lHQAAEOaMe0oIAADg6wgsAADAeAQWAABgvDHdwwIAmDhJ618+79r3N+ddwE6Ai4crLAAAwHgEFgAAYDwCCwAAMB73sACG4j4FADiFKywAAMB4BBYAAGA8AgsAADAegQUAABiPwAIAAIxHYAEAAMYjsAAAAOMRWAAAgPEILAAAwHgEFgAAYDwCCwAAMB6BBQAAGI/AAgAAjEdgAQAAxiOwAAAA4xFYAACA8QgsAADAeAQWAABgPAILAAAwHoEFAAAYj8ACAACMR2ABAADGI7AAAADjEVgAAIDxCCwAAMB4Ywos9fX1SkpKks1mU05Ojvbt23fW+qamJqWkpMhmsyk9PV27d+8+rebtt9/Wbbfdpvj4eE2bNk033HCDuru7x9IeAAAIMyEHlp07d6qsrExVVVXq6OhQRkaGXC6Xent7g9bv3btXhYWFKikpUWdnp9xut9xut7q6uvw17733nm666SalpKSotbVVBw4c0MMPPyybzTb2yQAAQNgIObDU1tZq9erVKi4uVmpqqhoaGjR16lRt3749aP3WrVuVm5ur8vJyLVy4UJs2bdLixYtVV1fnr/n7v/97/fmf/7kee+wx/cmf/ImuueYa3XbbbZoxY8bYJwMAAGEjpMAyPDys9vZ2OZ3OUyeIjJTT6ZTX6w16jNfrDaiXJJfL5a8fHR3Vyy+/rOuuu04ul0szZsxQTk6Odu3adcY+hoaGNDAwELABAIDwFVJg6evr08jIiBITEwP2JyYmyufzBT3G5/Odtb63t1efffaZNm/erNzcXP3mN7/R7bffrjvuuEN79uwJes7q6mrFx8f7tzlz5oQyBgAAmGQm/Cmh0dFRSdLKlSv1ox/9SJmZmVq/fr3+4i/+Qg0NDUGPqaioUH9/v387cuTIxWwZAABcZNGhFCckJCgqKko9PT0B+3t6emS324MeY7fbz1qfkJCg6OhopaamBtQsXLhQr7/+etBzxsbGKjY2NpTWAQDAJBZSYImJiVFWVpY8Ho/cbrekL6+QeDwelZaWBj3G4XDI4/Fo3bp1/n0tLS1yOBz+c95www06dOhQwHF/+MMfNHfu3FDaAy66pPUvh1T//ua8C9QJAIS3kAKLJJWVlamoqEhLlixRdna2tmzZosHBQRUXF0uSVq1apdmzZ6u6ulqStHbtWi1btkw1NTXKy8tTY2Oj2tratG3bNv85y8vLVVBQoJtvvlm33HKLmpub9atf/Uqtra3jMyUAAJjUQg4sBQUFOn78uCorK+Xz+ZSZmanm5mb/jbXd3d2KjDx1a8zSpUu1Y8cObdy4URs2bFBycrJ27dqltLQ0f83tt9+uhoYGVVdX64c//KEWLFig//qv/9JNN900DiMCAIDJLuTAIkmlpaVnfAso2FWR/Px85efnn/Wc9913n+67776xtAMAAMLchD8lBAAAcC4EFgAAYDwCCwAAMB6BBQAAGG9MN90CAMJTKJ8txOcK4WLiCgsAADAegQUAABiPwAIAAIxHYAEAAMYjsAAAAOMRWAAAgPEILAAAwHgEFgAAYDwCCwAAMB6BBQAAGI/AAgAAjEdgAQAAxiOwAAAA4xFYAACA8QgsAADAeAQWAABgPAILAAAwHoEFAAAYj8ACAACMR2ABAADGI7AAAADjEVgAAIDxCCwAAMB4BBYAAGA8AgsAADAegQUAABiPwAIAAIxHYAEAAMYbU2Cpr69XUlKSbDabcnJytG/fvrPWNzU1KSUlRTabTenp6dq9e3fA6/fee68iIiICttzc3LG0BgAAwlDIgWXnzp0qKytTVVWVOjo6lJGRIZfLpd7e3qD1e/fuVWFhoUpKStTZ2Sm32y23262urq6AutzcXB07dsy/Pfvss2ObCAAAhJ2QA0ttba1Wr16t4uJipaamqqGhQVOnTtX27duD1m/dulW5ubkqLy/XwoULtWnTJi1evFh1dXUBdbGxsbLb7f7tiiuuGNtEAAAg7IQUWIaHh9Xe3i6n03nqBJGRcjqd8nq9QY/xer0B9ZLkcrlOq29tbdWMGTO0YMECPfjgg/roo4/O2MfQ0JAGBgYCNgAAEL5CCix9fX0aGRlRYmJiwP7ExET5fL6gx/h8vnPW5+bm6plnnpHH49Gjjz6qPXv26NZbb9XIyEjQc1ZXVys+Pt6/zZkzJ5QxAADAJBM90Q1I0l133eX/OT09XYsWLdI111yj1tZWLV++/LT6iooKlZWV+X8fGBggtAAAEMZCusKSkJCgqKgo9fT0BOzv6emR3W4Peozdbg+pXpLmz5+vhIQEvfvuu0Ffj42NVVxcXMAGAADCV0hXWGJiYpSVlSWPxyO32y1JGh0dlcfjUWlpadBjHA6HPB6P1q1b59/X0tIih8Nxxj/nj3/8oz766CPNnDkzlPYAAIZKWv/yede+vznvAnaCySrkp4TKysr0L//yL3r66af19ttv68EHH9Tg4KCKi4slSatWrVJFRYW/fu3atWpublZNTY0OHjyoRx55RG1tbf6A89lnn6m8vFxvvPGG3n//fXk8Hq1cuVLXXnutXC7XOI0JAAAms5DvYSkoKNDx48dVWVkpn8+nzMxMNTc3+2+s7e7uVmTkqRy0dOlS7dixQxs3btSGDRuUnJysXbt2KS0tTZIUFRWlAwcO6Omnn9Ynn3yiWbNmacWKFdq0aZNiY2PHaUwAADCZjemm29LS0jO+BdTa2nravvz8fOXn5wetv+SSS/TrX/96LG0AAIBvCSOeEgIuNN4/B4DJjS8/BAAAxiOwAAAA4xFYAACA8QgsAADAeAQWAABgPAILAAAwHoEFAAAYj8ACAACMR2ABAADGI7AAAADjEVgAAIDxCCwAAMB4BBYAAGA8AgsAADAegQUAABiPwAIAAIxHYAEAAMYjsAAAAOMRWAAAgPEILAAAwHgEFgAAYDwCCwAAMB6BBQAAGI/AAgAAjEdgAQAAxiOwAAAA4xFYAACA8QgsAADAeAQWAABgPAILAAAwHoEFAAAYj8ACAACMN6bAUl9fr6SkJNlsNuXk5Gjfvn1nrW9qalJKSopsNpvS09O1e/fuM9Y+8MADioiI0JYtW8bSGgAACEMhB5adO3eqrKxMVVVV6ujoUEZGhlwul3p7e4PW7927V4WFhSopKVFnZ6fcbrfcbre6urpOq33++ef1xhtvaNasWaFPAgAAwlbIgaW2tlarV69WcXGxUlNT1dDQoKlTp2r79u1B67du3arc3FyVl5dr4cKF2rRpkxYvXqy6urqAug8//FA/+MEP9Mtf/lJTpkwZ2zQAACAshRRYhoeH1d7eLqfTeeoEkZFyOp3yer1Bj/F6vQH1kuRyuQLqR0dHdc8996i8vFzXX3/9OfsYGhrSwMBAwAYAAMJXdCjFfX19GhkZUWJiYsD+xMREHTx4MOgxPp8vaL3P5/P//uijjyo6Olo//OEPz6uP6upq/eQnPwmldUwCSetfPu/a9zfnXcBOAACmmfCnhNrb27V161Y99dRTioiIOK9jKioq1N/f79+OHDlygbsEAAATKaTAkpCQoKioKPX09ATs7+npkd1uD3qM3W4/a/1rr72m3t5eXX311YqOjlZ0dLQ++OAD/fjHP1ZSUlLQc8bGxiouLi5gAwAA4SukwBITE6OsrCx5PB7/vtHRUXk8HjkcjqDHOByOgHpJamlp8dffc889OnDggPbv3+/fZs2apfLycv36178OdR4AABCGQrqHRZLKyspUVFSkJUuWKDs7W1u2bNHg4KCKi4slSatWrdLs2bNVXV0tSVq7dq2WLVummpoa5eXlqbGxUW1tbdq2bZskafr06Zo+fXrAnzFlyhTZ7XYtWLDgm84HAAhz3P/27RByYCkoKNDx48dVWVkpn8+nzMxMNTc3+2+s7e7uVmTkqQs3S5cu1Y4dO7Rx40Zt2LBBycnJ2rVrl9LS0sZvCgAAENZCDiySVFpaqtLS0qCvtba2nrYvPz9f+fn5533+999/fyxtAQCAMDXhTwkBAACcC4EFAAAYj8ACAACMR2ABAADGI7AAAADjEVgAAIDxCCwAAMB4BBYAAGA8AgsAADAegQUAABiPwAIAAIxHYAEAAMYjsAAAAOMRWAAAgPEILAAAwHgEFgAAYDwCCwAAMB6BBQAAGI/AAgAAjEdgAQAAxiOwAAAA4xFYAACA8QgsAADAeNET3QAAACZKWv9ySPXvb867QJ1AIrBgDEL5R8w/YADAeOAtIQAAYDwCCwAAMB6BBQAAGI/AAgAAjEdgAQAAxiOwAAAA4xFYAACA8QgsAADAeGMKLPX19UpKSpLNZlNOTo727dt31vqmpialpKTIZrMpPT1du3fvDnj9kUceUUpKiqZNm6YrrrhCTqdTb7755lhaAwAAYSjkwLJz506VlZWpqqpKHR0dysjIkMvlUm9vb9D6vXv3qrCwUCUlJers7JTb7Zbb7VZXV5e/5rrrrlNdXZ3eeustvf7660pKStKKFSt0/PjxsU8GAADCRsiBpba2VqtXr1ZxcbFSU1PV0NCgqVOnavv27UHrt27dqtzcXJWXl2vhwoXatGmTFi9erLq6On/N97//fTmdTs2fP1/XX3+9amtrNTAwoAMHDox9MgAAEDZCCizDw8Nqb2+X0+k8dYLISDmdTnm93qDHeL3egHpJcrlcZ6wfHh7Wtm3bFB8fr4yMjKA1Q0NDGhgYCNgAAED4Cimw9PX1aWRkRImJiQH7ExMT5fP5gh7j8/nOq/6ll17SpZdeKpvNpn/6p39SS0uLEhISgp6zurpa8fHx/m3OnDmhjAEAACYZY54SuuWWW7R//37t3btXubm5uvPOO894X0xFRYX6+/v925EjRy5ytwAA4GIKKbAkJCQoKipKPT09Aft7enpkt9uDHmO328+rftq0abr22mt144036sknn1R0dLSefPLJoOeMjY1VXFxcwAYAAMJXSIElJiZGWVlZ8ng8/n2jo6PyeDxyOBxBj3E4HAH1ktTS0nLG+v//eYeGhkJpDwAAhKnoUA8oKytTUVGRlixZouzsbG3ZskWDg4MqLi6WJK1atUqzZ89WdXW1JGnt2rVatmyZampqlJeXp8bGRrW1tWnbtm2SpMHBQf3sZz/TbbfdppkzZ6qvr0/19fX68MMPlZ+fP46jAgCAySrkwFJQUKDjx4+rsrJSPp9PmZmZam5u9t9Y293drcjIUxduli5dqh07dmjjxo3asGGDkpOTtWvXLqWlpUmSoqKidPDgQT399NPq6+vT9OnTdcMNN+i1117T9ddfP05jAgCAySzkwCJJpaWlKi0tDfpaa2vrafvy8/PPeLXEZrPpueeeG0sbAADgW8KYp4QAAADOZExXWAAAwNglrX/5vGvf35x3ATuZPLjCAgAAjEdgAQAAxiOwAAAA4xFYAACA8QgsAADAeAQWAABgPB5rDlM8MgcACCdcYQEAAMYjsAAAAOMRWAAAgPEILAAAwHgEFgAAYDwCCwAAMB6BBQAAGI/AAgAAjEdgAQAAxiOwAAAA4xFYAACA8QgsAADAeAQWAABgPL6teYLxrcoAAJwbV1gAAIDxCCwAAMB4vCUEAECYCOU2A2ly3WrAFRYAAGA8AgsAADAegQUAABiPwAIAAIzHTbfngc9KAQBgYnGFBQAAGG9MgaW+vl5JSUmy2WzKycnRvn37zlrf1NSklJQU2Ww2paena/fu3f7XTp48qYceekjp6emaNm2aZs2apVWrVuno0aNjaQ0AAIShkAPLzp07VVZWpqqqKnV0dCgjI0Mul0u9vb1B6/fu3avCwkKVlJSos7NTbrdbbrdbXV1dkqTPP/9cHR0devjhh9XR0aHnnntOhw4d0m233fbNJgMAAGEj5MBSW1ur1atXq7i4WKmpqWpoaNDUqVO1ffv2oPVbt25Vbm6uysvLtXDhQm3atEmLFy9WXV2dJCk+Pl4tLS268847tWDBAt14442qq6tTe3u7uru7v9l0AAAgLIQUWIaHh9Xe3i6n03nqBJGRcjqd8nq9QY/xer0B9ZLkcrnOWC9J/f39ioiI0OWXXx5KewAAIEyF9JRQX1+fRkZGlJiYGLA/MTFRBw8eDHqMz+cLWu/z+YLWnzhxQg899JAKCwsVFxcXtGZoaEhDQ0P+3wcGBkIZAwAATDJGPSV08uRJ3XnnnbIsS7/4xS/OWFddXa34+Hj/NmfOnIvYJQAAuNhCCiwJCQmKiopST09PwP6enh7Z7fagx9jt9vOq/yqsfPDBB2ppaTnj1RVJqqioUH9/v387cuRIKGMAAIBJJqTAEhMTo6ysLHk8Hv++0dFReTweORyOoMc4HI6AeklqaWkJqP8qrLzzzjt65ZVXNH369LP2ERsbq7i4uIANAACEr5A/6basrExFRUVasmSJsrOztWXLFg0ODqq4uFiStGrVKs2ePVvV1dWSpLVr12rZsmWqqalRXl6eGhsb1dbWpm3btkn6Mqz81V/9lTo6OvTSSy9pZGTEf3/LlVdeqZiYmPGaFQAATFIhB5aCggIdP35clZWV8vl8yszMVHNzs//G2u7ubkVGnrpws3TpUu3YsUMbN27Uhg0blJycrF27diktLU2S9OGHH+rFF1+UJGVmZgb8Wa+++qq++93vjnE0AAAQLsb0XUKlpaUqLS0N+lpra+tp+/Lz85Wfnx+0PikpSZZljaUNAADwLWHUU0IAAADBEFgAAIDxCCwAAMB4BBYAAGA8AgsAADAegQUAABiPwAIAAIxHYAEAAMYjsAAAAOMRWAAAgPEILAAAwHgEFgAAYDwCCwAAMB6BBQAAGI/AAgAAjEdgAQAAxiOwAAAA4xFYAACA8QgsAADAeAQWAABgPAILAAAwHoEFAAAYj8ACAACMR2ABAADGI7AAAADjEVgAAIDxCCwAAMB4BBYAAGA8AgsAADAegQUAABiPwAIAAIxHYAEAAMYjsAAAAOONKbDU19crKSlJNptNOTk52rdv31nrm5qalJKSIpvNpvT0dO3evTvg9eeee04rVqzQ9OnTFRERof3794+lLQAAEKZCDiw7d+5UWVmZqqqq1NHRoYyMDLlcLvX29gat37t3rwoLC1VSUqLOzk653W653W51dXX5awYHB3XTTTfp0UcfHfskAAAgbIUcWGpra7V69WoVFxcrNTVVDQ0Nmjp1qrZv3x60fuvWrcrNzVV5ebkWLlyoTZs2afHixaqrq/PX3HPPPaqsrJTT6Rz7JAAAIGyFFFiGh4fV3t4eECwiIyPldDrl9XqDHuP1ek8LIi6X64z152NoaEgDAwMBGwAACF8hBZa+vj6NjIwoMTExYH9iYqJ8Pl/QY3w+X0j156O6ulrx8fH+bc6cOWM+FwAAMN+kfEqooqJC/f39/u3IkSMT3RIAALiAokMpTkhIUFRUlHp6egL29/T0yG63Bz3GbreHVH8+YmNjFRsbO+bjAQDA5BLSFZaYmBhlZWXJ4/H4942Ojsrj8cjhcAQ9xuFwBNRLUktLyxnrAQAAvi6kKyySVFZWpqKiIi1ZskTZ2dnasmWLBgcHVVxcLElatWqVZs+ererqaknS2rVrtWzZMtXU1CgvL0+NjY1qa2vTtm3b/Of8+OOP1d3draNHj0qSDh06JOnLqzPf5EoMAAAIDyEHloKCAh0/flyVlZXy+XzKzMxUc3Oz/8ba7u5uRUaeunCzdOlS7dixQxs3btSGDRuUnJysXbt2KS0tzV/z4osv+gOPJN11112SpKqqKj3yyCNjnQ0AAISJkAOLJJWWlqq0tDToa62trafty8/PV35+/hnPd++99+ree+8dSysAAOBbYFI+JQQAAL5dCCwAAMB4BBYAAGA8AgsAADAegQUAABiPwAIAAIxHYAEAAMYjsAAAAOMRWAAAgPEILAAAwHgEFgAAYDwCCwAAMB6BBQAAGI/AAgAAjEdgAQAAxiOwAAAA4xFYAACA8QgsAADAeAQWAABgPAILAAAwHoEFAAAYj8ACAACMR2ABAADGI7AAAADjEVgAAIDxCCwAAMB4BBYAAGA8AgsAADAegQUAABiPwAIAAIxHYAEAAMYjsAAAAOMRWAAAgPHGFFjq6+uVlJQkm82mnJwc7du376z1TU1NSklJkc1mU3p6unbv3h3wumVZqqys1MyZM3XJJZfI6XTqnXfeGUtrAAAgDIUcWHbu3KmysjJVVVWpo6NDGRkZcrlc6u3tDVq/d+9eFRYWqqSkRJ2dnXK73XK73erq6vLXPPbYY3r88cfV0NCgN998U9OmTZPL5dKJEyfGPhkAAAgbIQeW2tparV69WsXFxUpNTVVDQ4OmTp2q7du3B63funWrcnNzVV5eroULF2rTpk1avHix6urqJH15dWXLli3auHGjVq5cqUWLFumZZ57R0aNHtWvXrm80HAAACA/RoRQPDw+rvb1dFRUV/n2RkZFyOp3yer1Bj/F6vSorKwvY53K5/GHk8OHD8vl8cjqd/tfj4+OVk5Mjr9eru+6667RzDg0NaWhoyP97f3+/JGlgYCCUcc7b6NDn510bag8X6tz0fHHOHcp5L+S56fninHsy/r2j57GfezL+vbuQPV8IX/35lmWdu9gKwYcffmhJsvbu3Ruwv7y83MrOzg56zJQpU6wdO3YE7Kuvr7dmzJhhWZZl/e53v7MkWUePHg2oyc/Pt+68886g56yqqrIksbGxsbGxsYXBduTIkXNmkJCusJiioqIi4KrN6OioPv74Y02fPl0REREXpYeBgQHNmTNHR44cUVxc3EX5My8m5pv8wn1G5pv8wn3GcJ9P+uYzWpalTz/9VLNmzTpnbUiBJSEhQVFRUerp6QnY39PTI7vdHvQYu91+1vqv/tvT06OZM2cG1GRmZgY9Z2xsrGJjYwP2XX755aGMMm7i4uLC9i+ixHzhINxnZL7JL9xnDPf5pG82Y3x8/HnVhXTTbUxMjLKysuTxePz7RkdH5fF45HA4gh7jcDgC6iWppaXFXz9v3jzZ7faAmoGBAb355ptnPCcAAPh2CfktobKyMhUVFWnJkiXKzs7Wli1bNDg4qOLiYknSqlWrNHv2bFVXV0uS1q5dq2XLlqmmpkZ5eXlqbGxUW1ubtm3bJkmKiIjQunXr9NOf/lTJycmaN2+eHn74Yc2aNUtut3v8JgUAAJNWyIGloKBAx48fV2VlpXw+nzIzM9Xc3KzExERJUnd3tyIjT124Wbp0qXbs2KGNGzdqw4YNSk5O1q5du5SWluav+bu/+zsNDg7q/vvv1yeffKKbbrpJzc3Nstls4zDihREbG6uqqqrT3poKF8w3+YX7jMw3+YX7jOE+n3RxZ4ywrPN5lggAAGDi8F1CAADAeAQWAABgPAILAAAwHoEFAAAYj8AyBvX19UpKSpLNZlNOTo727ds30S2Nm0ceeUQREREBW0pKykS3NWb/8z//o7/8y7/UrFmzFBERcdoXalqWpcrKSs2cOVOXXHKJnE6n3nnnnYlpdgzONd+999572nrm5uZOTLNjUF1drRtuuEGXXXaZZsyYIbfbrUOHDgXUnDhxQmvWrNH06dN16aWX6nvf+95pH1ZpsvOZ8bvf/e5p6/jAAw9MUMeh+cUvfqFFixb5P1jM4XDov//7v/2vT/b1k84942Rev2A2b97s/0iSr1yMdSSwhGjnzp0qKytTVVWVOjo6lJGRIZfLpd7e3olubdxcf/31OnbsmH97/fXXJ7qlMRscHFRGRobq6+uDvv7YY4/p8ccfV0NDg958801NmzZNLpdLJ06cuMidjs255pOk3NzcgPV89tlnL2KH38yePXu0Zs0avfHGG2ppadHJkye1YsUKDQ4O+mt+9KMf6Ve/+pWampq0Z88eHT16VHfccccEdh2a85lRklavXh2wjo899tgEdRyaq666Sps3b1Z7e7va2tr0Z3/2Z1q5cqX+93//V9LkXz/p3DNKk3f9vu73v/+9/vmf/1mLFi0K2H9R1vGc3zaEANnZ2daaNWv8v4+MjFizZs2yqqurJ7Cr8VNVVWVlZGRMdBsXhCTr+eef9/8+Ojpq2e126+c//7l/3yeffGLFxsZazz777AR0+M18fT7LsqyioiJr5cqVE9LPhdDb22tJsvbs2WNZ1pfrNWXKFKupqclf8/bbb1uSLK/XO1FtfiNfn9GyLGvZsmXW2rVrJ66pcXbFFVdY//qv/xqW6/eVr2a0rPBZv08//dRKTk62WlpaAma6WOvIFZYQDA8Pq729XU6n078vMjJSTqdTXq93AjsbX++8845mzZql+fPn6+6771Z3d/dEt3RBHD58WD6fL2A94+PjlZOTE1br2draqhkzZmjBggV68MEH9dFHH010S2PW398vSbryyislSe3t7Tp58mTAGqakpOjqq6+etGv49Rm/8stf/lIJCQlKS0tTRUWFPv/884lo7xsZGRlRY2OjBgcH5XA4wnL9vj7jV8Jh/dasWaO8vLyA9ZIu3r/DSfltzROlr69PIyMj/k/1/UpiYqIOHjw4QV2Nr5ycHD311FNasGCBjh07pp/85Cf6f//v/6mrq0uXXXbZRLc3rnw+nyQFXc+vXpvscnNzdccdd2jevHl67733tGHDBt16663yer2Kioqa6PZCMjo6qnXr1ulP//RP/Z+U7fP5FBMTc9qXn07WNQw2oyR9//vf19y5czVr1iwdOHBADz30kA4dOqTnnntuArs9f2+99ZYcDodOnDihSy+9VM8//7xSU1O1f//+sFm/M80oTf71k6TGxkZ1dHTo97///WmvXax/hwQWBLj11lv9Py9atEg5OTmaO3eu/uM//kMlJSUT2BnG4q677vL/nJ6erkWLFumaa65Ra2urli9fPoGdhW7NmjXq6uqa1PdUncuZZrz//vv9P6enp2vmzJlavny53nvvPV1zzTUXu82QLViwQPv371d/f7/+8z//U0VFRdqzZ89EtzWuzjRjamrqpF+/I0eOaO3atWppaZnQr8zhLaEQJCQkKCoq6rQ7n3t6emS32yeoqwvr8ssv13XXXad33313olsZd1+t2bdpPefPn6+EhIRJt56lpaV66aWX9Oqrr+qqq67y77fb7RoeHtYnn3wSUD8Z1/BMMwaTk5MjSZNmHWNiYnTttdcqKytL1dXVysjI0NatW8Nq/c40YzCTbf3a29vV29urxYsXKzo6WtHR0dqzZ48ef/xxRUdHKzEx8aKsI4ElBDExMcrKypLH4/HvGx0dlcfjCXivMpx89tlneu+99zRz5syJbmXczZs3T3a7PWA9BwYG9Oabb4btev7xj3/URx99NGnW07IslZaW6vnnn9dvf/tbzZs3L+D1rKwsTZkyJWANDx06pO7u7kmzhueaMZj9+/dL0qRZx68bHR3V0NBQWKzfmXw1YzCTbf2WL1+ut956S/v37/dvS5Ys0d133+3/+aKs47jdvvst0djYaMXGxlpPPfWU9X//93/W/fffb11++eWWz+eb6NbGxY9//GOrtbXVOnz4sPW73/3OcjqdVkJCgtXb2zvRrY3Jp59+anV2dlqdnZ2WJKu2ttbq7Oy0PvjgA8uyLGvz5s3W5Zdfbr3wwgvWgQMHrJUrV1rz5s2zvvjiiwnu/Pycbb5PP/3U+tu//VvL6/Vahw8ftl555RVr8eLFVnJysnXixImJbv28PPjgg1Z8fLzV2tpqHTt2zL99/vnn/poHHnjAuvrqq63f/va3Vltbm+VwOCyHwzGBXYfmXDO+++671j/8wz9YbW1t1uHDh60XXnjBmj9/vnXzzTdPcOfnZ/369daePXusw4cPWwcOHLDWr19vRUREWL/5zW8sy5r862dZZ59xsq/fmXz9yaeLsY4EljF44oknrKuvvtqKiYmxsrOzrTfeeGOiWxo3BQUF1syZM62YmBhr9uzZVkFBgfXuu+9OdFtj9uqrr1qSTtuKioosy/ry0eaHH37YSkxMtGJjY63ly5dbhw4dmtimQ3C2+T7//HNrxYoV1ne+8x1rypQp1ty5c63Vq1dPqnAdbDZJ1r/927/5a7744gvrb/7mb6wrrrjCmjp1qnX77bdbx44dm7imQ3SuGbu7u62bb77ZuvLKK63Y2Fjr2muvtcrLy63+/v6Jbfw83XfffdbcuXOtmJgY6zvf+Y61fPlyf1ixrMm/fpZ19hkn+/qdydcDy8VYxwjLsqzxu14DAAAw/riHBQAAGI/AAgAAjEdgAQAAxiOwAAAA4xFYAACA8QgsAADAeAQWAABgPAILAAAwHoEFAAAYj8ACAACMR2ABAADGI7AAAADj/X8WsDEwAlYMkwAAAABJRU5ErkJggg==", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "def random_walk_bc(n, max, start = None, p = .5):\n", " # By default start in the middle of the box. \n", " if start is None: \n", " start = max // 2\n", " \n", " # Create a random sequence of 1 and -1 values. \n", " steps = np.random.choice([1, -1], n, p = [p, 1 - p])\n", " return (start + np.sum(steps)) % max\n", "\n", "N_STEPS = 100\n", "N_STATES = 40\n", "N_SAMPLES = 100000\n", "walks = [random_walk_bc(N_STEPS, N_STATES) for _ in range(N_SAMPLES)]\n", "plt.hist(walks, bins = N_STATES, density = True, range = (-.5, N_STATES - .5))\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The functions above simulate the random walk one by one. However, there exists a different approach, which allows calculating all probabilities at once. The idea is to represent the probabilities of ending up in a given position with an $n$ element vector, where the $k$-th element corresponds to the probability of finishing in position $k$. We initialise the starting state $\\vec{p_0}$ with the basis vector corresponding to the starting position, such that the only non-zero element is at position $k$. E.g. for 4 elements, starting in position 2 looks as follows: \n", "\n", "$$\n", "\\vec{p}_0 = \\vec{e}_2 = \n", "\\begin{pmatrix}\n", " 0 \\\\ 0 \\\\ 1 \\\\ 0\n", "\\end{pmatrix}$$\n", "\n", "Now, we can represent the transitions at each time step with a matrix $M$. For any state $\\vec{p}_k$, where $k$ corresponds to current position, there is a 50% chance to move to $k-1$ and 50% to move to $k+1$. Therefore, we need to create a matrix $M$ that implements this operation. To do this, we can decompose this matrix into a sum of permutations, such that $M = \\frac{1}{2} P_+ + \\frac{1}{2} P_-$, where $P_+$ corresponds to the upwards shift $\\vec{e}_i \\rightarrow \\vec{e}_{(i + 1)\\ \\% \\ n}$ and $P_-$ to the downwards shift $\\vec{e}_i \\rightarrow \\vec{e}_{(i - 1)\\ \\% \\ n}$. \n", "\n", "For example, for a box with 4 elements, the matrix is going to be the following: \n", "\n", "$$\n", "M = \\frac{1}{2} \n", "\\begin{pmatrix}\n", " 0 & 0 & 0 & 1 \\\\\n", " 1 & 0 & 0 & 0 \\\\\n", " 0 & 1 & 0 & 0 \\\\\n", " 0 & 0 & 1 & 0\n", "\\end{pmatrix} \n", "+ \\frac{1}{2} \n", "\\begin{pmatrix}\n", " 0 & 1 & 0 & 0 \\\\\n", " 0 & 0 & 1 & 0 \\\\\n", " 0 & 0 & 0 & 1 \\\\\n", " 1 & 0 & 0 & 0\n", "\\end{pmatrix}\n", "= \\frac{1}{2} \n", "\\begin{pmatrix}\n", " 0 & 1 & 0 & 1 \\\\\n", " 1 & 0 & 1 & 0 \\\\\n", " 0 & 1 & 0 & 1 \\\\\n", " 1 & 0 & 1 & 0\n", "\\end{pmatrix}\n", "$$\n", "\n", "To calculate the final probabilities for starting state $\\vec{v}_k$ and $T$ time steps, we can apply the following formula: \n", "\n", "$$\\vec{p}_T = M^T \\vec{p}_0$$\n", "\n", "### Exercise 1 [10 marks]\n", "\n", "Convince yourself why the formulation above works. Then, implement the following snippet of code. \n", "1. `transition_matrix(n, p)` implements the matrix $M$ for an arbitrary number of states $n$ and transition probability $p$ to the next state, and $1 - p$ to the previous state. *[2 marks]*\n", "2. `random_walk_vec(n, T, start, p)` calculates the vector of probabilities $\\vec{p}_T$, where $k$-th element in the vector gives the probability of ending up at the position $k$, given the starting state $\\vec{p}_0$ with 1 at the starting position. *[4 marks]*\n", "3. Finally, plot the results to check your implementation. For example, use the same parameters as in `random_walk_bc` above. Should the plots be exactly the same? Why or why not? *[4 marks]*" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "def transition_matrix(n, p = .5):\n", " # Implementation here. \n", " return np.zeros((n , n))\n", "\n", "def random_walk_vec(n, T, start = None, p = .5):\n", " if start is None:\n", " start = n // 2\n", "\n", " # Implementation here. \n", " return np.zeros(n)\n", "\n", "# Plot results here. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> *Insert any comments in this Markdown field*\n", "> \n", "> ..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Part 2 – Quantum Walk in 1D\n", "\n", "Since we reformulated the random walk problem using linear algebra, it is interesting to see if there is an equivalent quantum circuit that could implement this. Unfortunately, the matrix $M$ is non-unitary, and we need to find a way to make it unitary, as these are the only valid evolutions in quantum computers. \n", "\n", "One of the approaches is to separate the actions of our imaginary particle moving up and down its current position. We could have a quantum register $\\lvert \\rho_0 \\rangle$ of $N$ qubits representing $n = 2^N$ possible states, such that the probability of measuring a basis state $\\lvert k \\rangle$ corresponds to the probability of the particle ending up at position $k$. In other words, the element $\\lvert \\langle k \\vert \\rho_T \\rangle \\rvert^2$ is equivalent to the $k$-th element of $\\vec{p}_T$ defined in the previous section. \n", "\n", "Now, we can define unitary transition matrices for both next and previous state. Let \n", "$$\\hat{U}_- \\lvert k \\rangle = \\lvert (k - 1) \\ \\% \\ n \\rangle$$\n", "$$\\hat{U}_+ \\lvert k \\rangle = \\lvert (k + 1) \\ \\% \\ n \\rangle$$\n", "be those operators. You can prove that both are unitary. \n", "\n", "Let us think about how to implement the transition matrices. We can start with a simple example on 4 qubits, where $\\lvert k \\rangle \\rightarrow \\lvert k + 1 \\rangle$. $\\lvert k \\rangle$ can be written down in the binary representation: \n", "$$\\lvert k \\rangle = \\lvert \\overline{k_3 k_2 k_1 k_0} \\rangle = \\lvert k_3 \\rangle \\lvert k_2 \\rangle \\lvert k_1 \\rangle \\lvert k_0 \\rangle$$ \n", "If $k_0 = 0$, then it is increased to 1, and then the operation is finished. However, if $k_0 = 1$, then the addition is carried over to the next qubit. In both cases, $\\lvert k_0' \\rangle = \\hat{X}\\lvert k_0 \\rangle$. However, in the second case, we also need to add 1 to $\\lvert k_1 \\rangle$, which means applying an $\\hat{X}$ gate conditional on the first qubit being 0. This is then repeated recursively for the following qubits. \n", "\n", "*Note: all exercises below use big endian ordering, where lower-index qubits represent smaller powers of two when reading the register.*\n", "\n", "### Exercise 2 [15 marks]\n", "\n", "Pennylane gives you access to controlled gates with an arbitrary number of control qubits, and either 0 or 1 as control values. Implement both $\\hat{U}_+$ and $\\hat{U}_-$ operators using controlled $\\hat{X}$ gates. Then test and print your circuit. \n", "\n", "1. `mC0X(target)` should be a helper function that applies an $\\hat{X}$ gate controlled by 0 values for all qubits below it (i.e. lower index). For example the gate created for `target = 2` may look as follows: *[3 marks]*\n", " ```\n", " # Q0: ────╭○──── #\n", " # Q1: ────├○──── #\n", " # Q2: ────╰X──── #\n", " # Q3: ────────── #\n", " # ... #\n", " ```\n", "\n", "2. `U_plus()` applies the next-state transition unitary to the entire register. You can use the helper gates here. *[2 marks]*\n", "3. `U_minus()` applies the previous-state transition unitary to the entire register. You can use the helper gates here. Since the explanation above is only for the plus unitary, think about its relation to the minus unitary. Hint: consider unitarity. *[4 marks]*\n", "4. Use Pennylane to draw both `U_plus` and `U_minus` circuits defined above. *[1 marks]*\n", "5. `circuit()` represents a simple circuit to test the plus and minus gates. Feel free to do whatever you need here to verify that your gates are working correctly. How do you convert between Pennylane output and integer states? Are the boundary transitions between $\\lvert 0 \\rangle$ and $\\lvert 2^N - 1 \\rangle$ as expected? *[5 marks]*" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "\n" ] } ], "source": [ "N_WIRES = 8\n", "dev = pl.device(\"default.qubit\", wires = N_WIRES, shots = 100)\n", "\n", "# Multi-controlled X gate. \n", "def mC0X(target):\n", " # Implementation here. \n", " return\n", "\n", "# +1 transition unitary. \n", "def U_plus():\n", " # Implementation here. \n", " return\n", "\n", "# -1 transition unitary. \n", "def U_minus():\n", " # Implementation here. \n", " return\n", "\n", "# Draw th circuits here. \n", "\n", "@pl.qnode(dev)\n", "def circuit():\n", " # Test your methods here. \n", " return pl.sample()\n", "\n", "# Convert and check your results below. \n", "res = circuit()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> *Insert any comments in this Markdown field*\n", "> \n", "> ..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We learnt how to move each the state either up or down, but how do we apply both according to given probabilities? The trick is to utilise an ancilla qubit to represent the superposition of $\\lvert 0 \\rangle$ and $\\lvert 1 \\rangle$ states. This qubit we can call the **coin qubit**, and it can be used as control to each of the operators above, so that both operations are applied at once, i.e. \n", "$$\\hat{M} \\lvert k \\rangle \\lvert 0 \\rangle = \\lvert (k - 1) \\ \\% \\ n \\rangle \\lvert 0 \\rangle$$\n", "$$\\hat{M} \\lvert k \\rangle \\lvert 1 \\rangle = \\lvert (k + 1) \\ \\% \\ n \\rangle \\lvert 1 \\rangle$$\n", "\n", "A **quantum walk** step then looks as follows: \n", "\n", "![image](walk-step.svg)\n", "\n", "This is then repeated $T$ times for $T$ time steps. Importantly, the Hadamard gate is applied for every step. For now, the coin register is initialised to $\\lvert 0 \\rangle$. \n", "\n", "### Exercise 3 [15 marks]\n", "Reimplement the -1 and +1 operators from exercise 2 conditional on the coin qubit. Use them to write a full quantum walk. Feel free to add helper functions similar to `mC0X` above. \n", "\n", "1. Write `CU_plus()` and `CU_minus()`, which are now controlled by the coin qubit. Be careful which control values to use. *[4 marks]*\n", "2. Write `quantum_walk(T)`, which is a quantum walk with $T$ steps. The walk should start *in the middle state* (i.e. $\\frac{1}{2} \\cdot 2^N$). *[4 marks]*\n", "3. Plot the histogram of your results, similar to the ones in part 1. Explain what is different about the classical and quantum case. Why do you think this is the case? What happens if you vary the number of time steps $T$? *[7 marks]*" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n" ] } ], "source": [ "N_WIRES = 7\n", "dev = pl.device(\"default.qubit\", wires = [\"coin\", *range(N_WIRES)], shots = 10000)\n", "\n", "# Controlled +1 transition unitary. \n", "def CU_plus():\n", " # Implementation here. \n", " return\n", "\n", "# Controlled -1 transition unitary. \n", "def CU_minus():\n", " # Implementation here. \n", " return\n", "\n", "# Quantum walk with T steps. \n", "@pl.qnode(dev)\n", "def quantum_walk(T):\n", " # Implementation here. \n", " return pl.sample()\n", "\n", "# Plot the results below. \n", "res = quantum_walk(64)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> *Insert any comments in this Markdown field*\n", "> \n", "> ..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 4 [10 marks]\n", "Test what happens if the coin qubit is initialised to a different state than $\\lvert 0 \\rangle$. \n", "\n", "1. Write a function `init_coin(theta, phi)`, which rotates the coin qubit to an arbitrary state of the following form: *[3 marks]*\n", "\n", "$$\\lvert \\psi_{coin} \\rangle = \\cos{(\\theta)} \\lvert 0 \\rangle + {\\rm e}^{i\\phi} \\sin{(\\theta)} \\lvert 1 \\rangle$$\n", "\n", "2. Rewrite `quantum_walk(T, theta, phi)`, with two new parameters that can be passed to `init_coin`. What do your results look like if you initialise the coin in state $\\lvert \\psi_{coin} \\rangle = \\lvert 1 \\rangle$? What about $\\lvert \\psi_{coin} \\rangle = \\frac{1}{\\sqrt{2}} (\\lvert 0 \\rangle + i \\lvert 1 \\rangle)$? Plot your results for both cases. How would you choose the number of time steps $T$? *[7 marks]*" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Init general coin register. \n", "def init_coin(theta, phi):\n", " # Implementation here. \n", " return\n", "\n", "# Quantum walk with T steps, and given coin parameters. \n", "@pl.qnode(dev)\n", "def quantum_walk(T, theta = 0, phi = 0):\n", " # Implementation here. \n", " return pl.sample()\n", "\n", "# Plot the results below. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 5 [10 marks]\n", "\n", "How would you implement the classical walk on a quantum computer? Apply any ideas from the Pennylane library. Try to reproduce the results from part 1, but feel free to tweak any device parameters if it takes too long to run. \n", "\n", "1. Write `classical_walk(T)` below to simulate the classical walk with boundary conditions for $T$ time steps, similar to the second example in part 1. Plot your results. *[10 marks]*" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n" ] } ], "source": [ "# Feel free to modify the parameters here. \n", "N_WIRES = 7\n", "dev = pl.device(\"default.qubit\", wires = [\"coin\", *range(N_WIRES)], shots = 1000)\n", "\n", "@pl.qnode(dev)\n", "def classical_walk(T):\n", " # Implementation here. \n", " return pl.sample()\n", "\n", "# Plot the results below. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> *Insert any comments in this Markdown field*\n", "> \n", "> ..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Part 3 – 2D Quantum Walk\n", "\n", "Now you can use all of the ideas from previous part to construct a similar circuit that conducts the quantum walk in 2-dimensions. \n", "\n", "\n", "![image](2d-grid.svg)\n", "\n", "You can assume that the grid is of dimensions $2^N \\times 2^M$, so the first $M$ qubits represent columns, while the next $N$ represent rows. Use named registers to help you identify which qubits you are acting on. Instead of -1 and +1 transitions, now you will need left, right, up and down transitions. To control them, use two coin qubits, one for vertical directions, and one for horizontal. \n", "\n", "### Exercise 6 [25 marks]\n", "\n", "Use the ideas from previous exercises to implement a 2D quantum walk below. Make it flexible for different numbers of column and row qubits. This time, return the expectation value instead of samples. Feel free to define any helper methods. \n", "\n", "1. Implement gates for transitions in each Cartesian direction. Make horizontal transitions controlled on one qubit, and horizontal transitions controlled on the other qubit. Make use of named wires. *[12 marks]*\n", "2. Implement the 2D quantum walk. Make it return the expectation value instead of a sample. For now, leave the initial coin state as $\\lvert 00 \\rangle$. *[4 marks]*\n", "3. Test your code and plot the results (e.g. as 2D histograms) for different $T$ on a 16x32 grid. How do they compare to the 1D case? How would you expect them to change for different initial states? *[9 marks]*" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "ename": "NameError", "evalue": "name 'pl' is not defined", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mNameError\u001b[0m Traceback (most recent call last)", "Cell \u001b[0;32mIn[7], line 4\u001b[0m\n\u001b[1;32m 2\u001b[0m COL_REG \u001b[38;5;241m=\u001b[39m (\u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mcol0\u001b[39m\u001b[38;5;124m\"\u001b[39m, \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mcol1\u001b[39m\u001b[38;5;124m\"\u001b[39m, \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mcol2\u001b[39m\u001b[38;5;124m\"\u001b[39m, \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mcol3\u001b[39m\u001b[38;5;124m\"\u001b[39m, \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mcol4\u001b[39m\u001b[38;5;124m\"\u001b[39m)\n\u001b[1;32m 3\u001b[0m ROW_REG \u001b[38;5;241m=\u001b[39m (\u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mrow0\u001b[39m\u001b[38;5;124m\"\u001b[39m, \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mrow1\u001b[39m\u001b[38;5;124m\"\u001b[39m, \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mrow2\u001b[39m\u001b[38;5;124m\"\u001b[39m, \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mrow3\u001b[39m\u001b[38;5;124m\"\u001b[39m, \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mrow4\u001b[39m\u001b[38;5;124m\"\u001b[39m)\n\u001b[0;32m----> 4\u001b[0m dev \u001b[38;5;241m=\u001b[39m \u001b[43mpl\u001b[49m\u001b[38;5;241m.\u001b[39mdevice(\u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mdefault.qubit\u001b[39m\u001b[38;5;124m\"\u001b[39m, wires \u001b[38;5;241m=\u001b[39m COIN_REG \u001b[38;5;241m+\u001b[39m COL_REG \u001b[38;5;241m+\u001b[39m ROW_REG, shots \u001b[38;5;241m=\u001b[39m \u001b[38;5;241m100000\u001b[39m)\n\u001b[1;32m 6\u001b[0m \u001b[38;5;66;03m# Next column transition unitary\u001b[39;00m\n\u001b[1;32m 7\u001b[0m \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21mCCU_left\u001b[39m():\n\u001b[1;32m 8\u001b[0m \u001b[38;5;66;03m# Implementation here. \u001b[39;00m\n", "\u001b[0;31mNameError\u001b[0m: name 'pl' is not defined" ] } ], "source": [ "COIN_REG = (\"coin1\", \"coin2\")\n", "COL_REG = (\"col0\", \"col1\", \"col2\", \"col3\", \"col4\")\n", "ROW_REG = (\"row0\", \"row1\", \"row2\", \"row3\", \"row4\")\n", "dev = pl.device(\"default.qubit\", wires = COIN_REG + COL_REG + ROW_REG)\n", "\n", "# Previous column transition unitary\n", "def CCU_left():\n", " # Implementation here. \n", " return\n", "\n", "# Next column transition unitary\n", "def CCU_right():\n", " # Implementation here. \n", " return\n", "\n", "# Previous row transition unitary\n", "def CCU_up():\n", " # Implementation here. \n", " return\n", "\n", "# Next row transition unitary\n", "def CCU_down():\n", " # Implementation here. \n", " return\n", "\n", "@pl.qnode(dev)\n", "def quantum_walk_2d(T):\n", " # Implementation here. \n", " return #...\n", "\n", "# Plot the results below. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> *Insert any comments in this Markdown field*\n", "> \n", "> ..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The double Hadamard gate applied to the coin register before each walk step is called the **Hadamard coin**. This is not the only coin valid for the quantum walk. Let's consider the following two additional coins:\n", "* The **Fourier coin**: \n", "\n", "$$\n", "\\hat{F}_4 = \\frac{1}{2} \\begin{pmatrix}\n", "1 & 1 & 1 & 1 \\\\\n", "1 & i & -1 & -i \\\\\n", "1 & -1 & 1 & -1 \\\\\n", "1 & -i & -1 & i\n", "\\end{pmatrix}\n", "$$\n", "\n", "* The **Grover coin**: \n", "\n", "$$\n", "\\hat{G}_4 = \\frac{1}{2} \\begin{pmatrix}\n", "-1 & 1 & 1 & 1 \\\\\n", " 1 & -1 & 1 & 1 \\\\\n", " 1 & 1 & -1 & 1 \\\\\n", " 1 & 1 & 1 & -1\n", "\\end{pmatrix}\n", "$$\n", "\n", "\n", "### Exercise 7 [15 marks]\n", "\n", "Modify your code for the 2D quantum walk to allow arbitrary initial state and coin gate. Plot the results for the following configurations: \n", "1. Hadamard coin and $\\frac{1}{2} (\\lvert 0 \\rangle + i \\lvert 1 \\rangle) \\otimes (\\lvert 0 \\rangle + i \\lvert 1 \\rangle)$ initial state. *[4 marks]*\n", "2. Fourier coin and $\\frac{1}{2} (\\lvert 00 \\rangle + e^{-\\pi/4} \\lvert 01 \\rangle + \\lvert 10 \\rangle - e^{-\\pi/4} \\lvert 11 \\rangle)$ initial state. *[4 marks]*\n", "3. Grover coin and $\\lvert - \\rangle \\otimes \\lvert - \\rangle$ initial state. *[4 marks]*\n", "4. Describe how the results differ from each other. Suggest why this is the case. *[3 marks]*" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Feel free to add more arguments in the function below. \n", "\n", "@pl.qnode(dev)\n", "def quantum_walk_2d(T):\n", " # Implementation here. \n", " return\n", "\n", "# Plot the results below. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> *Insert any comments in this Markdown field*\n", "> \n", "> ..." ] } ], "metadata": { "kernelspec": { "display_name": ".venv", "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.12.6" } }, "nbformat": 4, "nbformat_minor": 2 }