exact_cover.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# -*- coding: utf-8 -*-\n",
    "# @author: S. Ramos\n",
    "import numpy as np\n",
    "from qutip import *\n",
    "from scipy import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"Qubit repetition\n",
    "returns list with the number of timess each qubit appears in an instance\n",
    "\"\"\"\n",
    "def Times(control, instance):\n",
    "    times = []\n",
    "    for i in range(control[0]):\n",
    "        times.append(0)\n",
    "    for clause in instance:\n",
    "        for num in clause:\n",
    "            times[num-1] += 1\n",
    "    return times\n",
    "\n",
    "\"\"\"Weight generation\n",
    "Assignes weights to each clause in the instance as a function of the repetition\n",
    "The weights are then normalized to the same maximum energy\n",
    "\"\"\"\n",
    "def Weights(control, times, instance):\n",
    "    coef = []\n",
    "    for clause in instance:\n",
    "        coef.append(times[clause[0]-1]+times[clause[1]-1]+times[clause[2]-1]-3)\n",
    "    norm = sum(coef)/control[1]\n",
    "    nWeight = [x / norm for x in coef]\n",
    "    return nWeight\n",
    "\n",
    "\"\"\"Initial Hamiltonian\n",
    "Creation of the initial product Hamiltonian. Uses the times a qubit appears in the instance\n",
    "\"\"\"\n",
    "def InitialH(control, sx_list, times):\n",
    "    HI = 0\n",
    "    for n in range(control[0]):\n",
    "        HI += times[n] * 0.5  * (1 - sx_list[n])\n",
    "    return HI\n",
    "\n",
    "\"\"\"Problem Hamiltonian\n",
    "Creation of the problem Hamiltonian of the Exact Cover without weights\n",
    "\"\"\"\n",
    "def ProblemH(control, Z_list, instance):\n",
    "    HP = 0\n",
    "    for i in range(control[1]):\n",
    "        HP += (Z_list[instance[i][0]-1]+Z_list[instance[i][1]-1]+Z_list[instance[i][2]-1]-1)**2.0\n",
    "    return HP\n",
    "\n",
    "\"\"\"Weighted Hamiltonian\n",
    "Creation of the problem Hamiltonian of the Exact Cover with weights\n",
    "\"\"\"\n",
    "def WeightedH(control, Z_list, instance, weight):\n",
    "    HW = 0\n",
    "    for i in range(control[1]):\n",
    "        HW += (weight[i])*(Z_list[instance[i][0]-1]+Z_list[instance[i][1]-1]+Z_list[instance[i][2]-1]-1)**2.00\n",
    "    return HW\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"Gap evolution of an Exact Cover Problem\n",
    "Inputs:\n",
    "    File with information of an Exact Cover Instance\n",
    "    Time evolution of the problem\n",
    "    W = True : if a weighted Problem Hamiltonian is desired \n",
    "\"\"\"\n",
    "def ExactCoverGap(file, taulist, args, W=True):\n",
    "    control = list(map(int, file.readline().split()))\n",
    "    solution = list(map(str, file.readline().split()))\n",
    "    \n",
    "    \"\"\"\n",
    "    Creation of the operators used for the Hamiltonians using the dimensions of the problem\n",
    "    \"\"\"\n",
    "    si = qeye(2)\n",
    "    sx = sigmax()\n",
    "    sz = sigmaz()\n",
    "    Z = (si - sz)/2.0\n",
    "    sx_list = []\n",
    "    Z_list = []\n",
    "    for n in range(control[0]):\n",
    "        op_list = []\n",
    "        for m in range(control[0]):\n",
    "            op_list.append(si)\n",
    "        op_list[n] = sx\n",
    "        sx_list.append(tensor(op_list))\n",
    "        op_list[n] = Z\n",
    "        Z_list.append(tensor(op_list))\n",
    "    \n",
    "    \"\"\"\n",
    "    Reads from the file and separates the clauses of the instance in lists\n",
    "    \"\"\"\n",
    "    instance = []\n",
    "    for i in range(control[1]):\n",
    "        instance.append(list(map(int, file.readline().split())))\n",
    "    \n",
    "    \"\"\"\n",
    "    Creates the initial and problem Hamiltonians, if W == False, the Hamiltonian is not weighted\n",
    "    \"\"\"\n",
    "    times = Times(control, instance)\n",
    "    H0 = InitialH(control, sx_list, times)\n",
    "    if W == True:\n",
    "        weight = Weights(control, times, instance)\n",
    "        H1 = WeightedH(control, Z_list, instance, weight)\n",
    "    else:\n",
    "        H1 = ProblemH(control, Z_list, instance)\n",
    "        \n",
    "    \"\"\"\n",
    "    Resolves and calculates the gap energy for the given time period. \n",
    "    For instances of more than 9 qubits, a sparse method of solving the diagonalization is faster\n",
    "    \"\"\"\n",
    "    Gap = []\n",
    "    for t in taulist:\n",
    "        H = (1.0 - (t/args['t_max'])) * H0 + (t/args['t_max']) * H1\n",
    "        if control[0] > 9:\n",
    "            evals, ekets = H.eigenstates(sparse=True, eigvals=2, tol=1.0e-3, maxiter=10000)\n",
    "            Gap.append(evals[1]-evals[0])\n",
    "        else:\n",
    "            evals, ekets = H.eigenstates(eigvals=2)\n",
    "            Gap.append(evals[1]-evals[0])\n",
    "          \n",
    "    \"\"\"\n",
    "    Checks if the final reult of the evolution coinciedes with the given in the input file\n",
    "    \"\"\"\n",
    "    s = 0\n",
    "    for i in ekets[0]:\n",
    "        if i == 0:\n",
    "            s += 1\n",
    "        if i != 0:\n",
    "            ss = s\n",
    "            break\n",
    "    form = '{0:0%sb}' % str(control[0])\n",
    "    if (form.format(ss)) != (''.join(solution)):\n",
    "        print('error')\n",
    "    \n",
    "    return Gap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 qubits:\n",
      "0.212299146269\n",
      "\n",
      "14 qubits:\n",
      "0.15505001457\n"
     ]
    }
   ],
   "source": [
    "\"\"\"Example\n",
    "Example of tha calculation of one Gap Energy for an instance of 10 and 14 qubits\n",
    "\"\"\"\n",
    "\n",
    "taumax = 10.0\n",
    "taulist = np.linspace(0.0, 10.0, 500)\n",
    "args = {'t_max': taumax}\n",
    "\n",
    "instance10 = open('n10i1.txt')\n",
    "instance14 = open('n14i1.txt')\n",
    "\n",
    "Gap10 = ExactCoverGap(instance10, taulist, args, W = True)\n",
    "\n",
    "Gap14 = ExactCoverGap(instance14, taulist, args, W = False)\n",
    "\n",
    "print('10 qubits:')\n",
    "print(min(Gap10))\n",
    "print()\n",
    "print('14 qubits:')\n",
    "print(min(Gap14))"
   ]
  },
  {
   "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
}