01-factoring-overview.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Factoring with D-Wave Quantum Computers\n",
    "\n",
    "In the [Leap](https://cloud.dwavesys.com/leap) factoring demo, you saw how a D-Wave quantum computer factored an integer by running a multiplication circuit in reverse.\n",
    "\n",
    "This notebook demonstrates how you can solve a [constraint satisfaction problem](https://docs.ocean.dwavesys.com/en/stable/concepts/csp.html) (CSP) on a quantum computer with the example of factoring. \n",
    "\n",
    "1. [Factoring as a Constraint Satisfaction Problem](#Factoring-as-a-Constraint-Satisfaction-Problem) describes the factoring problem as an example CSP.\n",
    "2. [Formulating the Problem for a D-Wave Quantum Computer](#Formulating-the-Problem-for-a-D-Wave-Quantum-Computer) shows how such CSPs can be formulated for solution on a quantum computer.\n",
    "3. [A Simple Example](#A-Simple-Example) codes a small CSP to clarify the solution technique.\n",
    "4. [Factoring on the Quantum Computer](#Factoring-on-the-Quantum-Computer) codes a factoring problem for solution on a D-Wave quantum computer.\n",
    "5. [Further Information](#Further-Information) details some points touched on in previous sections and examines more closely the results returned from the quantum computer. \n",
    "\n",
    "This notebook  should help you understand both the techniques and [Ocean software](https://github.com/dwavesystems) tools used for solving CSPs on D-Wave quantum computers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**New to Jupyter Notebooks?** JNs are divided into text or code cells. Pressing the **Run** button in the menu bar moves to the next cell. Code cells are marked by an \"In: \\[\\]\" to the left; when run, an asterisk displays until code completion: \"In: \\[\\*\\]\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Factoring as a Constraint Satisfaction Problem\n",
    "The [complexity class](https://en.wikipedia.org/wiki/Complexity_class) for classical integer factoring is believed to be between P and NP-hard.  Although research has yielded algorithms that perform faster than the intuitive trial division, including Fermat's algorithm, Pollard's two algorithms, and sieve algorithms, it's still an open question whether a classical algorithm exists that can factor in [polynomial time](https://en.wikipedia.org/wiki/Time_complexity). For quantum computing, Shor's algorithm runs in polynomial time (D-Wave quantum computers do not run this algorithm).  \n",
    "\n",
    "This notebook solves factoring on a D-Wave quantum computer by formulating it as a *[constraint satisfaction problem](https://docs.ocean.dwavesys.com/en/stable/concepts/csp.html)*. CSPs require that all a problem's variables be assigned values that result in the satisfying of all constraints. For factoring, the problem's constraints are that the two variables representing factors, $a$ and $b$, be assigned only natural numbers and that their multiplication be equal to the factored number, $P$. \n",
    "\n",
    "Among CSPs are hard problems well suited to solution on quantum computers. For example, the map-coloring problem is to color all regions of a map such that any two regions sharing a border have different colors (see a D-Wave quantum computer solve a four-color map-coloring problem here: [Ocean software examples](https://docs.ocean.dwavesys.com/en/stable/getting_started.html#examples)). The job-shop scheduling problem is to schedule multiple jobs done on several machines with constraints on the machines' execution of tasks. You can apply the solution technique shown here to many CSPs. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Formulating the Problem for a D-Wave Quantum Computer\n",
    "How can you formulate the factoring problem in a way that a quantum computer can understand? \n",
    "\n",
    "D-Wave quantum computers solve [binary quadratic models](https://docs.ocean.dwavesys.com/en/stable/concepts/bqm.html) (BQM), the [Ising](#https://en.wikipedia.org/wiki/Ising_model) model traditionally used in statistical mechanics and its computer-science equivalent, the [quadratic unconstrained binary optimization](https://en.wikipedia.org/wiki/Quadratic_unconstrained_binary_optimization) (QUBO) problem. Given $N$ variables $x_1,...,x_N$, where each variable $x_i$ can have binary values $0$ or $1$, the quantum computer finds assignments of values that minimize the QUBO\n",
    "\n",
    "$\\sum_i^N q_ix_i + \\sum_{i<j}^N q_{i,j}x_i  x_j$,\n",
    "\n",
    "where $q_i$ and $q_{i,j}$ are configurable (linear and quadratic) coefficients. To formulate a problem for a D-Wave quantum computer is to program $q_i$ and $q_{i,j}$ so that assignments of $x_1,...,x_N$ also represent solutions to the problem.\n",
    "\n",
    "There are different ways to formulate the factoring problem as a BQM. Formulation A starts with an intuitive one. \n",
    "\n",
    "## Formulation A\n",
    "<div class=\"alert alert-warning\" role=\"alert\" style=\"margin: 10px\">Skip this subsection if you prefer to move on to what this notebook codes. Or try implementing it yourself as an exercise, although this is not the recommended formulation.</div>\n",
    "\n",
    "You can solve an equation, say $x+1=2$, by minimizing the square of the subtraction of one side from another, $\\min_x[2-(x+1)]^2$. Intuitively such a minimization seeks the shortest distance between the sides, which occurs at equality, with the square eliminating negative distance. \n",
    "\n",
    "For a factored number, $P$, to be equal to its factors, $a, b$, you can solve  $P=ab$ with the minimization\n",
    "\n",
    "$\\min_{a,b}(P-ab)^2$.\n",
    "\n",
    "To solve this minimization on a quantum computer, you would represent the integers with equivalent binary numbers; for example, integer $a$ is represented as $a_0 + 2a_1 + 4a_2 +... +2^ma_m$, where variables $a_i$ can have binary values $0$ or $1$. \n",
    "\n",
    "D-Wave quantum computers solve binary *quadratic* models so this now-binary minimization should not have terms with higher order than $a_ib_j$. However, squaring $(P-ab)$ introduces non-quadratic terms for problems of any decent size. You would therefore use [order reduction](https://docs.dwavesys.com/docs/latest/handbook_reformulating.html) techniques on all higher terms. For example, by introducing a new variable $x_k=a_0b_2$, you can replace a non-quadratic term such as $8b_0b_2a_0^2$ with quadratic term $8b_0x_k$ (notice that $a_0^2=a_0$), and do so repeatedly until all terms are linear or quadratic. \n",
    "\n",
    "You would now have a BQM. Programming its coefficients on a D-Wave quantum computer would solve the factoring problem. \n",
    "\n",
    "## Formulation B\n",
    "\n",
    "Formulation A above produces a BQM in three steps: (1) state equation $P=ab$ as a minimization, (2) represent integers as binary numbers, and (3) reduce to quadratic.\n",
    "   \n",
    "An alternative is to express the constraints of the problem with Boolean logic. This technique is very versatile: modern computing is built on Boolean gates, the scope of addressable problems is immense. The implementation below follows these steps:\n",
    "\n",
    "1. Express $P=ab$ as a CSP with a binary multiplication circuit.\n",
    "2. Convert to a BQM.\n",
    "3. Program the quantum computer with the BQM's coefficients.\n",
    "\n",
    "Some differences between the two formulations are noted below."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# A Simple Example\n",
    "This section illustrates the steps of Formulation B above on a very simple problem: a circuit with two switches that turns on a light. \n",
    "\n",
    "<img src=\"images/example_light_and_switches.png\" width=300x/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step 1: Express as a CSP with Boolean Logic\n",
    "\n",
    "You can express the problem of how to turn on the light as a CSP with a single constraint: for light $L$ to shine, both switches $SW_1$ and $SW_2$ must be on. In logic, you express this constraint as the [conjunction](https://en.wikipedia.org/wiki/Logical_conjunction) $L = SW_1 \\wedge SW_2$. \n",
    "\n",
    "Unlike real-world CSPs, which can have thousands of constraints to satisfy simultaneously, the one constraint of this trivial CSP also expresses its solution. Although you forgo a surprise ending, it's instructive to run through the steps needed to \"solve the problem\".\n",
    "\n",
    "First, express the CSP with binary variables:\n",
    "\n",
    "* Switches $SW_1$ and $SW_2$ are represented by binary variables $x_1, x_2$ with values 1 when on and 0 when off.\n",
    "* Light $L$ is represented by binary variable $x_3$ with value 1 if it's shining and 0 if not.\n",
    "* Logical conjunction, $L = SW_1 \\wedge SW_2$, is expressed in binary format as $x_3 = x_1 \\wedge x_2$. \n",
    "\n",
    "The graphic below shows an AND gate and its [truth table](https://en.wikipedia.org/wiki/Truth_table), which gives the gate's output, $x_3$, for all combinations of inputs $x_1, x_2$. \n",
    "\n",
    "<img src=\"images/AND_TruthTableandGate.png\" width=300x/>\n",
    "\n",
    "It's clear from the table that the problem's constraint, $L = SW_1 \\wedge SW_2$, and the AND gate's operation, $x_3 = x_1x_2$, are equivalent. You can express the constraint as an AND gate. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step 2: Convert to a BQM \n",
    "The quantum computer solves binary quadratic models. Express the light-circuit CSP as a BQM.\n",
    "\n",
    "An advantage of Formulation B is that BQMs are known for logic gates ([D-Wave system documentation](https://docs.dwavesys.com/docs/latest/handbook_reformulating.html) gives the BQMs for common Boolean gates and [Ocean documentation](https://docs.ocean.dwavesys.com/en/stable/getting_started.html#examples) has usage examples). More than one BQM can represent an AND gate: it's just a polynomial of binary variables, with only linear and quadratic terms, that has lowest value for variables that match rows of the AND truth table; for example, \n",
    "\n",
    "$3x_3 + x_1x_2 - 2x_1x_3 - 2x_2x_3$.\n",
    "\n",
    "To see that this BQM represents the AND gate, you can set its variables to the values of the AND truth table (e.g., $x_1, x_2, x_3=0,0,0$) and to non-valid values (e.g., $ x_1, x_2, x_3=0,0,1$). All the former should produce lower values than any of the latter. \n",
    "\n",
    "Use `itertools` to produce all possible configurations of $ x_1, x_2, x_3$, and then print these (under \"x1, x2, x3\") to the right of the BQM's value (under \"E\"), sorted from low to high.\n",
    "\n",
    "Run the cell below by pressing the **Run** button with your mouse in the cell. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import itertools\n",
    "\n",
    "configurations = []\n",
    "for (x1, x2, x3) in  list(itertools.product([0, 1], repeat=3)):\n",
    "     E = 3*x3+x1*x2-2*x1*x3-2*x2*x3\n",
    "     configurations.append((E, x1, x2, x3))\n",
    "\n",
    "configurations.sort()\n",
    "\n",
    "print(\"E, x1, x2, x3\")\n",
    "configurations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use Ocean's [dimod](https://docs.ocean.dwavesys.com/en/stable/docs_dimod/sdk_index.html) to generate a BQM, then print out the BQM's coefficients, the inputs used to program a D-Wave quantum computer. As noted, more than one BQM can represent an AND gate, so the BQM generated here does not have to match the one written above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from dimod.generators import and_gate\n",
    "\n",
    "and_bqm = and_gate(\"x1\", \"x2\", \"x3\")\n",
    "\n",
    "print(\"Linear coefficients:\\n\\t{}\".format(\n",
    "      {key: val for key, val in and_bqm.linear.items()}))\n",
    "print(\"Quadratic coefficients:\\n\\t{}\".format(\n",
    "      {key: val for key, val in and_bqm.quadratic.items()}))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step 3: Solve By Minimization \n",
    "Lastly, solve the problem by finding variable values that produce the BQM's lowest values. For real-world problems, with large numbers of variables and constraints, minimizing a BQM is hard: this is where a quantum computer comes in handy. \n",
    "\n",
    "The next section, which solves a factoring problem, uses a D-Wave quantum computer. For this trivial example, instead of using a D-Wave quantum computer as the *sampler* (the component used to minimize a BQM), use one of Ocean software's test samplers. Ocean's [dimod](https://docs.ocean.dwavesys.com/en/stable/docs_dimod/sdk_index.html) provides one that simply returns the BQM's value for every possible assignment of variable values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from dimod import ExactSolver\n",
    "\n",
    "sampler = ExactSolver()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Print the BQM's values (\"energy\") in ascending order. Note that they are indeed lowest for valid assignments&mdash;values under \"x1, x2, x3\" match rows of the AND truth table&mdash;and higher for non-valid ones. (The `num_oc.`column, which specifies the number of returned occurrences for a particular solution, is irrelevant here.) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution = sampler.sample(and_bqm)\n",
    "\n",
    "print(solution)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note: to understand the examples of this Jupyter Notebook, it's enough to understand that samplers such as D-Wave quantum computers find solutions that minimize a BQM. If you want further details on that minimization (the \"energy\" here and \"E\" previously), see below under [Further Information](#Further-Information)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Factoring on the Quantum Computer\n",
    "This section solves a factoring problem as a CSP, following the same steps used for the simple problem of the light circuit:\n",
    "\n",
    "1. Express factoring as a CSP using Boolean logic operations.\n",
    "2. Convert to a BQM.\n",
    "3. Minimize the BQM."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step 1: Express Factoring as Multiplication Circuit\n",
    "Again start by expressing the problem with Boolean logic gates, in this case a multiplication circuit.\n",
    "\n",
    "This example factors integer 21 which is represented as a 6-bit binary number. To express the factoring equation, $P = ab$, in Boolean logic, use a simple 3-bit multiplier (a circuit that takes two 3-bit binary numbers and outputs their 6-bit binary product).  \n",
    "\n",
    "Note: Binary multipliers are made with logic gates like the AND gate used above. Understanding the factoring example and its application to solving CSPs does not require an understanding of binary multiplication. If you do want to know more, see below under [Further Information](#Further-Information)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "P = 21  \n",
    "\n",
    "bP = \"{:06b}\".format(P)    # \"{:06b}\" formats for 6-bit binary\n",
    "print(bP)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step 2: Convert to a BQM\n",
    "\n",
    "Express the multiplication circuit as a BQM that provides the coefficients used to program the problem on a D-Wave quantum computer.\n",
    "\n",
    "Ocean's [dimod](https://docs.ocean.dwavesys.com/en/stable/docs_dimod/sdk_index.html) has generators for Boolean gates that includes a BQM for a multiplication circuit.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from dimod.generators import multiplication_circuit \n",
    "\n",
    "bqm = multiplication_circuit(3)\n",
    "\n",
    "print(\"BQM has {} variables: \\n\\t{}\".format(len(bqm.variables), list(bqm.variables)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The next cell visualizes a BQM for a $3X3$ multiplication circuit. Each node of the graph represents a variable; these include P and its factors as binary numbers, and some internal variables of the multiplication circuit.\n",
    "\n",
    "<img src=\"images/bqm_3x3_mult.png\" width=700x/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As in the [Leap](https://cloud.dwavesys.com/leap) factoring demo, the D-Wave quantum computer factors this integer by running a multiplication circuit in reverse. Below, fix the variables of the multiplication circuit's BQM to the binary digits of the factored number P (represented by binary variables P0, P1...P6). This modifies the BQM by removing the known variables and updating neighboring values accordingly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "p_vars = ['p0', 'p1', 'p2', 'p3', 'p4', 'p5']\n",
    "\n",
    "# Convert P from decimal to binary\n",
    "fixed_variables = dict(zip(reversed(p_vars), \"{:06b}\".format(P)))\n",
    "fixed_variables = {var: int(x) for(var, x) in fixed_variables.items()}\n",
    "\n",
    "# Fix product variables\n",
    "for var, value in fixed_variables.items():\n",
    "    bqm.fix_variable(var, value)\n",
    "    \n",
    "print(\"BQM has {} non-fixed variables: \\n\\t{}\".format(len(bqm.variables), list(bqm.variables)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step 3: Submit to the Quantum Computer\n",
    "Lastly, solve the BQM by finding variable assignments that produce its lowest values. Here you use a D-Wave quantum computer. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Setting Up a Solver\n",
    "Set up a D-Wave quantum computer as your solver in the standard way described in the Ocean documentation's [Configuring Access to D-Wave Solvers](https://docs.ocean.dwavesys.com/en/stable/overview/sapi.html). \n",
    "\n",
    "Set a *sampler*, the component used to find variable values that minimize the binary quadratic model representing the problem. Here, use a D-Wave quantum computer, but Ocean tools are designed to swap in and out samplers with ease. For example you might first run a classical sampler on your computer's CPU during testing, and only once your code is ready, submit the problem for solution on the quantum computer.   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from dwave.system import DWaveSampler\n",
    "\n",
    "# Use a D-Wave system as the sampler\n",
    "sampler = DWaveSampler() \n",
    "\n",
    "print(\"QPU {} was selected.\".format(sampler.solver.name))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mapping between the problem graph&mdash;the multiplication circuit's graph with nodes labeled \"a0\", \"b0\" etc.&mdash;to the D-Wave QPU's numerically indexed qubits, is known as *minor-embedding*. A problem can be minor embedded onto the QPU in a variety of ways and this affects solution quality and performance. \n",
    "\n",
    "Ocean software provides a variety of embedding tools. This example uses [dwave-system](https://docs.ocean.dwavesys.com/en/stable/docs_system/sdk_index.html) *EmbeddingComposite()* that automatically handles minor-embedding."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from dwave.system import EmbeddingComposite\n",
    "\n",
    "embedding_sampler = EmbeddingComposite(sampler)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When the D‑Wave quantum computer solves a problem, it uses quantum phenomena such as superposition and tunneling to explore all possible solutions simultaneously and find a set of the best ones. Because the sampled solution is probabilistic, returned solutions may differ between runs. Typically, when submitting a problem to a quantum computer, you ask for many samples, not just one. This way, you see multiple answers and reduce the probability of settling on a suboptimal answer.\n",
    "\n",
    "In the code below, `num_reads` should provide enough samples to make it likely a valid answer is among them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sampleset = embedding_sampler.sample(bqm, num_reads=100, label='Notebook - Factoring')\n",
    "\n",
    "print(\"Best solution found: \\n\",sampleset.first.sample)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Viewing the Solution\n",
    "Convert back from binary numbers to integers. Because quantum computing is probabilistic, there is a slight chance that in many executions of this example, your execution might return an incorrect solution. Rerunning the previous cell will most likely produce a correct answer. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# To see helper functions, select Jupyter File Explorer View from the Online Learning page\n",
    "from helpers.convert import to_base_ten\n",
    " \n",
    "a, b = to_base_ten(sampleset.first.sample)\n",
    "\n",
    "print(\"Given integer P={}, found factors a={} and b={}\".format(P, a, b))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Summary\n",
    "\n",
    "This Jupyter Notebook showed how you can formulate a constraint satisfaction problem for solution on a quantum computer using Ocean software. You solved a factoring problem as an example of one proposed solution technique.   \n",
    "\n",
    "You saw two ways of formulating the factoring problem. Formulation A is intuitive and direct, but conversion of large integers to binary introduces (a) increasing weights per bit, $2^ma_m$, and (b) in the squaring of $(P-ab)$, terms of higher order that need to be reduced to quadratic. These affect performance. Formulation B, using binary gates, is a useful technique in general. The modularity of binary gates provides some benefits for minor-embedding: repeated small units that can be tiled onto the QPU's topology.       "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Further Information\n",
    "\n",
    "This section provides more information on binary multiplication, minimizing BQMs, sampling for solutions, and minor-embedding.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Multiplication\n",
    "\n",
    "Binary number multiplication works the same way that multiplication is taught in school. That is, for two 3-bit numbers $a_2a_1a_0$ and $b_2b_1b_0$, the multiplication is written as\n",
    "\n",
    "\\begin{array}{rrrrrr}\n",
    "&  &  &  &  & \\\\\n",
    "&  &  & a_{2} & a_{1} & a_{0}\\\\\n",
    "\\times &  &  & b_{2} & b_{1} & b_{0}\\\\\n",
    "\\hline \n",
    "& 0 & 0 & b_{0}a_{2} & b_{0}a_{1} & b_{0}a_{0}\\\\\n",
    "& 0 & b_{1}a_{2} & b_{1}a_{1} & b_{1}a_{0} & 0\\\\\n",
    "& b_{2}a_{2} & b_{2}a_{1} & b_{2}a_{0} & 0 & 0\\\\\n",
    "\\hline \n",
    "p_{5}  & p_{4} & p_{3} & p_{2} & p_{1} & p_{0}\\\\\n",
    "\\end{array}\n",
    "\n",
    "where each $p_i$ is the sum of the values in the $i$-th column; for example, $p_2 = b_{0}a_{2} + b_{1}a_{1} + b_{2}a_{0}$.\n",
    "\n",
    "A binary multiplication circuit represents each of the nine products $b_ia_j$ as an AND gate and each of the three summations of 5-bit partial products as an adder.\n",
    "\n",
    "<img src=\"images/BinaryMultiplicationCircuit_gates.png\" width=400x/>\n",
    "\n",
    "The simple implementation used by this example does not support two's complement, carry lookahead, or any other nifty features. If you're curious, [this Wikipedia article](https://en.wikipedia.org/wiki/Binary_multiplier) is a great place to start.\n",
    "\n",
    "In the circuit below, given inputs 011 (3) and 111 (7), the circuit outputs 010101 (21). \n",
    "\n",
    "<img src=\"images/21.jpg\" width=400x/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Minimizing BQMs\n",
    "\n",
    "A fundamental rule of physics is that everything tends to seek a minimum energy state. Objects slide down hills; hot things cool down over time. This behavior is also true in the world of quantum physics. To solve optimization problems on a D-Wave quantum computer, you frame them as energy-minimization problems, and solve them through the physics of the QPU, which finds low-energy states.\n",
    "\n",
    "D-Wave quantum computers solve a subset of binary quadratic models, the Ising and quadratic unconstrained binary optimization (QUBO) problems, by finding assignments of variables that correspond to minimum energy.\n",
    "\n",
    "For the Ising model, $N$ variables $\\bf s=[s_1,...,s_N]$ correspond to physical Ising spins, where $h_i$ are the biases and $J_{i,j}$ the couplings (interactions) between spins.\n",
    "\n",
    "$\\text{Ising:} \\qquad\n",
    "  E(\\bf{s}|\\bf{h},\\bf{J})\n",
    "  = \\left\\{ \\sum_{i=1}^N h_i s_i +\n",
    "  \\sum_{i<j}^N J_{i,j} s_i s_j  \\right\\}\n",
    "  \\qquad\\qquad s_i\\in\\{-1,+1\\}$\n",
    "\n",
    "For the QUBO model, $N$ binary variables represented as an upper-diagonal matrix $Q$, where diagonal terms are the linear coefficients and the nonzero off-diagonal terms the quadratic coefficients.\n",
    "\n",
    "$\\text{QUBO:} \\qquad E(\\bf{x}| \\bf{Q})\n",
    "    =  \\sum_{i\\le j}^N x_i Q_{i,j} x_j\n",
    "    \\qquad\\qquad x_i\\in \\{0,1\\}$\n",
    "\n",
    "The BQM you formulate to express a problem sets up qubits representing the binary variables on the QPU. The QPU finds low-energy states of the qubits. In most cases, the lower the energy, the better the solution. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Samples and Solutions\n",
    "\n",
    "[Samplers](https://docs.ocean.dwavesys.com/en/stable/concepts/samplers.html) are processes that sample from low energy states of an [objective function](https://docs.ocean.dwavesys.com/en/stable/concepts/index.html), which is a mathematical expression of the energy of a system. A binary quadratic model (BQM) sampler samples from low energy states in models such as those defined by an Ising model traditionally used in statistical mechanics or its computer-science equivalent, the QUBO, and returns an iterable of samples, in order of increasing energy.\n",
    "\n",
    "The D-Wave quantum computer returns a [dimod.SampleSet](https://docs.ocean.dwavesys.com/en/stable/docs_dimod/reference/sampleset.html) object that contains all of the information about the generated samples and has some access methods. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "View the energy (rounded to two decimal places) of the samples, using a `dict` mapping pairs `(a, b)` to information about them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import OrderedDict\n",
    "\n",
    "def response_to_dict(sampleset):\n",
    "    results_dict = OrderedDict()\n",
    "    for sample, energy in sampleset.data(['sample', 'energy']):\n",
    "        a, b = to_base_ten(sample)\n",
    "        if (a, b) not in results_dict:\n",
    "            results_dict[(a, b)] = round(energy, 2)\n",
    "            \n",
    "    return results_dict\n",
    "\n",
    "results = response_to_dict(sampleset)\n",
    "results"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Create a scatter plot of the samples and their energies, showing that the lowest energy states correspond to correct answers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from helpers import draw\n",
    "draw.energy_of(results)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Copyright &copy; 2020 D-Wave Systems, Inc\n",
    "\n",
    "The software is licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "you may not use this file except in compliance with the License.\n",
    "You may obtain a copy of the License at\n",
    "\n",
    "    http://www.apache.org/licenses/LICENSE-2.0\n",
    "\n",
    "Unless required by applicable law or agreed to in writing, software\n",
    "distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "See the License for the specific language governing permissions and\n",
    "limitations under the License.\n",
    "\n",
    "<a rel=\"license\" href=\"http://creativecommons.org/licenses/by-nc-sa/4.0/\"><img alt=\"Creative Commons License\" style=\"border-width:0\" src=\"https://i.creativecommons.org/l/by-nc-sa/4.0/88x31.png\" /></a><br />This Jupyter Notebook is licensed under a <a rel=\"license\" href=\"http://creativecommons.org/licenses/by-nc-sa/4.0/\">Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License</a>"
   ]
  }
 ],
 "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.5"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "165px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}