Shor's in 2n+3 (No custom gates).ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import qiskit as qk"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Gate Functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def init_reg(circ, q, val):\n",
    "    \"\"\"Initializes qubit register to value with NOT gates.\"\"\"\n",
    "    for i in range(len(q)):\n",
    "        if val & (1<<i):\n",
    "            circ.x(q[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def qft(circ, q, n):\n",
    "    \"\"\"n-qubit QFT on q in circ.\"\"\"\n",
    "    for j in range(n - 1, -1, -1):\n",
    "        circ.h(q[j])\n",
    "        for i in range(j):\n",
    "            circ.cu1(np.pi/float(2**(i + 1)), q[j - (i + 1)], q[j])\n",
    "\n",
    "def iqft(circ, q, n):\n",
    "    \"\"\"n-qubit Inverse QFT on q in circ.\"\"\"\n",
    "    for j in range(n):\n",
    "        for i in range(j - 1, -1, -1):\n",
    "            circ.cu1(-np.pi/float(2**(i + 1)), q[j - (i + 1)], q[j])\n",
    "        circ.h(q[j])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def PhiADDa(circ, a, b, c1=None, c2=None, inverse=False):\n",
    "    \"\"\"\n",
    "    Takes in an n bit number and an n qubit register and\n",
    "    applies the quantum addition circuit. Optionally takes\n",
    "    in one or two control qubits. Also, can be inversed to\n",
    "    make a subtraction circuit.\n",
    "    \"\"\" \n",
    "    angles = [0]*len(b)\n",
    "    for i in range(len(b)):\n",
    "        if a & (1 << i):\n",
    "            for j in range(i, len(b)):\n",
    "                angles[j] += np.pi/2**(j-i)\n",
    "    \n",
    "    # Inverse of U1 gates is just a negative theta\n",
    "    if inverse:\n",
    "        for i in range(len(angles)):\n",
    "            angles[i] *= -1\n",
    "    \n",
    "    # No controlled bits\n",
    "    if c1 is None and c2 is None:\n",
    "        for i in range(len(angles)):\n",
    "            circ.u1(angles[i], b[i])\n",
    "    \n",
    "    # One controlled bit\n",
    "    if c1 and c2 is None:\n",
    "        for i in range(len(angles)):\n",
    "            circ.cu1(angles[i], c1, b[i])\n",
    "    \n",
    "    # Two controlled bits\n",
    "    # Uses sqrt of U1 gates which is just half of theta\n",
    "    if c1 and c2:\n",
    "        for i in range(len(angles)):\n",
    "            circ.cu1(angles[i]/2., c2, b[i])\n",
    "        circ.cx(c1, c2)\n",
    "        for i in range(len(angles)):\n",
    "            circ.cu1(-angles[i]/2., c2, b[i])\n",
    "        circ.cx(c1, c2)\n",
    "        for i in range(len(angles)):\n",
    "            circ.cu1(angles[i]/2., c1, b[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def PhiADDaModN(circ, a, b, c1, c2, ancilla, N, inverse=False):\n",
    "    \"\"\"\n",
    "    Implements the modular adder gate and its inverse.\n",
    "    (a + b) mod N\n",
    "    \"\"\"\n",
    "    if not inverse:\n",
    "        PhiADDa(circ, a, b, c1, c2)\n",
    "        PhiADDa(circ, N, b, inverse=True)\n",
    "\n",
    "        iqft(circ, b, len(b))\n",
    "        circ.cx(b[len(b) - 1], ancilla)\n",
    "        qft(circ, b, len(b))\n",
    "\n",
    "        PhiADDa(circ, N, b, ancilla)\n",
    "\n",
    "        PhiADDa(circ, a, b, c1, c2, inverse=True)\n",
    "\n",
    "        iqft(circ, b, len(b))\n",
    "\n",
    "        circ.x(b[len(b) - 1])\n",
    "        circ.cx(b[len(b) - 1], ancilla)\n",
    "        circ.x(b[len(b) - 1])\n",
    "\n",
    "        qft(circ, b, len(b))\n",
    "\n",
    "        PhiADDa(circ, a, b, c1, c2)\n",
    "        \n",
    "    else:\n",
    "        PhiADDa(circ, a, b, c1, c2, inverse=True)\n",
    "        \n",
    "        iqft(circ, b, len(b))\n",
    "\n",
    "        circ.x(b[len(b) - 1])\n",
    "        circ.cx(b[len(b) - 1], ancilla)\n",
    "        circ.x(b[len(b) - 1])\n",
    "\n",
    "        qft(circ, b, len(b))\n",
    "        \n",
    "        PhiADDa(circ, a, b, c1, c2)\n",
    "        \n",
    "        PhiADDa(circ, N, b, ancilla, inverse=True)\n",
    "        \n",
    "        iqft(circ, b, len(b))\n",
    "        circ.cx(b[len(b) - 1], ancilla)\n",
    "        qft(circ, b, len(b))\n",
    "        \n",
    "        PhiADDa(circ, N, b)\n",
    "        \n",
    "        PhiADDa(circ, a, b, c1, c2, inverse=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def CMULTaModN(circ, a, b, c, x, ancilla, N, inverse=False):\n",
    "    qft(circ, b, len(b))\n",
    "    \n",
    "    if inverse:\n",
    "        bounds = range(len(x) - 1, -1, -1)\n",
    "    else:\n",
    "        bounds = range(len(x))\n",
    "    \n",
    "    for i in bounds:\n",
    "        PhiADDaModN(circ, ((2**i)*a) % N, b, c, x[i], ancilla, N, inverse=inverse)\n",
    "    \n",
    "    iqft(circ, b, len(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cswap(circ, c, a, b):\n",
    "    for i in range(len(a)):\n",
    "        circ.cx(b[i], a[i])\n",
    "        circ.ccx(c, a[i], b[i])\n",
    "        circ.cx(b[i], a[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def modInverse(a, m) : \n",
    "    m0 = m \n",
    "    y = 0\n",
    "    x = 1\n",
    "    \n",
    "    if (m == 1) : \n",
    "        return 0\n",
    "    \n",
    "    while (a > 1) : \n",
    "        # q is quotient \n",
    "        q = a // m \n",
    "        \n",
    "        t = m \n",
    "        \n",
    "        # m is remainder now, process \n",
    "        # same as Euclid's algo \n",
    "        m = a % m \n",
    "        a = t \n",
    "        t = y \n",
    "        \n",
    "        # Update x and y \n",
    "        y = x - q * y \n",
    "        x = t \n",
    "    \n",
    "    # Make x positive \n",
    "    if (x < 0) : \n",
    "        x = x + m0 \n",
    "    \n",
    "    return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cUa(circ, a, c, x, z, ancilla, N):\n",
    "    CMULTaModN(circ, a, z, c, x, ancilla, N)\n",
    "    \n",
    "    cswap(circ, c, x, z)\n",
    "    \n",
    "    CMULTaModN(circ, modInverse(a, N), z, c, x, ancilla, N, inverse=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Circuits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit.tools.visualization import plot_histogram\n",
    "sim_backend = qk.BasicAer.get_backend('qasm_simulator')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Circuit for quantum adder"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "b = qk.QuantumRegister(4, 'b')\n",
    "res_b = qk.ClassicalRegister(4, 'res\\_b')\n",
    "\n",
    "circ = qk.QuantumCircuit(b, res_b)\n",
    "\n",
    "# Add 9 + 4\n",
    "a = 9\n",
    "init_reg(circ, b, 4)\n",
    "\n",
    "qft(circ, b, 4)\n",
    "PhiADDa(circ, a, b)\n",
    "iqft(circ, b, 4)\n",
    "\n",
    "circ.measure(b, res_b)\n",
    "\n",
    "job = qk.execute(circ, sim_backend)\n",
    "result = job.result()\n",
    "counts = result.get_counts(circ)\n",
    "plot_histogram(counts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "circ.draw(output='mpl', plot_barriers=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Circuit for quantum adder modulo N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "b = qk.QuantumRegister(4, 'b')\n",
    "c = qk.QuantumRegister(2, 'c')\n",
    "anc = qk.QuantumRegister(1, 'anc')\n",
    "res_b = qk.ClassicalRegister(4, 'res\\_b')\n",
    "\n",
    "circ = qk.QuantumCircuit(c, b, anc, res_b)\n",
    "\n",
    "# Add 9 + 4 % 11\n",
    "a = 9\n",
    "N = 11\n",
    "\n",
    "init_reg(circ, b, 4)\n",
    "init_reg(circ, c, 3)\n",
    "\n",
    "qft(circ, b, len(b))\n",
    "PhiADDaModN(circ, a, b, c[0], c[1], anc, N)\n",
    "iqft(circ, b, len(b))\n",
    "\n",
    "circ.measure(b, res_b)\n",
    "\n",
    "job = qk.execute(circ, sim_backend)\n",
    "result = job.result()\n",
    "counts = result.get_counts(circ)\n",
    "plot_histogram(counts)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Controlled U-a Circuit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "c = qk.QuantumRegister(1, 'c')\n",
    "x = qk.QuantumRegister(4, 'x')\n",
    "z = qk.QuantumRegister(4, 'z')\n",
    "anc = qk.QuantumRegister(1, 'anc')\n",
    "res_x = qk.ClassicalRegister(4, 'res\\_x')\n",
    "\n",
    "circ = qk.QuantumCircuit(c, x, z, anc, res_x)\n",
    "\n",
    "# Multiply 3*5 % 7\n",
    "a = 5\n",
    "N = 7\n",
    "init_reg(circ, x, 3)\n",
    "init_reg(circ, c, 1)  # C needs to be 1 in order to add, otherwise measurement is x passed through\n",
    "\n",
    "cUa(circ, a, c[0], x, z, anc[0], N)\n",
    "\n",
    "circ.measure(x, res_x)\n",
    "\n",
    "job = qk.execute(circ, sim_backend)\n",
    "result = job.result()\n",
    "counts = result.get_counts(circ)\n",
    "plot_histogram(counts)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Warning: Large circuit, not going to be nice to follow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "circ.draw(output='mpl', plot_barriers=False)"
   ]
  }
 ],
 "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.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}