{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# 4-Introduction to D-Wave Ocean SDK" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "view-in-github" }, "source": [ "[![Open in Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/OpenJij/OpenJijTutorial/blob/master/source/en/004-DWaveOceanSDK.ipynb)" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "view-in-github" }, "source": [ "D-Wave Ocean SDK (Ocean) is a collection of software that uses D-Wave Machines. It is easy to use various features from Python.\n", "\n", "Github: https://github.com/dwavesystems/dwave-ocean-sdk \n", "Document: https://docs.ocean.dwavesys.com/en/latest/\n", "\n", "To install Ocean, use pip as described in the link above, or clone the github repository." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "!pip install dwave-ocean-sdk" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "!git clone https://github.com/dwavesystems/dwave-ocean-sdk.git\n", "!cd dwave-ocean-sdk\n", "!python setup.py install" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In this section, we will discuss the following through the number division problem.\n", "\n", "- How to make QUBO and Ising models\n", "- How to use Ocean\n", "- Optimization for different annealing parameters" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Formulation\n", "\n", "There are two formats tha can be run on D-Wave machine: Ising model and QUBO. We won't got into the details here, will describe the minimum requirements for using Ocean.\n", "\n", "### QUBO and Ising model\n", "\n", "#### QUBO\n", "\n", "In the case of QUBO, we consider the following Hamiltonian for binary variable $q_{i} \\in \\{0, 1\\}$.\n", "\n", "$$\n", "H\\left(\\left\\{q_{i}\\right\\}\\right)= \\sum_{i} Q_{i i} q_{i} + \\sum_{i>j} Q_{i j} q_{i} q_{j}\n", "$$\n", "\n", "In solving QUBO, the classical computer calculates $Q_{ii}$ and $Q_{i j}$ in the above equation. The next step is to run on D-Wave machine.\n", "\n", "#### Ising model\n", "\n", "In the case of Ising model, we consider the following Hamiltonian for spin variable $\\sigma_{i} \\in \\{1, -1\\}$.\n", "\n", "$$\n", "H\\left(\\left\\{\\sigma_{i}\\right\\}\\right)=\\sum_{i} h_{i} \\sigma_{i} + \\sum_{i>j} J_{i j} \\sigma_{i} \\sigma_{j}\n", "$$\n", "\n", "In solving Ising model, the classical computer calculates $h_{i}$\u3068$J_{i j}$ in the above equation. The next step is to run on D-Wave machine.\n", "\n", "#### Reciprocal conversion\n", "\n", "QUBO and Ising model canbe converted to each other by the conversion formula $q_{i} = (\\sigma_{i} + 1) / 2$. It doesn't matter which way you formulate the Hamiltonian, so we can choose the one that is easier to consider from the subject matter. However, it should be noted that the D-Wave machine may behave differently for two different forms of the same problem." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Number division problem\n", "\n", "We consider dividing a fiven set of integers into two groups. The problem of dividing each group so that the sum of each group is the same is called a number division problem.\n", "\n", "For example, we divide the following set of intergers $C$ into two groups." ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "ExecuteTime": { "end_time": "2019-04-15T12:30:57.465840Z", "start_time": "2019-04-15T12:30:57.462152Z" } }, "outputs": [], "source": [ "# set integers C\n", "C = [2, 10, 3, 8, 5, 7, 9, 5, 3, 2]\n", "N = len(C)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In this case, There are 23 optimal solutions where the difference between the sum of the two is zero. There are multiple states in which the energy, called the difference in sums, is the same value, but the solutions are different. These states are called \"degenerate\" in physical terms.\n", "For example, a optimal solution is $\\{2,5,3,10,7\\}, \\{2,5,3,9,8\\}$ (both of the sum of two is 27)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### QUBO \n", "\n", "We will make the formulation with the goal of making the difference between the sum of the two groups equal to zero.\n", "\n", "(Sum of the numbers belonging to group A) - (Sum of the numbers belonging to group B) = 0\n", "\n", "We need binary variables $q_{i}$. We define $q_{i} = 0$ if the $i$th number belongs to group A and $q_{i} = 1$ if it belongs to group B.\n", "\n", "Then the sum of group A is $\\sum_{i=1}^{N}c_{i}q_{i}$ and the sum of group B is $\\sum_{i=1}^{N}c_{i}(1 - q_{i})$, so we obtain\n", "\n", "$$\\sum_{i=1}^{N} c_{i} q_{i}-\\sum_{i=1}^{N} c_{i}\\left(1-q_{i}\\right)=0$$\n", "\n", "Since we want to solver the problem in that this equality holds, this must represent a `constraint`.\n", "\n", "We use the fine method as a way of expressiong such an equality constraint.\n", "\n", "> (the fine method)\n", "> Let $f(x)$ be the cost (objective function) to be minimized and $g(x)=0$ for the constraint. Solving the optimization problem by adding the following terms usig the hyperparameter $\\lambda$ to solve the optimization problem is called a fine method.\n", "> $$\\min_{x} \\left\\{ f(x) + \\lambda g(x)^2\\right\\}$$\n", "\n", "Therefore, QUBO for number division problem is as follows.\n", "\n", "$$\n", "H\\left(\\left\\{q_{i}\\right\\}\\right)=\\left(\\sum_{i=1}^{N} c_{i} q_{i}-\\sum_{i=1}^{N} c_{i}\\left(1-q_{i}\\right)\\right)^{2}\n", "$$\n", "\n", "In order to perform the calculation on the D-Wave machine, we need to find the value of $Q_{i j}$. We expand and organize $H\\left(\\left\\{\\sigma_{i}\\right\\}\\right)$.\n", "\n", "$$\n", "H\\left(\\left\\{q_{i}\\right\\}\\right)=\\left(2\\sum_{i=1}^{N} c_{i} q_{i} - \\sum_{i=1}^{N} c_{i} \\right)^{2} =4 \\sum_{i=1}^{N} c_{i} \\left( c_{i} - \\sum_{j=1}^{N} c_{j}\\right) q_{i}+8 \\sum_{i=1}^{N} \\sum_{j=i+1}^{N} c_{i} c_{j} q_{i} q_{j}+\\left(\\sum_{i=1}^{N} c_{i}\\right)^{2}\n", "$$\n", "\n", "Therefore, we obtain\n", "\n", "$$Q_{i i} = 4 c_{i} \\left( c_{i} - \\sum_{j=1}^{N} c_{j}\\right)$$\n", "$$Q_{i j} = 8 c_{i} c_{j}$$\n", "\n", "The last term is a constant that does not depends on $\\{ q_i\\}$. We can ignore this term in looking for combinations of $\\{ q_i\\}$ that minimize $H{(\\{q_i\\})}$." ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "ExecuteTime": { "end_time": "2019-04-15T12:30:57.472827Z", "start_time": "2019-04-15T12:30:57.469113Z" } }, "outputs": [], "source": [ "# set the above Q_{ii} & Q_{ij} as a dictionary type such as {(i, j): Q_{ij}}\n", "Q = {}\n", "for i in range(N):\n", " Q[i, i] = 4 * C[i] * (C[i] - sum(C))\n", " for j in range(i + 1, N):\n", " Q[i, j] = 8 * C[i] * C[j]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In order to under stand target issues such as degree of coupling and coefficient ratios, we visualize QUBO." ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "ExecuteTime": { "end_time": "2019-04-15T12:30:58.871404Z", "start_time": "2019-04-15T12:30:57.476381Z" } }, "outputs": [], "source": [ "import numpy as np\n", "import matplotlib.cm as cm\n", "import matplotlib.pyplot as plt\n", "%matplotlib inline" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "ExecuteTime": { "end_time": "2019-04-15T12:30:58.881716Z", "start_time": "2019-04-15T12:30:58.873657Z" } }, "outputs": [], "source": [ "def show_qubo(qubo, cmap=cm.GnBu, save_path=None):\n", " n_qubo = max(sorted(qubo.keys())[-1][0], sorted(qubo.keys(), key=lambda x: x[1])[-1][1]) + 1\n", "\n", " np_qubo = np.zeros((n_qubo, n_qubo))\n", " for (pos_x, pos_y), coeff in qubo.items():\n", " np_qubo[pos_x][pos_y] = coeff\n", "\n", " plt.imshow(np_qubo, cmap=cmap)\n", " plt.colorbar()\n", " if save_path is not None:\n", " plt.savefig(save_path)\n", " plt.show()" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "ExecuteTime": { "end_time": "2019-04-15T12:30:59.101750Z", "start_time": "2019-04-15T12:30:58.885051Z" } }, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAATkAAAD4CAYAAACXIpFUAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8li6FKAAAUGElEQVR4nO3df5BdZX3H8fdn77IkgcRAY/mRRNm20TbYEXQHQaydCtaAjlFHbXSkSB2jUyJondpQx6HTDjPYsVXaoThpQHGkRiZAzUgkCipOO4pZCKP5AeMakGwMkoDhZwpZ8u0f92TmGnf3ns2ec+/e5/m8mDO59zlnn/MNJF+e5zw/jiICM7NU9XU7ADOzOjnJmVnSnOTMLGlOcmaWNCc5M0tafx2Vzp4/P+aefErl9T719IuV1wnQ16g+1x86VM+odZ9qqZa6BtmDuv491PAvoo46gTpqff6JRxl7Zv+0qm6cuCTi4HOlro1nfrkpIpZN537dUkuSm3vyKfzF2i9XXu+37n6q8joB5s47tvI6Dzx3sPI6AQYGGrXUOzZ2qKfqnTWr+j+6jf56OjZ9Nfyf6YHPfnjadcTB5zh26COlrv2/71+5YNo37JJakpyZ9QBRW+t1JnGSM8tZo56ewUziJGeWLbklZ2YJE6D0J1g4yZnlrK7h+hnESc4sZxl0V0u1VSUtk/SgpBFJq+sOysw6Qc3uapmjh7VtyUlqANcCbwZGgc2SNkTE9rqDM7MaCahhIvxMU+Z3eBYwEhE7I+IFYB2wvN6wzKx+ebTkykS/ENjV8n20KPsNklZKGpY0fGD//qriM7M6SeWOHlZZio6INRExFBFDs+fPr6paM6vL4Skkibfkyoyu7gYWt3xfVJSZWa/zFBIANgNLJA3STG4rgPfXGpWZ1U+CPi/rIiLGJK0CNgEN4IaI2FZ7ZGZWvx5/3lZGqcnAEbER2FhzLGbWaRV1VyU9DDwNvAiMRcSQpBOBrwOnAQ8D742IX0sScA1wIfAc8MGIuK+SQMbR208UzWwaKp9C8mcRcUZEDBXfVwN3RcQS4K7iO8AFwJLiWAlcV+Fv6rc4yZnl6vB+cvVNIVkO3Fh8vhF4R0v5V6LpR8B8SdVvJV5wkjPLWXVJLoBvS7pX0sqi7KSI2FN8fhQ4qfhcau5tVbxA3yxbmsqmmQskDbd8XxMRa1q+vyEidkv6XeA7kh5o/eGICEk1vUlkck5yZrma2vbn+1qetf2WiNhd/PqYpNtoLgf9laRTImJP0R19rLi8o3Nva0lyzx4IfrxtrPJ6t64+q/I6AX7/yv+tvM4nttSzf4FePlhLvbH3sfYXHY19e2upVn90euV1nnDi7MrrBJg9+5jK63zxxSpeEKRKVjNIOg7oi4ini89/DvwjsAG4GLi6+PUbxY9sAFZJWge8DniypVtbObfkzHJWzRSSk4DbmjND6Af+KyLukLQZuFnSh4BfAO8trt9Ic/rICM0pJJdUEcREnOTMclbBZOCI2Am8epzyx4HzxikP4NJp37gkJzmzXHlZl5klzwv0zSxpPb6NUhlOcma5mtoUkp7lJGeWLSEnOTNLVSYNOSc5s2wJGo30s5yTnFnG3F01s2S5u2pmyXNLzsyS5iRnZunq/fdGl+IkZ5YpIfo8umpmKXN31czS5e6qmaWuL4Ms5yRnlqnmPDknOTNLWJ/3kzOzZPmZ3Mzzp2u31lLvZe+dU3mdXzzmjyuvE+DYWfX8Jzt46txa6h07WM/bxWbPqf4NWAMD9WwF3uivfmPKvkYVdQq5JWdmqfLaVTNLngcezCxdfiZnZqnr6/OLbMwsUSKLNxI6yZllS3h01czSlsMzubYdckmLJX1P0nZJ2yRd3onAzKxuzVcSljl6WZmW3BjwyYi4T9Jc4F5J34mI7TXHZmY18jy5QkTsAfYUn5+WtANYCDjJmfUyeXT1t0g6DTgTuGeccyuBlQADJ55UQWhmVrccWnKl07ik44FbgI9HxFNHno+INRExFBFD/cfPrzJGM6uJ+lTq6GWlWnKSjqGZ4G6KiFvrDcnMOsHP5ApqDq1cD+yIiH+tPyQz6wjlsTNwme7qucBFwJsk3V8cF9Ycl5nVTvT1lTt6WZnR1f+h2bI1s4SI6lY8SFoGXAM0gLURcXUlFVcg/fFjMxufqGQysKQGcC1wAbAUeJ+kpR34HZTiJGeWManc0cZZwEhE7IyIF4B1wPK6Yy/La1fNMjaFJVsLJA23fF8TEWuKzwuBXS3nRoHXVRBeJZzkzDI2hWdy+yJiqM5Y6uIkB9z6w+pfivKDTy6uvE6AM67cVku9zz35bC318sTjtVQ7Z/Blldc5b96xldcJ9bx86NChmHYdUmUjp7uB1j/wi4qyGcFJzixjFc2T2wwskTRIM7mtAN5fRcVVcJIzy1gVOS4ixiStAjbRnEJyQ0TU0+U4Ck5yZplShTsDR8RGYGMllVXMSc4sY72+IWYZTnJmGcsgxznJmWVLoq+R/noAJzmzTHmrJTNLnp/JmVnSnOTMLF2CHt8qrhQnObNMCTzwYGZpy6C36iRnlq0SG2KmwEnOLGO9/rrBMpzkzDLleXJmljx3V80sXYKGu6tmlqpmd3X6OwzPdE5yZhnLoLfqJGeWsz635MwsVSqO1DnJ1eTdNz1aS71f+8RxtdR70b/Xs7znwJxZtdQ7d+5A5XXW8VYtgIGBRuV1VjJeIGj0uSVnZgnzMzkzS5YIP5Mzs7Rl0JBzkjPLmVtyZpYsyc/kzCxxDbfkzCxlOSzrKj05SlJD0hZJ36wzIDPrDNGcb1fm6GVTacldDuwA5tUUi5l1mFtyBUmLgLcCa+sNx8w6pmQrrtdbcmW7q18APgUcmugCSSslDUsaHntmfyXBmVl9RJQ+elnbJCfpbcBjEXHvZNdFxJqIGIqIof7j51cWoJnVp9EXpY5eVuaZ3LnA2yVdCMwC5kn6akR8oN7QzKxuOcyTa9uSi4grImJRRJwGrAC+6wRn1vuao6tR6uhlnidnlrEMGnJTS3IR8X3g+7VEYmadlcmyrnp2SjSzGU90ZuBB0j9I2i3p/uK4sOXcFZJGJD0o6S0t5cuKshFJq6dzf3dXzTLW17npIZ+PiM+1FkhaSvM5/+nAqcCdkl5RnL4WeDMwCmyWtCEith/NjZ3kzDLW5e7qcmBdRDwPPCRpBDirODcSETsBJK0rrj2qJOfuqlmmRCCVO4AFhyf7F8fKKd5ulaSfSLpB0glF2UJgV8s1o0XZROVHxS05s1xNbcnWvogYmrAq6U7g5HFOfRq4DvgnIIpf/wX4qynFOg1Ocj3mM7fX8/aru694aS31nrlq0oUyR+3A7GMqr7PRX0/Hpq+GxZ9R0aO0qhboR8T55e6n/wQO72S0G1jccnpRUcYk5VPm7qpZpkRz08wyx7TuI53S8vWdwNbi8wZghaRjJQ0CS4AfA5uBJZIGJQ3QHJzYcLT3d0vOLGMdauX8s6QzaHZXHwY+AhAR2yTdTHNAYQy4NCJeBJC0CtgENIAbImLb0d7cSc4sY53YTy4iLprk3FXAVeOUbwQ2VnF/JzmzTAkv6zKzxPX64vsynOTMMuaWnJklS+r9DTHLcJIzy5hbcmaWND+TM7NkeXTVzJLnlpyZJc1JzsySJfJYvO4kZ5YrdWZZV7c5yZllzC05M0vW4Z2BU+ckZ5Yxt+TMLGkeXTWzZAknOTNLXJdfSdgRTnJmGevgy6W7xknOALj460/XUu/o9ctqqXfwb39UeZ2zZtXz16HROFR5nVFBcpLckjOzxGWQ45zkzHJ1+JWEqXOSM8tWeHTVzNLm7qqZJc3LuswsWd5qycyS15fBHJJSiVzSfEnrJT0gaYekc+oOzMxqJqGSRy8r25K7BrgjIt4taQCYU2NMZtYBfpFNQdJLgDcCHwSIiBeAF+oNy8w6QRmkuTLd1UFgL/AlSVskrZV03JEXSVopaVjS8Ngz+ysP1Myqd3hpV7ujl5VJcv3Aa4DrIuJM4Flg9ZEXRcSaiBiKiKH+4+dXHKaZ1aEPlTp6WZkkNwqMRsQ9xff1NJOemfWw5n5yKnX0srZJLiIeBXZJemVRdB6wvdaozKwjcuiulh1d/RhwUzGyuhO4pL6QzKxTchh4KJXkIuJ+YKjmWMysw3q9lVZGDqs6zGwcmsI/07qP9B5J2yQdkjR0xLkrJI1IelDSW1rKlxVlI5JWt5QPSrqnKP960buclJOcWa4EDanUMU1bgXcBP/iN20tLgRXA6cAy4D8kNSQ1gGuBC4ClwPuKawE+C3w+Iv4A+DXwoXY3d5Izy5hKHtMRETsi4sFxTi0H1kXE8xHxEDACnFUcIxGxs1h8sA5Yrub6sjfRnOEBcCPwjnb39wJ9s0wJprIudYGk4ZbvayJizTRDWAi0vqxjtCgD2HVE+euA3wH2R8TYONdPyEnOLGNTaKXti4gJBx8l3QmcPM6pT0fEN6YeWXWc5KxWF355Zy31rv/UvMrrvOymyqsEYGCgUXmdVU3QrWqHkYg4/yh+bDewuOX7oqKMCcofB+ZL6i9ac63XT8jP5Mwy1olncpPYAKyQdKykQWAJ8GNgM7CkGEkdoDk4sSEiAvge8O7i5y8G2rYSneTMMtV8W1f9o6uS3ilpFDgHuF3SJoCI2AbcTHMF1R3ApRHxYtFKWwVsAnYANxfXAvwd8DeSRmg+o7u+3f3dXTXL1vTnwJUREbcBt01w7irgqnHKNwIbxynfSXP0tTQnObOM5bDiwUnOLGNeu2pmyUphh5EynOTMMuaWnJklrdc3xCzDSc4sU365tJklr9ffqVqGk5xZtvJ486qTnFnG0k9xTnJmWZPSfyrnJGeWMbfkzCxZzSdy6ac5JzmznHl01cxSln6Kc5Izy5inkJhZyuRlXWaWPCc5sxnpM7fPqrzOSy44WHmdAOvurmEuWlUvsnGSM7NU5fFEzknOLG9+Jmdm6erMi2y6zUnOLGNOcmaWNO8nZ2aJc5Izs4Sln+JKbvEu6ROStknaKulrkqqfpGRmHXV4F5Iy//SytklO0kLgMmAoIl4FNIAVdQdmZnUTUrmjl5XtrvYDsyUdBOYAv6wvJDPrlF5vpZXRtiUXEbuBzwGPAHuAJyPi20deJ2mlpGFJw2PP7K8+UjOrgUoevatMd/UEYDkwCJwKHCfpA0deFxFrImIoIob6j59ffaRmVi01FzyUOXpZmYGH84GHImJvRBwEbgVeX29YZtYZ6bfkyjyTewQ4W9Ic4ABwHjBca1Rm1hE5PJNrm+Qi4h5J64H7gDFgC7Cm7sDMrF6i90dOyyg1uhoRVwJX1hyLmXWYW3JmlrQcklz6r882s4l1YNxB0nuKFVOHJA21lJ8m6YCk+4vjiy3nXivpp5JGJP2bin61pBMlfUfSz4pfT2h3fyc5s4x1aFnXVuBdwA/GOffziDijOD7aUn4d8GFgSXEsK8pXA3dFxBLgruL7pJzkzDLWiSQXETsi4sHSMUmnAPMi4kcREcBXgHcUp5cDNxafb2wpn5CTnFmmDo+ully7uuDwiqbiWFlRGIOStki6W9KfFGULgdGWa0aLMoCTImJP8flR4KR2N/DAg1nh1h8eU0u9bziz+r9mu+d0/G1d+yJiaKKTku4ETh7n1Kcj4hsT/Nge4GUR8bik1wL/Len0sgFFREiKdtc5yZllrKqx1Yg4/yh+5nng+eLzvZJ+DrwC2A0sarl0UVEG8CtJp0TEnqJb+1i7+7i7apazLi5elfRSSY3i8+/RHGDYWXRHn5J0djGq+pfA4dbgBuDi4vPFLeUTcpIzy1gnBh4kvVPSKHAOcLukTcWpNwI/kXQ/sB74aEQ8UZz7a2AtMAL8HPhWUX418GZJP6O5rv7qdvd3d9UsUwL6OjAZOCJuA24bp/wW4JYJfmYYeNU45Y/TXD9fmpOcWa56f4ORUpzkzLLV++9vKMNJzixjOSQ5DzyYWdLckjPLmPeTM7NkdWp0tduc5Mxy5pacmaXLo6tmlrj0U5yTnFnW3JIzs7T5mZyZpcqjq2aWPrfkzCxl6ac4JzmzjHkKiZklzknOzJLV3Nk8/SSn5msNK65U2gv8osSlC4B9lQdQn16Kt5dihd6KdybE+vKIeOl0KpB0B83fSxn7ImJZ+8tmnlqSXOmbS8OTveZspumleHspVuiteHspVvN+cmaWOCc5M0tat5Pcmi7ff6p6Kd5eihV6K95eijV7XX0mZ2ZWt2635MzMauUkZ2ZJ61qSk7RM0oOSRiSt7lYc7UhaLOl7krZL2ibp8m7HVIakhqQtkr7Z7VgmI2m+pPWSHpC0Q9I53Y5pMpI+Ufw52Crpa5JmdTsmm1xXkpykBnAtcAGwFHifpKXdiKWEMeCTEbEUOBu4dAbH2upyYEe3gyjhGuCOiPhD4NXM4JglLQQuA4Yi4lVAA1jR3aisnW615M4CRiJiZ0S8AKwDlncplklFxJ6IuK/4/DTNv4QLuxvV5CQtAt4KrO12LJOR9BLgjcD1ABHxQkTs725UbfUDsyX1A3OAX3Y5HmujW0luIbCr5fsoMzxxAEg6DTgTuKe7kbT1BeBTwKFuB9LGILAX+FLRtV4r6bhuBzWRiNgNfA54BNgDPBkR3+5uVNaOBx5KknQ8cAvw8Yh4qtvxTETS24DHIuLebsdSQj/wGuC6iDgTeBaYyc9nT6DZ4xgETgWOk/SB7kZl7XQrye0GFrd8X1SUzUiSjqGZ4G6KiFu7HU8b5wJvl/QwzccAb5L01e6GNKFRYDQiDreM19NMejPV+cBDEbE3Ig4CtwKv73JM1ka3ktxmYImkQUkDNB/ebuhSLJNScy+a64EdEfGv3Y6nnYi4IiIWRcRpNP+9fjciZmRrIyIeBXZJemVRdB6wvYshtfMIcLakOcWfi/OYwQMl1tSV/eQiYkzSKmATzRGqGyJiWzdiKeFc4CLgp5LuL8r+PiI2djGmlHwMuKn4n91O4JIuxzOhiLhH0nrgPpqj7lvwEq8Zz8u6zCxpHngws6Q5yZlZ0pzkzCxpTnJmljQnOTNLmpOcmSXNSc7Mkvb/ikMHxU1Z6QsAAAAASUVORK5CYII=\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "show_qubo(Q)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The diagonal component represents $Q_{ii}$ and the non-diagonal component represents $Q_{ij}$. It turns out that the number division problem is and all-coupling problem, where there is an interaction between all the qubits." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Ising model\n", "\n", "From the formula for Ising model and teh QUBO interconversion, the number division problem can be expressed in the ising model in the following concise formula.\n", "\n", "\n", "$$\n", "H\\left(\\left\\{\\sigma_{i}\\right\\}\\right) = \\left(\\sum_{i} c_{i} \\sigma_{i}\\right)^2\n", "$$\n", "\n", "Same as QUBO, In order to perform the calculation on the D-Wave machine, we need to find the value of $h_i, J_{ij}$. Note that $\\sigma_i^2 = 1$, we expand $H\\left(\\left{\\sigma_{i}\\right\\}\\right)$.\n", "\n", "$$\n", "H\\left(\\left\\{\\sigma_{i}\\right\\}\\right) = \\sum_{i} c_{i}^2 \\sigma_{i}^2 + 2 \\sum_{i < j} c_{i} c_{j} \\sigma_{i} \\sigma_{j} = \\sum_{i} c_{i}^2 + 2 \\sum_{i < j} c_{i} c_{j} \\sigma_{i} \\sigma_{j}\n", "$$\n", "\n", "Therefore, we obtain\n", "\n", "$$h_{i} = 0$$\n", "\n", "$$J_{i j} = 2 c_{i} c_{j}$$\n", "\n", "As with the discussion in QUBO, we ignore the constant term." ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "ExecuteTime": { "end_time": "2019-04-15T12:30:59.108701Z", "start_time": "2019-04-15T12:30:59.103910Z" } }, "outputs": [], "source": [ "# set h_i & J_ij\n", "h = {}\n", "J = {}\n", "for i in range(N):\n", " h[i] = 0\n", " for j in range(i + 1, N):\n", " J[i, j] = 2 * C[i] * C[j]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ocean's basic library, dimod `.BinaryQuadraticModel()` allows Ising model and QUBO's interconversion.\n", "\n", "- .BinaryQuadraticModel(linear, quadratic, offset, vartype)\n", " * linear: dict, h_i(or Q_{ii})\n", " * quadratic: dict, J_ij(or Q_{ij})\n", " * offset: number, Energy offset in conversion\n", " * vartype: set 'SPIN' if use ising model or 'BINARY' if use QUBO" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "ExecuteTime": { "end_time": "2019-04-15T12:30:59.185784Z", "start_time": "2019-04-15T12:30:59.111952Z" } }, "outputs": [], "source": [ "import dimod" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "ExecuteTime": { "end_time": "2019-04-15T12:30:59.194658Z", "start_time": "2019-04-15T12:30:59.188913Z" }, "scrolled": true }, "outputs": [], "source": [ "# convert from ising model to QUBO\n", "model = dimod.BinaryQuadraticModel(h, J, 0.0, vartype='SPIN')\n", "qubo, offset = model.to_qubo()" ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "ExecuteTime": { "end_time": "2019-04-15T12:30:59.337789Z", "start_time": "2019-04-15T12:30:59.197763Z" } }, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAATkAAAD4CAYAAACXIpFUAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8li6FKAAAUGElEQVR4nO3df5BdZX3H8fdn77IkgcRAY/mRRNm20TbYEXQHQaydCtaAjlFHbXSkSB2jUyJondpQx6HTDjPYsVXaoThpQHGkRiZAzUgkCipOO4pZCKP5AeMakGwMkoDhZwpZ8u0f92TmGnf3ns2ec+/e5/m8mDO59zlnn/MNJF+e5zw/jiICM7NU9XU7ADOzOjnJmVnSnOTMLGlOcmaWNCc5M0tafx2Vzp4/P+aefErl9T719IuV1wnQ16g+1x86VM+odZ9qqZa6BtmDuv491PAvoo46gTpqff6JRxl7Zv+0qm6cuCTi4HOlro1nfrkpIpZN537dUkuSm3vyKfzF2i9XXu+37n6q8joB5s47tvI6Dzx3sPI6AQYGGrXUOzZ2qKfqnTWr+j+6jf56OjZ9Nfyf6YHPfnjadcTB5zh26COlrv2/71+5YNo37JJakpyZ9QBRW+t1JnGSM8tZo56ewUziJGeWLbklZ2YJE6D0J1g4yZnlrK7h+hnESc4sZxl0V0u1VSUtk/SgpBFJq+sOysw6Qc3uapmjh7VtyUlqANcCbwZGgc2SNkTE9rqDM7MaCahhIvxMU+Z3eBYwEhE7I+IFYB2wvN6wzKx+ebTkykS/ENjV8n20KPsNklZKGpY0fGD//qriM7M6SeWOHlZZio6INRExFBFDs+fPr6paM6vL4Skkibfkyoyu7gYWt3xfVJSZWa/zFBIANgNLJA3STG4rgPfXGpWZ1U+CPi/rIiLGJK0CNgEN4IaI2FZ7ZGZWvx5/3lZGqcnAEbER2FhzLGbWaRV1VyU9DDwNvAiMRcSQpBOBrwOnAQ8D742IX0sScA1wIfAc8MGIuK+SQMbR208UzWwaKp9C8mcRcUZEDBXfVwN3RcQS4K7iO8AFwJLiWAlcV+Fv6rc4yZnl6vB+cvVNIVkO3Fh8vhF4R0v5V6LpR8B8SdVvJV5wkjPLWXVJLoBvS7pX0sqi7KSI2FN8fhQ4qfhcau5tVbxA3yxbmsqmmQskDbd8XxMRa1q+vyEidkv6XeA7kh5o/eGICEk1vUlkck5yZrma2vbn+1qetf2WiNhd/PqYpNtoLgf9laRTImJP0R19rLi8o3Nva0lyzx4IfrxtrPJ6t64+q/I6AX7/yv+tvM4nttSzf4FePlhLvbH3sfYXHY19e2upVn90euV1nnDi7MrrBJg9+5jK63zxxSpeEKRKVjNIOg7oi4ini89/DvwjsAG4GLi6+PUbxY9sAFZJWge8DniypVtbObfkzHJWzRSSk4DbmjND6Af+KyLukLQZuFnSh4BfAO8trt9Ic/rICM0pJJdUEcREnOTMclbBZOCI2Am8epzyx4HzxikP4NJp37gkJzmzXHlZl5klzwv0zSxpPb6NUhlOcma5mtoUkp7lJGeWLSEnOTNLVSYNOSc5s2wJGo30s5yTnFnG3F01s2S5u2pmyXNLzsyS5iRnZunq/fdGl+IkZ5YpIfo8umpmKXN31czS5e6qmaWuL4Ms5yRnlqnmPDknOTNLWJ/3kzOzZPmZ3Mzzp2u31lLvZe+dU3mdXzzmjyuvE+DYWfX8Jzt46txa6h07WM/bxWbPqf4NWAMD9WwF3uivfmPKvkYVdQq5JWdmqfLaVTNLngcezCxdfiZnZqnr6/OLbMwsUSKLNxI6yZllS3h01czSlsMzubYdckmLJX1P0nZJ2yRd3onAzKxuzVcSljl6WZmW3BjwyYi4T9Jc4F5J34mI7TXHZmY18jy5QkTsAfYUn5+WtANYCDjJmfUyeXT1t0g6DTgTuGeccyuBlQADJ55UQWhmVrccWnKl07ik44FbgI9HxFNHno+INRExFBFD/cfPrzJGM6uJ+lTq6GWlWnKSjqGZ4G6KiFvrDcnMOsHP5ApqDq1cD+yIiH+tPyQz6wjlsTNwme7qucBFwJsk3V8cF9Ycl5nVTvT1lTt6WZnR1f+h2bI1s4SI6lY8SFoGXAM0gLURcXUlFVcg/fFjMxufqGQysKQGcC1wAbAUeJ+kpR34HZTiJGeWManc0cZZwEhE7IyIF4B1wPK6Yy/La1fNMjaFJVsLJA23fF8TEWuKzwuBXS3nRoHXVRBeJZzkzDI2hWdy+yJiqM5Y6uIkB9z6w+pfivKDTy6uvE6AM67cVku9zz35bC318sTjtVQ7Z/Blldc5b96xldcJ9bx86NChmHYdUmUjp7uB1j/wi4qyGcFJzixjFc2T2wwskTRIM7mtAN5fRcVVcJIzy1gVOS4ixiStAjbRnEJyQ0TU0+U4Ck5yZplShTsDR8RGYGMllVXMSc4sY72+IWYZTnJmGcsgxznJmWVLoq+R/noAJzmzTHmrJTNLnp/JmVnSnOTMLF2CHt8qrhQnObNMCTzwYGZpy6C36iRnlq0SG2KmwEnOLGO9/rrBMpzkzDLleXJmljx3V80sXYKGu6tmlqpmd3X6OwzPdE5yZhnLoLfqJGeWsz635MwsVSqO1DnJ1eTdNz1aS71f+8RxtdR70b/Xs7znwJxZtdQ7d+5A5XXW8VYtgIGBRuV1VjJeIGj0uSVnZgnzMzkzS5YIP5Mzs7Rl0JBzkjPLmVtyZpYsyc/kzCxxDbfkzCxlOSzrKj05SlJD0hZJ36wzIDPrDNGcb1fm6GVTacldDuwA5tUUi5l1mFtyBUmLgLcCa+sNx8w6pmQrrtdbcmW7q18APgUcmugCSSslDUsaHntmfyXBmVl9RJQ+elnbJCfpbcBjEXHvZNdFxJqIGIqIof7j51cWoJnVp9EXpY5eVuaZ3LnA2yVdCMwC5kn6akR8oN7QzKxuOcyTa9uSi4grImJRRJwGrAC+6wRn1vuao6tR6uhlnidnlrEMGnJTS3IR8X3g+7VEYmadlcmyrnp2SjSzGU90ZuBB0j9I2i3p/uK4sOXcFZJGJD0o6S0t5cuKshFJq6dzf3dXzTLW17npIZ+PiM+1FkhaSvM5/+nAqcCdkl5RnL4WeDMwCmyWtCEith/NjZ3kzDLW5e7qcmBdRDwPPCRpBDirODcSETsBJK0rrj2qJOfuqlmmRCCVO4AFhyf7F8fKKd5ulaSfSLpB0glF2UJgV8s1o0XZROVHxS05s1xNbcnWvogYmrAq6U7g5HFOfRq4DvgnIIpf/wX4qynFOg1Ocj3mM7fX8/aru694aS31nrlq0oUyR+3A7GMqr7PRX0/Hpq+GxZ9R0aO0qhboR8T55e6n/wQO72S0G1jccnpRUcYk5VPm7qpZpkRz08wyx7TuI53S8vWdwNbi8wZghaRjJQ0CS4AfA5uBJZIGJQ3QHJzYcLT3d0vOLGMdauX8s6QzaHZXHwY+AhAR2yTdTHNAYQy4NCJeBJC0CtgENIAbImLb0d7cSc4sY53YTy4iLprk3FXAVeOUbwQ2VnF/JzmzTAkv6zKzxPX64vsynOTMMuaWnJklS+r9DTHLcJIzy5hbcmaWND+TM7NkeXTVzJLnlpyZJc1JzsySJfJYvO4kZ5YrdWZZV7c5yZllzC05M0vW4Z2BU+ckZ5Yxt+TMLGkeXTWzZAknOTNLXJdfSdgRTnJmGevgy6W7xknOALj460/XUu/o9ctqqXfwb39UeZ2zZtXz16HROFR5nVFBcpLckjOzxGWQ45zkzHJ1+JWEqXOSM8tWeHTVzNLm7qqZJc3LuswsWd5qycyS15fBHJJSiVzSfEnrJT0gaYekc+oOzMxqJqGSRy8r25K7BrgjIt4taQCYU2NMZtYBfpFNQdJLgDcCHwSIiBeAF+oNy8w6QRmkuTLd1UFgL/AlSVskrZV03JEXSVopaVjS8Ngz+ysP1Myqd3hpV7ujl5VJcv3Aa4DrIuJM4Flg9ZEXRcSaiBiKiKH+4+dXHKaZ1aEPlTp6WZkkNwqMRsQ9xff1NJOemfWw5n5yKnX0srZJLiIeBXZJemVRdB6wvdaozKwjcuiulh1d/RhwUzGyuhO4pL6QzKxTchh4KJXkIuJ+YKjmWMysw3q9lVZGDqs6zGwcmsI/07qP9B5J2yQdkjR0xLkrJI1IelDSW1rKlxVlI5JWt5QPSrqnKP960buclJOcWa4EDanUMU1bgXcBP/iN20tLgRXA6cAy4D8kNSQ1gGuBC4ClwPuKawE+C3w+Iv4A+DXwoXY3d5Izy5hKHtMRETsi4sFxTi0H1kXE8xHxEDACnFUcIxGxs1h8sA5Yrub6sjfRnOEBcCPwjnb39wJ9s0wJprIudYGk4ZbvayJizTRDWAi0vqxjtCgD2HVE+euA3wH2R8TYONdPyEnOLGNTaKXti4gJBx8l3QmcPM6pT0fEN6YeWXWc5KxWF355Zy31rv/UvMrrvOymyqsEYGCgUXmdVU3QrWqHkYg4/yh+bDewuOX7oqKMCcofB+ZL6i9ac63XT8jP5Mwy1olncpPYAKyQdKykQWAJ8GNgM7CkGEkdoDk4sSEiAvge8O7i5y8G2rYSneTMMtV8W1f9o6uS3ilpFDgHuF3SJoCI2AbcTHMF1R3ApRHxYtFKWwVsAnYANxfXAvwd8DeSRmg+o7u+3f3dXTXL1vTnwJUREbcBt01w7irgqnHKNwIbxynfSXP0tTQnObOM5bDiwUnOLGNeu2pmyUphh5EynOTMMuaWnJklrdc3xCzDSc4sU365tJklr9ffqVqGk5xZtvJ486qTnFnG0k9xTnJmWZPSfyrnJGeWMbfkzCxZzSdy6ac5JzmznHl01cxSln6Kc5Izy5inkJhZyuRlXWaWPCc5sxnpM7fPqrzOSy44WHmdAOvurmEuWlUvsnGSM7NU5fFEzknOLG9+Jmdm6erMi2y6zUnOLGNOcmaWNO8nZ2aJc5Izs4Sln+JKbvEu6ROStknaKulrkqqfpGRmHXV4F5Iy//SytklO0kLgMmAoIl4FNIAVdQdmZnUTUrmjl5XtrvYDsyUdBOYAv6wvJDPrlF5vpZXRtiUXEbuBzwGPAHuAJyPi20deJ2mlpGFJw2PP7K8+UjOrgUoevatMd/UEYDkwCJwKHCfpA0deFxFrImIoIob6j59ffaRmVi01FzyUOXpZmYGH84GHImJvRBwEbgVeX29YZtYZ6bfkyjyTewQ4W9Ic4ABwHjBca1Rm1hE5PJNrm+Qi4h5J64H7gDFgC7Cm7sDMrF6i90dOyyg1uhoRVwJX1hyLmXWYW3JmlrQcklz6r882s4l1YNxB0nuKFVOHJA21lJ8m6YCk+4vjiy3nXivpp5JGJP2bin61pBMlfUfSz4pfT2h3fyc5s4x1aFnXVuBdwA/GOffziDijOD7aUn4d8GFgSXEsK8pXA3dFxBLgruL7pJzkzDLWiSQXETsi4sHSMUmnAPMi4kcREcBXgHcUp5cDNxafb2wpn5CTnFmmDo+ully7uuDwiqbiWFlRGIOStki6W9KfFGULgdGWa0aLMoCTImJP8flR4KR2N/DAg1nh1h8eU0u9bziz+r9mu+d0/G1d+yJiaKKTku4ETh7n1Kcj4hsT/Nge4GUR8bik1wL/Len0sgFFREiKdtc5yZllrKqx1Yg4/yh+5nng+eLzvZJ+DrwC2A0sarl0UVEG8CtJp0TEnqJb+1i7+7i7apazLi5elfRSSY3i8+/RHGDYWXRHn5J0djGq+pfA4dbgBuDi4vPFLeUTcpIzy1gnBh4kvVPSKHAOcLukTcWpNwI/kXQ/sB74aEQ8UZz7a2AtMAL8HPhWUX418GZJP6O5rv7qdvd3d9UsUwL6OjAZOCJuA24bp/wW4JYJfmYYeNU45Y/TXD9fmpOcWa56f4ORUpzkzLLV++9vKMNJzixjOSQ5DzyYWdLckjPLmPeTM7NkdWp0tduc5Mxy5pacmaXLo6tmlrj0U5yTnFnW3JIzs7T5mZyZpcqjq2aWPrfkzCxl6ac4JzmzjHkKiZklzknOzJLV3Nk8/SSn5msNK65U2gv8osSlC4B9lQdQn16Kt5dihd6KdybE+vKIeOl0KpB0B83fSxn7ImJZ+8tmnlqSXOmbS8OTveZspumleHspVuiteHspVvN+cmaWOCc5M0tat5Pcmi7ff6p6Kd5eihV6K95eijV7XX0mZ2ZWt2635MzMauUkZ2ZJ61qSk7RM0oOSRiSt7lYc7UhaLOl7krZL2ibp8m7HVIakhqQtkr7Z7VgmI2m+pPWSHpC0Q9I53Y5pMpI+Ufw52Crpa5JmdTsmm1xXkpykBnAtcAGwFHifpKXdiKWEMeCTEbEUOBu4dAbH2upyYEe3gyjhGuCOiPhD4NXM4JglLQQuA4Yi4lVAA1jR3aisnW615M4CRiJiZ0S8AKwDlncplklFxJ6IuK/4/DTNv4QLuxvV5CQtAt4KrO12LJOR9BLgjcD1ABHxQkTs725UbfUDsyX1A3OAX3Y5HmujW0luIbCr5fsoMzxxAEg6DTgTuKe7kbT1BeBTwKFuB9LGILAX+FLRtV4r6bhuBzWRiNgNfA54BNgDPBkR3+5uVNaOBx5KknQ8cAvw8Yh4qtvxTETS24DHIuLebsdSQj/wGuC6iDgTeBaYyc9nT6DZ4xgETgWOk/SB7kZl7XQrye0GFrd8X1SUzUiSjqGZ4G6KiFu7HU8b5wJvl/QwzccAb5L01e6GNKFRYDQiDreM19NMejPV+cBDEbE3Ig4CtwKv73JM1ka3ktxmYImkQUkDNB/ebuhSLJNScy+a64EdEfGv3Y6nnYi4IiIWRcRpNP+9fjciZmRrIyIeBXZJemVRdB6wvYshtfMIcLakOcWfi/OYwQMl1tSV/eQiYkzSKmATzRGqGyJiWzdiKeFc4CLgp5LuL8r+PiI2djGmlHwMuKn4n91O4JIuxzOhiLhH0nrgPpqj7lvwEq8Zz8u6zCxpHngws6Q5yZlZ0pzkzCxpTnJmljQnOTNLmpOcmSXNSc7Mkvb/ikMHxU1Z6QsAAAAASUVORK5CYII=\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "show_qubo(qubo)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We have expanded the constructed Hamiltonian to find the coefficient matrices such as $Q_{i i}, Q_{i j}$ and $h_{i}, J_{i j}$. However, When dealing with more complex Hamiltonian, manual calculations are more complicated and may result in errors. Therefore, we can use PyQUBO, domain-specific language developed by Recruit Communications and create QUBO and ising models without having to expand Hamiltonian. For more details of PyQUBO, see also documents below.\n", "\n", "* Github: https://github.com/recruit-communications/pyqubo \n", "* Document: https://pyqubo.readthedocs.io/en/latest/\n", "* OpenJijTutorial: https://github.com/OpenJij/OpenJijTutorial/blob/master/3-PyQUBO_2_OpenJij.ipynb \n", "* Qiita: https://qiita.com/ynntech/items/fcfe7caf49f6a8eb3c53" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Optimization on D-Wave machine\n", "\n", "Let us consider optimizing this problem using D-Wave machine. In this tutorial, we show (1). solving simply, (2). solving by varying the number of readings, (3). solving by changing annealing time.\n", "\n", "\n", "### Solve Ising model\n", "\n", "We use D-Wave machin sampler `DWaveSampler`, and use `EmbeddingComposite` for Embedding the problem in the chimeragraph of D-Wave machine." ] }, { "cell_type": "code", "execution_count": 90, "metadata": { "ExecuteTime": { "end_time": "2019-04-15T12:31:01.159068Z", "start_time": "2019-04-15T12:30:59.340179Z" } }, "outputs": [], "source": [ "from dwave.system.samplers import DWaveSampler\n", "from dwave.system.composites import EmbeddingComposite" ] }, { "cell_type": "code", "execution_count": 91, "metadata": { "ExecuteTime": { "end_time": "2019-04-15T12:31:02.135118Z", "start_time": "2019-04-15T12:31:01.161905Z" } }, "outputs": [], "source": [ "# set the connection information as an option\n", "endpoint = 'https://cloud.dwavesys.com/sapi'\n", "token = '##########'\n", "solver = 'DW_2000Q_VFYC_5'\n", "\n", "# use DWaveSampler\n", "dw = DWaveSampler(endpoint=endpoint, token=token, solver=solver)\n", "# embed to Chimera graph\n", "sampler = EmbeddingComposite(dw)" ] }, { "cell_type": "code", "execution_count": 107, "metadata": { "ExecuteTime": { "end_time": "2019-04-15T12:31:03.906310Z", "start_time": "2019-04-15T12:31:02.137216Z" } }, "outputs": [], "source": [ "# in the case of ising model, use the following\n", "response = sampler.sample_ising(h, J, num_reads=100)\n", "\n", "# in the case of QUBO, use the following\n", "# response = sampler.sample_qubo(Q, num_reads=100)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let us check result. We can see states of solution, energy, frequence of occurrence, and percentage of broken chain on D-Wave machine with `.record`." ] }, { "cell_type": "code", "execution_count": 108, "metadata": { "ExecuteTime": { "end_time": "2019-04-15T12:31:03.913301Z", "start_time": "2019-04-15T12:31:03.908557Z" } }, "outputs": [ { "data": { "text/plain": [ "rec.array([([ 1, -1, 1, 1, 1, 1, -1, 1, 1, -1], -226., 1, 0.8),\n", " ([-1, 1, -1, 1, 1, -1, 1, -1, 1, 1], 30., 2, 0.8),\n", " ([-1, 1, -1, 1, -1, -1, 1, -1, 1, 1], -270., 1, 0.8),\n", " ([-1, 1, -1, 1, -1, -1, 1, -1, 1, 1], -270., 2, 0.8),\n", " ([-1, 1, -1, 1, 1, -1, 1, -1, -1, 1], -174., 1, 0.8),\n", " ([ 1, -1, 1, -1, -1, 1, -1, 1, 1, -1], -174., 1, 0.8),\n", " ([-1, 1, -1, 1, 1, -1, 1, -1, 1, 1], 30., 2, 0.8),\n", " ([ 1, -1, 1, -1, -1, 1, -1, 1, 1, -1], -174., 1, 0.8),\n", " ([ 1, -1, 1, -1, 1, 1, -1, 1, -1, -1], -270., 1, 0.8),\n", " ([ 1, -1, 1, -1, -1, 1, -1, 1, 1, -1], -174., 1, 0.8),\n", " ([-1, 1, 1, 1, -1, -1, 1, -1, 1, 1], -114., 1, 0.8),\n", " ([-1, 1, 1, 1, 1, -1, 1, -1, -1, 1], 30., 1, 0.8),\n", " ([ 1, -1, 1, -1, 1, 1, -1, 1, -1, -1], -270., 1, 0.8),\n", " ([-1, 1, -1, 1, -1, -1, 1, -1, 1, 1], -270., 2, 0.8),\n", " ([-1, 1, -1, 1, -1, -1, 1, -1, 1, 1], -270., 2, 0.8),\n", " ([ 1, -1, 1, -1, -1, 1, -1, 1, 1, -1], -174., 1, 0.8),\n", " ([-1, 1, 1, 1, -1, -1, 1, -1, 1, 1], -114., 1, 0.8),\n", " ([ 1, -1, 1, 1, 1, 1, -1, 1, -1, -1], -334., 1, 0.8),\n", " ([-1, 1, -1, 1, 1, -1, 1, -1, 1, 1], 30., 1, 0.8),\n", " ([ 1, -1, 1, -1, 1, 1, -1, 1, -1, -1], -270., 3, 0.8),\n", " ([-1, 1, 1, 1, -1, -1, 1, -1, 1, 1], -114., 1, 0.8),\n", " ([-1, 1, -1, 1, 1, -1, 1, 1, -1, 1], 206., 2, 0.8),\n", " ([-1, 1, 1, 1, -1, -1, 1, -1, 1, 1], -114., 2, 0.8),\n", " ([ 1, -1, 1, 1, -1, 1, -1, 1, 1, -1], -366., 1, 0.8),\n", " ([ 1, -1, 1, 1, -1, 1, -1, 1, 1, -1], -366., 1, 0.8),\n", " ([-1, 1, 1, 1, 1, -1, 1, -1, -1, 1], 30., 3, 0.8),\n", " ([ 1, -1, 1, -1, 1, 1, -1, 1, 1, -1], -354., 1, 0.8),\n", " ([-1, 1, 1, 1, 1, -1, 1, -1, 1, 1], 306., 1, 0.8),\n", " ([-1, 1, -1, 1, 1, -1, -1, -1, 1, 1], -366., 1, 0.8),\n", " ([-1, 1, -1, 1, -1, -1, 1, 1, 1, 1], 30., 3, 0.8),\n", " ([-1, 1, 1, 1, 1, -1, 1, -1, -1, 1], 30., 1, 0.8),\n", " ([ 1, -1, 1, -1, 1, 1, 1, 1, -1, -1], -306., 4, 0.8),\n", " ([ 1, -1, -1, -1, 1, 1, -1, 1, 1, -1], -270., 1, 0.8),\n", " ([ 1, -1, 1, -1, -1, 1, 1, 1, 1, -1], -354., 2, 0.8),\n", " ([-1, 1, -1, 1, 1, -1, 1, -1, 1, 1], 30., 2, 0.8),\n", " ([-1, 1, 1, -1, 1, -1, 1, -1, 1, 1], -270., 1, 0.8),\n", " ([-1, 1, -1, 1, 1, -1, -1, -1, 1, 1], -366., 4, 0.8),\n", " ([-1, 1, 1, 1, 1, -1, 1, -1, -1, 1], 30., 1, 0.8),\n", " ([-1, 1, 1, 1, -1, -1, 1, -1, 1, 1], -114., 2, 0.8),\n", " ([-1, 1, 1, 1, -1, -1, 1, -1, 1, 1], -114., 1, 0.8),\n", " ([ 1, -1, 1, -1, 1, 1, -1, 1, 1, -1], -354., 1, 0.8),\n", " ([ 1, -1, 1, 1, 1, 1, -1, 1, -1, -1], -334., 1, 0.8),\n", " ([-1, 1, 1, 1, 1, -1, 1, -1, -1, 1], 30., 1, 0.8),\n", " ([ 1, -1, 1, -1, 1, 1, 1, 1, -1, -1], -306., 1, 0.8),\n", " ([-1, 1, -1, 1, -1, -1, 1, 1, 1, 1], 30., 1, 0.8),\n", " ([ 1, -1, 1, -1, 1, 1, -1, 1, 1, -1], -354., 1, 0.8),\n", " ([ 1, -1, 1, -1, -1, 1, 1, 1, 1, -1], -354., 1, 0.8),\n", " ([-1, 1, -1, 1, 1, -1, -1, -1, 1, 1], -366., 1, 0.8),\n", " ([ 1, -1, 1, -1, 1, 1, 1, 1, -1, -1], -306., 1, 0.8),\n", " ([ 1, -1, 1, 1, -1, 1, -1, 1, 1, -1], -366., 2, 0.8),\n", " ([-1, 1, -1, -1, 1, -1, 1, -1, 1, 1], -354., 1, 0.8),\n", " ([-1, 1, 1, -1, 1, -1, 1, -1, 1, 1], -270., 2, 0.8),\n", " ([-1, 1, -1, 1, 1, -1, 1, -1, 1, 1], 30., 1, 0.8),\n", " ([ 1, -1, -1, 1, -1, 1, -1, 1, 1, -1], -354., 1, 1. ),\n", " ([-1, 1, 1, 1, 1, -1, 1, -1, 1, 1], 306., 3, 1. ),\n", " ([ 1, -1, -1, 1, 1, 1, -1, 1, 1, -1], -334., 1, 1. ),\n", " ([ 1, -1, 1, 1, -1, 1, -1, 1, 1, -1], -366., 1, 1. ),\n", " ([ 1, -1, -1, -1, -1, 1, 1, 1, 1, -1], -366., 1, 1. ),\n", " ([ 1, -1, -1, 1, 1, 1, -1, 1, -1, -1], -370., 1, 1. ),\n", " ([-1, 1, 1, 1, -1, -1, -1, -1, 1, 1], -366., 1, 1. ),\n", " ([ 1, -1, 1, -1, 1, 1, 1, -1, 1, -1], -354., 2, 1. ),\n", " ([ 1, -1, 1, 1, 1, 1, -1, -1, 1, -1], -366., 2, 1. ),\n", " ([-1, 1, 1, -1, 1, -1, 1, -1, 1, 1], -270., 1, 1. ),\n", " ([-1, 1, 1, -1, -1, -1, 1, -1, 1, 1], -370., 1, 1. ),\n", " ([-1, 1, 1, 1, 1, -1, -1, -1, 1, 1], -306., 1, 1. ),\n", " ([ 1, -1, -1, 1, 1, 1, -1, 1, -1, -1], -370., 1, 1. ),\n", " ([-1, 1, 1, 1, 1, -1, -1, -1, 1, 1], -306., 1, 1. ),\n", " ([-1, 1, 1, 1, -1, -1, -1, -1, 1, 1], -366., 1, 1. ),\n", " ([-1, 1, -1, 1, 1, -1, -1, 1, -1, 1], -334., 1, 1. ),\n", " ([-1, 1, -1, 1, -1, -1, 1, 1, 1, 1], 30., 1, 1. ),\n", " ([ 1, -1, -1, 1, 1, 1, -1, 1, 1, -1], -334., 1, 1. ),\n", " ([-1, 1, 1, -1, 1, -1, 1, -1, 1, 1], -270., 1, 1. )],\n", " dtype=[('sample', 'i1', (10,)), ('energy', '" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "plt.hist([calcurate_energy(solution, vartype='SPIN') for solution in twenty_sol], alpha=0.5, label='20\u03bcs')\n", "plt.hist([calcurate_energy(solution, vartype='SPIN') for solution in fifty_sol], alpha=0.5, label='50\u03bcs')\n", "plt.xlabel('Energy')\n", "plt.ylabel('Frequency')\n", "plt.legend()\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": { "ExecuteTime": { "end_time": "2019-04-15T12:42:17.112182Z", "start_time": "2019-04-15T12:42:17.104935Z" } }, "source": [ "From the histogram above, we can see that the number of optimal solutions obtained decreased as the annealing time was increased, but we found more low energy solutions. However, it's not as simple as just increasing the annealing time. Sometimes the optimization works better when the annealing time is small. This dependency depends on each problem. In addition, quantum annealing and other annealing methods are meta-heuristic altorigthms. It is also important to note that each time you execute, the results you get will be different." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Conclusion\n", "\n", "Through the optimization of number division problem, we introduced D-Wave Ocean. We can do a lot of things just by holding on to what we've discussed in this tutorial. For example, we can investigate as follows.\n", "\n", "- success probability (percentage of optimal solutions) relative to the number of readings, annealing time\n", "- energy relative to the number of readings, annealing time\n", "- the percentage of optimal solutions obtained relative to multiple optimal solutions.\n", "\n", "As of April 2019, we can use the D-Wave machine for free for 1 minute per month. You should try.\n", "\n", "D-Wave Leap: https://cloud.dwavesys.com/leap/\n", "\n", "There are other annealing parameters that are not mentioned in this tutorial. For example, by specitying and annealing schedule, we can perform different techniques from normal annealing, such as reverse annealing." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "_draft": { "nbviewer_url": "https://gist.github.com/c98df8dc4fdf3cf70537f9a4e82ccbda" }, "gist": { "data": { "description": "4-DWaveOceanSDK.ipynb", "public": false }, "id": "c98df8dc4fdf3cf70537f9a4e82ccbda" }, "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.8.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": true, "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": "288px" }, "toc_section_display": true, "toc_window_display": true } }, "nbformat": 4, "nbformat_minor": 2 }