{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "fVwhYb2J0p7k",
        "outputId": "408f6556-08eb-458b-9a8d-7274f411a005"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Collecting dwave-ocean-sdk\n",
            "  Downloading dwave_ocean_sdk-9.3.0-py3-none-any.whl.metadata (5.6 kB)\n",
            "Collecting dimod==0.12.21 (from dwave-ocean-sdk)\n",
            "  Downloading dimod-0.12.21-cp312-cp312-manylinux2014_x86_64.manylinux_2_17_x86_64.whl.metadata (4.0 kB)\n",
            "Collecting dwave-cloud-client==0.14.4 (from dwave-ocean-sdk)\n",
            "  Downloading dwave_cloud_client-0.14.4-py3-none-any.whl.metadata (5.4 kB)\n",
            "Collecting dwave-gate==0.3.5 (from dwave-ocean-sdk)\n",
            "  Downloading dwave_gate-0.3.5-cp312-cp312-manylinux2014_x86_64.manylinux_2_17_x86_64.whl.metadata (18 kB)\n",
            "Collecting dwave-hybrid==0.6.15 (from dwave-ocean-sdk)\n",
            "  Downloading dwave_hybrid-0.6.15-py3-none-any.whl.metadata (4.5 kB)\n",
            "Collecting dwave-inspector==0.5.5 (from dwave-ocean-sdk)\n",
            "  Downloading dwave_inspector-0.5.5-py3-none-any.whl.metadata (4.4 kB)\n",
            "Collecting dwave-networkx==0.8.18 (from dwave-ocean-sdk)\n",
            "  Downloading dwave_networkx-0.8.18-py3-none-any.whl.metadata (2.7 kB)\n",
            "Collecting dwave-optimization==0.6.11 (from dwave-ocean-sdk)\n",
            "  Downloading dwave_optimization-0.6.11-cp312-abi3-manylinux_2_24_x86_64.manylinux_2_28_x86_64.whl.metadata (19 kB)\n",
            "Collecting dwave-preprocessing==0.6.11 (from dwave-ocean-sdk)\n",
            "  Downloading dwave_preprocessing-0.6.11-cp312-cp312-manylinux2014_x86_64.manylinux_2_17_x86_64.whl.metadata (3.5 kB)\n",
            "Collecting dwave-samplers==1.7.0 (from dwave-ocean-sdk)\n",
            "  Downloading dwave_samplers-1.7.0-cp312-cp312-manylinux2014_x86_64.manylinux_2_17_x86_64.whl.metadata (11 kB)\n",
            "Collecting dwave-system==1.34.0 (from dwave-ocean-sdk)\n",
            "  Downloading dwave_system-1.34.0-py3-none-any.whl.metadata (3.9 kB)\n",
            "Collecting minorminer==0.2.21 (from dwave-ocean-sdk)\n",
            "  Downloading minorminer-0.2.21-cp312-cp312-manylinux_2_24_x86_64.manylinux_2_28_x86_64.whl.metadata (7.9 kB)\n",
            "Collecting penaltymodel==1.3.0 (from dwave-ocean-sdk)\n",
            "  Downloading penaltymodel-1.3.0-py3-none-any.whl.metadata (3.4 kB)\n",
            "Requirement already satisfied: numpy>=1.17.3 in /usr/local/lib/python3.12/dist-packages (from dimod==0.12.21->dwave-ocean-sdk) (2.0.2)\n",
            "Requirement already satisfied: requests<3,>=2.25 in /usr/local/lib/python3.12/dist-packages (from requests[socks]<3,>=2.25->dwave-cloud-client==0.14.4->dwave-ocean-sdk) (2.32.4)\n",
            "Requirement already satisfied: urllib3<3,>=1.26 in /usr/local/lib/python3.12/dist-packages (from dwave-cloud-client==0.14.4->dwave-ocean-sdk) (2.5.0)\n",
            "Requirement already satisfied: pydantic<3,>=2 in /usr/local/lib/python3.12/dist-packages (from dwave-cloud-client==0.14.4->dwave-ocean-sdk) (2.12.3)\n",
            "Collecting homebase<2,>=1.0 (from dwave-cloud-client==0.14.4->dwave-ocean-sdk)\n",
            "  Downloading homebase-1.0.1-py2.py3-none-any.whl.metadata (3.3 kB)\n",
            "Requirement already satisfied: click<9,>=8.2 in /usr/local/lib/python3.12/dist-packages (from dwave-cloud-client==0.14.4->dwave-ocean-sdk) (8.3.3)\n",
            "Requirement already satisfied: python-dateutil<3,>=2.7 in /usr/local/lib/python3.12/dist-packages (from dwave-cloud-client==0.14.4->dwave-ocean-sdk) (2.9.0.post0)\n",
            "Collecting plucky<0.5,>=0.4.3 (from dwave-cloud-client==0.14.4->dwave-ocean-sdk)\n",
            "  Downloading plucky-0.4.3-py2.py3-none-any.whl.metadata (4.4 kB)\n",
            "Collecting diskcache<6,>=5.2.1 (from dwave-cloud-client==0.14.4->dwave-ocean-sdk)\n",
            "  Downloading diskcache-5.6.3-py3-none-any.whl.metadata (20 kB)\n",
            "Requirement already satisfied: packaging>=19 in /usr/local/lib/python3.12/dist-packages (from dwave-cloud-client==0.14.4->dwave-ocean-sdk) (26.1)\n",
            "Requirement already satisfied: werkzeug<4,>=3.1.0 in /usr/local/lib/python3.12/dist-packages (from dwave-cloud-client==0.14.4->dwave-ocean-sdk) (3.1.8)\n",
            "Requirement already satisfied: typing-extensions<5,>=4.5.0 in /usr/local/lib/python3.12/dist-packages (from dwave-cloud-client==0.14.4->dwave-ocean-sdk) (4.15.0)\n",
            "Requirement already satisfied: authlib<2,>=1.2 in /usr/local/lib/python3.12/dist-packages (from dwave-cloud-client==0.14.4->dwave-ocean-sdk) (1.6.11)\n",
            "Requirement already satisfied: importlib_metadata>=5.0.0 in /usr/local/lib/python3.12/dist-packages (from dwave-cloud-client==0.14.4->dwave-ocean-sdk) (8.7.1)\n",
            "Requirement already satisfied: orjson>=3.11 in /usr/local/lib/python3.12/dist-packages (from dwave-cloud-client==0.14.4->dwave-ocean-sdk) (3.11.8)\n",
            "Collecting http-sf>=1.0.4 (from dwave-cloud-client==0.14.4->dwave-ocean-sdk)\n",
            "  Downloading http_sf-1.2.0-py3-none-any.whl.metadata (5.8 kB)\n",
            "Requirement already satisfied: networkx in /usr/local/lib/python3.12/dist-packages (from dwave-hybrid==0.6.15->dwave-ocean-sdk) (3.6.1)\n",
            "Requirement already satisfied: Flask<4,>=2.2 in /usr/local/lib/python3.12/dist-packages (from dwave-inspector==0.5.5->dwave-ocean-sdk) (3.1.3)\n",
            "Requirement already satisfied: scipy>=1.7.3 in /usr/local/lib/python3.12/dist-packages (from dwave-system==1.34.0->dwave-ocean-sdk) (1.16.3)\n",
            "Collecting fasteners>=0.15 (from minorminer==0.2.21->dwave-ocean-sdk)\n",
            "  Downloading fasteners-0.20-py3-none-any.whl.metadata (4.8 kB)\n",
            "Requirement already satisfied: cryptography in /usr/local/lib/python3.12/dist-packages (from authlib<2,>=1.2->dwave-cloud-client==0.14.4->dwave-ocean-sdk) (43.0.3)\n",
            "Requirement already satisfied: blinker>=1.9.0 in /usr/local/lib/python3.12/dist-packages (from Flask<4,>=2.2->dwave-inspector==0.5.5->dwave-ocean-sdk) (1.9.0)\n",
            "Requirement already satisfied: itsdangerous>=2.2.0 in /usr/local/lib/python3.12/dist-packages (from Flask<4,>=2.2->dwave-inspector==0.5.5->dwave-ocean-sdk) (2.2.0)\n",
            "Requirement already satisfied: jinja2>=3.1.2 in /usr/local/lib/python3.12/dist-packages (from Flask<4,>=2.2->dwave-inspector==0.5.5->dwave-ocean-sdk) (3.1.6)\n",
            "Requirement already satisfied: markupsafe>=2.1.1 in /usr/local/lib/python3.12/dist-packages (from Flask<4,>=2.2->dwave-inspector==0.5.5->dwave-ocean-sdk) (3.0.3)\n",
            "Requirement already satisfied: zipp>=3.20 in /usr/local/lib/python3.12/dist-packages (from importlib_metadata>=5.0.0->dwave-cloud-client==0.14.4->dwave-ocean-sdk) (3.23.1)\n",
            "Requirement already satisfied: annotated-types>=0.6.0 in /usr/local/lib/python3.12/dist-packages (from pydantic<3,>=2->dwave-cloud-client==0.14.4->dwave-ocean-sdk) (0.7.0)\n",
            "Requirement already satisfied: pydantic-core==2.41.4 in /usr/local/lib/python3.12/dist-packages (from pydantic<3,>=2->dwave-cloud-client==0.14.4->dwave-ocean-sdk) (2.41.4)\n",
            "Requirement already satisfied: typing-inspection>=0.4.2 in /usr/local/lib/python3.12/dist-packages (from pydantic<3,>=2->dwave-cloud-client==0.14.4->dwave-ocean-sdk) (0.4.2)\n",
            "Requirement already satisfied: six>=1.5 in /usr/local/lib/python3.12/dist-packages (from python-dateutil<3,>=2.7->dwave-cloud-client==0.14.4->dwave-ocean-sdk) (1.17.0)\n",
            "Requirement already satisfied: charset_normalizer<4,>=2 in /usr/local/lib/python3.12/dist-packages (from requests<3,>=2.25->requests[socks]<3,>=2.25->dwave-cloud-client==0.14.4->dwave-ocean-sdk) (3.4.7)\n",
            "Requirement already satisfied: idna<4,>=2.5 in /usr/local/lib/python3.12/dist-packages (from requests<3,>=2.25->requests[socks]<3,>=2.25->dwave-cloud-client==0.14.4->dwave-ocean-sdk) (3.13)\n",
            "Requirement already satisfied: certifi>=2017.4.17 in /usr/local/lib/python3.12/dist-packages (from requests<3,>=2.25->requests[socks]<3,>=2.25->dwave-cloud-client==0.14.4->dwave-ocean-sdk) (2026.4.22)\n",
            "Requirement already satisfied: PySocks!=1.5.7,>=1.5.6 in /usr/local/lib/python3.12/dist-packages (from requests[socks]<3,>=2.25->dwave-cloud-client==0.14.4->dwave-ocean-sdk) (1.7.1)\n",
            "Requirement already satisfied: cffi>=1.12 in /usr/local/lib/python3.12/dist-packages (from cryptography->authlib<2,>=1.2->dwave-cloud-client==0.14.4->dwave-ocean-sdk) (2.0.0)\n",
            "Requirement already satisfied: pycparser in /usr/local/lib/python3.12/dist-packages (from cffi>=1.12->cryptography->authlib<2,>=1.2->dwave-cloud-client==0.14.4->dwave-ocean-sdk) (3.0)\n",
            "Downloading dwave_ocean_sdk-9.3.0-py3-none-any.whl (8.4 kB)\n",
            "Downloading dimod-0.12.21-cp312-cp312-manylinux2014_x86_64.manylinux_2_17_x86_64.whl (8.9 MB)\n",
            "\u001b[2K   \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m8.9/8.9 MB\u001b[0m \u001b[31m29.3 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hDownloading dwave_cloud_client-0.14.4-py3-none-any.whl (167 kB)\n",
            "\u001b[2K   \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m167.5/167.5 kB\u001b[0m \u001b[31m13.9 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hDownloading dwave_gate-0.3.5-cp312-cp312-manylinux2014_x86_64.manylinux_2_17_x86_64.whl (1.5 MB)\n",
            "\u001b[2K   \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m1.5/1.5 MB\u001b[0m \u001b[31m52.2 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hDownloading dwave_hybrid-0.6.15-py3-none-any.whl (78 kB)\n",
            "\u001b[2K   \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m78.5/78.5 kB\u001b[0m \u001b[31m6.5 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hDownloading dwave_inspector-0.5.5-py3-none-any.whl (30 kB)\n",
            "Downloading dwave_networkx-0.8.18-py3-none-any.whl (106 kB)\n",
            "\u001b[2K   \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m106.5/106.5 kB\u001b[0m \u001b[31m8.5 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hDownloading dwave_optimization-0.6.11-cp312-abi3-manylinux_2_24_x86_64.manylinux_2_28_x86_64.whl (14.7 MB)\n",
            "\u001b[2K   \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m14.7/14.7 MB\u001b[0m \u001b[31m44.0 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hDownloading dwave_preprocessing-0.6.11-cp312-cp312-manylinux2014_x86_64.manylinux_2_17_x86_64.whl (3.4 MB)\n",
            "\u001b[2K   \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m3.4/3.4 MB\u001b[0m \u001b[31m46.0 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hDownloading dwave_samplers-1.7.0-cp312-cp312-manylinux2014_x86_64.manylinux_2_17_x86_64.whl (8.9 MB)\n",
            "\u001b[2K   \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m8.9/8.9 MB\u001b[0m \u001b[31m56.1 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hDownloading dwave_system-1.34.0-py3-none-any.whl (119 kB)\n",
            "\u001b[2K   \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m119.1/119.1 kB\u001b[0m \u001b[31m8.1 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hDownloading minorminer-0.2.21-cp312-cp312-manylinux_2_24_x86_64.manylinux_2_28_x86_64.whl (4.0 MB)\n",
            "\u001b[2K   \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m4.0/4.0 MB\u001b[0m \u001b[31m40.2 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hDownloading penaltymodel-1.3.0-py3-none-any.whl (36 kB)\n",
            "Downloading diskcache-5.6.3-py3-none-any.whl (45 kB)\n",
            "\u001b[2K   \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m45.5/45.5 kB\u001b[0m \u001b[31m2.8 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hDownloading fasteners-0.20-py3-none-any.whl (18 kB)\n",
            "Downloading homebase-1.0.1-py2.py3-none-any.whl (11 kB)\n",
            "Downloading http_sf-1.2.0-py3-none-any.whl (20 kB)\n",
            "Downloading plucky-0.4.3-py2.py3-none-any.whl (10 kB)\n",
            "Installing collected packages: plucky, homebase, http-sf, fasteners, dwave-optimization, dwave-gate, diskcache, dimod, penaltymodel, dwave-samplers, dwave-preprocessing, dwave-networkx, minorminer, dwave-cloud-client, dwave-system, dwave-inspector, dwave-hybrid, dwave-ocean-sdk\n",
            "Successfully installed dimod-0.12.21 diskcache-5.6.3 dwave-cloud-client-0.14.4 dwave-gate-0.3.5 dwave-hybrid-0.6.15 dwave-inspector-0.5.5 dwave-networkx-0.8.18 dwave-ocean-sdk-9.3.0 dwave-optimization-0.6.11 dwave-preprocessing-0.6.11 dwave-samplers-1.7.0 dwave-system-1.34.0 fasteners-0.20 homebase-1.0.1 http-sf-1.2.0 minorminer-0.2.21 penaltymodel-1.3.0 plucky-0.4.3\n",
            "Collecting pyqubo\n",
            "  Downloading pyqubo-1.5.0-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.metadata (7.0 kB)\n",
            "Requirement already satisfied: numpy>=1.17.3 in /usr/local/lib/python3.12/dist-packages (from pyqubo) (2.0.2)\n",
            "Requirement already satisfied: dimod<0.13,>=0.9.14 in /usr/local/lib/python3.12/dist-packages (from pyqubo) (0.12.21)\n",
            "Collecting dwave-neal>=0.5.7 (from pyqubo)\n",
            "  Downloading dwave_neal-0.6.0-py3-none-any.whl.metadata (3.0 kB)\n",
            "Collecting Deprecated>=1.2.12 (from pyqubo)\n",
            "  Downloading deprecated-1.3.1-py2.py3-none-any.whl.metadata (5.9 kB)\n",
            "Requirement already satisfied: six>=1.15.0 in /usr/local/lib/python3.12/dist-packages (from pyqubo) (1.17.0)\n",
            "Requirement already satisfied: wrapt<3,>=1.10 in /usr/local/lib/python3.12/dist-packages (from Deprecated>=1.2.12->pyqubo) (2.1.2)\n",
            "Requirement already satisfied: dwave-samplers<2.0.0,>=1.0.0 in /usr/local/lib/python3.12/dist-packages (from dwave-neal>=0.5.7->pyqubo) (1.7.0)\n",
            "Requirement already satisfied: networkx>=3.0 in /usr/local/lib/python3.12/dist-packages (from dwave-samplers<2.0.0,>=1.0.0->dwave-neal>=0.5.7->pyqubo) (3.6.1)\n",
            "Downloading pyqubo-1.5.0-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (256 kB)\n",
            "\u001b[2K   \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m256.8/256.8 kB\u001b[0m \u001b[31m11.3 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hDownloading deprecated-1.3.1-py2.py3-none-any.whl (11 kB)\n",
            "Downloading dwave_neal-0.6.0-py3-none-any.whl (8.7 kB)\n",
            "Installing collected packages: Deprecated, dwave-neal, pyqubo\n",
            "Successfully installed Deprecated-1.3.1 dwave-neal-0.6.0 pyqubo-1.5.0\n"
          ]
        }
      ],
      "source": [
        "# 安裝 D-Wave 量子退火套件與 pyqubo\n",
        "!pip install dwave-ocean-sdk\n",
        "!pip install pyqubo"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "\"\"\"\n",
        "引入 Pyqubo 中的 Binary 變數類別\n",
        "更多資料：https://pyqubo.readthedocs.io/en/latest/reference/express.html?highlight=binary#pyqubo.Binary\n",
        "\"\"\"\n",
        "from pyqubo import Binary"
      ],
      "metadata": {
        "id": "bDbtmRWG1Jwa"
      },
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# QUBO 簡介\n",
        "QUBO 是一種二元優化問題的表達形式，目標是透過調整一組二元變數來最小化一個二次目標函數。QUBO 主要形式如下：\n",
        "​$f(x)=\\Sigma_i Q_{ii}x_i+\\Sigma_{i\\neq j}Q_{ij}x_i x_j$\n",
        "其中：\n",
        "$x_i$​ 為二元變數（0 或 1）。\n",
        "$Q_{ii}$ 和 $Q_{ij}$​ 是 Q 矩陣中的係數。\n",
        "\n",
        "QUBO 常應用於組合優化問題，如最大割 (Max-Cut)、旅行推銷員問題 (TSP)，以及子集和問題 (Subset Sum Problem)。"
      ],
      "metadata": {
        "id": "uWH0fKbBPJgn"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#Subset Sum Problem 簡述\n",
        "\n",
        "Subset Sum Problem 是一個經典的 NP 完全問題。給定一組整數和一個目標值 target，目標是在這些整數中找出一個子集，使其和等於 target。\n",
        "# 問題轉換\n",
        "\n",
        "假設我們有一組整數 ${A_1,A_2,…,A_n}$ 和一個目標值 target，我們希望選擇這組整數的某個子集，使其和為 target。我們可以將此問題轉換為 QUBO 的形式，具體步驟如下：\n",
        "\n",
        "## 定義二元變數：\n",
        "將每個整數 $A_i$​ 對應到一個二元變數 $x_i$​，若 $x_i=1$，表示選擇 $A_i$​ 作為子集的一部分；若 $x_i=0$，表示不選擇該數。\n",
        "\n",
        "構建 QUBO 目標函數：\n",
        "\n",
        "目標是使選擇的整數和 target 盡可能接近，即希望滿足：\n",
        "\n",
        "\n",
        "$\\Sigma_i^n A_i x_i = target$\n",
        "\n",
        "將其轉換為一個 QUBO 目標函數，可以表示為對此和與目標值 target 之間的差平方最小化：\n",
        "\n",
        "$(\\Sigma_i^n A_i x_i - target)^2 $\n",
        "\n",
        "展開並簡化：\n",
        "\n",
        "將上述目標函數展開後，我們得到一個二次項與一次項組成的函數：\n",
        "\n",
        "其中常數項對優化過程無影響，可以忽略。因此我們最小化以下目標函數：\n",
        "\n",
        "轉換成 QUBO 矩陣：\n",
        "根據展開的式子，我們可以將 QUBO 問題表示為矩陣 Q 的形式，並將其輸入到量子計算機或經典優化算法中進行求解。"
      ],
      "metadata": {
        "id": "EC2PQXN6LSPo"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# 定義子集合問題資料\n",
        "A = [1, 2, 3, 4] # 定義集合元素\n",
        "n = len(A)\n",
        "target = 5 # 定義子集和的目標\n"
      ],
      "metadata": {
        "id": "MNczbeL91bFa"
      },
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "\"\"\"\n",
        "宣告一個變數 H，H 表示 Hamiltonian 是描述系統能量的函數，我們將需要最小化的函數視為系統能量（Hamiltonian），定義目標函數。\n",
        "首先，我們需要初始化 H 變數為 0 即可。\n",
        "\"\"\"\n",
        "H = 0\n",
        "\n",
        "\"\"\"\n",
        "因為我們有 n 個元素，所以定義 n 個二元變數，xi 變數用來決定集合中的第 i 個元素是否放入子集中（如果 xi 為 1 則放入，為 0 則不放入）。\n",
        "e.g. x = [Binary(x0), Binary(x1), Binary(x2), Binary(x3)]。\n",
        "Binary 是宣告二元變數變數，讓程式知道這是二元變數，Pyqubo 就會將 H 視為一個可以轉換成 QUBO 的目標函數。\n",
        "Binary(\"x\") 是指建構一個 Label 為 \"x\" 的 Binary 變數 Object\n",
        "\"\"\"\n",
        "x = [Binary('x'+str(i)) for i in range(n)]\n",
        "\n"
      ],
      "metadata": {
        "id": "Ymnd8iCS1mep"
      },
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "\"\"\"\n",
        "定義目標函式，\n",
        "首先，我們將計算 A[i]*x[i] 總和\n",
        "e.g. H = A[0]*x[0]+A[1]*x[1]+A[2]*x[2]+A[3]*x[3]\n",
        "\n",
        "接著我們將這個總和減去目標後平方。\n",
        "e.g. H = ((A[0]*x[0]+A[1]*x[1]+A[2]*x[2]+A[3]*x[3])-5)^2\n",
        "\n",
        "量子退火的目標是要找到若干組 x 變數的值（0 或 1）可以使得能量（H）最小。\n",
        "\"\"\"\n",
        "for i in range(len(A)): # 總和所有的 A[i] * x[i]\n",
        "  H += A[i]*x[i]\n",
        "\n",
        "H -= target # (總和 - 目標)\n",
        "H = H*H # (總和 - 目標)^2\n"
      ],
      "metadata": {
        "id": "jH2Vua7TR5pU"
      },
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "\"\"\"\n",
        "最後，我們要將目標函式編譯成 QUBO 形式。\n",
        "H.compile() 將 H 編譯成 Pyqubo 的 Model 物件，這個 Model 物件是一個用來描述目標函式的抽象物件，它具備將目標函式轉換成 qubo、ising、bqm 等形式的 Method。\n",
        "[Model 文件](https://pyqubo.readthedocs.io/en/latest/reference/model.html#pyqubo.to_qubo)\n",
        "\n",
        "model.to_qubo() 會回傳一個 tuple 為 (QUBO矩陣, 能量偏移量 offset)，QUBO 矩陣是用一個字典（dictionary）描述，格式為 {('變數j', '變數i'): Qij 的值}，另外 Qij 的值同時就代表 QUBO 中 xi*xj 項的係數。\n",
        "[to_qubo() 文件](https://pyqubo.readthedocs.io/en/latest/reference/model.html#pyqubo.to_qubo)\n",
        "註：offset 是 pyqubo 轉換為 qubo 的過程中所產生的常數項，通常可以忽略。在後續的返回的結果中得到的 energy 加上 offset 就是我們原先定義 H 的值。\n",
        "\"\"\"\n",
        "model = H.compile()\n",
        "Q, offset = model.to_qubo() # 將目標函數轉換成 QUBO 形式\n",
        "print(Q) # 印出 QUBO 矩陣"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "eOQM645_R6p1",
        "outputId": "3fca4dc3-03bc-4827-b041-799817188dd7"
      },
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "{('x2', 'x0'): 6.0, ('x3', 'x2'): 24.0, ('x3', 'x3'): -24.0, ('x2', 'x1'): 12.0, ('x3', 'x1'): 16.0, ('x3', 'x0'): 8.0, ('x2', 'x2'): -21.0, ('x0', 'x0'): -9.0, ('x1', 'x0'): 4.0, ('x1', 'x1'): -16.0}\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "from dwave.samplers import SimulatedAnnealingSampler\n",
        "sampler = SimulatedAnnealingSampler() # 宣告 Sampler\n",
        "sampleset = sampler.sample_qubo(Q, num_reads=1000) # 求解 Q，取樣 1000 次\n",
        "best_sample = sampleset.first.sample # 將能量最低的解拿出來\n",
        "print(\"best solution: \", best_sample)\n",
        "print(\"Hamiltonian: \", sampleset.first.energy+offset)"
      ],
      "metadata": {
        "id": "H2xhciho2DNY",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "facd78ea-03dc-448d-deff-7ba87cb36424"
      },
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "best solution:  {'x0': np.int8(1), 'x1': np.int8(0), 'x2': np.int8(0), 'x3': np.int8(1)}\n",
            "Hamiltonian:  0.0\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# 檢查解答是否符合要求\n",
        "total = 0\n",
        "for i in range(len(A)):\n",
        "  if best_sample[f'x{i}'] == 1:\n",
        "    total += A[i]\n",
        "print(total == target)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "0BbMVJTO28zN",
        "outputId": "27613793-0064-4296-876a-10b9a37ad00c"
      },
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "True\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Exercise (Extra 2 point): Use Annealers to solve the following subset sum problem.\n",
        "\n",
        "A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 14, 16, 19] # 定義集合元素\n",
        "\n",
        "target = 68 #定義子集和的目標\n",
        "\n",
        "已退火模擬機求解以上的子集合加總的解答:\n",
        "例如，若T=5，則顯示\"2+3=5\"或是\"1+4=5\"或是\"5=5\"；但是若無解則顯示\"無解答\"\n",
        "\n",
        "Advanced version (Extra 3 point): The subset sum problem solution with the minimum number of selected elements"
      ],
      "metadata": {
        "id": "xPVGuWmuoyrn"
      }
    }
  ]
}