Bernstein-Vazirani Algorithm.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import itertools\n",
    "import numpy as np\n",
    "import pyquil.api as api\n",
    "from pyquil.gates import *\n",
    "from pyquil.quil import Program"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Bernstein-Vazirani problem consists of finding $$\\mathbf{a} \\in Z_{2}^{n}$$ given one application of the black-box operator that maps <br>\n",
    "<br>\n",
    "$$\\left\\vert \\mathbf{x} \\right\\rangle \\left\\vert b \\right\\rangle \\rightarrow \\left\\vert \\mathbf{x} \\right\\rangle \\left\\vert b \\oplus \\mathbf{x} \\cdot \\mathbf{a} \\right\\rangle$$\n",
    "<br>\n",
    "The setup is similar to the Deutsch-Jozsa algorithm in that we still construct the same unitary operator to represent the black-box, but with $$f(\\mathbf{x}) = \\mathbf{x} \\cdot \\mathbf{a},$$ so that\n",
    "<br>\n",
    "$$U_{f(\\mathbf{x})} = \\sum_{\\mathbf{x} = 0}^{2^{n} - 1} \\left\\vert \\mathbf{x} \\right\\rangle \\left\\langle \\mathbf{x} \\right\\vert \\otimes \\left[ I + (\\mathbf{x} \\cdot \\mathbf{a}) [X - I]\\right]$$\n",
    "Starting out with the state $$\\left\\vert 0 \\right\\rangle^{\\otimes n} \\otimes \\left\\vert 0 \\right\\rangle,$$ we transform the first n qubits via a Hadamard transform, the (n-1)th qubit to (|0> - |1>)/((2)^(-1)), apply the black-box, then apply a final Hadamard to obtain the vector |a> over the first n qubits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def qubit_strings(n):\n",
    "    qubit_strings = []\n",
    "    for q in itertools.product(['0', '1'], repeat=n):\n",
    "        qubit_strings.append(''.join(q))\n",
    "    return qubit_strings"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def black_box_map(n, a):\n",
    "    \"\"\"\n",
    "    Black-box map, f(x) = x.a for all vectors x, given a\n",
    "    \"\"\"\n",
    "    qubs = qubit_strings(n)\n",
    "    # calculate each dot product x.a and store in a dict\n",
    "    d_blackbox = {}\n",
    "    for q in qubs:\n",
    "        dot_prod = 0\n",
    "        for i, xx in enumerate(q):\n",
    "            dot_prod += a[i] * int(xx)\n",
    "        d_blackbox[q] = dot_prod % 2\n",
    "\n",
    "    return d_blackbox"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def qubit_ket(qub_string):\n",
    "    \"\"\"\n",
    "    Form a basis ket out of n-bit string specified by the input 'qub_string', e.g.\n",
    "    '001' -> |001>\n",
    "    \"\"\"\n",
    "    e0 = np.array([[1], [0]])\n",
    "    e1 = np.array([[0], [1]])\n",
    "    d_qubstring = {'0': e0, '1': e1}\n",
    "\n",
    "    # initialize ket\n",
    "    ket = d_qubstring[qub_string[0]]\n",
    "    for i in range(1, len(qub_string)):\n",
    "        ket = np.kron(ket, d_qubstring[qub_string[i]])\n",
    "    \n",
    "    return ket"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def projection_op(qub_string):\n",
    "    \"\"\"\n",
    "    Creates a projection operator out of the basis element specified by 'qub_string', e.g.\n",
    "    '101' -> |101> <101|\n",
    "    \"\"\"\n",
    "    ket = qubit_ket(qub_string)\n",
    "    bra = np.transpose(ket)  # all entries real, so no complex conjugation necessary\n",
    "    proj = np.kron(ket, bra)\n",
    "    return proj"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def black_box(n, a):\n",
    "    \"\"\"\n",
    "    Unitary representation of the black-box operator on (n+1)-qubits, given the vector a\n",
    "    \"\"\"\n",
    "    d_bb = black_box_map(n, a)\n",
    "    # initialize unitary matrix\n",
    "    N = 2**(n+1)\n",
    "    unitary_rep = np.zeros(shape=(N, N))\n",
    "    # populate unitary matrix\n",
    "    for k, v in d_bb.items():\n",
    "        unitary_rep += np.kron(projection_op(k), np.eye(2) + v*(-np.eye(2) + np.array([[0, 1], [1, 0]])))\n",
    "        \n",
    "    return unitary_rep"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bernstein-Vazirani algorithm using (n+1) qubits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "This is the (randomly chosen) value of a:  [1 1 1 0 0]\n",
      "This is the measured values of the first 5 qubits at the end:  [1, 1, 1, 0, 0]\n"
     ]
    }
   ],
   "source": [
    "p = Program()\n",
    "\n",
    "# pick numer of control qubits to be used\n",
    "n = 5\n",
    "\n",
    "# pick a random value for the vector 'a'\n",
    "a = np.random.randint(low=0, high=2, size=n)\n",
    "print (\"This is the (randomly chosen) value of a: \", a)\n",
    "\n",
    "# Define U_f\n",
    "p.defgate(\"U_f\", black_box(n, a))\n",
    "\n",
    "# Prepare the starting state |0>^(\\otimes n) x (1/sqrt[2])*(|0> - |1>)\n",
    "for n_ in range(1, n+1):\n",
    "    p.inst(I(n_))\n",
    "p.inst(X(0))\n",
    "p.inst(H(0))\n",
    "\n",
    "# Apply H^(\\otimes n)\n",
    "for n_ in range(1, n+1):\n",
    "    p.inst(H(n_))\n",
    "    \n",
    "# Apply U_f\n",
    "p.inst((\"U_f\",) + tuple(range(n+1)[::-1]))\n",
    "\n",
    "# Apply final H^(\\otimes n)\n",
    "for n_ in range(1, n+1):\n",
    "    p.inst(H(n_))\n",
    "    \n",
    "# Final measurement\n",
    "classical_regs = list(range(n))\n",
    "for i, n_ in enumerate(list(range(1, n+1))[::-1]):\n",
    "    p.measure(n_, classical_regs[i])\n",
    "    \n",
    "qvm = api.QVMConnection()\n",
    "measure_n_qubits = qvm.run(p, classical_regs)\n",
    "\n",
    "# flatten out list\n",
    "measure_n_qubits = [item for sublist in measure_n_qubits for item in sublist]\n",
    "\n",
    "print (\"This is the measured values of the first %s qubits at the end: \" %n, measure_n_qubits)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}