{
  "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": 3,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "id": "fVwhYb2J0p7k",
        "outputId": "752e77bd-27db-44ed-a2ac-4a746ec2b2d3",
        "collapsed": true
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Requirement already satisfied: dwave-ocean-sdk in /usr/local/lib/python3.13/dist-packages (9.4.0)\n",
            "Requirement already satisfied: dimod==0.12.22 in /usr/local/lib/python3.13/dist-packages (from dwave-ocean-sdk) (0.12.22)\n",
            "Requirement already satisfied: dwave-cloud-client==0.14.6 in /usr/local/lib/python3.13/dist-packages (from dwave-ocean-sdk) (0.14.6)\n",
            "Requirement already satisfied: dwave-gate==0.3.5 in /usr/local/lib/python3.13/dist-packages (from dwave-ocean-sdk) (0.3.5)\n",
            "Requirement already satisfied: dwave-graphs==1.0.0 in /usr/local/lib/python3.13/dist-packages (from dwave-ocean-sdk) (1.0.0)\n",
            "Requirement already satisfied: dwave-hybrid==0.6.16 in /usr/local/lib/python3.13/dist-packages (from dwave-ocean-sdk) (0.6.16)\n",
            "Requirement already satisfied: dwave-inspector==0.5.5 in /usr/local/lib/python3.13/dist-packages (from dwave-ocean-sdk) (0.5.5)\n",
            "Requirement already satisfied: dwave-networkx==0.8.19 in /usr/local/lib/python3.13/dist-packages (from dwave-ocean-sdk) (0.8.19)\n",
            "Requirement already satisfied: dwave-optimization==0.7.1 in /usr/local/lib/python3.13/dist-packages (from dwave-ocean-sdk) (0.7.1)\n",
            "Requirement already satisfied: dwave-preprocessing==0.6.11 in /usr/local/lib/python3.13/dist-packages (from dwave-ocean-sdk) (0.6.11)\n",
            "Requirement already satisfied: dwave-samplers==1.8.0 in /usr/local/lib/python3.13/dist-packages (from dwave-ocean-sdk) (1.8.0)\n",
            "Requirement already satisfied: dwave-system==1.35.0 in /usr/local/lib/python3.13/dist-packages (from dwave-ocean-sdk) (1.35.0)\n",
            "Requirement already satisfied: minorminer==0.2.22 in /usr/local/lib/python3.13/dist-packages (from dwave-ocean-sdk) (0.2.22)\n",
            "Requirement already satisfied: penaltymodel==1.3.0 in /usr/local/lib/python3.13/dist-packages (from dwave-ocean-sdk) (1.3.0)\n",
            "Requirement already satisfied: numpy>=1.17.3 in /usr/local/lib/python3.13/dist-packages (from dimod==0.12.22->dwave-ocean-sdk) (2.1.3)\n",
            "Requirement already satisfied: requests<3,>=2.25 in /usr/local/lib/python3.13/dist-packages (from requests[socks]<3,>=2.25->dwave-cloud-client==0.14.6->dwave-ocean-sdk) (2.32.4)\n",
            "Requirement already satisfied: urllib3<3,>=1.26 in /usr/local/lib/python3.13/dist-packages (from dwave-cloud-client==0.14.6->dwave-ocean-sdk) (2.5.0)\n",
            "Requirement already satisfied: pydantic<3,>=2 in /usr/local/lib/python3.13/dist-packages (from dwave-cloud-client==0.14.6->dwave-ocean-sdk) (2.13.5)\n",
            "Requirement already satisfied: homebase<2,>=1.0 in /usr/local/lib/python3.13/dist-packages (from dwave-cloud-client==0.14.6->dwave-ocean-sdk) (1.0.1)\n",
            "Requirement already satisfied: click<9,>=8.2 in /usr/local/lib/python3.13/dist-packages (from dwave-cloud-client==0.14.6->dwave-ocean-sdk) (8.5.0)\n",
            "Requirement already satisfied: python-dateutil<3,>=2.7 in /usr/local/lib/python3.13/dist-packages (from dwave-cloud-client==0.14.6->dwave-ocean-sdk) (2.9.0.post0)\n",
            "Requirement already satisfied: plucky<0.5,>=0.4.3 in /usr/local/lib/python3.13/dist-packages (from dwave-cloud-client==0.14.6->dwave-ocean-sdk) (0.4.3)\n",
            "Requirement already satisfied: diskcache<6,>=5.2.1 in /usr/local/lib/python3.13/dist-packages (from dwave-cloud-client==0.14.6->dwave-ocean-sdk) (5.6.3)\n",
            "Requirement already satisfied: packaging>=19 in /usr/local/lib/python3.13/dist-packages (from dwave-cloud-client==0.14.6->dwave-ocean-sdk) (26.3)\n",
            "Requirement already satisfied: werkzeug<4,>=3.1.0 in /usr/local/lib/python3.13/dist-packages (from dwave-cloud-client==0.14.6->dwave-ocean-sdk) (3.1.8)\n",
            "Requirement already satisfied: typing-extensions<5,>=4.5.0 in /usr/local/lib/python3.13/dist-packages (from dwave-cloud-client==0.14.6->dwave-ocean-sdk) (4.16.0)\n",
            "Requirement already satisfied: authlib<2,>=1.2 in /usr/local/lib/python3.13/dist-packages (from dwave-cloud-client==0.14.6->dwave-ocean-sdk) (1.8.0)\n",
            "Requirement already satisfied: importlib_metadata>=5.0.0 in /usr/local/lib/python3.13/dist-packages (from dwave-cloud-client==0.14.6->dwave-ocean-sdk) (9.0.1)\n",
            "Requirement already satisfied: orjson>=3.11 in /usr/local/lib/python3.13/dist-packages (from dwave-cloud-client==0.14.6->dwave-ocean-sdk) (3.12.0)\n",
            "Requirement already satisfied: http-sf>=1.2.1 in /usr/local/lib/python3.13/dist-packages (from dwave-cloud-client==0.14.6->dwave-ocean-sdk) (1.3.0)\n",
            "Requirement already satisfied: networkx<4,>=3.2 in /usr/local/lib/python3.13/dist-packages (from dwave-graphs==1.0.0->dwave-ocean-sdk) (3.6.1)\n",
            "Requirement already satisfied: Flask<4,>=2.2 in /usr/local/lib/python3.13/dist-packages (from dwave-inspector==0.5.5->dwave-ocean-sdk) (3.1.3)\n",
            "Requirement already satisfied: scipy>=1.13 in /usr/local/lib/python3.13/dist-packages (from dwave-system==1.35.0->dwave-ocean-sdk) (1.16.3)\n",
            "Requirement already satisfied: fasteners>=0.15 in /usr/local/lib/python3.13/dist-packages (from minorminer==0.2.22->dwave-ocean-sdk) (0.20)\n",
            "Requirement already satisfied: cryptography>=45.0.1 in /usr/local/lib/python3.13/dist-packages (from authlib<2,>=1.2->dwave-cloud-client==0.14.6->dwave-ocean-sdk) (50.0.1)\n",
            "Requirement already satisfied: joserfc>=1.6.1 in /usr/local/lib/python3.13/dist-packages (from authlib<2,>=1.2->dwave-cloud-client==0.14.6->dwave-ocean-sdk) (1.7.5)\n",
            "Requirement already satisfied: blinker>=1.9.0 in /usr/local/lib/python3.13/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.13/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.13/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.13/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.13/dist-packages (from importlib_metadata>=5.0.0->dwave-cloud-client==0.14.6->dwave-ocean-sdk) (4.1.0)\n",
            "Requirement already satisfied: annotated-types>=0.6.0 in /usr/local/lib/python3.13/dist-packages (from pydantic<3,>=2->dwave-cloud-client==0.14.6->dwave-ocean-sdk) (0.8.0)\n",
            "Requirement already satisfied: pydantic-core==2.46.5 in /usr/local/lib/python3.13/dist-packages (from pydantic<3,>=2->dwave-cloud-client==0.14.6->dwave-ocean-sdk) (2.46.5)\n",
            "Requirement already satisfied: typing-inspection>=0.4.2 in /usr/local/lib/python3.13/dist-packages (from pydantic<3,>=2->dwave-cloud-client==0.14.6->dwave-ocean-sdk) (0.4.4)\n",
            "Requirement already satisfied: six>=1.5 in /usr/local/lib/python3.13/dist-packages (from python-dateutil<3,>=2.7->dwave-cloud-client==0.14.6->dwave-ocean-sdk) (1.17.0)\n",
            "Requirement already satisfied: charset_normalizer<4,>=2 in /usr/local/lib/python3.13/dist-packages (from requests<3,>=2.25->requests[socks]<3,>=2.25->dwave-cloud-client==0.14.6->dwave-ocean-sdk) (3.4.9)\n",
            "Requirement already satisfied: idna<4,>=2.5 in /usr/local/lib/python3.13/dist-packages (from requests<3,>=2.25->requests[socks]<3,>=2.25->dwave-cloud-client==0.14.6->dwave-ocean-sdk) (3.19)\n",
            "Requirement already satisfied: certifi>=2017.4.17 in /usr/local/lib/python3.13/dist-packages (from requests<3,>=2.25->requests[socks]<3,>=2.25->dwave-cloud-client==0.14.6->dwave-ocean-sdk) (2026.7.22)\n",
            "Requirement already satisfied: PySocks!=1.5.7,>=1.5.6 in /usr/local/lib/python3.13/dist-packages (from requests[socks]<3,>=2.25->dwave-cloud-client==0.14.6->dwave-ocean-sdk) (1.7.1)\n",
            "Requirement already satisfied: cffi>=2.0.0 in /usr/local/lib/python3.13/dist-packages (from cryptography>=45.0.1->authlib<2,>=1.2->dwave-cloud-client==0.14.6->dwave-ocean-sdk) (2.1.1)\n",
            "Requirement already satisfied: pycparser in /usr/local/lib/python3.13/dist-packages (from cffi>=2.0.0->cryptography>=45.0.1->authlib<2,>=1.2->dwave-cloud-client==0.14.6->dwave-ocean-sdk) (3.0)\n",
            "Requirement already satisfied: pyqubo in /usr/local/lib/python3.13/dist-packages (1.5.0)\n",
            "Requirement already satisfied: numpy>=1.17.3 in /usr/local/lib/python3.13/dist-packages (from pyqubo) (2.1.3)\n",
            "Requirement already satisfied: dimod<0.13,>=0.9.14 in /usr/local/lib/python3.13/dist-packages (from pyqubo) (0.12.22)\n",
            "Requirement already satisfied: dwave-neal>=0.5.7 in /usr/local/lib/python3.13/dist-packages (from pyqubo) (0.6.0)\n",
            "Requirement already satisfied: Deprecated>=1.2.12 in /usr/local/lib/python3.13/dist-packages (from pyqubo) (1.3.1)\n",
            "Requirement already satisfied: six>=1.15.0 in /usr/local/lib/python3.13/dist-packages (from pyqubo) (1.17.0)\n",
            "Requirement already satisfied: wrapt<3,>=1.10 in /usr/local/lib/python3.13/dist-packages (from Deprecated>=1.2.12->pyqubo) (2.4.0)\n",
            "Requirement already satisfied: dwave-samplers<2.0.0,>=1.0.0 in /usr/local/lib/python3.13/dist-packages (from dwave-neal>=0.5.7->pyqubo) (1.8.0)\n",
            "Requirement already satisfied: networkx<4,>=3 in /usr/local/lib/python3.13/dist-packages (from dwave-samplers<2.0.0,>=1.0.0->dwave-neal>=0.5.7->pyqubo) (3.6.1)\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": 4,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# QUBO公式簡介\n",
        "QUBO代表「二次無約束二元最佳化(Quadratic Unconstrained Binary Optimization)」[1]。QUBO公式是表達最佳化問題的的一種標準形式（canonical form），可以透過調整一組二元變數(binary variable)來最小化一個二次(quadratic)目標函數(objective function)。QUBO公式主要形式如下：\n",
        "\n",
        "\\begin{equation}\n",
        "\\min_{x \\in \\{0,1\\}^n} f(x) \\;=\\; \\sum_{i} Q_{ii}x_i \\;+\\; \\sum_{i<j} Q_{ij}x_i x_j \\;+\\; c.\n",
        "\\end{equation}\n",
        "\n",
        "上式中$x_i$​ 為二元決策變數（其值為0 或 1），或是等義的，$x = (x_1, x_2, \\dots, x_n)^\\top \\in \\{0,1\\}^n$ 是二元決策變數向量，$Q_{ii}$是一次項係數，$Q_{ij}$​ 是二次項係數，而$c$是常數。\n",
        "\n",
        "由於$x_i$的值為0 或 1，因此$x_i=x_i^2$，所以QUBO公式也可以寫成全部為二次項的形式:\n",
        "\n",
        "\\begin{equation}\n",
        "\\min_{x \\in \\{0,1\\}^n} f(x) \\;=\\; \\sum_{i} Q_{ii}x_i^2 \\;+\\; \\sum_{i<j} Q_{ij}x_i x_j \\;+\\; c.\n",
        "\\end{equation}\n",
        "\n",
        "或是QUBO公式也可以寫成以下的矩陣形式:\n",
        "\n",
        "$$\\min_{x \\in \\{0,1\\}^n} f(x) \\;=\\;x^\\top Q x \\;+\\; c, $$\n",
        "\n",
        "\n",
        "\n",
        "其中， $x = (x_1, x_2, \\dots, x_n)^\\top \\in \\{0,1\\}^n$ 是二元決策向量；$Q$ 是一個大小為$n\\times n$的上三角係數矩陣，也就是$Q_{ij}=0$針對$i>j$，而$c$ 是常數項。\n",
        "\n",
        "\n",
        "以下更詳細的展開，令\n",
        "\n",
        "$$Q = \\begin{bmatrix}\n",
        "Q_{11} & Q_{12} & \\cdots & Q_{1n} \\\\\n",
        "Q_{21} & Q_{22} & \\cdots & Q_{2n} \\\\\n",
        "\\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
        "Q_{n1} & Q_{n2} & \\cdots & Q_{nn}\n",
        "\\end{bmatrix},\n",
        "\\quad\n",
        "x = \\begin{bmatrix}\n",
        "x_1 \\\\ x_2 \\\\ \\vdots \\\\ x_n\n",
        "\\end{bmatrix},\n",
        "$$\n",
        "則有\n",
        "\n",
        "$$x^\\top Q x \\;=\\; \\sum_{i=1}^n \\sum_{j=1}^n Q_{ij} x_i x_j.\n",
        "$$\n",
        "\n",
        "我們也可以將$Q$改為對稱矩陣（即 $Q_{ij} = Q_{ji}$），則需要常將原本的上三角矩陣係數平均分配一半到下三角矩陣係數中。具體定義為：\n",
        "$$\n",
        "Q^{\\text{sym}}_{ij} = \\begin{cases}\n",
        "Q_{ii}, & i=j, \\\\\n",
        "\\frac{1}{2}Q_{ij}, & i \\ne j,\n",
        "\\end{cases}\n",
        "$$\n",
        "\n",
        "此時可保證\n",
        "$$\n",
        "x^\\top Q^{\\text{sym}} x \\;=\\; \\sum_i Q_{ii}x_i \\;+\\; \\sum_{i<j} Q_{ij}x_i x_j.\n",
        "$$\n",
        "\n",
        "在實作時，常透過對稱化處理將 $Q$ 視為對稱矩陣。\n",
        "\n",
        "總的來說，QUBO公式具有「通用容器」特性：許多組合最佳化問題(Combinatorial Optimization Problems, COPs)，例如最大割問題(Max-Cut Problem, MCP)、旅行推銷員問題(Traveling Salesperson Problem, TSP)、圖著色問題(Graph Coloring Problem, GCP)、二次指派問題(Quadratic Assignment Problem, QAP)、0/1背包問題(0/1 Knapsack Problem, 0/1 KP)以及子集加總問題 (Subset Sum Problem, SSP)等，皆可以使用QUBO公式建模。稍後我們會說明，除了COP本身的最佳化目標之外，若COP帶有約束條件(constraint condition)，則約束條件會以懲罰項嵌入目標函數中。\n",
        "\n",
        "\n",
        "# 易辛(Ising)模型簡介\n",
        "\n",
        "易辛(Ising)模型[2]最初由德國物理學家Ernst Ising於1925年提出，作為一個研究鐵磁性（ferromagnetism）的理論模型，用來描述鐵磁材料中自旋系統的總能量（Hamiltonian）。伊辛模型使用自旋變數 $s_i \\in \\{-1,+1\\}$，其能量常寫作\n",
        "\\begin{equation}\n",
        "E(s) \\;=\\; \\sum_{i} h_i s_i \\;+\\; \\sum_{i<j} J_{ij} s_i s_j \\;+\\; \\mathrm{const},\n",
        "\\end{equation}\n",
        "其中 $h_i$ 為外場（bias），$J_{ij}$ 為耦合（coupler）。\n",
        "\n",
        "# QUBO公式與Ising模型應用\n",
        "QUBO公式與Ising模型可以精確的互相轉換，說明如下:\n",
        "\n",
        "令\n",
        "$$\n",
        "x_i \\;=\\; \\frac{1+s_i}{2} \\quad (\\;x_i \\in \\{0,1\\},\\,s_i \\in \\{-1,+1\\}\\;)\n",
        "$$\n",
        "代入QUBO公式可得Ising參數：\n",
        "\\begin{align}\n",
        "J_{ij} &= \\frac{Q_{ij}}{4} \\quad (i<j), \\\\\n",
        "h_i &= \\frac{Q_{ii}}{2} \\;+\\; \\frac{1}{4}\\sum_{j \\ne i} Q_{ij}, \\\\\n",
        "\\mathrm{const} &= c \\;+\\; \\frac{1}{2}\\sum_i Q_{ii} \\;+\\; \\frac{1}{4}\\sum_{i<j} Q_{ij}.\n",
        "\\end{align}\n",
        "反向亦成立：若已知 Ising $(h,J)$，令 $s_i=2x_i-1$ 並整理，\n",
        "\\begin{align}\n",
        "Q_{ij} &= 4J_{ij} \\quad (i<j), \\\\\n",
        "Q_{ii} &= 2h_i \\;-\\; 2\\!\\sum_{j\\ne i} J_{ij}, \\\\\n",
        "c &= \\mathrm{const} \\;+\\; \\sum_i h_i \\;+\\; \\sum_{i<j} J_{ij}.\n",
        "\\end{align}\n",
        "\n",
        "此對應確保QUBO公式能對接Ising模型，而Ising模型也能轉成QUBO公式。此形式正是量子退火機(quantum annealer)（如 D-Wave公司的Advantage [3]）、量子啟發退火機(quantum-inspired annealer)（如日本Fujitsu公司的Digital Annealer [4]與日本Hitachi公司的FPGA/CMOS退火機 [5]）、光學相干伊辛機(Coherent Ising Machine, CIM)(如史丹佛大學與日本NTT研究團隊提出的CIM [6])與許多古典啟發式最佳化演算法(如模擬退火(Simulated Annealing, SA)演算法[7]以及禁忌搜尋(Tabu Search)演算法[8]）所處理的標的。\n",
        "\n",
        "\n",
        "[1] Glover, F., Kochenberger, G., & Du, Y. (2018). A tutorial on formulating and using QUBO models. arXiv preprint arXiv:1811.11538.\n",
        "\n",
        "[2] Ising, E. (1925). Beitrag zur theorie des ferromagnetismus. Zeitschrift für Physik, 31(1), 253-258.\n",
        "\n",
        "[3] Johnson, M. W., Amin, M. H., Gildert, S., Lanting, T., Hamze, F., Dickson, N., ... & Rose, G. (2011). Quantum annealing with manufactured spins. Nature, 473(7346), 194-198.\n",
        "\n",
        "[4] Aramon, M., Rosenberg, G., Valiante, E., Miyazawa, T., Tamura, H., & Katzgraber, H. G. (2019). Physics-inspired optimization for quadratic unconstrained problems using a digital annealer. Frontiers in Physics, 7, 48.\n",
        "\n",
        "[5] Inagaki, T., Haribara, Y., Igarashi, K., Sonobe, T., Tamate, S., Honjo, T., ... & Takesue, H. (2016). A coherent Ising machine for 2000-node optimization problems. Science, 354(6312), 603-606.\n",
        "\n",
        "[6] Yamaoka, M., Yoshimura, C., Hayashi, M., Okuyama, T., Aoki, H., & Mizuno, H. (2015). A 20k-spin Ising chip to solve combinatorial optimization problems with CMOS annealing. IEEE Journal of Solid-State Circuits, 51(1), 303-309.\n",
        "\n",
        "[7] Kirkpatrick, S., Gelatt Jr, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. science, 220(4598), 671-680.\n",
        "\n",
        "[8] Glover, F. (1989). Tabu search—part I. ORSA Journal on computing, 1(3), 190-206."
      ],
      "metadata": {
        "id": "9qSa6qM5j6pp"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# PyQUBO 的源起與歷史\n",
        "\n",
        "## 起源背景\n",
        "QUBO（Quadratic Unconstrained Binary Optimization，二次無約束二元最佳化）與 Ising 模型是各種**組合最佳化問題**的通用表述方式。隨著 D-Wave 量子退火機與各種伊辛機 (Ising machines) 的出現，研究者需要一個方便的程式工具，將現實問題快速轉換為 QUBO/Ising 形式。  \n",
        "\n",
        "為此，**Recruit Communications Co., Ltd.** 的研究團隊開發了 **PyQUBO** —— 一個以 Python 實現的 **DSL（Domain Specific Language）**，能夠以數學表達式方式建構 QUBO 模型，並自動輸出可供 D-Wave Ocean SDK 或其他 BQM（Binary Quadratic Model）相容框架使用的格式。  \n",
        "\n",
        "---\n",
        "\n",
        "## 歷史沿革\n",
        "- **2019 年**：在 *Journal of the Physical Society of Japan* 發表的文章中首次介紹了 PyQUBO 的設計理念【Tanahashi et al., 2019】。該論文討論了伊辛機的應用以及對應的軟體開發工具，其中就包含 PyQUBO 的初版構想。  \n",
        "- **2021 年**：PyQUBO 的完整介紹與功能發表於 *IEEE Transactions on Computers*【Zaman, Tanahashi & Tanaka, 2021】。同時在 arXiv 發表技術報告 (arXiv:2103.01708)，詳細介紹了 Constraint、Placeholder 與 Integer 類別的設計。  \n",
        "- **GitHub 開源**：專案由 Recruit Communications Co., Ltd. 在 GitHub 公開，維護者包含 **Kotaro Tanahashi** 與 **Shu Tanaka** 等人。其後與 C++ 庫 **cimod** 整合以提升效能。  \n",
        "- **後續更新**：PyQUBO 持續維護至今，支援 Python 3.13，並保持與 D-Wave Ocean 生態系整合。\n",
        "\n",
        "---\n",
        "\n",
        "## 作者與單位\n",
        "- **主要作者**：\n",
        "  - Mashiyat Zaman  \n",
        "  - Kotaro Tanahashi  \n",
        "  - Shu Tanaka  \n",
        "\n",
        "- **所屬單位**：Recruit Communications Co., Ltd., Japan\n",
        "\n",
        "---\n",
        "\n",
        "## 設計理念\n",
        "PyQUBO 的設計目標是讓使用者以「數學表達式」描述最佳化問題，透過編譯器將其轉換為 QUBO 或 Ising 形式，並提供：\n",
        "- **Constraint**：可將約束條件嵌入 QUBO。  \n",
        "- **Placeholder**：允許在不重新編譯的情況下調整懲罰參數。  \n",
        "- **Integer**：提供整數變數的編碼支援。  \n",
        "\n",
        "這些功能使得 PyQUBO 特別適合於實驗性建模與快速原型開發。\n",
        "\n",
        "---\n",
        "\n",
        "## 參考文獻\n",
        "- Tanahashi, K., Takayanagi, S., Motohashi, T., & Tanaka, S. (2019). *Application of Ising Machines and a Software Development for Ising Machines*. Journal of the Physical Society of Japan, 88(6), 061010. https://doi.org/10.7566/JPSJ.88.061010  \n",
        "\n",
        "- Zaman, M., Tanahashi, K., & Tanaka, S. (2021). *PyQUBO: Python Library for Mapping Combinatorial Optimization Problems to QUBO Form*. IEEE Transactions on Computers, 70(8), 1201–1213. https://doi.org/10.1109/TC.2021.3065091  \n",
        "\n",
        "- GitHub Repository: https://github.com/recruit-communications/pyqubo  \n",
        "- PyQUBO Documentation: https://pyqubo.readthedocs.io/\n"
      ],
      "metadata": {
        "id": "1gx-Tyituftr"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#Subset Sum Problem 簡述\n",
        "\n",
        "Subset Sum Problem 是一個經典的 NP 完全(NP-Complete, NPC)問題。給定一組整數和一個目標值 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": null,
      "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": null,
      "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": null,
      "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": "bffd50f8-1bd3-423d-bfe3-a1bd28c5f73d"
      },
      "execution_count": null,
      "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": "17a2fd19-4359-44ff-e592-b42a4f81be97"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "best solution:  {'x0': np.int8(0), 'x1': np.int8(1), 'x2': np.int8(1), 'x3': np.int8(0)}\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",
        "\n",
        "print(total == target)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "0BbMVJTO28zN",
        "outputId": "cfb25d7d-bb69-472d-db2a-568a2c9a51fb"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "True\n"
          ]
        }
      ]
    }
  ]
}