sympy/Project Q - Quantum Computing.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Quantum Random Numer Generator "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Measured: 0\n"
     ]
    }
   ],
   "source": [
    "# QRNG - a basic form of quantum random number genrator\n",
    "from projectq.ops import H, Measure\n",
    "from projectq import MainEngine\n",
    "\n",
    "# create a main compiler engine\n",
    "eng = MainEngine()\n",
    "\n",
    "# allocate one qubit\n",
    "q1 = eng.allocate_qubit()\n",
    "\n",
    "# put it in superposition\n",
    "H | q1\n",
    "\n",
    "# measure\n",
    "Measure | q1\n",
    "\n",
    "eng.flush()\n",
    "# print the result:\n",
    "print(\"Measured: {}\".format(int(q1)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Quantum Teleportation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Alice is creating her state from scratch, i.e., |0>.\n",
      "Alice entangled her qubit with her share of the Bell-pair.\n",
      "Alice is sending the message [1, 1] to Bob.\n",
      "Bob is trying to uncompute the state.\n",
      "Bob successfully arrived at |0>\n"
     ]
    }
   ],
   "source": [
    "import projectq.setups.default\n",
    "from projectq.ops import H, X, Z, Rz, CNOT, Measure\n",
    "from projectq import MainEngine\n",
    "from projectq.meta import Dagger, Control\n",
    "\n",
    "\n",
    "def create_bell_pair(eng):\n",
    "    b1 = eng.allocate_qubit()\n",
    "    b2 = eng.allocate_qubit()\n",
    "\n",
    "    H | b1\n",
    "    CNOT | (b1, b2)\n",
    "\n",
    "    return b1, b2\n",
    "\n",
    "\n",
    "def run_teleport(eng, state_creation_function, verbose=False):\n",
    "    # make a Bell-pair\n",
    "    b1, b2 = create_bell_pair(eng)\n",
    "\n",
    "    # Alice creates a nice state to send\n",
    "    psi = eng.allocate_qubit()\n",
    "    if verbose:\n",
    "        print(\"Alice is creating her state from scratch, i.e., |0>.\")\n",
    "    state_creation_function(eng, psi)\n",
    "\n",
    "    # entangle it with Alice's b1\n",
    "    CNOT | (psi, b1)\n",
    "    if verbose:\n",
    "        print(\"Alice entangled her qubit with her share of the Bell-pair.\")\n",
    "\n",
    "    # measure two values (once in Hadamard basis) and send the bits to Bob\n",
    "    H | psi\n",
    "    Measure | (psi, b1)\n",
    "    msg_to_bob = [int(psi), int(b1)]\n",
    "    if verbose:\n",
    "        print(\"Alice is sending the message {} to Bob.\".format(msg_to_bob))\n",
    "\n",
    "    # Bob may have to apply up to two operation depending on the message sent\n",
    "    # by Alice:\n",
    "    with Control(eng, b1):\n",
    "        X | b2\n",
    "    with Control(eng, psi):\n",
    "        Z | b2\n",
    "\n",
    "    # try to uncompute the psi state\n",
    "    if verbose:\n",
    "        print(\"Bob is trying to uncompute the state.\")\n",
    "    with Dagger(eng):\n",
    "        state_creation_function(eng, b2)\n",
    "\n",
    "    # check whether the uncompute was successful. The simulator only allows to\n",
    "    # delete qubits which are in a computational basis state.\n",
    "    del b2\n",
    "    eng.flush()\n",
    "\n",
    "    if verbose:\n",
    "        print(\"Bob successfully arrived at |0>\")\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    # create a main compiler engine with a simulator backend:\n",
    "    eng = MainEngine()\n",
    "\n",
    "    # define our state-creation routine, which transforms a |0> to the state\n",
    "    # we would like to send. Bob can then try to uncompute it and, if he\n",
    "    # arrives back at |0>, we know that the teleportation worked.\n",
    "    def create_state(eng, qb):\n",
    "        H | qb\n",
    "        Rz(1.21) | qb\n",
    "\n",
    "    # run the teleport and then, let Bob try to uncompute his qubit:\n",
    "    run_teleport(eng, create_state, verbose=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Shor's Algorithm \n",
    "\n",
    "As a third example, consider Shor’s algorithm for factoring, which for a given (large) number N\n",
    "determines the two prime factor $p_1$ and $p_2$, such that $p1⋅p2=N$ in polynomial time! \n",
    " \n",
    " This is a superpolynomial speed-up over the best known classical algorithm (which is the number field sieve) and enables the breaking of modern encryption schemes such as RSA on a future quantum computer.\n",
    "\n",
    "**A tiny bit of number theory**\n",
    "\n",
    "There is a small amount of number theory involved, which reduces the problem of factoring to period-finding of the function $$f(x)=a^xmodN$$\n",
    "\n",
    "for some a (relative prime to N, otherwise we get a factor right away anyway by calling $gcd(a,N))$. The period r for a function f(x) is the number for which $f(x)=f(x+r)∀x$\n",
    " holds. In this case, this means that ax=ax+r(modN)∀x\n",
    ". Therefore, ar=1+qN\n",
    " for some integer q and hence, ar−1=(ar/2−1)(ar/2+1)=qN\n",
    ". This suggests that using the gcd on N and ar/2±1\n",
    " we may find a factor of N!\n",
    "\n",
    "Factoring on a quantum computer: An example\n",
    "At the heart of Shor’s algorithm lies modular exponentiation of a classically known constant (denoted by a in the code) by a quantum superposition of numbers x\n",
    ", i.e.,\n",
    "\n",
    "$$|x⟩|0⟩↦|x⟩|axmodN⟩$$\n",
    "Using N=15\n",
    " and a=2\n",
    ", and applying this operation to the uniform superposition over all x\n",
    "leads to the superposition (modulo renormalization)\n",
    "\n",
    "$$|0⟩|1⟩+|1⟩|2⟩+|2⟩|4⟩+|3⟩|8⟩+|4⟩|1⟩+|5⟩|2⟩+|6⟩|4⟩+⋯$$\n",
    "In Shor’s algorithm, the second register will not be touched again before the end of the quantum program, which means it might as well be measured now. Let’s assume we measure 2; this collapses the state above to\n",
    "\n",
    "|1⟩|2⟩+|5⟩|2⟩+|9⟩|2⟩+⋯\n",
    "The period of a modulo N can now be read off. On a quantum computer, this information can be accessed by applying an inverse quantum Fourier transform to the x-register, followed by a measurement of x."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Running Shor.py file here\n",
    "! python shor.py 15"
   ]
  },
  {
   "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
}