Created
May 18, 2021 03:14
-
-
Save mohzeki222/7ff6e97c263f042dc671f7f45e460fbb to your computer and use it in GitHub Desktop.
Embedding.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": "Embedding.ipynb", | |
| "provenance": [], | |
| "collapsed_sections": [], | |
| "authorship_tag": "ABX9TyM5MMrhBKQnjdLG8xty54W9", | |
| "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/7ff6e97c263f042dc671f7f45e460fbb/embedding.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "CB8giTRTcTwQ" | |
| }, | |
| "source": [ | |
| "### **埋め込みについて**" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "QBmpfCO0cT3T" | |
| }, | |
| "source": [ | |
| "第一回で様々な質問の中で注目を集めたのがエンベッド（埋め込み）でした。\n", | |
| "量子アニーリングマシンにおける計算を実行する際には、\n", | |
| "量子演算回路（Quantum Processing Unit: QPU）に、自分の解きたい最適化問題のネットワークを埋め込むということをしています。\n", | |
| "\n", | |
| "講義内ではEmbeddingComposite()という関数を通して、**自動的に埋め込みをした上で量子アニーリングマシンを使う**ということをしています。\n", | |
| "\n", | |
| "そこで問題となるのがマシンに問題を解いてもらう手前で、埋め込みを行う時間がかかること、自動的に埋め込みを行う結果が実行のたびに変わるので、再現性のある結果を生み出すことができないことが挙げられます。\n", | |
| "とりあえず実行する上では差し支えがありませんが、量子アニーリングマシンを利用した研究を行う、または性能を向上させる努力を続ける上では望ましい状況ではありません。\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "OUWcXMbvcT5Z" | |
| }, | |
| "source": [ | |
| "そこで今回は埋め込みと量子アニーリングマシンの実行部分を切り離した実行方法について紹介します。\n", | |
| "\n", | |
| "第一回で示したコードは次のような手順のものでした。まずはD-Wave Ocean SDKをインストールして、いくつかの関数を読み込んでいました。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "IlK_zkhAifRE", | |
| "outputId": "a6742244-96fd-48c2-bd23-04bc845d902e" | |
| }, | |
| "source": [ | |
| "pip install dwave-ocean-sdk" | |
| ], | |
| "execution_count": null, | |
| "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: dwave-neal==0.5.7 in /usr/local/lib/python3.7/dist-packages (from dwave-ocean-sdk) (0.5.7)\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-inspector==0.2.5 in /usr/local/lib/python3.7/dist-packages (from dwave-ocean-sdk) (0.2.5)\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: dimod==0.9.13 in /usr/local/lib/python3.7/dist-packages (from dwave-ocean-sdk) (0.9.13)\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: pyqubo==1.0.10 in /usr/local/lib/python3.7/dist-packages (from dwave-ocean-sdk) (1.0.10)\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: 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: 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-tabu==0.3.1 in /usr/local/lib/python3.7/dist-packages (from dwave-ocean-sdk) (0.3.1)\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-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: minorminer==0.2.5 in /usr/local/lib/python3.7/dist-packages (from dwave-ocean-sdk) (0.2.5)\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: dwave-hybrid==0.6.1 in /usr/local/lib/python3.7/dist-packages (from dwave-ocean-sdk) (0.6.1)\n", | |
| "Requirement already satisfied: numpy>=1.16.0 in /usr/local/lib/python3.7/dist-packages (from dwave-neal==0.5.7->dwave-ocean-sdk) (1.19.5)\n", | |
| "Requirement already satisfied: networkx<3.0,>=2.4 in /usr/local/lib/python3.7/dist-packages (from penaltymodel==0.16.4->dwave-ocean-sdk) (2.5.1)\n", | |
| "Requirement already satisfied: six<2.0.0,>=1.11.0 in /usr/local/lib/python3.7/dist-packages (from penaltymodel==0.16.4->dwave-ocean-sdk) (1.15.0)\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: 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: 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: 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: homebase<2.0.0,>=1.0.0 in /usr/local/lib/python3.7/dist-packages (from dwave-system==1.4.0->dwave-ocean-sdk) (1.0.1)\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: click>=7.0 in /usr/local/lib/python3.7/dist-packages (from dwave-cloud-client==0.8.4->dwave-ocean-sdk) (8.0.0)\n", | |
| "Requirement already satisfied: plucky>=0.4.3 in /usr/local/lib/python3.7/dist-packages (from dwave-cloud-client==0.8.4->dwave-ocean-sdk) (0.4.3)\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: 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: fasteners in /usr/local/lib/python3.7/dist-packages (from minorminer==0.2.5->dwave-ocean-sdk) (0.16)\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: 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: Werkzeug>=0.15 in /usr/local/lib/python3.7/dist-packages (from Flask>=1.1.1->dwave-inspector==0.2.5->dwave-ocean-sdk) (2.0.0)\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) (2.0.0)\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: 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: 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: 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: 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: 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: 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.17.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) (2.0.0)\n" | |
| ], | |
| "name": "stdout" | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "oERV37iQnQvL" | |
| }, | |
| "source": [ | |
| "そしてD-Wave Systems社のサイトで発行されるAPI tokenと、接続先を指定するendpointを指定しましょう。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "NaV5tTpKnbNT" | |
| }, | |
| "source": [ | |
| "token = '**'\n", | |
| "endpoint = 'https://cloud.dwavesys.com/sapi/'" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "AurEJ7shmvEZ" | |
| }, | |
| "source": [ | |
| "まずは適当なQUBO行列を作りましょう。\n", | |
| "これは第一回と同様にN個の変数を持つ組合せ最適化問題を用意します。\n", | |
| "それぞれの変数は**他のすべての変数と相互作用をする全結合**の問題にしました。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "oOi_IFn_mjgr" | |
| }, | |
| "source": [ | |
| "import numpy as np\n", | |
| "\n", | |
| "N = 10\n", | |
| "QUBO = np.random.randn(N**2).reshape(N,N)" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "EK0G2tZ9WRd_" | |
| }, | |
| "source": [ | |
| "" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "dNd8gbJum_aD" | |
| }, | |
| "source": [ | |
| "まずこの問題を第一回と同様に自動的に埋め込みをして、その埋め込み結果を直ちに量子アニーリングマシンに投じる場合は以下のとおりです。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "bzRtw00tnAXG" | |
| }, | |
| "source": [ | |
| "from dwave.system import DWaveSampler, EmbeddingComposite\n", | |
| "\n", | |
| "dw_sampler = DWaveSampler(solver='Advantage_system1.1', token=token, endpoint=endpoint)\n", | |
| "sampler = EmbeddingComposite(dw_sampler)\n", | |
| "sampleset = sampler.sample_qubo(QUBO,num_reads=10)" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "RSv20F4NVJUF", | |
| "outputId": "632c787b-6eaf-4d67-8a8a-a1cc132867a7" | |
| }, | |
| "source": [ | |
| "print(sampleset.record)" | |
| ], | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "text": [ | |
| "[([1, 1, 1, 1, 0, 0, 1, 1, 1, 1], -18.98243441, 9, 0.)\n", | |
| " ([1, 1, 1, 0, 0, 0, 1, 1, 1, 1], -17.55796202, 1, 0.)]\n" | |
| ], | |
| "name": "stdout" | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "-Z-wDEfQcT7i" | |
| }, | |
| "source": [ | |
| "ここではEmbeddingComposite()を用いています。\n", | |
| "この場合はsamplerにQUBOを投入すると、\n", | |
| "投入されたQUBOに対して、**適切な埋め込みを探し**、その結果を使って**実際にQPUに組合せ最適化問題を解く**という一連の作業を行うようになります。\n", | |
| "しかしその埋め込みを毎回探すことになるので、試行錯誤をする際に**余計な時間がかかる**ことになります。そこで埋め込みの探索と、計算を分離する書き方にします。\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "cAHQ8zyZWesR" | |
| }, | |
| "source": [ | |
| "この形式ですとnumpyのarrayという行列やベクトルを利用するための形式になっています。\n", | |
| "容量節約のため、そして**明示的にどのような相互作用をしているか**を表すためにdict形式にしましょう。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "cGB_4zp6WuxG" | |
| }, | |
| "source": [ | |
| "第一回でもdict形式に直しましたが同じ手続きを実施しましょう。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "s1sJstj43bo3" | |
| }, | |
| "source": [ | |
| "Qdict = {}\n", | |
| "for i in range(N):\n", | |
| " for j in range(N):\n", | |
| " if QUBO[i][j] != 0.0:\n", | |
| " Qdict[(i,j)] = QUBO[i][j]" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "duSJlHPgtVWT" | |
| }, | |
| "source": [ | |
| "このQdictにさらにkeys()という打つと、\n", | |
| "**どことどこがつながっているのか**を示してくれます。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "lZ1fK3QR3qBl", | |
| "outputId": "ca2658a4-8d64-44cb-b906-4632e687047d" | |
| }, | |
| "source": [ | |
| "Qdict.keys()" | |
| ], | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "dict_keys([(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 9), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (2, 9), (3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (3, 9), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (4, 7), (4, 8), (4, 9), (5, 0), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5), (5, 6), (5, 7), (5, 8), (5, 9), (6, 0), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6), (6, 7), (6, 8), (6, 9), (7, 0), (7, 1), (7, 2), (7, 3), (7, 4), (7, 5), (7, 6), (7, 7), (7, 8), (7, 9), (8, 0), (8, 1), (8, 2), (8, 3), (8, 4), (8, 5), (8, 6), (8, 7), (8, 8), (8, 9), (9, 0), (9, 1), (9, 2), (9, 3), (9, 4), (9, 5), (9, 6), (9, 7), (9, 8), (9, 9)])" | |
| ] | |
| }, | |
| "metadata": { | |
| "tags": [] | |
| }, | |
| "execution_count": 7 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "oK4Ms5DNpfEx" | |
| }, | |
| "source": [ | |
| "これで準備完了です。D-Wave Ocean SDKに含まれるminorminerからfind_embeddingという関数を利用します。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "Ls0gtuayWJsl" | |
| }, | |
| "source": [ | |
| "from minorminer import find_embedding\n", | |
| "\n", | |
| "adj = {}\n", | |
| "for k in Qdict.keys():\n", | |
| " adj[k] = 1\n", | |
| "embedding = find_embedding(adj, dw_sampler.edgelist)" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "qbkRYHPKppvp" | |
| }, | |
| "source": [ | |
| "まずadjでは、Qdict.keys()に含まれる(i,j)のペアに1という値を入れるという作業をfor文で順々に行います。この1というのは、手があるよ、という意味です。その情報をもとにfind_embedding()という関数で埋め込みの探索をさせます。\n", | |
| "dw_sampler.edgelistで、D-Waveマシンの中にあるQPUで実装可能なペアの配置を入れて、adjと照らし合わせて埋め込みを行います。\n", | |
| "その結果を見てみると" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "hatEugWin_tA", | |
| "outputId": "3b419b7d-39f9-427d-f10d-cce6329c4c72" | |
| }, | |
| "source": [ | |
| "embedding" | |
| ], | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "{0: [3419],\n", | |
| " 1: [3404],\n", | |
| " 2: [2732],\n", | |
| " 3: [2747],\n", | |
| " 4: [2837, 3389],\n", | |
| " 5: [3299, 2702],\n", | |
| " 6: [3449, 2687],\n", | |
| " 7: [3434, 2777, 2776],\n", | |
| " 8: [2822, 3374],\n", | |
| " 9: [3284, 2717]}" | |
| ] | |
| }, | |
| "metadata": { | |
| "tags": [] | |
| }, | |
| "execution_count": 9 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "DvdyBKH4cT9q" | |
| }, | |
| "source": [ | |
| "何番目の変数は、[]内にある複数の量子ビットで担当します、ということがわかります。\n", | |
| "この量子ビットの集まりの中はチェーンという結合があり、同じ値を取るように調整されます。\n", | |
| "この埋め込みを採用したsamplerを構築するためには次のようにします。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "N2QYafjrq9MG" | |
| }, | |
| "source": [ | |
| "from dwave.system import FixedEmbeddingComposite\n", | |
| "sampler = FixedEmbeddingComposite(dw_sampler, embedding)" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "b5DO1PP73w6b" | |
| }, | |
| "source": [ | |
| "ここで利用しているのは、ある特定の埋め込み方法を利用するFixedEmbeddingComposite()という関数です。\n", | |
| "引数でdw_samplerだけでなく、embeddingというのを追加します。\n", | |
| "これで埋め込み方法を固定したsamplerが完成です。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "1aCnytJUcT_y" | |
| }, | |
| "source": [ | |
| "あとはいつも通りsamplerに問題を投入するだけです。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "PEa5XLEsrJvt", | |
| "outputId": "3debc9a5-d89b-4e9d-f538-e646a7a92637" | |
| }, | |
| "source": [ | |
| "sampleset = sampler.sample_qubo(Qdict,num_reads=10)\n", | |
| "print(sampleset.record)" | |
| ], | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "text": [ | |
| "[([1, 1, 1, 1, 0, 0, 1, 1, 1, 1], -18.98243441, 10, 0.)]\n" | |
| ], | |
| "name": "stdout" | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "--W0MkyrcUB5" | |
| }, | |
| "source": [ | |
| "この**FixedEmbeddingComposite()では同じ構造を持つQUBO行列を利用した計算を繰り返すときに便利**です。**逆にEmbeddingComposite()ですと**、何度も何度も埋め込み作業を行なってしまうために**余計な時間がかかります**。それで量子アニーリングマシンのレスポンスが遅いという感覚になるかもしれません。\n", | |
| "ご注意ください。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "-sBcq5axxlXo" | |
| }, | |
| "source": [ | |
| "ちなみに上記の方法ではfind_embedding()が様々なQUBO行列に対応して埋め込み方法を探索してくれるというものでした。\n", | |
| "\n", | |
| "一方であらかじめ決められた埋め込み方法を利用することもできます。\n", | |
| "\n", | |
| "QUBO行列の要素が全て値を持ち、一つの変数が他のすべての変数と関係づけられたような問題、\n", | |
| "それを**全結合**をする問題と呼びます。\n", | |
| "そのような場合は次のDWaveCliqueSampler()を利用すると良いでしょう。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "rju8h_wZyG-m" | |
| }, | |
| "source": [ | |
| "from dwave.system import DWaveCliqueSampler\n", | |
| "\n", | |
| "sampler = DWaveCliqueSampler(solver='Advantage_system1.1', token=token)" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "auC1qhY6y8na" | |
| }, | |
| "source": [ | |
| "この場合は埋め込み方法を改めて探す必要はなく、あらかじめ用意された埋め込み方法を適用するだけですので高速です。ちなみにCliqueというのは派閥とか仲間とかそういう意味ですが、ここでは全結合をしたグラフのことを意味します。\n", | |
| "\n", | |
| "結果を得るのはいつも通りの次のコードですね。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "90FnxnAAzRVP", | |
| "outputId": "bfbde25a-c95f-4104-9f92-507dab247b02" | |
| }, | |
| "source": [ | |
| "sampleset = sampler.sample_qubo(Qdict,num_reads=10)\n", | |
| "print(sampleset.record)" | |
| ], | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "text": [ | |
| "[([1, 1, 1, 1, 0, 0, 1, 1, 1, 1], -18.98243441, 10, 0.)]\n" | |
| ], | |
| "name": "stdout" | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "oBfLezBKxlaL" | |
| }, | |
| "source": [ | |
| "各種Samplerについては次のURLにあるドキュメント（英語）に詳しくありますので、もう少し知りたいという方はコチラにどうぞ。\n", | |
| "https://docs.ocean.dwavesys.com/projects/system/en/stable/reference/samplers.html#dwavecliquesampler\n", | |
| "\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "x6aTHd35cUEM" | |
| }, | |
| "source": [ | |
| "### チェーンブレイクの後処理（Advanced）" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "yS1ESsRxcUGn" | |
| }, | |
| "source": [ | |
| "実は上記の設定でFixedEmbeddingComposite()からさらに踏み込むことができます。\n", | |
| "埋め込みにより、1つの変数に対して複数の量子ビットを対応させることがあります。\n", | |
| "その際にそれらの**量子ビットの間はチェーンと呼ばれる結合でつながっています。\n", | |
| "このチェーンの間で、もしも量子ビットが示す答えがまちまちであった場合どうでしょう。\n", | |
| "最終的な答えは$0$にするべきでしょうか$1$にするべきでしょうか。\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "pD2bs3Jw0bdJ" | |
| }, | |
| "source": [ | |
| "**ここの話題は発展的な内容ですので、多少の簡易的な方法とは異なる手法を利用しますことをあらかじめご了承ください。**" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "u0ox51HG0k37" | |
| }, | |
| "source": [ | |
| "まず初めにQUBO行列を、D-Waveマシン専用のBQM形式に変更します。\n", | |
| "それには次の関数を利用します。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "qjcg3HL20uhL" | |
| }, | |
| "source": [ | |
| "import dimod\n", | |
| "bqm = dimod.BinaryQuadraticModel.from_numpy_matrix(QUBO)" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "FP0siDkq01Pp" | |
| }, | |
| "source": [ | |
| "ここで利用されているdimodはD-Wave Systems社が提供する様々な便利なツールが用意されたライブラリです。\n", | |
| "BinaryQuadraticModel（BQM）形式は、D-Waveマシンを利用する際のデータ形式として利用されるものです。from_numpy_matrixとありますようにQUBO行列から簡単に移行できます。\n", | |
| "\n", | |
| "QUBO行列からdict形式にしたのとほとんど同じことで、例えば以下のようにQUBO行列の対角成分（大学学部1年以上の知識。行列で左上から右下に向けて斜めに並んだ数値のこと）だけを抜き出したlinearや" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "WeiSOkSj1dEC", | |
| "outputId": "d7326f79-d365-42a5-b89f-78836e7988e2" | |
| }, | |
| "source": [ | |
| "print(bqm.linear)" | |
| ], | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "text": [ | |
| "{0: 0.17772579570569946, 1: 0.7781235870832651, 2: 0.5973630964991513, 3: 0.03239133498808222, 4: 0.47510655183858597, 5: -1.3422039290534766, 6: -1.168826935380701, 7: -0.676896646470971, 8: -1.3433108506715563, 9: -0.3179681056988881}\n" | |
| ], | |
| "name": "stdout" | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "3lHsmbKs1ilD" | |
| }, | |
| "source": [ | |
| "非対角成分（対角成分以外の数値）を示すquadraticの辞書形式などからなります。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "zo37_5dk1pdp", | |
| "outputId": "fd7992ba-fb5b-449f-e863-f9d1218e6b09" | |
| }, | |
| "source": [ | |
| "print(bqm.quadratic)" | |
| ], | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "text": [ | |
| "{(0, 1): 0.28241058530553753, (0, 2): -0.8205394756748072, (0, 3): -1.2529151380775154, (0, 4): 1.7446202238073365, (0, 5): 3.6712867436721495, (0, 6): 0.29019165748531256, (0, 7): -2.731197969489295, (0, 8): 0.16452895158113023, (0, 9): 1.481951907181526, (1, 2): -1.823091824035553, (1, 3): 1.1275200707683215, (1, 4): 0.42620245568984416, (1, 5): -1.0174094291969116, (1, 6): -0.04628367789210608, (1, 7): -1.8615524052193846, (1, 8): -0.5295831389874577, (1, 9): -1.326096265226543, (2, 3): -2.067346590951093, (2, 4): 0.17330781451074234, (2, 5): 1.9829209901725502, (2, 6): -2.063528919304073, (2, 7): -0.5966882019485572, (2, 8): -2.5393227620080747, (2, 9): 0.009627717207510572, (3, 4): 0.41094780026184785, (3, 5): 1.1084076810801313, (3, 6): 0.8232393115350934, (3, 7): -0.5785325634385088, (3, 8): 0.855612721751162, (3, 9): -0.36444153845606314, (4, 5): 0.042080702309051254, (4, 6): -0.39387708942574773, (4, 7): 0.2897283388005959, (4, 8): 1.8349436870166835, (4, 9): 1.2945285984835928, (5, 6): -0.013516901678206072, (5, 7): 1.1908159267714975, (5, 8): -2.030880272831392, (5, 9): 1.423659668879734, (6, 7): 2.8776388513426183, (6, 8): -1.9222206808316527, (6, 9): -0.07157855526912192, (7, 8): -0.5971485310865536, (7, 9): -1.3889930312039587, (8, 9): -2.392696194501537}\n" | |
| ], | |
| "name": "stdout" | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "44_NqeLS1sps" | |
| }, | |
| "source": [ | |
| "さてこの場合に埋め込みを行うために、先ほどと同様にQUBO行列の様子から、どのように手が出ているかを調べましょう。Qdictの代わりにbqm.quadraticを利用します。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "7wsEt4nu2MZd" | |
| }, | |
| "source": [ | |
| "adj = {}\n", | |
| "for k in bqm.quadratic.keys():\n", | |
| " adj[k] = 1\n", | |
| "embedding = find_embedding(adj, dw_sampler.edgelist)" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "YNx6Ym8E2i7a" | |
| }, | |
| "source": [ | |
| "埋め込み方法を得るところまで同じです。ここからFixedEmbeddingComposite()を利用せずに、\n", | |
| "次のようにします。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "4HGEyzvb1tBo" | |
| }, | |
| "source": [ | |
| "from dwave.embedding import embed_bqm\n", | |
| "\n", | |
| "bqm_embed = embed_bqm(bqm, embedding, dw_sampler.adjacency)" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "R4YPkpuB2wSa" | |
| }, | |
| "source": [ | |
| "ここでembed_bqm()という関数を利用しました。\n", | |
| "これは埋め込みをすることでチェーンを作ると、一つの変数に関わる量子ビットが多くなるため、\n", | |
| "QUBO行列の内容を適切に調整する必要があります。\n", | |
| "その調整を済ませた新しいQUBOを作る関数です。\n", | |
| "この新しいQUBOはそのままD-Waveマシンに載るように設計されています。\n", | |
| "\n", | |
| "なのでそのままdw_samplerに投じることができます。\n", | |
| "これまではdw_samplerからFixedEmbeddingComposite()などを経る必要がありましたが、\n", | |
| "直接dw_sampler()に投じます。\n", | |
| "この際、**bqm形式を利用するので、sample_quboではなくsampleである**ことにご注意ください。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "lIxhgOgsxhv6" | |
| }, | |
| "source": [ | |
| "sampleset_embed = dw_sampler.sample(bqm_embed,num_reads=10)" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "mm865zro6HVW" | |
| }, | |
| "source": [ | |
| "結果を取り出すためには、チェーンの後処理方法を選ぶ必要があります。\n", | |
| "できるだけエネルギーの低い結果を取り出す（新しく作られたQUBO行列において最小値をとる結果）場合はminimize_energyと言います。\n", | |
| "その場合は下記の通り、" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "nyl4piOc6xD6" | |
| }, | |
| "source": [ | |
| "from dwave.embedding import MinimizeEnergy\n", | |
| "minimize_energy = MinimizeEnergy(bqm, embedding)" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "a6ra2MII65eR" | |
| }, | |
| "source": [ | |
| "これであとは結果を取り出すだけです。\n", | |
| "次のようにプログラムしましょう。\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "qsvb8Y0A0H27", | |
| "outputId": "5637ac20-5eb3-4320-fc91-5d3d0f189636" | |
| }, | |
| "source": [ | |
| "from dwave.embedding import unembed_sampleset\n", | |
| "sampleset = unembed_sampleset(sampleset_embed, embedding, bqm, chain_break_method=minimize_energy)\n", | |
| "print(sampleset.record)" | |
| ], | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "text": [ | |
| "[([1, 1, 1, 1, 0, 0, 1, 1, 1, 1], -18.98243441, 1)\n", | |
| " ([0, 1, 1, 1, 0, 0, 1, 1, 1, 1], -16.57459073, 2)\n", | |
| " ([0, 1, 1, 0, 0, 0, 1, 1, 1, 1], -16.40303347, 1)\n", | |
| " ([0, 1, 1, 0, 0, 1, 1, 0, 1, 1], -15.15682338, 2)\n", | |
| " ([0, 1, 1, 0, 0, 1, 0, 1, 1, 1], -13.8013306 , 1)\n", | |
| " ([0, 1, 1, 1, 0, 0, 1, 0, 1, 1], -13.7524182 , 1)\n", | |
| " ([1, 1, 1, 1, 0, 1, 0, 1, 1, 1], -12.71446809, 1)\n", | |
| " ([0, 0, 1, 0, 0, 1, 1, 0, 1, 0], -9.84352717, 1)]\n" | |
| ], | |
| "name": "stdout" | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "ECcD2yF370n2" | |
| }, | |
| "source": [ | |
| "いつものように結果を得ることができました。ただしここでchain_break_methodというオプションでminize_energyとしていますね。これが後処理方法を決めているところということです。\n", | |
| "\n", | |
| "他にも後処理方法はありまして、majority_vote（多数決）、weighted_random（重み付けのサンプリング）、discard（棄却）です。\n", | |
| "多数決は名前の通りですが、weighted_sampleは出てきた結果の傾向から変数の値を結局どれにするのかを乱数で決めます。discardはいくつかの結果を参照して、チェーンブレイクしている結果を捨てるというものです。\n", | |
| "それぞれの後処理方法に応じて、次のように書き換えてください。" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "ElETnuRZ9L0F" | |
| }, | |
| "source": [ | |
| "majority_vote" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "hPxqu3rT7NA6" | |
| }, | |
| "source": [ | |
| "from dwave.embedding import majority_vote\n", | |
| "sampleset = unembed_sampleset(sampleset_embed, embedding, bqm, chain_break_method=minimize_energy)" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "xztTd0m59Tj0" | |
| }, | |
| "source": [ | |
| "weighted_random" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "vHufOxQo9WTd" | |
| }, | |
| "source": [ | |
| "from dwave.embedding import weighted_random\n", | |
| "sampleset = unembed_sampleset(sampleset_embed, embedding, bqm, chain_break_method=weighted_random)" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "Ab66BfwE9Tma" | |
| }, | |
| "source": [ | |
| "discard" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "IrbxD6hQ9cKZ" | |
| }, | |
| "source": [ | |
| "from dwave.embedding import discard\n", | |
| "sampleset = unembed_sampleset(sampleset_embed, embedding, bqm, chain_break_method=discard)" | |
| ], | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "RaTlx_7R9dGd" | |
| }, | |
| "source": [ | |
| "コードサンプル提供（東北大学大学院情報科学研究科・丸山尚貴）\n" | |
| ] | |
| } | |
| ] | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment