Created
May 11, 2021 05:54
-
-
Save mohzeki222/7faebc6a45a511fa33c769ed88ca740b to your computer and use it in GitHub Desktop.
chapter1.ipynb
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "nbformat": 4, | |
| "nbformat_minor": 0, | |
| "metadata": { | |
| "colab": { | |
| "name": "chapter1.ipynb", | |
| "provenance": [], | |
| "collapsed_sections": [ | |
| "p8BlwZzKcjkn", | |
| "EacfNfq0zleF" | |
| ], | |
| "include_colab_link": true | |
| }, | |
| "kernelspec": { | |
| "name": "python3", | |
| "display_name": "Python 3" | |
| }, | |
| "language_info": { | |
| "name": "python" | |
| } | |
| }, | |
| "cells": [ | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "view-in-github", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "<a href=\"https://colab.research.google.com/gist/mohzeki222/7faebc6a45a511fa33c769ed88ca740b/chapter1.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "Sfaxj_ywcd7q" | |
| }, | |
| "source": [ | |
| "## **はじめに**\n", | |
| "\n", | |
| "---\n", | |
| "\n", | |
| "Google colaboratory上にD-Wave Systemsが提供しているOcean SDKをインストールするところから始めましょう。\n", | |
| "\n", | |
| "以下のように\n", | |
| "pip install\n", | |
| "と言うコマンドでシステムに新しいライブラリをインストールすることができます。\n", | |
| "\n", | |
| "（こうした呪文であらかじめ頭のいい人がプログラムしたものを呼び出すことができる）\n", | |
| "\n", | |
| "今回の場合ですと、dwave-ocean-sdkをインストールすることになります。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "UJSm0-dpcfkb", | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "outputId": "772c4923-0a0b-4b31-f2d9-89041b246edf" | |
| }, | |
| "source": [ | |
| "pip install dwave-ocean-sdk" | |
| ], | |
| "execution_count": 1, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "text": [ | |
| "Requirement already satisfied: dwave-ocean-sdk in /usr/local/lib/python3.7/dist-packages (3.3.0)\n", | |
| "Requirement already satisfied: pyqubo==1.0.10 in /usr/local/lib/python3.7/dist-packages (from dwave-ocean-sdk) (1.0.10)\n", | |
| "Requirement already satisfied: penaltymodel-lp==0.1.4 in /usr/local/lib/python3.7/dist-packages (from dwave-ocean-sdk) (0.1.4)\n", | |
| "Requirement already satisfied: dwave-hybrid==0.6.1 in /usr/local/lib/python3.7/dist-packages (from dwave-ocean-sdk) (0.6.1)\n", | |
| "Requirement already satisfied: dimod==0.9.13 in /usr/local/lib/python3.7/dist-packages (from dwave-ocean-sdk) (0.9.13)\n", | |
| "Requirement already satisfied: dwave-greedy==0.1.2 in /usr/local/lib/python3.7/dist-packages (from dwave-ocean-sdk) (0.1.2)\n", | |
| "Requirement already satisfied: penaltymodel-cache==0.4.3 in /usr/local/lib/python3.7/dist-packages (from dwave-ocean-sdk) (0.4.3)\n", | |
| "Requirement already satisfied: dwave-inspector==0.2.5 in /usr/local/lib/python3.7/dist-packages (from dwave-ocean-sdk) (0.2.5)\n", | |
| "Requirement already satisfied: dwave-cloud-client==0.8.4 in /usr/local/lib/python3.7/dist-packages (from dwave-ocean-sdk) (0.8.4)\n", | |
| "Requirement already satisfied: dwave-qbsolv==0.3.2 in /usr/local/lib/python3.7/dist-packages (from dwave-ocean-sdk) (0.3.2)\n", | |
| "Requirement already satisfied: dwave-neal==0.5.7 in /usr/local/lib/python3.7/dist-packages (from dwave-ocean-sdk) (0.5.7)\n", | |
| "Requirement already satisfied: dwave-system==1.4.0 in /usr/local/lib/python3.7/dist-packages (from dwave-ocean-sdk) (1.4.0)\n", | |
| "Requirement already satisfied: dwavebinarycsp==0.1.2 in /usr/local/lib/python3.7/dist-packages (from dwave-ocean-sdk) (0.1.2)\n", | |
| "Requirement already satisfied: penaltymodel==0.16.4 in /usr/local/lib/python3.7/dist-packages (from dwave-ocean-sdk) (0.16.4)\n", | |
| "Requirement already satisfied: dwave-tabu==0.3.1 in /usr/local/lib/python3.7/dist-packages (from dwave-ocean-sdk) (0.3.1)\n", | |
| "Requirement already satisfied: dwave-networkx==0.8.8 in /usr/local/lib/python3.7/dist-packages (from dwave-ocean-sdk) (0.8.8)\n", | |
| "Requirement already satisfied: minorminer==0.2.5 in /usr/local/lib/python3.7/dist-packages (from dwave-ocean-sdk) (0.2.5)\n", | |
| "Requirement already satisfied: penaltymodel-mip==0.2.4; platform_machine == \"x86_64\" or platform_machine == \"amd64\" or platform_machine == \"AMD64\" in /usr/local/lib/python3.7/dist-packages (from dwave-ocean-sdk) (0.2.4)\n", | |
| "Requirement already satisfied: numpy<1.20,>=1.17.3 in /usr/local/lib/python3.7/dist-packages (from pyqubo==1.0.10->dwave-ocean-sdk) (1.19.5)\n", | |
| "Requirement already satisfied: Deprecated>=1.2.10 in /usr/local/lib/python3.7/dist-packages (from pyqubo==1.0.10->dwave-ocean-sdk) (1.2.12)\n", | |
| "Requirement already satisfied: six>=1.11.0 in /usr/local/lib/python3.7/dist-packages (from pyqubo==1.0.10->dwave-ocean-sdk) (1.15.0)\n", | |
| "Requirement already satisfied: scipy<2.0.0,>=0.15.0 in /usr/local/lib/python3.7/dist-packages (from penaltymodel-lp==0.1.4->dwave-ocean-sdk) (1.4.1)\n", | |
| "Requirement already satisfied: plucky>=0.4.3 in /usr/local/lib/python3.7/dist-packages (from dwave-hybrid==0.6.1->dwave-ocean-sdk) (0.4.3)\n", | |
| "Requirement already satisfied: click>5 in /usr/local/lib/python3.7/dist-packages (from dwave-hybrid==0.6.1->dwave-ocean-sdk) (7.1.2)\n", | |
| "Requirement already satisfied: networkx in /usr/local/lib/python3.7/dist-packages (from dwave-hybrid==0.6.1->dwave-ocean-sdk) (2.5.1)\n", | |
| "Requirement already satisfied: homebase<2.0.0,>=1.0.0 in /usr/local/lib/python3.7/dist-packages (from penaltymodel-cache==0.4.3->dwave-ocean-sdk) (1.0.1)\n", | |
| "Requirement already satisfied: Flask>=1.1.1 in /usr/local/lib/python3.7/dist-packages (from dwave-inspector==0.2.5->dwave-ocean-sdk) (1.1.2)\n", | |
| "Requirement already satisfied: importlib-resources>=3.2.0; python_version < \"3.9\" in /usr/local/lib/python3.7/dist-packages (from dwave-inspector==0.2.5->dwave-ocean-sdk) (5.1.2)\n", | |
| "Requirement already satisfied: requests[socks]>=2.18 in /usr/local/lib/python3.7/dist-packages (from dwave-cloud-client==0.8.4->dwave-ocean-sdk) (2.23.0)\n", | |
| "Requirement already satisfied: python-dateutil>=2.7 in /usr/local/lib/python3.7/dist-packages (from dwave-cloud-client==0.8.4->dwave-ocean-sdk) (2.8.1)\n", | |
| "Requirement already satisfied: decorator<5.0.0,>=4.1.0 in /usr/local/lib/python3.7/dist-packages (from dwave-networkx==0.8.8->dwave-ocean-sdk) (4.4.2)\n", | |
| "Requirement already satisfied: fasteners in /usr/local/lib/python3.7/dist-packages (from minorminer==0.2.5->dwave-ocean-sdk) (0.16)\n", | |
| "Requirement already satisfied: ortools<9.0.0,>=6.6.4659 in /usr/local/lib/python3.7/dist-packages (from penaltymodel-mip==0.2.4; platform_machine == \"x86_64\" or platform_machine == \"amd64\" or platform_machine == \"AMD64\"->dwave-ocean-sdk) (8.2.8710)\n", | |
| "Requirement already satisfied: wrapt<2,>=1.10 in /usr/local/lib/python3.7/dist-packages (from Deprecated>=1.2.10->pyqubo==1.0.10->dwave-ocean-sdk) (1.12.1)\n", | |
| "Requirement already satisfied: itsdangerous>=0.24 in /usr/local/lib/python3.7/dist-packages (from Flask>=1.1.1->dwave-inspector==0.2.5->dwave-ocean-sdk) (1.1.0)\n", | |
| "Requirement already satisfied: Werkzeug>=0.15 in /usr/local/lib/python3.7/dist-packages (from Flask>=1.1.1->dwave-inspector==0.2.5->dwave-ocean-sdk) (1.0.1)\n", | |
| "Requirement already satisfied: Jinja2>=2.10.1 in /usr/local/lib/python3.7/dist-packages (from Flask>=1.1.1->dwave-inspector==0.2.5->dwave-ocean-sdk) (2.11.3)\n", | |
| "Requirement already satisfied: zipp>=0.4; python_version < \"3.8\" in /usr/local/lib/python3.7/dist-packages (from importlib-resources>=3.2.0; python_version < \"3.9\"->dwave-inspector==0.2.5->dwave-ocean-sdk) (3.4.1)\n", | |
| "Requirement already satisfied: idna<3,>=2.5 in /usr/local/lib/python3.7/dist-packages (from requests[socks]>=2.18->dwave-cloud-client==0.8.4->dwave-ocean-sdk) (2.10)\n", | |
| "Requirement already satisfied: certifi>=2017.4.17 in /usr/local/lib/python3.7/dist-packages (from requests[socks]>=2.18->dwave-cloud-client==0.8.4->dwave-ocean-sdk) (2020.12.5)\n", | |
| "Requirement already satisfied: urllib3!=1.25.0,!=1.25.1,<1.26,>=1.21.1 in /usr/local/lib/python3.7/dist-packages (from requests[socks]>=2.18->dwave-cloud-client==0.8.4->dwave-ocean-sdk) (1.24.3)\n", | |
| "Requirement already satisfied: chardet<4,>=3.0.2 in /usr/local/lib/python3.7/dist-packages (from requests[socks]>=2.18->dwave-cloud-client==0.8.4->dwave-ocean-sdk) (3.0.4)\n", | |
| "Requirement already satisfied: PySocks!=1.5.7,>=1.5.6; extra == \"socks\" in /usr/local/lib/python3.7/dist-packages (from requests[socks]>=2.18->dwave-cloud-client==0.8.4->dwave-ocean-sdk) (1.7.1)\n", | |
| "Requirement already satisfied: absl-py>=0.11 in /usr/local/lib/python3.7/dist-packages (from ortools<9.0.0,>=6.6.4659->penaltymodel-mip==0.2.4; platform_machine == \"x86_64\" or platform_machine == \"amd64\" or platform_machine == \"AMD64\"->dwave-ocean-sdk) (0.12.0)\n", | |
| "Requirement already satisfied: protobuf>=3.14.0 in /usr/local/lib/python3.7/dist-packages (from ortools<9.0.0,>=6.6.4659->penaltymodel-mip==0.2.4; platform_machine == \"x86_64\" or platform_machine == \"amd64\" or platform_machine == \"AMD64\"->dwave-ocean-sdk) (3.16.0)\n", | |
| "Requirement already satisfied: MarkupSafe>=0.23 in /usr/local/lib/python3.7/dist-packages (from Jinja2>=2.10.1->Flask>=1.1.1->dwave-inspector==0.2.5->dwave-ocean-sdk) (1.1.1)\n" | |
| ], | |
| "name": "stdout" | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "Zw5Nu95vcwJO" | |
| }, | |
| "source": [ | |
| "上記のコードを実行すると、RESTART RUNTIMEというボタンが表示されると思います。\n", | |
| "そのボタンを押してランタイムの再行動をしておきましょう。\n", | |
| "これでD-Wave Systemsの量子アニーリングマシンを利用することができる準備が整いました。\n", | |
| "たったこれだけの準備だてでOKです。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "uFeftXGSdMs1" | |
| }, | |
| "source": [ | |
| "## **量子アニーリングマシンへの入力**\n", | |
| "\n", | |
| "量子アニーリングマシンでは一体どのようなことができるのでしょうか。\n", | |
| "できることはある意味数が少なく「組合せ最適化問題を解く」ということが主な用途となります。\n", | |
| "しかもその組合せ最適化問題のうち、\n", | |
| "シンプルな形を持つ次のような関数を最小化するだけという不器用さです。\n", | |
| "\\begin{equation}\n", | |
| "E({\\bf x}) = \\sum_{i=1}^{N} \\sum_{j=1}^N Q_{ij} x_i x_j\n", | |
| "\\end{equation}\n", | |
| "このような関数を最小化する問題のことを**制約なし2値の2次計画問題**と言います。英語でQuadratic unconstrained binary optimization（QUBO）と呼びます。\n", | |
| "最小化される対象となる関数のことを**コスト関数**と呼びます。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "FXyD2-_9dMvH" | |
| }, | |
| "source": [ | |
| "ここで$x_i$は$0$か$1$を取る２値の変数です。\n", | |
| "変数というのは、状況によって値を変えるものですので、ここではどんな値を取るのか、色々な可能性があります。\n", | |
| "$Q_{ij}$はQUBO行列と呼び、その値によって様々な組合せ最適化問題を表すことができます。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "tLb70uqFdMxP" | |
| }, | |
| "source": [ | |
| "### **高校数学との接点**\n", | |
| "シグマ記号（$\\Sigma$）が登場して驚く読者もいると思います。\n", | |
| "ただシグマ記号を始め、数学の記号はじっくり眺めるとちゃんと読むことのできるものであり、\n", | |
| "その読み方さえ習えば怖いものではないのです。\n", | |
| "それこそ辞書を片手に英語を読むようなものです。だからさっと見せられて翻訳の済む前に次の話に行くと、\n", | |
| "わからないままに進むので嫌な気分だけが記憶に残り、苦手意識に変わります。\n", | |
| "\n", | |
| "そこでじっくりとシグマ記号に慣れ親しむことにしましょう。\n", | |
| "シグマ記号は\n", | |
| "**「下についた文字の始まりから上に書いてある終わりまで、その数値を変えながら、どんどん足していくぞ」**\n", | |
| "という宣言をするものです。だから**たくさん足し算するぞ**と言っているだけです。\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "oEWlU0EjdM4T" | |
| }, | |
| "source": [ | |
| "例えば先ほどのコスト関数は、、、\n", | |
| "\\begin{equation}\n", | |
| "\\sum_{i=1}^N \\sum_{j=1}^N Q_{ij}x_ix_j = Q_{11}x_1x_1 + Q_{12}x_1x_2 + Q_{13}x_1x_3 + \\ldots \n", | |
| "\\end{equation}\n", | |
| "というぐあいに、$i$に$1$を入れてから$j$に$1$を入れて$2$を入れて$3$を入れて、それらを全て足す、ということをしますよという意味です。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "p8BlwZzKcjkn" | |
| }, | |
| "source": [ | |
| "### **早速量子アニーリングマシンを使ってみよう！**\n", | |
| "\n", | |
| "いきなり数学の話が長々と続いてしまっては面白くなくなりますよね。\n", | |
| "早く量子アニーリングを実行したいと思っているはずですから。まずは動かすということをやってみましょう！\n", | |
| "まずは皆さん、D-Wave Systems社のWebページからアカウントを作成しましょう。\n", | |
| "実は1分間だけは誰でも無料で使えます。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "EacfNfq0zleF" | |
| }, | |
| "source": [ | |
| "### **アカウント登録**\n", | |
| "https://cloud.dwavesys.com/leap/\n", | |
| "にアクセスしてください。\n", | |
| "\n", | |
| "メールアドレスや氏名・所属情報を記入してご自身のアカウントを作成してください。\n", | |
| "\n", | |
| "そのアカウントでログインしたのちに、画面左下にあるAPI tokenをコピーしてください。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "-CHtp856zlgD" | |
| }, | |
| "source": [ | |
| "### **簡単な問題を投入してみよう！**\n", | |
| "\n", | |
| "それではアカウント登録が済んだら、そこで得られたご自身のAPI keyを利用して、量子アニーリングマシンに問題を投じてみましょう。先ほど紹介したように量子アニーリングマシンに問題を投じるというのは、QUBO行列をカナダにある量子アニーリングマシンに送信するという意味です。\n", | |
| "だからQUBO行列さえ用意することができれば良いわけです。\n", | |
| "やってみましょう。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "XZEDrVPOz_F2" | |
| }, | |
| "source": [ | |
| "import numpy as np\n", | |
| "\n", | |
| "N = 10\n", | |
| "QUBO = np.random.randn(N**2).reshape(N,N)" | |
| ], | |
| "execution_count": 2, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "mfy9gAZL0GIy" | |
| }, | |
| "source": [ | |
| "まずは簡単な例として、10×10行列によるQUBOを考えてみます。\n", | |
| "np.random.randn()は、平均0、分散1のガウス分布に従う乱数を生成するという関数です。\n", | |
| "それをN**2=100個作ったのち、reshape(N,N)として、10×10の行列の形にします。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "V44e1gKFyD7Q" | |
| }, | |
| "source": [ | |
| "これでQUBO行列が用意できました。\n", | |
| "このQUBO行列には正負の値がでたらめに入っています。\n", | |
| "それぞれの値を見ることもできます。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "b3Kmb3PNyYRd", | |
| "outputId": "9674a18c-1ffa-420e-d851-68eb065786dc" | |
| }, | |
| "source": [ | |
| "print(QUBO[0][1])" | |
| ], | |
| "execution_count": 3, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "text": [ | |
| "0.5018231198621114\n" | |
| ], | |
| "name": "stdout" | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "jzt4b3xBybzd" | |
| }, | |
| "source": [ | |
| "$Q_{ij}$の値が正であれば、コスト関数の一部分を注目すると$Q_{ij}x_ix_j$を小さい値にするには、$x_ix_j = 0$になるのが良い。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "mWn1i2M20lnD" | |
| }, | |
| "source": [ | |
| "- $x_i=0$, $x_j=1$\n", | |
| "- $x_i=1$, $x_j=0$\n", | |
| "- $x_i=0$, $x_j=0$" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "gu_QVIEs1HJK" | |
| }, | |
| "source": [ | |
| "という3通りが選ばれることになる。逆に$Q_{ij}$が負の値をとると$x_ix_j=1$となるのが良い。\n", | |
| "- $x_i=1$,$x_j=1$\n", | |
| "\n", | |
| "単純に$ij$のペア1つだけに注目するのであれば、こうした傾向を考えていけば良い。\n", | |
| "しかし他にも$i$にかかる別のペアから他の向きになることを要求される可能性もある。\n", | |
| "さらに$Q_{ii}x_ix_i$というQUBO行列の対角成分$Q_{ii}$の値次第で、$x_i$がまた影響を受ける。$Q_{ii}$が正の値を取ると$x_i=0$になった方が良いし、$Q_{ii}$が負の値を取ると$x_i=1$になった方が良い。\n", | |
| "以上のような様々な影響がかかり、どの向きを向いたら良いのかがすぐにはわからない悩ましい問題となる。組合せ最適化問題にはそうした悩ましい状況が往々にして生じる。\n", | |
| "こうした問題に対して、D-Wave Systemsの量子アニーリングマシンで答えを出してみよう。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "F03UTTZ3_9YU" | |
| }, | |
| "source": [ | |
| "まず先ほど登録したアカウントからAPI tokenを入手します。\n", | |
| "ログインした後の画面において左側にあるボタンからAPI tokenをコピーしましょう。\n", | |
| "そのtokenを以下の**の代わりに入力してください。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "D5juECTB1g98" | |
| }, | |
| "source": [ | |
| "token = '**' # 個人のAPI tokenを使用\n", | |
| "endpoint = 'https://cloud.dwavesys.com/sapi/'" | |
| ], | |
| "execution_count": 4, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "YQ4eXAXN2T1K" | |
| }, | |
| "source": [ | |
| "これでD-Wave Systems社の量子アニーリングマシンを利用する環境が整いました。\n", | |
| "続けて量子アニーリングマシンを呼び出す関数をいくつか用意します。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "PquuZ9G2CBMP" | |
| }, | |
| "source": [ | |
| "from dwave.system import DWaveSampler, EmbeddingComposite\n", | |
| "\n", | |
| "dw_sampler = DWaveSampler(solver='Advantage_system1.1', token=token, endpoint=endpoint)" | |
| ], | |
| "execution_count": 5, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "BOEtLqhnCGsv" | |
| }, | |
| "source": [ | |
| "まず from dwave.systemとあるのはOcean SDKのdwave.systemの中からということです。\n", | |
| "\n", | |
| "**import DWaveSampler**でDWaveSamplerという関数を呼び出しており、\n", | |
| "\n", | |
| "**import EmbeddingComposite**でEmbeddingCompositeという関数を呼び出しています。\n", | |
| "\n", | |
| "この呼び出した関数のうちDWaveSamplerは、量子アニーリングマシンにアクセスするための関数です。\n", | |
| "solver=というオプションで、どの量子アニーリングマシンを使うのかを指定することができます。\n", | |
| "\n", | |
| "最新式の量子アニーリングマシンはD-Wave Advantageであり、それを利用する場合には\n", | |
| "\n", | |
| "**solver = 'Advantage_system1.1'**としましょう。\n", | |
| "\n", | |
| "前の形式の量子アニーリングマシンであるD-Wave 2000Qを利用する場合には\n", | |
| "\n", | |
| "**solver = 'DW_2000Q_6'**としましょう。\n", | |
| "\n", | |
| "それぞれ利用したいものを指定すれば準備完了です。\n", | |
| "\n", | |
| "量子アニーリングマシンの中にはQPU（Quantum Processing Unit）と呼ばれる部品があり、\n", | |
| "そこに搭載された超伝導量子ビットによる回路のパラメータを調整して$Q_{ij}$を与えます。\n", | |
| "回路の設計上、$Q_{ij}$で指定された構造を作ることができない場合には、他の回路や量子ビットをうまく組み合わせるエンベッドという作業をします。\n", | |
| "その作業をするには先ほど読み込んだ関数のうちEmbeddingComposite()という関数を利用することができます。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "xlidH5HhHEF9" | |
| }, | |
| "source": [ | |
| "sampler = EmbeddingComposite(dw_sampler)" | |
| ], | |
| "execution_count": 6, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "jQBD8SUmCGvM" | |
| }, | |
| "source": [ | |
| "エンべディングを終えると、超伝導量子ビットにどの$x_i$を割り当てるか、\n", | |
| "どのように$Q_{ij}$を割り当てるのかが決められた新しいsamplerに置き換わります。\n", | |
| "これを利用することで,先ほど用意したQUBO行列に基づく組合せ最適化問題を量子アニーリングマシンに解かせることができます。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "1PbAeKHRCGBj" | |
| }, | |
| "source": [ | |
| "sampleset = sampler.sample_qubo(QUBO, num_reads=10)" | |
| ], | |
| "execution_count": 7, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "R3cmzq7GK1RX" | |
| }, | |
| "source": [ | |
| "sampler.sample_quboというのが、用意したsamplerの機能のうちQUBO形式の組合せ最適化問題を解く関数です。この引数として、先ほど用意したQUBO行列を入れます。\n", | |
| "num_readsは非常にユニークなオプションで、何度結果を読み出すかを指定するところです。\n", | |
| "結果を受け取ったsamplesetには、指定した組合せ最適化問題をnum_readsで指定した回数分解いた答えが格納されています。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "MXHWX34fM8Xc", | |
| "outputId": "bb4d51ba-65d7-4ea1-d083-953ed22a71e4" | |
| }, | |
| "source": [ | |
| "print(sampleset.record)" | |
| ], | |
| "execution_count": 8, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "text": [ | |
| "[([1, 0, 1, 1, 0, 1, 0, 1, 0, 0], -6.56034852, 4, 0.)\n", | |
| " ([1, 0, 1, 1, 0, 1, 1, 1, 0, 0], -6.19286179, 3, 0.)\n", | |
| " ([1, 0, 0, 1, 0, 1, 0, 1, 0, 0], -5.60593592, 1, 0.)\n", | |
| " ([1, 1, 0, 1, 0, 0, 0, 1, 0, 0], -5.5340956 , 1, 0.)\n", | |
| " ([1, 0, 0, 1, 0, 0, 0, 1, 0, 0], -5.3870332 , 1, 0.)]\n" | |
| ], | |
| "name": "stdout" | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "LbtbInMfNh4i" | |
| }, | |
| "source": [ | |
| "結果の一番目を取り出したいときはsampleset.record[0]として、\n", | |
| "$x_i$などの結果を知りたいときは、sampleset.record[0][0]から取り出すことができます。\n", | |
| "さらにコスト関数の値を知りたいときはsampleset.record[0][1]\n", | |
| "その答えが何度出てきたのか頻度を知りたいときはsampleset.record[0][2]で調べることができます。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "DQPBPoXNNSKd", | |
| "outputId": "76a2b05a-3a83-4c65-fbe0-b271ac3e6f64" | |
| }, | |
| "source": [ | |
| "sampleset.record[0][0]" | |
| ], | |
| "execution_count": 9, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "array([1, 0, 1, 1, 0, 1, 0, 1, 0, 0], dtype=int8)" | |
| ] | |
| }, | |
| "metadata": { | |
| "tags": [] | |
| }, | |
| "execution_count": 9 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "TWAnuQk_Kxfh" | |
| }, | |
| "source": [ | |
| "簡単に利用できることがご理解いただけましたかね。では次に行ってみよう！" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "dWzmOoJPzlkJ" | |
| }, | |
| "source": [ | |
| "### **実感の湧く問題を解いてみよう**" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "gzgI7qDUzll-" | |
| }, | |
| "source": [ | |
| "上記の例はでたらめなQUBO行列によるものであったので、あまり解いたとしても実感が湧かない。\n", | |
| "そこで少し具体的に意味のある問題を解いてみることにしましょう。\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "gu_yM2KXzloD" | |
| }, | |
| "source": [ | |
| "**いくつかの荷物があり、それぞれには重さが異なるものとします。\n", | |
| "それを運ぶ2人がいて、重さが均等になるようにその荷物を2つのグループに分けたい。**" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "40LzLXSPzlqM" | |
| }, | |
| "source": [ | |
| "どのようにしたら良いでしょうか？\n", | |
| "ここで考えなければならないのは**QUBO行列を作る**ことです。\n", | |
| "ただしいきなり$Q_{ij}$のことを思っても何も思い浮かばないものです。\n", | |
| "そこで重要となるのが**数式によるモデリング**です。\n", | |
| "ここが量子アニーリングの研究開発を行う上での成長ポイントです。\n", | |
| "量子そのものの前に、数理モデリングに挑戦する必要があるのです。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "SwFe5FJEzlsX" | |
| }, | |
| "source": [ | |
| "重さを持ついくつかの荷物があるというのだから、その重さを$w_i$としましょう。\n", | |
| "$N$個あるとして、合計した重さは$W=\\sum_{i=1}^N w_i$です。\n", | |
| "\n", | |
| "（こうやって何も与えられていないところで**自分で文字式を立てる**ところから訓練です）\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "4vbhaCW3zlup" | |
| }, | |
| "source": [ | |
| "2人のうちAさんがその荷物を取る場合$x_i=1$として、取らない場合は$x_i=0$とすると、\n", | |
| "Aさんが持つ荷物の重さの合計は、\n", | |
| "\\begin{equation}\n", | |
| "W_A = \\sum_{i=1}^N w_i x_i\n", | |
| "\\end{equation}\n", | |
| "逆にBさんは残りの荷物を持つので\n", | |
| "\\begin{equation}\n", | |
| "W_B = W - W_A\n", | |
| "\\end{equation}\n", | |
| "となります。\n", | |
| "これらが等しくなるというのだから、\n", | |
| "\\begin{equation}\n", | |
| "W_A - W_B\n", | |
| "\\end{equation}\n", | |
| "という引き算をしたズレが$0$になれば完璧です。\n", | |
| "もしくは非常に小さいものとなってくれれば嬉しい。\n", | |
| "ただ$W_A$がわずかに大きくても仕方ないし、小さくても仕方ない。正負の値どちらでも良いからとにかく**ズレの大きさ**ができるだけ小さいことが望ましいというわけです。\n", | |
| "できるだけ小さい、すなわちズレの大きさが最小になるような組み合わせを見つければ良いですよね。\n", | |
| "そうするとコスト関数として、次のようなものを考えてみましょう。\n", | |
| "\\begin{equation}\n", | |
| "E({\\bf x}) = \\left( W_A - W_B \\right)^2 = \\left( 2W_A - W \\right)^2\n", | |
| "\\end{equation}\n", | |
| "ここに$W_A$の具体的な形として先ほど準備しておいた形を入れてみましょう。\n", | |
| "\\begin{equation}\n", | |
| "E({\\bf x}) = \\left( 2\\sum_{i=1}^N w_i x_i - W \\right)^2\n", | |
| "\\end{equation}\n", | |
| "\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "XS7EVj71zlwx" | |
| }, | |
| "source": [ | |
| "何か近い形になってきましたね。二乗をするというのは同じものを掛け算するという意味です。\n", | |
| "シグマ記号は嫌らしいけれども意味はとにかく足し算をするというものでした。\n", | |
| "下にある$i=1$は$i$という文字を$1$から動かして上にある$N$まで変えて足し算してくださいね、ということです。\n", | |
| "だったら$i$という文字は仮置きをしているだけですから、別の文字を使っても良いですね。\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "OXjkUAmOXRcx" | |
| }, | |
| "source": [ | |
| "\\begin{equation}\n", | |
| "E({\\bf x}) = \\left( 2\\sum_{i=1}^N w_i x_i - W \\right)\\left( 2\\sum_{j=1}^N w_j x_j - W \\right)\n", | |
| "\\end{equation}" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "NZifi9yCXWyS" | |
| }, | |
| "source": [ | |
| "この掛け算を展開してみましょう。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "i3VkKv_WXbow" | |
| }, | |
| "source": [ | |
| "\\begin{equation}\n", | |
| "E({\\bf x}) = 4\\sum_{i=1}^N\\sum_{j=1}^N w_iw_j x_ix_j - 2W\\sum_{i=1}^N w_i x_i - 2W\\sum_{j=1}^N w_j x_j + W^2\n", | |
| "\\end{equation}" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "J6GWTPrzY9vy" | |
| }, | |
| "source": [ | |
| "ここで第二項と第三項で同じ和が2つ出ていますので、まとめておきましょう。\n", | |
| "\\begin{equation}\n", | |
| "E({\\bf x}) = 4\\sum_{i=1}^N\\sum_{j=1}^N w_iw_j x_ix_j - 4W\\sum_{i=1}^N w_i x_i + W^2\n", | |
| "\\end{equation}\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "6rFLqcTlYtO6" | |
| }, | |
| "source": [ | |
| "$x_ix_j$という部分が出てきましたね。その係数は$4w_iw_j$で、この部分がQUBO行列に相当します。$x_i$が$0$と$1$のどちらかの値を持つことから、$x_i$が$x_ix_i$と同じことを思いつくと、第二項は、$-4W\\sum_{i=1}^N w_i x_ix_i$という意味で、QUBO行列のうち添え字が同じ$i$と$i$のとき、対角成分のことを示していることがわかります。\n", | |
| "これらの事実からQUBO行列を作るプログラムの発想ができます。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "IkimRioVZ25x" | |
| }, | |
| "source": [ | |
| "N = 10\n", | |
| "w = np.random.rand(N)" | |
| ], | |
| "execution_count": 10, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "BtaN3gwwZ6_o" | |
| }, | |
| "source": [ | |
| "まず例えば$N=10$個の荷物について、その重さを適当な乱数で決めることにしましょう。\n", | |
| "\n", | |
| "np.random.rand()で$0$から$1$の範囲にある適当な数値が出ます。\n", | |
| "\n", | |
| "この係数からQUBO行列を作ります。\n", | |
| "まず最初に全重量の計算です。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "bBEtvgMcXQxB" | |
| }, | |
| "source": [ | |
| "W = np.sum(w)" | |
| ], | |
| "execution_count": 11, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "sf6-PIHAaUbo" | |
| }, | |
| "source": [ | |
| "numpyのsum()を利用すれば全重量の合計が計算できます。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "B6UbhVJ_abdQ" | |
| }, | |
| "source": [ | |
| "Q = np.zeros(N**2).reshape(N,N)" | |
| ], | |
| "execution_count": 12, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "3lLNGyMKzlzE" | |
| }, | |
| "source": [ | |
| "まずはQUBO行列を格納する場所を用意しましょう。np.zeros()はその名の通り、全成分を0で埋めたものを並べて作ります。これを.reshape(N,N)でN×Nの行列に整形します。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "tRE0jFCCas-4" | |
| }, | |
| "source": [ | |
| "for i in range(N):\n", | |
| " for j in range(N):\n", | |
| " Q[i][j] = 4*w[i]*w[j]" | |
| ], | |
| "execution_count": 13, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "I3i4SSXWzl1N" | |
| }, | |
| "source": [ | |
| "まず第一項の計算をここで実行しています。for文を使って、iとjを動かしながら、$Q_{ij}$すなわちQ[i][j]に値を入れていきます。その値は$4w_iw_j$ですから、その結果を入れていきます。\n", | |
| "次に第二項をQUBO行列の対角成分に追加しましょう。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "TraXwF00bOdq" | |
| }, | |
| "source": [ | |
| "for i in range(N):\n", | |
| " Q[i][i] = Q[i][i] - 4*W*w[i]" | |
| ], | |
| "execution_count": 14, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "iBsMrsaNbWGA" | |
| }, | |
| "source": [ | |
| "ここで注意して欲しいのが、第一項で計算した結果に追加するので、元からあるQ[i][i]に引き算をするようにしています。\n", | |
| "\n", | |
| "これでQUBO行列の作成完了です。\n", | |
| "すでにD-Waveマシンの利用準備は整っておりますので、QUBO行列を投入するだけです。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "6le7e1vccnpU" | |
| }, | |
| "source": [ | |
| "sampleset = sampler.sample_qubo(Q, num_reads=10)" | |
| ], | |
| "execution_count": 15, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "Ox0otlu5eFYB", | |
| "outputId": "4714cf59-27a5-4558-ce67-ef565dedf951" | |
| }, | |
| "source": [ | |
| "print(sampleset.record)" | |
| ], | |
| "execution_count": 16, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "text": [ | |
| "[([1, 1, 0, 0, 0, 1, 1, 0, 1, 0], -22.65586681, 1, 0. )\n", | |
| " ([1, 1, 0, 0, 0, 1, 0, 1, 1, 0], -22.65382921, 1, 0. )\n", | |
| " ([0, 0, 0, 1, 1, 1, 1, 0, 0, 1], -22.61011989, 1, 0. )\n", | |
| " ([1, 0, 0, 1, 0, 0, 1, 0, 1, 1], -22.5964122 , 1, 0. )\n", | |
| " ([0, 0, 1, 1, 1, 0, 1, 0, 0, 0], -22.58268331, 1, 0. )\n", | |
| " ([0, 0, 1, 1, 0, 1, 1, 1, 0, 0], -22.57144702, 1, 0. )\n", | |
| " ([0, 1, 1, 0, 0, 0, 0, 1, 1, 1], -22.48753267, 1, 0. )\n", | |
| " ([1, 1, 1, 0, 1, 1, 1, 0, 0, 0], -22.12185328, 1, 0. )\n", | |
| " ([0, 1, 0, 0, 0, 1, 1, 0, 1, 0], -21.72540848, 1, 0. )\n", | |
| " ([1, 0, 0, 1, 0, 1, 1, 1, 0, 0], -21.8696764 , 1, 0.1)]\n" | |
| ], | |
| "name": "stdout" | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "j-nG_poleIKR" | |
| }, | |
| "source": [ | |
| "結果が出てきましたね。それでは一番結果の良かった一番目の結果を抜き出してみましょう。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "ExDMgxAQy-yZ" | |
| }, | |
| "source": [ | |
| "x = sampleset.record[0][0]" | |
| ], | |
| "execution_count": 17, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "PZnR0skCeUx4" | |
| }, | |
| "source": [ | |
| "結果を示す$x_i$の数列をxに格納しました。\n", | |
| "これから$W_A$と$W_B$を計算してみましょう。\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "EER-2s6VeTER", | |
| "outputId": "bb473c75-ed1f-41ec-98ea-ca208ab7ae07" | |
| }, | |
| "source": [ | |
| "print(np.dot(w,x))" | |
| ], | |
| "execution_count": 18, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "text": [ | |
| "2.3703739534391586\n" | |
| ], | |
| "name": "stdout" | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "FEZeQCcOeg-L", | |
| "outputId": "6af977e5-6b66-4793-97ce-fb0c2430dbda" | |
| }, | |
| "source": [ | |
| "print(W-np.dot(w,x))" | |
| ], | |
| "execution_count": 19, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "text": [ | |
| "2.3894823408627266\n" | |
| ], | |
| "name": "stdout" | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "Kpb5K9YLg4_9" | |
| }, | |
| "source": [ | |
| "ほぼ揃った答えがうまく出せたでしょうか？" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "tK2pSw4KhFeg" | |
| }, | |
| "source": [ | |
| "### **他のソルバーを利用してみよう！**" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "mRWMJ28qjUk7" | |
| }, | |
| "source": [ | |
| "D-Wave Systems社の量子アニーリングマシンは、QPUの成長とともに扱える問題の規模を大きくしてきました。\n", | |
| "最近ではハイブリッドソルバーの登場により、飛躍的にその規模を大きくしました。\n", | |
| "純粋に量子現象を利用した計算だけではないものの、古典的な計算アルゴリズムを巧みに利用して、計算性能も向上させているため大規模な問題を解く上では有用です。\n", | |
| "その利用方法についても容易であり、以下のようなコードでsamplerを書き換えるだけです。\n", | |
| "\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "2SODQpKdj-1a" | |
| }, | |
| "source": [ | |
| "from dwave.system import LeapHybridSampler\n", | |
| "sampler = LeapHybridSampler(solver='hybrid_binary_quadratic_model_version2', token=token, endpoint=endpoint)" | |
| ], | |
| "execution_count": 20, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "MaUJ6H0HkEfF" | |
| }, | |
| "source": [ | |
| "ソルバーのオプションとして、solver='hybrid_binary_quadratic_model_version2'を選ぶだけでOKです。注意としてはハイブリッドソルバーを利用する場合には、エンベッドの必要がないことです。ここで用意したsamplerを使って直ちに結果を得ることができます。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "bkd5hXLPky55" | |
| }, | |
| "source": [ | |
| "sampleset = sampler.sample_qubo(Q)" | |
| ], | |
| "execution_count": 21, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "WvevSC0BkC9-" | |
| }, | |
| "source": [ | |
| "注意としてハイブリッドソルバーは、オプションとしてnum_readsを持ちません。\n", | |
| "ハイブリッドソルバーは**最大で100万変数**のものを扱うことができる（扱うことのできるQUBO行列には全ての値が詰まっていないなどの条件はあります）\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "em70zZwplHqS", | |
| "outputId": "495a847b-0846-48c3-9c75-cc2eb93c08b7" | |
| }, | |
| "source": [ | |
| "print(sampleset.record)" | |
| ], | |
| "execution_count": 22, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "text": [ | |
| "[([1, 0, 1, 0, 0, 1, 0, 1, 1, 1], -22.65620135, 1)]\n" | |
| ], | |
| "name": "stdout" | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "XmkD0jEplawq" | |
| }, | |
| "source": [ | |
| "場合によっては上記の純粋な量子現象のみのQPUによる結果よりも良好な結果を得たのではないでしょうか。これがD-Wave Systems社の用意したハイブリッドソルバーの威力です。\n", | |
| "他にもD-Wave Systems社が用意したソルバーとして、**整数値を利用することのできるhybrid_discrete_quadratic_model_version1**があります。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "45jyT_Vh6nZB" | |
| }, | |
| "source": [ | |
| "### **QUBO行列の設定方法について**" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "Z1C_kBE96saW" | |
| }, | |
| "source": [ | |
| "QUBO行列はだんだんと巨大なものになってくると、そのデータ転送にも時間がかかるようになり、せっかくの量子アニーリングマシンのパワーを台無しにしてしまうことがあります。\n", | |
| "データの転送量を抑えるためにも、不要な成分についてはその情報を送らないようにしておくと良いでしょう。\n", | |
| "python上ではnumpyによるarray形式で行列を扱うことが多いのですが、代わりにdict形式でデータを送りましょう。\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "w6DAxcPm7FCn" | |
| }, | |
| "source": [ | |
| "Qdict = {}\n", | |
| "for i in range(N):\n", | |
| " for j in range(N):\n", | |
| " if Q[i][j] != 0.0:\n", | |
| " Qdict[(i,j)] = Q[i][j]" | |
| ], | |
| "execution_count": 23, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "Uiv3XbN77RnA" | |
| }, | |
| "source": [ | |
| "dict形式の初期化は{}で中身は空欄にしておくだけです。\n", | |
| "Qdict[(i,j)]のように(i,j)でどの成分に値があるのかを指定して、その値を代入します。\n", | |
| "ここではif文を使い、ゼロではないところだけ、Qdictのデータとして格納しています。\n", | |
| "出来上がったものを確認したい場合にはQdictとそのまま打って実行したり、print(Qdict)と実行してみましょう。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "tKL6Jbtg7m_a", | |
| "outputId": "6c8d484f-3628-4d3f-df3f-09b3dadd2252" | |
| }, | |
| "source": [ | |
| "print(Qdict)" | |
| ], | |
| "execution_count": 24, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "text": [ | |
| "{(0, 0): -8.108318134950009, (0, 1): 0.5927202975009696, (0, 2): 0.33097256794538177, (0, 3): 0.6208075411225487, (0, 4): 1.4072491071247608, (0, 5): 0.0815439373191539, (0, 6): 1.8858205691235246, (0, 7): 1.8575358434748175, (0, 8): 1.028845098141531, (0, 9): 0.30282317319732127, (1, 0): 0.5927202975009696, (1, 1): -5.5737791540160915, (1, 2): 0.21935631422602386, (1, 3): 0.41144815991769923, (1, 4): 0.9326723941293269, (1, 5): 0.05404429028317331, (1, 6): 1.2498517683883206, (1, 7): 1.2311057037047406, (1, 8): 0.6818802840333316, (1, 9): 0.20069994183250597, (2, 0): 0.33097256794538177, (2, 1): 0.21935631422602386, (2, 2): -3.209243930058555, (2, 3): 0.22975095443587412, (2, 4): 0.5208004157074536, (2, 5): 0.030178108651287172, (2, 6): 0.6979120692823623, (2, 7): 0.6874443441287714, (2, 8): 0.3807591364584049, (2, 9): 0.11207001922299548, (3, 0): 0.6208075411225487, (3, 1): 0.41144815991769923, (3, 2): 0.22975095443587412, (3, 3): -5.818406592789154, (3, 4): 0.9768689517020647, (3, 5): 0.05660528769449673, (3, 6): 1.3090785086528158, (3, 7): 1.2894441239843566, (3, 8): 0.7141925529722307, (3, 9): 0.210210512307068, (4, 0): 1.4072491071247608, (4, 1): 0.9326723941293269, (4, 2): 0.5208004157074536, (4, 3): 0.9768689517020647, (4, 4): -11.951686542047312, (4, 5): 0.12831310074388438, (4, 6): 2.967424588829591, (4, 7): 2.922917284289328, (4, 8): 1.6189346390154866, (4, 9): 0.4765060605054165, (5, 0): 0.0815439373191539, (5, 1): 0.05404429028317331, (5, 2): 0.030178108651287172, (5, 3): 0.05660528769449673, (5, 4): 0.12831310074388438, (5, 5): -0.8134259339425914, (5, 6): 0.17194928989170336, (5, 7): 0.1693702860513023, (5, 8): 0.09381018901295493, (5, 9): 0.027611444294635325, (6, 0): 1.8858205691235246, (6, 1): 1.2498517683883206, (6, 2): 0.6979120692823623, (6, 3): 1.3090785086528158, (6, 4): 2.967424588829591, (6, 5): 0.17194928989170336, (6, 6): -15.007017226687848, (6, 7): 3.916930917669297, (6, 8): 2.169495242075364, (6, 9): 0.6385542727748674, (7, 0): 1.8575358434748175, (7, 1): 1.2311057037047406, (7, 2): 0.6874443441287714, (7, 3): 1.2894441239843566, (7, 4): 2.922917284289328, (7, 5): 0.1693702860513023, (7, 6): 3.916930917669297, (7, 7): -14.8406811214364, (7, 8): 2.1369557848634844, (7, 9): 0.6289768332703014, (8, 0): 1.028845098141531, (8, 1): 0.6818802840333316, (8, 2): 0.3807591364584049, (8, 3): 0.7141925529722307, (8, 4): 1.6189346390154866, (8, 5): 0.09381018901295493, (8, 6): 2.169495242075364, (8, 7): 2.1369557848634844, (8, 8): -9.17324829387886, (8, 9): 0.3483753673060714, (9, 0): 0.30282317319732127, (9, 1): 0.20069994183250597, (9, 2): 0.11207001922299548, (9, 3): 0.210210512307068, (9, 4): 0.4765060605054165, (9, 5): 0.027611444294635325, (9, 6): 0.6385542727748674, (9, 7): 0.6289768332703014, (9, 8): 0.3483753673060714, (9, 9): -2.945827624711183}\n" | |
| ], | |
| "name": "stdout" | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "U-5Lhef57D8S" | |
| }, | |
| "source": [ | |
| "どこの成分に重要な非零の行列成分があるのかを指定する形になっています。\n", | |
| "上記の問題では非零成分のない問題になっていますので影響はさほどありませんが、\n", | |
| "基本的なテクニックとして知っておくと良いでしょう。\n", | |
| "\n", | |
| "（正直この入力の違いだけでハイブリッドソルバーなどでは如実に性能が変わります）" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "z4LcRgYE4J_b" | |
| }, | |
| "source": [ | |
| "### **シミュレータを活用しよう**" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "d3kszBzahK9k" | |
| }, | |
| "source": [ | |
| "さて上記のように用意した量子アニーリングマシンは、利用回数には制限があり、大事に使いたいところでしょう。演習の際には豊富なマシンタイムを利用することのできるAPI tokenを発行する予定ですが、講義の間の試し利用の場合には、代わりになるシミュレータを利用すると良いでしょう。\n", | |
| "その一つが**株式会社Jijの開発するOpenJij**です。\n", | |
| "\n", | |
| "OpenJijは量子アニーリングマシンのシミュレータを搭載するオープンソースソフトウェアです。\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "IP9-zetq5OZP" | |
| }, | |
| "source": [ | |
| "基本的な利用方法は、これまでと同じようにQUBO行列を作ったのちにsamplerに投入するだけです。その際にOpenJijのsamplerを利用します。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "u-5Dp62i5YN_" | |
| }, | |
| "source": [ | |
| "その前にまずはOpenJijのインストールが必要です。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "GiWddXap5fIL", | |
| "outputId": "29bab353-7e1f-4c06-e071-b09c750c6a70" | |
| }, | |
| "source": [ | |
| "pip install openjij" | |
| ], | |
| "execution_count": 25, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "text": [ | |
| "Requirement already satisfied: openjij in /usr/local/lib/python3.7/dist-packages (0.2.2)\n", | |
| "Requirement already satisfied: requests in /usr/local/lib/python3.7/dist-packages (from openjij) (2.23.0)\n", | |
| "Requirement already satisfied: numpy>=1.18.4 in /usr/local/lib/python3.7/dist-packages (from openjij) (1.19.5)\n", | |
| "Requirement already satisfied: scipy in /usr/local/lib/python3.7/dist-packages (from openjij) (1.4.1)\n", | |
| "Requirement already satisfied: jij-cimod>=1.1.0 in /usr/local/lib/python3.7/dist-packages (from openjij) (1.1.1)\n", | |
| "Requirement already satisfied: dimod>=0.9.1 in /usr/local/lib/python3.7/dist-packages (from openjij) (0.9.13)\n", | |
| "Requirement already satisfied: urllib3!=1.25.0,!=1.25.1,<1.26,>=1.21.1 in /usr/local/lib/python3.7/dist-packages (from requests->openjij) (1.24.3)\n", | |
| "Requirement already satisfied: certifi>=2017.4.17 in /usr/local/lib/python3.7/dist-packages (from requests->openjij) (2020.12.5)\n", | |
| "Requirement already satisfied: idna<3,>=2.5 in /usr/local/lib/python3.7/dist-packages (from requests->openjij) (2.10)\n", | |
| "Requirement already satisfied: chardet<4,>=3.0.2 in /usr/local/lib/python3.7/dist-packages (from requests->openjij) (3.0.4)\n" | |
| ], | |
| "name": "stdout" | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "3xLQbXWn5bp3" | |
| }, | |
| "source": [ | |
| "再びpip installを利用して、OpenJijをインストールします。\n", | |
| "その後にimport SQASamplerを実行してsamplerの準備を行いましょう。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "iOnD6obYfGnp" | |
| }, | |
| "source": [ | |
| "from openjij import SQASampler\n", | |
| "sampler = SQASampler()" | |
| ], | |
| "execution_count": 26, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "2_l066yk8AcA" | |
| }, | |
| "source": [ | |
| "準備はこれだけです。SQAというのはシミュレーテッド量子アニーリングというもので、\n", | |
| "**量子モンテカルロ法**という計算技術を活用して、**量子アニーリングのシミュレーション**を行っています。\n", | |
| "オプションでそのシミュレーションのパラメータ等を設定することができますが、とりあえず前に進めていきましょう。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "fR5-8aee5vDn" | |
| }, | |
| "source": [ | |
| "sampleset = sampler.sample_qubo(Qdict, num_reads=10)" | |
| ], | |
| "execution_count": 27, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "iJeu9wTa6g0K", | |
| "outputId": "8726dbf9-2c65-42b1-e2e8-89694ed93e50" | |
| }, | |
| "source": [ | |
| "print(sampleset.record)" | |
| ], | |
| "execution_count": 28, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "text": [ | |
| "[([0, 0, 1, 0, 1, 0, 0, 1, 1, 0], -22.63923668, 1)\n", | |
| " ([0, 1, 0, 1, 0, 1, 0, 1, 1, 1], -22.6559072 , 1)\n", | |
| " ([0, 0, 0, 1, 0, 0, 1, 1, 0, 1], -22.62554223, 1)\n", | |
| " ([1, 0, 1, 0, 1, 1, 0, 0, 1, 0], -22.01311023, 1)\n", | |
| " ([1, 1, 0, 0, 0, 1, 0, 1, 1, 1], -22.58268331, 1)\n", | |
| " ([0, 0, 1, 0, 1, 1, 1, 0, 1, 0], -22.59546837, 1)\n", | |
| " ([1, 1, 0, 1, 1, 1, 0, 0, 1, 1], -22.45236762, 1)\n", | |
| " ([0, 0, 0, 1, 1, 0, 0, 1, 0, 1], -22.54675435, 1)\n", | |
| " ([1, 0, 0, 0, 1, 0, 1, 0, 0, 1], -22.65609399, 1)\n", | |
| " ([1, 1, 1, 1, 1, 0, 0, 0, 0, 1], -22.51734916, 1)]\n" | |
| ], | |
| "name": "stdout" | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "B40tNNEt9KHW" | |
| }, | |
| "source": [ | |
| "OpenJijではdict形式で問題を受け付けますので、注意してください。\n", | |
| "\n", | |
| "（先程の手順でnumpy array形式だったものをdict形式に直しておきましょう）\n", | |
| "\n", | |
| "結構いい答えが出てきたのではないでしょうか。これでとりあえずは十分ですよね。\n", | |
| "ただ問題のサイズが大きくなるにつれて結果が次第に悪化してくることがありますのでご注意を。\n", | |
| "それはパラメータの設定で改善する可能性があります。" | |
| ] | |
| } | |
| ] | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
D-waveのアップデートでendpointが変わっているので、修正していただきたいです。
https://gist.github.com/Lich496/d8803f8c5a180faf721d604ffcdc60d4