{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# 4-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/ja/004-DWaveOceanSDK.ipynb)" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "view-in-github" }, "source": [ "D-Wave Ocean SDK(以下、Ocean) は、D-Waveマシンを使用するソフトウェアがまとまっている開発キットです。Pythonから各種機能を簡単に利用することができます。\n", "\n", "Github: https://github.com/dwavesystems/dwave-ocean-sdk \n", "Document: https://docs.ocean.dwavesys.com/en/latest/\n", "\n", "インストールするには上にある通り、pipを使用するかgithubのリポジトリをクローンします。" ] }, { "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": [ "以降では、数分割問題を通して以下の内容について説明していきます。\n", "\n", "- QUBOまたはイジングモデルの作り方\n", "- Oceanの使い方\n", "- アニーリングパラメータを変えた場合の最適化" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 定式化\n", "\n", "D-Waveマシンに投げることができる形式にはイジングモデルとQUBOがあります。ここでは詳細には触れず、Oceanを使用する上で最低限必要なことを説明します。\n", "\n", "### QUBOとイジングモデル\n", "\n", "#### QUBO\n", "\n", "QUBOの場合、2値変数(バイナリ変数)$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", "QUBOを解く際には、上の式の$Q_{i i}$と$Q_{i j}$を古典コンピュータで計算し、D-Waveマシンに与えることになります。\n", "\n", "#### イジングモデル\n", "\n", "イジングモデルの場合、2値変数$\\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", "イジングモデルを解く際には、上の式の$h_{i}$と$J_{i j}$を古典コンピュータで計算し、D-Waveマシンに与えることになります。\n", "\n", "#### 相互変換\n", "\n", "QUBOとイジングモデルは、$q_{i} = (\\sigma_{i} + 1) / 2$という変換式によって相互変換が可能です。 \n", "この点において、どちらでハミルトニアンを定式化しても問題はないので、対象の問題から考えやすい方を選びましょう。 \n", "ただし同じ問題の2種類の形式に対して、D-Waveマシンの振る舞いが異なる場合があるので注意が必要です。" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 数分割問題\n", "\n", "与えられた整数の集合を、2つのグループに分けることを考えます。このとき、各グループの総和が同じになるように分ける問題を数分割問題といいます。 \n", "例として、以下の整数の集合$C$を2つのグループに分けることを目標にしてみましょう。" ] }, { "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": [ "# 整数の集合を定義します。\n", "C = [2, 10, 3, 8, 5, 7, 9, 5, 3, 2]\n", "N = len(C)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "この場合、それぞれの総和の差がゼロになる最適解は23通り存在します(総和の差という名のエネルギーが同じ値ですが、解が違う状態が複数あります。このような状態を物理用語で「縮退している」と呼びます)。 \n", "例えば、$\\{2,5,3,10,7\\}, \\{2,5,3,9,8\\}$(総和はどちらも27)があります。" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### QUBO\n", "\n", "2つのグループの総和の差を0にすることを目指して、定式化を行いましょう。\n", "\n", "

グループAに属する数字の総和 - グループBに属する数字の総和 = 0

\n", "\n", "そこで2値変数(バイナリ変数)$q_{i}$を用意し、$i$番目の数字がグループAに属する場合$q_{i} = 0$、グループBに属する場合$q_{i} = 1$と定義します。このときグループAに属する数字の総和は$\\sum_{i=1}^{N}c_{i}q_{i}$、グループBに属する数字の総和は$\\sum_{i=1}^{N}c_{i}(1 - q_{i})$と表されるので、先ほどの式は\n", "\n", "$$\\sum_{i=1}^{N} c_{i} q_{i}-\\sum_{i=1}^{N} c_{i}\\left(1-q_{i}\\right)=0$$\n", "\n", "となります。この等式が成り立つように問題を解きたいと考えるので、この式は`制約`を表していることがわかります。このような等式制約を素直に表現する場合には、罰金法が用いられます。\n", "\n", "> (罰金法) 最小化したいコスト(目的関数)を$f(x)$、制約条件を$g(x) = 0$とすると、ハイパーパラメータ$\\lambda$を用いて以下の項を追加して最適化問題を解くことを罰金法と呼びます。 \n", "> $$\\min_{x} \\left\\{ f(x) + \\lambda g(x)^2\\right\\}$$\n", "\n", "よって、数分割問題に対するQUBOは以下のようになります。\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", "D-Waveマシンに問題を投げるためには$Q_{i j}$の値を求める必要があります。そのために$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", "よって\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", "となります。\n", "\n", "> 一番最後の項は$\\{ q_i\\}$に依存しない定数であるため、ハミルトニアン$H (\\{ q_i\\})$を最小化する$\\{ 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": [ "# 上で求めたQ_{ii}, Q_{ij}を{(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": [ "結合の度合いや係数比など対象の問題を理解するために、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": [ "対角成分が$Q_{i i}$、非対角成分が$Q_{i j}$です。定式化の時点から明らかですが、数分割問題は全ての量子ビット間に相互作用が存在する、全結合の問題であることが分かります。" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### イジングモデル\n", "\n", "イジングモデルとQUBOの相互変換の式から、数分割問題をイジングモデルで表すと以下のような簡潔な式で表されます。\n", "\n", "$$\n", "H\\left(\\left\\{\\sigma_{i}\\right\\}\\right) = \\left(\\sum_{i} c_{i} \\sigma_{i}\\right)^2\n", "$$\n", "\n", "QUBOと同様に、D-Waveマシンに問題を投げるためには$h_{i}$と$J_{i j}$の値が必要です。$\\sigma_{i}^2 = 1$であることに注意して、$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", "よって\n", "\n", "$$h_{i} = 0$$\n", "\n", "$$J_{i j} = 2 c_{i} c_{j}$$\n", "\n", "となります。\n", "\n", "> QUBOでの議論と同様に、定数項は無視します。" ] }, { "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": [ "# 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の基本的なライブラリであるdimodの.BinaryQuadraticModel()を用いることで、イジングモデルとQUBOの相互変換が可能です。\n", "\n", "- .BinaryQuadraticModel(linear, quadratic, offset, vartype)\n", " * linear: dict, h_i(もしくはQ_{ii})を辞書型で入れます。\n", " * quadratic: dict, J_ij(もしくはQ_{ij})を辞書型で入れます。\n", " * offset: number, 変換する際のエネルギーオフセットを指定します。\n", " * vartype: インプットとして入れる変数がイジングモデルの場合は'SPIN'を、QUBOの場合は'BINARY'を指定します。" ] }, { "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": [ "# イジングモデルから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": [ "ここまで、$Q_{i i}, Q_{i j}$や$h_{i}, J_{i j}$といった係数行列を求めるために、構成したハミルトニアンを展開しました。しかし、より複雑なハミルトニアンを扱う場合には手計算がより複雑になり、計算ミスが生じる可能性があります。 \n", "そこで、(株)リクルートコミュニケーションズが開発しているドメイン固有言語**PyQUBO**を用いることで、ハミルトニアンを展開することなくQUBOやイジングモデルを作成する事ができます。PyQUBOの使い方については以下のドキュメントを参照ください。\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": [ "## D-Waveマシンによる最適化\n", "\n", "それでは上記の数分割問題を、D-Waveマシンを用いて最適化することを考えましょう。このチュートリアルでは、(1)単純に解く場合 (2)読み取り回数を変えた場合、 (3)アニーリング時間を変えた場合を見てみます。\n", "\n", "### イジングモデルを解く\n", "\n", "D-WaveマシンのサンプラーはDWaveSampler()、さらに問題をD-Waveマシンのキメラグラフに埋め込むためにEmbeddingComposite()を使用します。" ] }, { "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": [ "# 接続情報をオプションとして渡す場合は以下のようにします。\n", "endpoint = 'https://cloud.dwavesys.com/sapi'\n", "token = '##########'\n", "solver = 'DW_2000Q_VFYC_5'\n", "\n", "# DWaveSamplerを用います。\n", "dw = DWaveSampler(endpoint=endpoint, token=token, solver=solver)\n", "# キメラグラフに埋め込みを行います。\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": [ "# イジングモデルの場合は以下を使用します。\n", "response = sampler.sample_ising(h, J, num_reads=100)\n", "\n", "# QUBOの場合は以下を使用します。\n", "# response = sampler.sample_qubo(Q, num_reads=100)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "得られた結果を確認してみましょう。解の状態、エネルギー、その状態の発生回数、D-Waveマシンのグラフにおいて壊れたチェーンの割合を.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μs')\n", "plt.hist([calcurate_energy(solution, vartype='SPIN') for solution in fifty_sol], alpha=0.5, label='50μs')\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": [ "上のヒストグラムから、アニーリング時間を増加させたことで得られた最適解の個数は減少しましたが、低いエネルギーの解を多く見つけていることが分かります。ただし、アニーリング時間を大きくすればいいという単純な話ではありません。アニーリング時間が小さい場合の方が最適化がうまくいくこともあり、その依存関係はそれぞれの問題に依ります。 \n", "また、量子アニーリングをはじめとするアニーリング法はメタヒューリスティックスなアルゴリズムであるため、実行するたびに得られる結果は異なる点にも注意しましょう。" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 結言\n", "\n", "数分割問題の最適化を通して、D-Wave Oceanの使い方を紹介しました。このチュートリアルで説明したことを押さえるだけでも、様々なことができるようになります。例えば、以下のことを調べられるでしょう。\n", "\n", "- 読み取り回数、アニーリングタイムに対する成功確率(最適解が得られる割合)\n", "- 読み取り回数、アニーリングタイムに対するエネルギー値\n", "- 複数の最適解が存在する数分割問題に対して、得られる最適解の割合\n", "\n", "2019年4月現在、1ヶ月1分間無料でD-Waveマシンを利用することができます。ぜひ利用して、上の項目について実験してみてください。\n", "\n", "D-Wave Leap: https://cloud.dwavesys.com/leap/\n", "\n", "このチュートリアルでは触れることができませんでしたが、他にもアニーリングパラメータが存在します。例えば、アニーリングのスケジュールを指定することで、リバースアニーリングなど通常のアニーリングとは異なる手法を実行することができます。気になった方は、D-Waveのドキュメントを読んでみてください。" ] }, { "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.9.3" }, "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 }