{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# QUBO on Dirac\n",
    "#### Device: Dirac-1\n",
    "\n",
    "## Introduction\n",
    "\n",
    "\n",
    "Quadratic Unconstrained Binary Optimization (QUBO) problems are a class of optimization problems where the goal is to maximize or minimize a quadratic objective function without any constraints on the decision variables. Furthermore, QUBO problems serve as fundamental building blocks for more complex optimization models that can address many real-world problems. This tutorial will go through why QUBOs are valuable, what they can do, and how to run such problems on QCi's Dirac entropy computing systems.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Importance\n",
    "\n",
    "QUBO encodings tend to naturally arise in quantum settings, or any setting where variable interactions are directly encoded into physical interactions between bits. The reason for this is that physical interactions tend to naturally be two-body, while most constraints in computer science problems do not. For this reason, QUBOs are a natural underlying model to think about when using a wide variety of quantum optimization systems. Since QUBOs are formally NP-hard, it is technically possible to map any optimization problem to a QUBO. Efforts have been made to do so efficiently. For example, [this work](https://link.springer.com/article/10.1007/s10479-022-04634-2) expresses many common problems as QUBOs with the aim of bridging to quantum technology. QUBOs can be used to construct the kinds of linear constraints often found in optimization problems. Since automatic handling of such constraints is often very useful, we have also developed a related model called Quadratic Linearly Constrained Binary Optimization (QLCBO), which is documented in [this tutorial](https://quantumcomputinginc.com/learn/tutorials-and-use-cases/qlcbo-on-dirac). This lesson however will focus on using the underlying unconstrained model."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Applications\n",
    "\n",
    "QUBOs are fundamental in various fields, serving as a basis for formulating discrete combinatorial optimization problems. As an NP-hard problem, QUBO finds numerous applications across diverse domains, including machine learning, operations research, finance, chemistry, medicine, machine learning and beyond. A number of our tutorials and use cases use the QUBO representation directly:\n",
    "\n",
    "* [QBoost: A QUBO Based Binary Classification Method](https://quantumcomputinginc.com/learn/tutorials-and-use-cases/qboost-for-qubo)\n",
    "* [Max-Cut Demonstration using Dirac-1](https://quantumcomputinginc.com/learn/tutorials-and-use-cases/max-cut-on-dirac)\n",
    "* [Dimensionality reduction](https://quantumcomputinginc.com/learn/tutorials-and-use-cases/dimensionality-reduction-on-dirac)\n",
    "* [Set Partitioning](https://quantumcomputinginc.com/learn/tutorials-and-use-cases/set-partitioning-on-dirac) (A QUBO is sent to the device but linear constraints are constructed directly)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "## Mathematical Definition\n",
    "\n",
    "\n",
    "A Quadratic Unconstrained Binary Optimization (QUBO) defined by second order interactions between binary variables with no constraints, is defined by linear and quadratic terms, but since $x^2 = x$ when $x \\in \\{0,1\\}$, we can simplify the optimization expression as such $f(x) = \\sum_{i} \\sum_{j} J_{ij} x_i x_j$, where $f: \\mathbb{B}^n \\rightarrow \\mathbb{R}$. Note that the coefficients naturally encode as a square symmetric matrix, so that $f(x) = x^T Q x$, where $Q$ has entries $Q_{ij}$. The goal of the optimization problem is to find the binary vector, $x^{*}$, that minimizes $f(x)$, \n",
    "$x^{*} = \\mathop{\\arg \\min}_{x} x^T Q x$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Package Installation and Remote Connection\n",
    "Begin by importing the necessary packages:\n",
    "- `numpy`\n",
    "- `qci_client`\n",
    "- `os`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from qci_client import QciClient\n",
    "import os"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Establish connection with `qci_client` and QCi's server using your unique token ID and our default API URL."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "token = \"token_here\"\n",
    "api_url = \"https://api.qci-prod.com\"\n",
    "qclient = QciClient(api_token=token, url=api_url)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Uploading a QUBO job\n",
    "### Data format\n",
    "To upload a **square symmetric matrix** or QUBO, we encode it in a sparse matrix format as shown below. We use Numpy array notation. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "Q = np.array([[0, -1.5, 0.5], [-1.5, 0, 0], [0.5, 0, 0]]) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Enter your file credentials, including the QUBO file."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "qubo_data = {\n",
    "    'file_name': \"smallest_objective.json\",\n",
    "    'file_config': {'qubo':{\"data\": Q}}\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### Uploading\n",
    "To upload the matrix encoded above in `qubo_data`, we use the `qci_client` imported previously. The following line \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "response_json = qclient.upload_file(file=qubo_data)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The response contains a file_id for the uploaded file. This id is provided when a job is run, along with a few other parameters (see #Running). Note: the same `file_id` can be used multiple times to run a problem repeatedly. This enables an \"upload once, run many times\" scheme, which is especially useful for job types in which parameter searches may be involved.\n",
    "Triggering a job requires two items: first a job body that contains essential and optional metadata for the job, and second, the type of job a user wants to run. \n",
    "\n",
    "## Running a QUBO job\n",
    "### Job body\n",
    "This section defines the job body for a QUBO job. Be sure to state the Dirac device of your choice under `sampler_type` and the number of samples `nsamples` required for your job.  \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'job_submission': {'problem_config': {'quadratic_unconstrained_binary_optimization': {'qubo_file_id': '662faead98263204a36541fa'}},\n",
       "  'device_config': {'dirac-1': {'num_samples': 5}}}}"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "job_body = qclient.build_job_body(job_type=\"sample-qubo\",\n",
    "                                  qubo_file_id=response_json['file_id'],\n",
    "                                  job_params={\"device_type\": \"dirac-1\", \"num_samples\": 5})\n",
    "\n",
    "job_body"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once the `job_body` is complete, use `job_response` to start running your job on the Dirac device."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2024-04-29 15:29:26 - Dirac allocation balance = 0 s (unmetered)\n",
      "2024-04-29 15:29:26 - Job submitted: job_id='662faec6e15a79bd9d02c485'\n",
      "2024-04-29 15:29:26 - QUEUED\n",
      "2024-04-29 15:29:29 - RUNNING\n",
      "2024-04-29 15:31:05 - COMPLETED\n",
      "2024-04-29 15:31:08 - Dirac allocation balance = 0 s (unmetered)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'job_info': {'job_id': '662faec6e15a79bd9d02c485',\n",
       "  'job_submission': {'problem_config': {'quadratic_unconstrained_binary_optimization': {'qubo_file_id': '662faead98263204a36541fa'}},\n",
       "   'device_config': {'dirac-1': {'num_samples': 5}}},\n",
       "  'job_status': {'submitted_at_rfc3339nano': '2024-04-29T14:29:26.546Z',\n",
       "   'queued_at_rfc3339nano': '2024-04-29T14:29:26.547Z',\n",
       "   'running_at_rfc3339nano': '2024-04-29T14:29:26.943Z',\n",
       "   'completed_at_rfc3339nano': '2024-04-29T14:31:04.134Z'},\n",
       "  'job_result': {'file_id': '662faf2898263204a3654200', 'device_usage_s': 9}},\n",
       " 'status': 'COMPLETED',\n",
       " 'results': {'counts': [5], 'energies': [-3], 'solutions': [[1, 1, 0]]}}"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "job_response = qclient.process_job(job_body=job_body)\n",
    "job_response"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Below we show how to query the result object if an error occurs:\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'No errors detected'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def error_status(job_response):\n",
    "    try:\n",
    "        if job_response['status'] == \"ERROR\":\n",
    "            return job_response['status'], job_response['job_info']['results']['error']\n",
    "        else:\n",
    "            return \"No errors detected\"\n",
    "    except KeyError:\n",
    "        return \"Error: Unable to retrieve error status information from the job response\"\n",
    "\n",
    "error_status(job_response)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Dissecting results\n",
    "Under `file_config`, the job title and your results should be present in `solutions`.\n",
    "\n",
    "### `process_job` status\n",
    "Here, we have the `process_job` presenting the timestamp of each step of the run process."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "vscode": {
     "languageId": "latex"
    }
   },
   "source": [
    "```json\n",
    "Dirac allocation balance = 0\n",
    "\n",
    "Job submitted job_id='xxxxx'-: yyyy/mm/dd hh:mm:ss\n",
    "\n",
    "queued: yyyy/mm/dd hh:mm:ss\n",
    "\n",
    "running: yyyy/mm/dd hh:mm:ss\n",
    "\n",
    "completed: yyyy/mm/dd hh:mm:ss\n",
    "\n",
    "Dirac allocation balance = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `job_response` status\n",
    "Details pertaining to the configuration of your job are presented here, including information about the job submitted, `job_info`, the device chosen, `device_config`, the status of the job repeated from `process_job`, `job_status`, and details of whether the job was completed or uncompleted, `details`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```json\n",
    "{\n",
    "  \"job_info\": {\n",
    "    \"job_id\": \"6601958b832ac38bab8fe27f\",\n",
    "    \"job_submission\": {\n",
    "      \"problem_config\": {\n",
    "        \"quadratic_unconstrained_binary_optimization\": {\n",
    "          \"qubo_file_id\": \"6601953438d25ec78cae8a65\"\n",
    "        }\n",
    "      },\n",
    "\n",
    "      \"device_config\": {\n",
    "        \"dirac-1\": {\n",
    "          \"num_samples\": 1\n",
    "        }\n",
    "      }\n",
    "    },\n",
    "    \n",
    "    \"job_status\": {\n",
    "      \"submitted_at_rfc3339nano\": \"yyyy-mm-ddThh:mm:ss\",\n",
    "      \"queued_at_rfc3339nano\": \"yyyy-mm-ddThh:mm:ss\",\n",
    "      \"running_at_rfc3339nano\": \"yyyy-mm-ddThh:mm:ss\",\n",
    "      \"completed_at_rfc3339nano\": \"yyyy-mm-ddThh:mm:ss\"\n",
    "    },\n",
    "\n",
    "    \"job_result\": {\n",
    "      \"file_id\": \"660198fc38d25ec78cae8a67\",\n",
    "      \"device_usage_s\": 1\n",
    "    },\n",
    "    \n",
    "    \"details\": {\n",
    "      \"status\": \"completed\"\n",
    "    }\n",
    "  },\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `job_response` results\n",
    "Within the `job_response` we can identify the `solutions`, `energies`, and `counts` resulting from the job.\n",
    "\n",
    "`Solutions` are the binary solutions of the polynomial function.\n",
    "`Energies` are values obtained by evaluating a polynomial function at each solution obtained from the optimization process.\n",
    "`Counts` are the number of times a solution was found among all the samples taken."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```json\n",
    "{\n",
    "  \"results\": {\n",
    "    \"file_id\": \"660198fc38d25ec78cae8a67\",\n",
    "    \"num_parts\": 1,\n",
    "    \"num_bytes\": 235,\n",
    "    \"file_config\": {\n",
    "      \"quadratic_unconstrained_binary_optimization_results\": {\n",
    "        \"counts\": [1],\n",
    "        \"energies\": [-3],\n",
    "        \"solutions\": [[1, 1, 0]]\n",
    "      }\n",
    "    }\n",
    "  }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusion\n",
    "\n",
    "Quadratic Unconstrained Binary Optimization (QUBO) problems are the underlying model used by many quadratic solvers, based on physical interactions being naturally quadratic. Understanding QUBOs is therefore key to understanding how to solve problems on quantum hardware. Sometimes a slightly higher level of abstraction including constraints may also be useful, such as QLCBO as explained in [this tutorial](https://quantumcomputinginc.com/learn/tutorials-and-use-cases/qlcbo-on-dirac). If you feel like you understand QUBOs and want to see how they are applied without engineering constraints, then we encourage you to look at one of the lessons linked above. If however, your application includes constraints, you may wish to proceed to the QLCBO tutorial. Of course, once you are ready, you should try our device with one of your own problems."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "testing",
   "language": "python",
   "name": "testing"
  },
  "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.12.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}