sympy/Quantum Algorithms and Machine Learning - Grover's Algorithm.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Grover's Algorithm\n",
    "\n",
    "- W gate construction (or perhaps -W gate based on Mermin’s book)\n",
    "- Generalize the algorithm for an unknown function that returns 1 on multiple qubit states, not just one.\n",
    "- Implement _represent_ZGate in OracleGate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sympy.physics.quantum.qubit import IntQubit\n",
    "from sympy.physics.quantum.qapply import qapply\n",
    "from sympy.physics.quantum.grover import OracleGate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-|2>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f = lambda qubits: qubits == IntQubit(2)\n",
    "v = OracleGate(2, f)\n",
    "qapply(v*IntQubit(2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "|3>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "qapply(v*IntQubit(3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "|3>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "qapply(v*IntQubit(3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "ename": "QuantumError",
     "evalue": "OracleGate operates on 2 qubits, got: 3",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mQuantumError\u001b[0m                              Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-7-8d0814fdf4f6>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mqapply\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mv\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0mIntQubit\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m4\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m~/anaconda/lib/python3.6/site-packages/sympy/physics/quantum/qapply.py\u001b[0m in \u001b[0;36mqapply\u001b[0;34m(e, **options)\u001b[0m\n\u001b[1;32m    112\u001b[0m     \u001b[0;31m# We have a Mul where there might be actual operators to apply to kets.\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    113\u001b[0m     \u001b[0;32melif\u001b[0m \u001b[0misinstance\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0me\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mMul\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 114\u001b[0;31m         \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mqapply_Mul\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0me\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m**\u001b[0m\u001b[0moptions\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    115\u001b[0m         \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0me\u001b[0m \u001b[0;32mand\u001b[0m \u001b[0mdagger\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    116\u001b[0m             \u001b[0;32mreturn\u001b[0m \u001b[0mDagger\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mqapply_Mul\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mDagger\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0me\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m**\u001b[0m\u001b[0moptions\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/anaconda/lib/python3.6/site-packages/sympy/physics/quantum/qapply.py\u001b[0m in \u001b[0;36mqapply_Mul\u001b[0;34m(e, **options)\u001b[0m\n\u001b[1;32m    173\u001b[0m     \u001b[0;31m# Now try to actually apply the operator and build an inner product.\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    174\u001b[0m     \u001b[0;32mtry\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 175\u001b[0;31m         \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mlhs\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_apply_operator\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mrhs\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m**\u001b[0m\u001b[0moptions\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    176\u001b[0m     \u001b[0;32mexcept\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mNotImplementedError\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mAttributeError\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    177\u001b[0m         \u001b[0;32mtry\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/anaconda/lib/python3.6/site-packages/sympy/physics/quantum/operator.py\u001b[0m in \u001b[0;36m_apply_operator\u001b[0;34m(self, ket, **options)\u001b[0m\n\u001b[1;32m    164\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    165\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0m_apply_operator\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mket\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m**\u001b[0m\u001b[0moptions\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 166\u001b[0;31m         \u001b[0;32mreturn\u001b[0m \u001b[0mdispatch_method\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m'_apply_operator'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mket\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m**\u001b[0m\u001b[0moptions\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    167\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    168\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0mmatrix_element\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m*\u001b[0m\u001b[0margs\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/anaconda/lib/python3.6/site-packages/sympy/physics/quantum/qexpr.py\u001b[0m in \u001b[0;36mdispatch_method\u001b[0;34m(self, basename, arg, **options)\u001b[0m\n\u001b[1;32m    431\u001b[0m         \u001b[0mf\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mgetattr\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmethod_name\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    432\u001b[0m         \u001b[0;31m# This can raise and we will allow it to propagate.\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 433\u001b[0;31m         \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mf\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0marg\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m**\u001b[0m\u001b[0moptions\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    434\u001b[0m         \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    435\u001b[0m             \u001b[0;32mreturn\u001b[0m \u001b[0mresult\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/anaconda/lib/python3.6/site-packages/sympy/physics/quantum/gate.py\u001b[0m in \u001b[0;36m_apply_operator_IntQubit\u001b[0;34m(self, qubits, **options)\u001b[0m\n\u001b[1;32m    204\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0m_apply_operator_IntQubit\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mqubits\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m**\u001b[0m\u001b[0moptions\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    205\u001b[0m         \u001b[0;34m\"\"\"Redirect an apply from IntQubit to Qubit\"\"\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 206\u001b[0;31m         \u001b[0;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_apply_operator_Qubit\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mqubits\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m**\u001b[0m\u001b[0moptions\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    207\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    208\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0m_apply_operator_Qubit\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mqubits\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m**\u001b[0m\u001b[0moptions\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/anaconda/lib/python3.6/site-packages/sympy/physics/quantum/grover.py\u001b[0m in \u001b[0;36m_apply_operator_Qubit\u001b[0;34m(self, qubits, **options)\u001b[0m\n\u001b[1;32m    156\u001b[0m             raise QuantumError(\n\u001b[1;32m    157\u001b[0m                 \u001b[0;34m'OracleGate operates on %r qubits, got: %r'\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 158\u001b[0;31m                 \u001b[0;34m%\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mnqubits\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mqubits\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mnqubits\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    159\u001b[0m             )\n\u001b[1;32m    160\u001b[0m         \u001b[0;31m# If function returns 1 on qubits\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mQuantumError\u001b[0m: OracleGate operates on 2 qubits, got: 3"
     ]
    }
   ],
   "source": [
    "qapply(v*IntQubit(4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "|0>/2 + |1>/2 + |2>/2 + |3>/2"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# OK! So we can't manipulate beyond 2\n",
    "from sympy.physics.quantum.grover import superposition_basis\n",
    "superposition_basis(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Lets run one iteration on Grover's algorithm to see a phase change\n",
    "from sympy.physics.quantum.qapply import qapply\n",
    "from sympy.physics.quantum.qubit import IntQubit\n",
    "from sympy.physics.quantum.grover import OracleGate\n",
    "from sympy.physics.quantum.grover import superposition_basis\n",
    "from sympy.physics.quantum.grover import grover_iteration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "numqubits = 2\n",
    "basis_states = superposition_basis(numqubits)\n",
    "f = lambda qubits: qubits == IntQubit(2)\n",
    "v = OracleGate(numqubits, f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "|2>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "qapply(grover_iteration(basis_states, v))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Applying to an even superposition of 2 qubits\n",
    "from sympy.physics.quantum.qapply import qapply\n",
    "from sympy.physics.quantum.qubit import IntQubit\n",
    "from sympy.physics.quantum.grover import apply_grover"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "|2>"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f = lambda qubits: qubits == IntQubit(2)\n",
    "qapply(apply_grover(f, 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Grover's Algorithm in a bit more detail"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from register import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Cycles : 12.5663706144\n",
      "Measured state:  128\n"
     ]
    }
   ],
   "source": [
    "class GroverReg(QuantumRegister):\n",
    "    def conditional_phase_shift(self):\n",
    "        for state in range(1, self.n_states):\n",
    "            self.qubits[state] = -1*self.qubits[state]\n",
    "        return self\n",
    "    \n",
    "    def oracle(self):\n",
    "        correct_state = 128\n",
    "        self.qubits[correct_state] = -1*self.qubits[correct_state]\n",
    "        return self\n",
    "    \n",
    "register = GroverReg(8)\n",
    "register.hadamar()\n",
    "\n",
    "cycles = np.pi/4*np.sqrt(2**register.n_qubits)\n",
    "print(\"Cycles :\", cycles)\n",
    "\n",
    "for i in range(int(np.round(cycles))):\n",
    "    register.oracle().hadamar().conditional_phase_shift().hadamar()\n",
    "    \n",
    "print(\"Measured state: \", register.measure())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}