examples/quantum_annealing/Running_large_problems_using_QBSolv.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Running large problems on D-Wave QPUs using QBSolv"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To solve a problem with a D-Wave QPU, one defines the problem in QUBO (or Ising) form. Owing to the limited qubit connectivity in D-Wave devices, the source graph given by the QUBO (or Ising) problem must be mapped to the target graph of the underlying hardware following a process called minor embedding. For the D-Wave 2000Q device with a Chimera graph, there is no guarantee to find an embedding for a problem with more than 64 variables; for the Advantage device with a Pegasus graph, the upper limit for an arbitrary problem is around 145. However, some real-world problems may require more variables than a QPU can support. To solve large problems with the D-Wave devices, you can use `QBSolv()`, which is offered by the Ocean SDK.\n",
    "\n",
    "`QBSolv()` is a hybrid solver that can decompose large QUBO problems into sub-problems. The sub-problems are solved using either both the QPU and a classical Tabu solver, or the classical solver alone. The solution to the problem is then constructed by the results of the sub-problems. More details can be found in the D-Wave documentation [here](https://docs.ocean.dwavesys.com/projects/qbsolv/en/latest/).\n",
    "\n",
    "This notebook demonstrates how to run large problems with `QBsolv()` on Amazon Braket."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## General imports"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import itertools\n",
    "from itertools import combinations\n",
    "import networkx as nx\n",
    "from collections import defaultdict\n",
    "from dwave_qbsolv import QBSolv\n",
    "from dwave.system.composites import FixedEmbeddingComposite\n",
    "from braket.ocean_plugin import BraketSampler, BraketDWaveSampler\n",
    "import minorminer\n",
    "import time"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Define the problem\n",
    "\n",
    "`QBSolv()` accepts input models in QUBO, Ising or BQM forms, which correspond to `QBSolv().sample_qubo()`, `QBSolv().sample_ising()` and `QBSolv().sample()` methods respectively. This notebook takes a random QUBO problem as the example.\n",
    "\n",
    "The following code generates a random graph and constructs a QUBO matrix as the problem to solve.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# number of nodes\n",
    "nodes = 240\n",
    "# number of edges\n",
    "edges = round(nodes * (nodes-1)/2 * 0.4)\n",
    "seed = 2\n",
    "\n",
    "# generate a random graph\n",
    "Graph = nx.gnm_random_graph(nodes, edges, seed)\n",
    "\n",
    "# Initialize the QUBO matrix\n",
    "QUBO = defaultdict(int)\n",
    "\n",
    "# Update the QUBO matrix for every edge in the graph\n",
    "for u, v in Graph.edges:\n",
    "    QUBO[(u,u)]+= -1\n",
    "    QUBO[(v,v)]+= -3\n",
    "    QUBO[(u,v)]+= 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Run tasks with QBSolv\n",
    "\n",
    "You can specify the size of the sub-problems with the `solver_limit` parameter, and choose a solver to run the sub-problems. Note if the size of the problem you want to solve is smaller than this value, the task will run only with the Tabu solver. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# define size of the sub-problems\n",
    "solver_limit = 40\n",
    "\n",
    "# choose a D-Wave Advantage system\n",
    "system = BraketDWaveSampler(device_arn='arn:aws:braket:::device/qpu/d-wave/Advantage_system4')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To run sub-problems on a D-Wave QPU, you must find an embedding to map the sub-problems to the graph of the device. The following example finds an embedding of a complete graph (thus is applicable to any problem of the same size), and provides the embedding to the solve using the `FixedEmbeddingComposite()` method. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 ... 239   energy num_oc.\n",
      "0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 ...   1 -25884.0       1\n",
      "1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 ...   1 -25884.0       2\n",
      "['BINARY', 2 rows, 3 samples, 240 variables]\n"
     ]
    }
   ],
   "source": [
    "# find embedding of subproblem-sized complete graph to the QPU\n",
    "G = nx.complete_graph(solver_limit)\n",
    "embedding = minorminer.find_embedding(G.edges, system.edgelist)\n",
    "\n",
    "# use the FixedEmbeddingComposite() method with a fixed embedding\n",
    "solver = FixedEmbeddingComposite(system, embedding)\n",
    "\n",
    "# define the number of repeats for the hybrid solver to search for the optimal solution.\n",
    "num_repeats = 2\n",
    "\n",
    "# define the number of shots (or reads) per task on the D-Wave QPU\n",
    "num_reads = 100 # the default value for D-Wave Advantage_system4.1 is 1000\n",
    "\n",
    "response = QBSolv().sample_qubo(QUBO, solver=solver, num_repeats=num_repeats, solver_limit=solver_limit, num_reads=num_reads)\n",
    "print(response)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "More information on the input parameters and a detailed description of the algorithm can be found [here](https://docs.ocean.dwavesys.com/projects/qbsolv/en/latest/intro.html)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "conda_braket",
   "language": "python",
   "name": "conda_braket"
  },
  "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.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}