{ "cells": [ { "cell_type": "markdown", "id": "e1dea188", "metadata": {}, "source": [ "---\n", "title: \"Aqarios制約付き量子最適化ツールを使用して、最大独立集合を見つける\"\n", "description: \"反復的なウォームスタートとXYミキサーに基づくAqarios Constrained Quantum Optimizerを使用して、 IBM Quantum ハードウェア上で最大独立集合問題を解く\"\n", "---\n", "\n", "{/* cspell:ignore Aqarios QOBLIB Bucher forall */}\n", "\n", "\n", "\n", "# Aqarios制約付き量子最適化ツールを使用して、最大独立集合を見つける\n", "\n", "\n", " Qiskit Functions これらは、 IBM Quantum® Premium Plan、Flex Plan、および On-Prem （ IBM Quantum Platform API経由）プランのユーザーのみが利用できる実験的な機能です。 これらはプレビュー版の状態で、変更される可能性があります。\n", "\n", "\n", "推定実行*時間：Heron r2 プロセッサで 30 秒。 （注：これはあくまで目安です。 （実行時間は異なる場合があります。）*\n", "\n" ] }, { "cell_type": "markdown", "id": "be93797d", "metadata": { "tags": [ "version-info" ] }, "source": [ "\n" ] }, { "cell_type": "markdown", "id": "39ff36f6", "metadata": {}, "source": [ "\n", "\n", "## 背景\n", "\n", "このチュートリアルでは、 [Aqarios Constrained Quantum Optimizer](/docs/guides/aqarios-constrained-quantum-optimizer) [\\[1\\]](#references) を使用して、グラフの最大独立集合を求める方法について解説します。これは、制約付き組み合わせ最適化問題です。\n", "QOBLIB [\\[2\\]](#references) ベンチマークライブラリのインスタンスは、二値線形計画問題として定式化され、最適化アプリケーション関数に渡されます。\n", "オプティマイザは、すべての再定式化、回路合成、トランスパイル、および反復的なウォームスタートを内部で処理する（詳細については [\\[3\\]](#references) を参照）。\n", "\n", "このチュートリアルでは、以下の手順について解説します：\n", "\n", "1. [qiskit-addon-opt-mapper](https://github.com/qiskit/qiskit-addon-opt-mapper) の `OptimizationProblem` 機能を使用して、問題を線形計画問題として定式化する\n", "2. Aqarios Constrained Quantum Optimizer を使用して量子最適化を実行する\n", "3. 結果を取得して可視化する\n", "\n", "\n", "\n", "### 最大独立集合問題\n", "\n", "最大独立集合（MIS）問題は、組み合わせ最適化における基本的な課題である。\n", "形式的には、グラフ $G(V, E)$ が与えられたとき、目標は、 $V_I$ 内の任意の2つの頂点が辺で結ばれていないような、頂点の最大部分集合 $V_I \\subset V$ を見つけることである（ $\\nexists (u, v) \\in E : v \\in V_I \\wedge u \\in V_I$ 参照）。\n", "各頂点には二値決定変数 $x_i \\in \\{0, 1\\}$ が割り当てられ、各辺に対して制約 $x_u + x_v \\leq 1$ が導入される。これにより、各辺の端点のうち、選択されるのはせいぜい1つだけとなることが保証される。\n", "したがって、この問題は次のような最大化問題として定式化できる：\n", "\n", "$$\n", "\\max_{x_i} \\sum_{i \\in V} x_i \\qquad\\text{(find the largest set)}\\\\\n", "\\text{s.t.} \\quad x_u + x_v \\leq 1 \\quad \\forall (u, v) \\in E.\n", "$$\n", "\n", "MISには、幅広い実用的な応用分野があります。 無線ネットワークの計画において、独立集合とは、相互に干渉することなく、すべて同時に送信できる送信機のグループを指します。 スケジューリングにおいて、このモデルは、リソース間の2つごとの競合を考慮した上で、並行して実行可能なタスクの最大集合をモデル化しています。 計算生物学において、これはネットワーク内で互いに相互作用しないタンパク質の集合を表す。\n", "\n", "その直感的な定式化にもかかわらず、MISはNP困難であり、ノード数が数百程度のグラフであっても、特定のインスタンスについては、厳密解やヒューリスティック解の求解が困難となる [\\[2\\]](#references)。\n", "また、この問題は、量子最適化のハードウェア実装に最適な疎な制約構造を生み出すため、近未来の量子デバイスにとって魅力的なベンチマークとなっている。\n", "\n", "\n", "\n", "### Aqarios 制約付き量子オプティマイザー\n", "\n", "制約付き二値問題を量子最適化に組み込む際の標準的なアプローチは、ペナルティ項を追加することでモデルを制約なしの形式に変換するものです。つまり、各制約違反 $x_u + x_v \\leq 1$ に対して、最小化目的関数 $-\\sum_i x_i$ に $2 x_u x_v$ が加算されます。この処理は、制約付き量子最適化（Constrained Quantum Optimizer）のQiskit関数によって自動的に行われます。\n", "\n", "この標準的な変換に加え、オプティマイザは制約グラフ内の**クリークを**特定します。 「クリーク」とは、 $V_C$ において、すべてのノードのペアが辺で結ばれているノードの集合のことである。 その結果、 $\\binom{|V_C|}{2}$ のペアワイズ制約 $x_u + x_v \\leq 1 \\;\\forall (u,v) \\in E_C$ は、単一のより厳密な制約 $\\sum_{i \\in V_C} x_i \\leq 1$ に置き換えることができる。スラック変数 $y$ を導入することで、これは等式 $\\sum_i x_i + y = 1$ となり、 **XY-ミキサー**[ \\[3\\]](#references) を用いてQAOAで直接適用可能なワンホット制約の形式をとる。 これにより、探索空間が縮小され、それらの制約に対するペナルティ項を設ける必要がなくなるため、解の質が向上する。\n", "\n", "さらに、単一の隣接ノードのみに接続されている変数は「 **ペンダント**ノード」と呼ばれ、量子実行の前にアルゴリズムによって決定論的に固定されるため、有効な問題規模がさらに縮小される。\n", "\n", "制約付き量子オプティマイザーは、XYミキサー [\\[1\\]](#references) と互換性のある**反復的なウォームスタート**手法を採用しており、反復を重ねるごとに量子状態の分布を有望な解の領域へと偏らせることで、探索空間を段階的に絞り込んでいく。 これにより、 **固定角度のQAOAパラメータ**を使用できるようになり、変分パラメータ学習が不要になる。 必要な量子リソースの総量は、ウォームスタートの反復回数によってのみ決まるため、量子コストは簡単に制御できる。\n", "\n" ] }, { "cell_type": "markdown", "id": "01da2a6e", "metadata": { "lines_to_next_cell": 0 }, "source": [ "\n", "\n", "## 要件\n", "\n", "このチュートリアルを始める前に、以下の要件が満たされていることを確認してください：\n", "\n", "* Qiskit Runtime (`pip install qiskit-ibm-runtime`)\n", "* Qiskit Functions Catalog IBM クライアント (`pip install qiskit-ibm-catalog`)\n", "* Qiskit アドオン「Optimization Mapper」(`pip install qiskit-addon-opt-mapper`)\n", "* NumPy (`pip install numpy`)\n", "* Matplotlib (`pip install matplotlib`)\n", "* NetworkX (`pip install networkx`)\n", "\n", "必要に応じて、 [付録](#appendix-problem-statement-with-luna-model)のために以下をインストールする必要があります\n", "\n", "* ルナ・モデル (`pip install luna-model`)\n", "\n", "\n", "\n", "## セットアップ\n", "\n", "必要な依存関係をすべてインポートします。\n", "\n" ] }, { "cell_type": "code", "execution_count": 1, "id": "3fe5037e-e02b-40cb-bba7-7349d729df53", "metadata": {}, "outputs": [], "source": [ "import networkx as nx\n", "import urllib.request\n", "\n", "from qiskit_ibm_catalog import QiskitFunctionsCatalog\n", "\n", "from qiskit_addon_opt_mapper import OptimizationProblem\n", "from qiskit_addon_opt_mapper.applications import IndependentSet\n", "from qiskit_addon_opt_mapper.translators import to_docplex_mp" ] }, { "cell_type": "markdown", "id": "d47802c3", "metadata": {}, "source": [ "まず、 [IBM Quantum のAPIキー](http://quantum.cloud.ibm.com/) を使用して認証を行ってください。 次に、次のようにQiskit関数を選択します。 （このコードは、 [アカウントが](/docs/guides/functions-get-started#install-qiskit-functions-catalog-client)すでにローカル環境に保存されていることを前提としています。）\n", "\n" ] }, { "cell_type": "code", "execution_count": 2, "id": "2e6b3761", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[QiskitFunction(aqarios/constrained-quantum-optimizer)]" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "catalog = QiskitFunctionsCatalog(channel=\"ibm_quantum_platform\")\n", "\n", "# Verify that you have access to the function\n", "catalog.list()" ] }, { "cell_type": "code", "execution_count": 3, "id": "2b3688f0", "metadata": {}, "outputs": [], "source": [ "# Load the function\n", "optimizer = catalog.load(\"aqarios/constrained-quantum-optimizer\")" ] }, { "cell_type": "code", "execution_count": 4, "id": "bd0fd445", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[,\n", " ,\n", " ,\n", " ,\n", " ,\n", " ,\n", " ]" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Check the list of backends you have access to\n", "catalog.backends()" ] }, { "cell_type": "code", "execution_count": 5, "id": "e50deb54", "metadata": {}, "outputs": [], "source": [ "# Select the backend you want to use\n", "backend = catalog.backend(\"ibm_pittsburgh\")" ] }, { "cell_type": "markdown", "id": "5435d391", "metadata": {}, "source": [ "\n", "\n", "## ステップ1：古典的な入力を量子問題に写像する\n", "\n", "この問題は、最適化問題で一般的に用いられる形式である **LPファイルとして**定式化されており、Aqarios Constrained Quantum Optimizerへの入力として使用されます。 この機能は、LPファイルのほか、 **MPSファイル**や **Luna Model** のネイティブ表現にも対応しています。\n", "LPファイルは、以下の手順で生成されます：\n", "\n", "1. QOBLIB [\\[2\\]](#references) からグラフインスタンスを取得する\n", "2. 最適化問題をモデル化する\n", "3. LPファイルを生成する\n", "\n" ] }, { "cell_type": "markdown", "id": "c773d45b", "metadata": {}, "source": [ "\n", "\n", "### 問題のインスタンスグラフを読み込む\n", "\n", "グラフはDIMACS `.gph` 形式で指定されます。これは行単位の形式であり、で始まる行はエッジを定義 `e` し、で始まる行は問題ヘッダーを定義 `p` し、で始まる行はコメント `c` となります：\n", "\n", "```\n", "c some-comment\n", "p edge 3 2\n", "e 1 2\n", "e 2 3\n", "...\n", "```\n", "\n", "このファイル `.gph` は、以下の関数を使用してQOBLIBリポジトリからダウンロードでき、同時に NetworkX グラフとして解析されます。 なお、DIMACS形式では1を起点とするノード番号付けが採用されていますが、ここでは0を起点とするインデックスに変換されています。\n", "\n" ] }, { "cell_type": "code", "execution_count": 6, "id": "8e09bff6-0d5b-4ce5-869b-449755d7edad", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Loading graph with 186 nodes and 280 edges.\n" ] } ], "source": [ "URL_BASE = \"https://raw.githubusercontent.com/ZIB-AOPT/QOBLIB/refs/heads/main/07-independentset/instances/\"\n", "\n", "\n", "def fetch_qoblib_graph(name: str) -> nx.Graph:\n", " \"\"\"Fetch and parse the QOBLIB graph file.\"\"\"\n", " # Download the .gph file\n", " file, _ = urllib.request.urlretrieve(URL_BASE + f\"{name}.gph\")\n", " with open(file) as f:\n", " # Read the file contents\n", " lines = f.readlines()\n", "\n", " # Skip comments\n", " lines = [line for line in lines if not line.startswith(\"c\")]\n", "\n", " # Read graph definition\n", " _, _, num_nodes, num_edges = lines[0].split()\n", " print(f\"Loading graph with {num_nodes} nodes and {num_edges} edges.\")\n", "\n", " # Parse edge information\n", " # The .gph format starts node labeling with 1; we need 0 here, so we subtract one.\n", " split_edges = (line.split() for line in lines[1:])\n", " edges = [(int(u) - 1, int(v) - 1) for _, u, v in split_edges]\n", "\n", " return nx.Graph(edges)\n", "\n", "\n", "graph_name = \"es60fst02\"\n", "graph = fetch_qoblib_graph(graph_name)" ] }, { "cell_type": "markdown", "id": "2851abad", "metadata": {}, "source": [ "この例では、QOBLIBのインスタンス `es60fst02` 、すなわち186個のノードと280本のエッジを持つグラフを使用しています。 Constrained Quantum Optimizer が採用している前処理手順のおかげで、このインスタンスは 156 キュービットの Heron デバイス上で解くことができます。 このグラフは、matplotlib を使って可視化できます：\n", "\n" ] }, { "cell_type": "code", "execution_count": 7, "id": "182c672d-bab4-48e7-93c1-5e19dc9226ab", "metadata": { "lines_to_next_cell": 2 }, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Keep layout for later reuse\n", "layout = nx.spring_layout(graph, seed=1)\n", "nx.draw(graph, layout, node_size=40)" ] }, { "cell_type": "markdown", "id": "59456755", "metadata": {}, "source": [ "\n", "\n", "### 最適化問題を定式化する\n", "\n", "最大独立集合問題は、…を用いて直接定式化することができる `OptimizationProblem`。 各グラフのノードは二値の決定変数となり、各辺は、その両端点のうち最大1つだけが選択されることを保証する制約を導入する：\n", "\n" ] }, { "cell_type": "code", "execution_count": 8, "id": "d5363fd3", "metadata": { "lines_to_next_cell": 2 }, "outputs": [], "source": [ "# Create an OptimizationProblem instance\n", "mis_problem = OptimizationProblem(\"MIS\")\n", "\n", "# Add a binary variable for each node\n", "x = mis_problem.binary_var_list(graph.number_of_nodes())\n", "\n", "# Maximize the sum of all node variables\n", "mis_problem.maximize(linear={xi.name: 1 for xi in x})\n", "\n", "# Add '<= 1' constraints for each edge\n", "for u, v in graph.edges:\n", " mis_problem.linear_constraint({x[u].name: 1, x[v].name: 1}, \"<=\", 1)" ] }, { "cell_type": "markdown", "id": "7f9a8247", "metadata": {}, "source": [ "\n", "\n", "#### 近道\n", "\n", "このパッケージ [`qiskit-addon-opt-mapper`](https://qiskit.github.io/qiskit-addon-opt-mapper/) には、最大独立集合（MIS）問題用のあらかじめ実装済みのアプリケーションクラスが用意されており、これにより上記の定式化が1回の呼び出しに簡略化されます：\n", "\n" ] }, { "cell_type": "code", "execution_count": 9, "id": "01e2a4e0", "metadata": {}, "outputs": [], "source": [ "mis = IndependentSet(graph)\n", "mis_problem = mis.to_optimization_problem()" ] }, { "cell_type": "markdown", "id": "c6870d4e", "metadata": {}, "source": [ "\n", "\n", "### 問題をLPファイルに変換する\n", "\n", "このツール `OptimizationProblem` 自体はLPファイルへのエクスポートに対応していませんが、LPファイルへの[エクス](https://www.ibm.com/docs/de/icos/22.1.2?topic=docplex-python-modeling-api)ポートに対応しているDOcplexとは相互運用が可能です。 LPファイルの内容を生成するには、たった2行のコードで済みます：\n", "\n" ] }, { "cell_type": "code", "execution_count": 10, "id": "bf4d697a", "metadata": { "lines_to_next_cell": 0 }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\\ This file has been generated by DOcplex\n", "\\ ENCODING=ISO-8859-1\n", "\\Problem name: Independent set\n", "\n", "Maximize\n", " obj: x_0 + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 + x_10 + x_11\n", " + x_12 + x_13 + x_14 + x_15 + x_16 + x_17 + x_18 + x_19 + x_20 + x_21\n", " + x_22 + x_23 + x_24 + x_25 + x_26 + x_27 + x_28 + x_29 + x_30 + x_31\n", " + x_32 + x_33 + x_34 + x_35 + x_36 + x_37 + x_38 + x_39 + x_40 + x_41\n", " + x_42 + x_43 + x_44 + x_45 + x_46 + x_47 + x_48 + x_49 + x_50 + x_51\n", " + x_52 + x_53 + x_54 + x_55 + x_56 + x_57 + x_58 + x_59 + x_60 + x_61\n", " + x_62 + x_63 + x_64 + x_65 + x_66 + x_67 + x_68 + x_69 + x_70 + x_71\n", " + x_72 + x_73 + x_74 + x_75 + x_76 + x_77 + x_78 + x_79 + x_80 + x_81\n", " + x_82 + x_83 + x_84 + x_85 + x_86 + x_87 + x_88 + x_89 + x_90 + x_91\n", " + x_92 + x_93 + x_94 + x_95 + x_96 + x_97 + x_98 + x_99 + x_100 + x_101\n", " + x_102 + x_103 + x_104 + x_105 + x_106 + x_107 + x_108 + x_109 + x_110\n", " + x_111 + x_112 + x_113 + x_114 + x_115 + x_116 + x_117 + x_118 + x_119\n", " + x_120 + x_121 + x_122 + x_123 + x_124 + x_125 + x_126 + x_127 + x_128\n", " + x_129 + x_130 + x_131 + x_132 + x_133 + x_134 + x_135 + x_136 + x_137\n", " + x_138 + x_139 + x_140 + x_141 + x_142 + x_143 + x_144 + x_145 + x_146\n", " + x_147 + x_148 + x_149 + x_150 + x_151 + x_152 + x_153 + x_154 + x_155\n", " + x_156 + x_157 + x_158 + x_159 + x_160 + x_161 + x_162 + x_163 + x_164\n", " + x_165 + x_166 + x_167 + x_168 + x_169 + x_170 + x_171 + x_172 + x_173\n", " + x_174 + x_175 + x_176 + x_177 + x_178 + x_179 + x_180 + x_181 + x_182\n", " + x_183 + x_184 + x_185\n", "Subject To\n", " c0: x_60 + x_61 <= 1\n", " c1: x_14 + x_60 <= 1\n", " c2: x_7 + x_60 <= 1\n", " c3: x_7 + x_61 <= 1\n", " c4: x_61 + x_62 <= 1\n", " c5: x_61 + x_64 <= 1\n", " c6: x_14 + x_62 <= 1\n", " c7: x_62 + x_65 <= 1\n", " c8: x_23 + x_63 <= 1\n", " c9: x_53 + x_63 <= 1\n", " c10: x_39 + x_63 <= 1\n", " c11: x_7 + x_68 <= 1\n", " c12: x_18 + x_68 <= 1\n", " c13: x_68 + x_69 <= 1\n", " c14: x_68 + x_72 <= 1\n", " c15: x_64 + x_65 <= 1\n", " c16: x_64 + x_69 <= 1\n", " c17: x_65 + x_66 <= 1\n", " c18: x_51 + x_53 <= 1\n", " c19: x_69 + x_73 <= 1\n", " c20: x_66 + x_67 <= 1\n", " c21: x_42 + x_66 <= 1\n", " c22: x_67 + x_75 <= 1\n", " c23: x_43 + x_67 <= 1\n", " c24: x_42 + x_75 <= 1\n", " c25: x_75 + x_83 <= 1\n", " c26: x_12 + x_51 <= 1\n", " c27: x_18 + x_70 <= 1\n", " c28: x_18 + x_26 <= 1\n", " c29: x_70 + x_71 <= 1\n", " c30: x_70 + x_76 <= 1\n", " c31: x_71 + x_72 <= 1\n", " c32: x_72 + x_73 <= 1\n", " c33: x_72 + x_78 <= 1\n", "...\n" ] } ], "source": [ "mp_model = to_docplex_mp(mis_problem)\n", "lp_str = mp_model.export_as_lp_string()\n", "\n", "print(\"\\n\".join(lp_str.split(\"\\n\")[:60]))\n", "print(\"...\")" ] }, { "cell_type": "markdown", "id": "0c6ca33d", "metadata": {}, "source": [ "この形式は、Constrained Quantum Optimizer に固有のものです。\n", "\n", "\n", "\n", "## ステップ2：量子ハードウェアでの実行に向けて問題を最適化する\n", "\n", "回路の合成、最適化、およびトランスパイラ処理はすべて、この関数によってネイティブに処理されます。 この関数を呼び出す際の引数については、APIリファレンスの「 [入力」セクション](/docs/api/functions/aqarios-constrained-quantum-optimizer#inputs)を参照してください。\n", "\n", "アルゴリズムの動作を微調整するには、APIリファレンスの「 [オプション」リスト](/docs/api/functions/aqarios-constrained-quantum-optimizer#options-list)を参照してください。\n", "\n", "詳細については、『 [Aqarios Constrained Quantum Optimizer](/docs/guides/aqarios-constrained-quantum-optimizer) 』のガイドおよび [APIリファレンス](/docs/api/functions/aqarios-constrained-quantum-optimizer)をご覧ください。\n", "\n" ] }, { "cell_type": "markdown", "id": "241b80a6", "metadata": {}, "source": [ "\n", "\n", "## ステップ 3: `Qiskit primitives` を使用して実行する\n", "\n", "これで、LPファイルをオプティマイザーに送信できるようになりました：\n", "\n" ] }, { "cell_type": "code", "execution_count": 11, "id": "02469f27-1ea9-4fa2-8412-3e7c5ec1a59f", "metadata": { "lines_to_next_cell": 0 }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Job ID: 87ec08b9-6275-40fa-be94-340a0a916bf1\n" ] } ], "source": [ "job = optimizer.run(model=lp_str, backend_name=backend.name)\n", "\n", "print(f\"Job ID: {job.job_id}\")" ] }, { "cell_type": "markdown", "id": "4804bb92", "metadata": {}, "source": [ "アルゴリズムは内部的に、以下の段階を経て処理を進めます：\n", "\n", "1. **前処理** ：\n", " * 修正可能な変数を減らす\n", " * グループを探す\n", " * 制約の種類を特定する\n", " * ペナルティ条項に対するペナルティ要因を評価する\n", " * 制約変換を適用する\n", " * 制約を遵守させる手法を用いた回路の合成\n", " * 問題の近似とトランスパイレーション\n", "2. **並列に実行される反復ループの連鎖** ：\n", " * パラメータが固定された回路からのサンプル\n", " * 後処理を適用する\n", " * ウォームスタートの確率を評価し、新たに設定する\n", "3. **後処理** ：\n", " * 最適なサンプルを見つけ、与えられた問題について実現可能性を確認する\n", "\n" ] }, { "cell_type": "markdown", "id": "25fa45d3", "metadata": {}, "source": [ "\n", "\n", "### 進捗状況を監視する\n", "\n", "ジョブの進行状況を監視するには、「 Qiskit Functions のはじめに」ページの以下のセクションを参照してください：\n", "\n", "* [ジョブのステータスの確認](/docs/guides/functions-get-started#check-job-status)\n", "* [検索結果](/docs/guides/functions-get-started#retrieve-results)\n", "\n" ] }, { "cell_type": "code", "execution_count": 12, "id": "416cf0c0", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'QUEUED'" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Monitor the job status\n", "job.status()" ] }, { "cell_type": "markdown", "id": "8378a14f", "metadata": {}, "source": [ "\n", "\n", "## ステップ4：後処理を行い、結果を所望の従来の形式で出力する\n", "\n", "出力結果は辞書であり、そのフィールドについてはAPIリファレンスの「 [出力](/docs/api/functions/aqarios-constrained-quantum-optimizer#outputs)」 セクションに記載されています。\n", "\n", "リスト [`solutions`](/docs/api/functions/aqarios-constrained-quantum-optimizer#output-structure) に複数のエントリが含まれている場合、複数の縮退最適解が見つかったことになります。 ここでは、最初の解のみを検討する：\n", "\n" ] }, { "cell_type": "code", "execution_count": 13, "id": "fe8a3b9d", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The found maximum independent set of es60fst02 contains: 88 nodes and is feasible.\n", "{100 103 107 109 111 113 115 118 121 123 124 127 129 130 132 133 138 142 144 148 149 155 156 16 161 162 165 167 169 170 175 28 31 33 35 36 47 50 58 59 60 62 64 66 68 71 73 75 78 79 84 85 87 90 91 93 94 95 39 5 27 23 43 15 22 9 4 56 32 30 53 26 17 54 1 37 41 49 34 11 139 153 12 3 6 57 20 44}\n" ] } ], "source": [ "# Retrieve the job result\n", "result = job.result()\n", "\n", "# Retrieve the first solution from the result\n", "solution = result[\"solutions\"][0]\n", "\n", "print(f\"The found maximum independent set of {graph_name} contains:\", end=\" \")\n", "print(\n", " f\"{int(result['obj_value'])} nodes and is {'feasible' if result['feasible'] else 'infeasible'}.\"\n", ")\n", "print(\"{\" + \" \".join(k[2:] for k, v in solution.items() if v == 1) + \"}\")" ] }, { "cell_type": "markdown", "id": "e0ac4233", "metadata": {}, "source": [ "\n", "\n", "### 視覚化\n", "\n", "特定された独立集合は、グラフ上で選択したノードを強調表示することで可視化できます：\n", "\n" ] }, { "cell_type": "code", "execution_count": 14, "id": "f068c750", "metadata": { "lines_to_next_cell": 2 }, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Color all selected nodes in orange\n", "node_map = {\n", " int(k.split(\"_\")[1]): \"tab:orange\" if v else \"tab:blue\"\n", " for k, v in solution.items()\n", "}\n", "node_colors = [node_map[k] for k in graph.nodes]\n", "\n", "# Draw with the same layout used before\n", "nx.draw(graph, layout, node_size=40, node_color=node_colors)" ] }, { "cell_type": "markdown", "id": "1463b529", "metadata": {}, "source": [ "\n", "\n", "## 付録：ルナ・モデルを用いた問題定義\n", "\n", "上記の手法 `qiskit-addon-opt-mapper` に加え、Qiskit Function では、Aqarios のモデリング SDK である Luna Model [\\[4\\]](#references) を使用して作成されたモデルも利用可能です。\n", "PyPI`luna-model` パッケージをインストールしたら、次のようにインポートしてください：\n", "\n", "**セットアップ**\n", "\n" ] }, { "cell_type": "code", "execution_count": 15, "id": "299a6d7c", "metadata": {}, "outputs": [], "source": [ "from luna_model import Model, Sense\n", "import numpy as np" ] }, { "cell_type": "markdown", "id": "03a63f0d", "metadata": {}, "source": [ "その後、このグラフから、と同様にモデルが構築されます `qiskit-addon-opt-mapper`：\n", "\n" ] }, { "cell_type": "markdown", "id": "fbf74687", "metadata": {}, "source": [ "**モデルの構築：**\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "cf52944f-8908-4b4e-8e65-556fbe3b7a38", "metadata": {}, "outputs": [], "source": [ "edges = np.array(graph.edges)\n", "\n", "# Create the optimization model with a name\n", "model = Model(name=f\"MIS-{graph_name}\", sense=Sense.MAX)\n", "# Add binary variables\n", "x = model.add_variables(\"x\", graph.number_of_nodes())\n", "# Set the objective\n", "model.objective = x.sum()\n", "\n", "# Use numpy like batch generation of constraints\n", "model.add_constraints(x[edges].sum(axis=1) <= 1)\n", "\n", "input_str = model.encode_b64()\n", "\n", "# optimizer.run(model=input_str, backend_name=\"ibm_fez\")" ] }, { "cell_type": "markdown", "id": "42730c89", "metadata": {}, "source": [ "\n", "\n", "## ネクスト・ステップ\n", "\n", "\n", " * すべての機能の詳細な手順については、『 [Aqarios Constrained Quantum Optimizer』ガイド](/docs/guides/aqarios-constrained-quantum-optimizer)を参照してください。\n", " * 入力パラメータおよび出力フィールドの完全な一覧については、 [APIリファレンス](/docs/api/functions/aqarios-constrained-quantum-optimizer)をご覧ください。\n", " * 独自の制約付き二値最適化問題を用いて、アルゴリズムのオプション（`reps`, `num_parallel`, `shots`, `postprocessing`）を試行し、それらが解の品質や実行時間に与える影響を評価してください。\n", "\n", "\n", "\n", "\n", "## 参照\n", "\n", "1. IBM Quantum、『 [*Aqarios Constrained Quantum Optimizer』ガイド*](/docs/guides/aqarios-constrained-quantum-optimizer)\n", "2. Koch ら (2026)、 \\*「量子最適化ベンチマークライブラリ」 \\*[10.1038/s43588-026-00991-1](https://doi.org/10.1038/s43588-026-00991-1)\n", "3. Bucher ら (2026)、「 \\*反復ウォームスタートXYミキサーを用いた制約付き量子最適化」 \\*[10.1088/1367-2630/ae8ea2](https://doi.org/10.1088/1367-2630/ae8ea2)\n", "4. Aqarios GmbH, [*Luna モデルドキュメント*](https://docs.aqarios.com/luna-model)\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "id": "a1b8767d", "source": "© IBM Corp., 2017-2026" } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3" } }, "nbformat": 4, "nbformat_minor": 5 }