{ "cells": [ { "cell_type": "markdown", "id": "b6d1e3ec", "metadata": {}, "source": [ "---\n", "title: \"ParityQC の「Parity Twine Optimizer」で、市場の分断問題を解決しましょう\"\n", "description: \"Parity Twine Optimizer を使用して、マーケットスプリットの問題を解決する方法について学びましょう。\"\n", "---\n", "\n", "{/* cspell:ignore parityqc QOBLIB marketsplit independentset */}\n", "\n", "\n", "\n", "# ParityQC の「Parity Twine Optimizer」で、市場の分断問題を解決しましょう\n", "\n" ] }, { "attachments": {}, "cell_type": "markdown", "id": "a6f69b77", "metadata": {}, "source": [ "推定*実行時間：Nighthawk r2 プロセッサ上で10秒。 （注：これはあくまで目安です。 （実行時間は異なる場合があります。）*\n", "\n" ] }, { "cell_type": "markdown", "id": "21156b6f", "metadata": {}, "source": [ "\n", "\n", "## 学習成果\n", "\n", "* [QOBLIB（Quantum Optimization Benchmarking Library](https://github.com/ZIB-AOPT/QOBLIB) ）から「Market Split」問題を取得し、フォーマットを整えてください。\n", "* Parity Twine Optimizer をセットアップして使用し、マーケット・スプリットの事例を解決します。\n", "* Parity Twine Optimizer のオプションの選び方や、どのような結果が出力されるかについて学びましょう。\n", "\n" ] }, { "cell_type": "markdown", "id": "d185259f257c1618", "metadata": {}, "source": [ "\n", "\n", "## 背景\n", "\n", "このチュートリアルでは、 ParityQC の「Parity Twine Optimizer」を使用して、マーケット・スプリット問題を解く方法について解説します。\n", "\n", "この問題のインスタンスは[、QOBLIB（量子最適化ベンチマークライブラリ）](https://github.com/ZIB-AOPT/QOBLIB) から取得したものです。\n", "\n", "\n", "\n", "### 市場の分割問題\n", "\n", "マーケット・スプリット問題は、現実世界のNP困難な資源配分問題であり、量子最適化アルゴリズムのベンチマークとなっている。\n", "これは、極めて重要な物流上の課題である。すなわち、顧客や製品から成る複雑な構造を、管理しやすく、かつ均等な販売エリアに分割する方法である。\n", "\n", "目標は、 $n$ の市場を2つの均等な販売地域に分割し、各地域が $m$ 製品の総需要のちょうど半分を受け持つようにすることです。\n", "この解決策とは、製品需要を可能な限り均等に分散させるための具体的な構成であり、これにより企業は両地域でバランスが取れた物流および人員配置戦略を実施し、\n", "特定の地域での製品不足や倉庫の過剰在庫といったリスクを最小限に抑えることができる。\n", "\n", "市場や製品の数が増えるにつれて、考えられる組み合わせの数は指数関数的に増加するため、従来の網羅的探索では最適な分割を見つけることが困難になります。\n", "\n", "\n", "\n", "### 数学的定式化\n", "\n", "$A$ を、各市場における製品の需要を表す $m \\times n$ の行列とする。ここで、 $A_{ij}$ は、市場 $j$ における製品 $i$ の需要を表す。\n", "\n", "2値の割り当てベクトル $x = [x_1, x_2, \\dots, x_n]^T \\in \\{0, 1\\}^n$ は、以下のように定義される。ここで：\n", "\n", "* $x_j = 1$ 市場 $j$ を地域Aに割り当てます。\n", "* $x_j = 0$ 市場 $j$ を地域Bに割り当てます。\n", "\n", "$d = [d_1, d_2, \\dots, d_m]^T$ を各製品の総需要ベクトルとし、 $d = A \\cdot \\mathbf{1}$ として計算する。製品 $i$ の地域ごとの目標販売量は、 $\\frac{d_i}{2}$ となる。\n", "\n", "最適化または実現可能性の制約条件として、地域Aに割り当てられる総売上高は、すべての製品について、総需要の半分と完全に一致しなければならない\n", "\n", "$A x = \\frac{1}{2} A \\mathbf{1} = b.$\n", "\n", "実際には、正確な除算が可能なことはめったにないため、この問題は、制約違反の二乗和（コスト関数）を最小化するよう定式化される：\n", "\n", "$\\min_{x} \\left\\Vert{} A x - b \\right\\Vert{}^2 = \\sum_{i=1}^{m} \\left( \\sum_{j=1}^{n} A_{ij} x_j - b\\right)^2.$\n", "\n", "これを展開すると、制約なしの二次バイナリ最適化（QUBO）問題に相当する形式が得られる。\n", "\n", "解が得られた際、解ベクトル $x$ によって、市場がどの領域に割り当てられるかが決定されます。 これは、製品の需要を可能な限り均等に分散させるための構成です。\n", "\n" ] }, { "cell_type": "markdown", "id": "55b94021", "metadata": {}, "source": [ "\n", "\n", "## 要件\n", "\n", "このチュートリアルを始める前に、以下のものがインストールされていることを確認してください：\n", "\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", "\n", "また、 ParityQC のTwine Optimizer関数にアクセスするには、権限が必要です。 アクセスを希望される場合は、この[フォーム](https://parityqc.com/products/parity-twine-optimizer/free-trial)にご記入ください。\n", "\n" ] }, { "attachments": {}, "cell_type": "markdown", "id": "7db2e559", "metadata": {}, "source": [ "\n", "\n", "## セットアップ\n", "\n", "（このコードは、 [アカウントが](/docs/guides/functions-get-started#install-qiskit-functions-catalog-client)すでにローカル環境に保存されていることを前提としています。）\n", "\n", "まず、このチュートリアルに必要なすべてのパッケージをインポートします。\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "bc380c46", "metadata": {}, "outputs": [], "source": [ "import tempfile\n", "\n", "from collections.abc import Callable\n", "from pathlib import Path\n", "\n", "import numpy as np\n", "import requests\n", "\n", "from qiskit_addon_opt_mapper import OptimizationProblem\n", "from qiskit_addon_opt_mapper.converters import OptimizationProblemToQubo\n", "from qiskit_ibm_catalog import QiskitFunctionsCatalog" ] }, { "cell_type": "markdown", "id": "d59c6bf33095b413", "metadata": {}, "source": [ "Qiskit Functions カタログからParity Twine Optimizerを読み込みます：\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "805c80a1180e79fe", "metadata": {}, "outputs": [], "source": [ "catalog = QiskitFunctionsCatalog(channel=\"ibm_quantum_platform\")\n", "function = catalog.load(\"parityqc/parity-twine-optimizer\")" ] }, { "attachments": {}, "cell_type": "markdown", "id": "988ee237", "metadata": {}, "source": [ "\n", "\n", "### ステップ 1：問題を目的関数として定式化する\n", "\n", "[QOBLIB（量子最適化ベンチマークライブラリ）](https://github.com/ZIB-AOPT/QOBLIB) から、市場分割問題のインスタンスを次のように取得します。\n", "\n", "この関 `load_market_split_problem` 数は、QOBLIBから指定された問題を取得し、それをQUBO問題に変換します。\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "2a90bce6-1925-436f-a167-4fab3255f4a0", "metadata": {}, "outputs": [], "source": [ "def load_market_split_problem(instance_name: str) -> OptimizationProblem:\n", " \"\"\"Load and formulate a market split optimization problem from an QOBLIB instance.\n", "\n", " The QOBLIB library can be found here:\n", " https://github.com/ZIB-AOPT/QOBLIB.\n", "\n", " Args:\n", " instance_name: Name of the market split instance to load as specified by the .dat file\n", " in the QOBLIB repo.\n", "\n", " Returns:\n", " The output OptimizationProblem containing the loaded market split problem.\n", " \"\"\"\n", "\n", " problem_matrix, problem_vector = fetch_and_parse(\n", " instance_name, \"01-marketsplit\", parse_marketsplit_dat\n", " )\n", "\n", " # Create optimization problem\n", " optimization_problem = OptimizationProblem(instance_name)\n", "\n", " # Add binary variables (one for each market)\n", " optimization_problem.binary_var_list(problem_matrix.shape[1])\n", "\n", " # Add equality constraints (one for each product)\n", " for idx, rhs in enumerate(problem_vector):\n", " optimization_problem.linear_constraint(\n", " problem_matrix[idx, :], sense=\"==\", rhs=rhs\n", " )\n", "\n", " # Convert to QUBO with penalty parameter\n", " return OptimizationProblemToQubo(penalty=1).convert(optimization_problem)" ] }, { "cell_type": "markdown", "id": "becd6460-8eb9-4796-8a21-60d6edc56cd1", "metadata": {}, "source": [ "この関数 `load_market_split_problem` では、QOBLIBから市場分割問題のデータを取得・処理するために、以下のパーサー関数が必要です。\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "c07d1d1b-3dc1-4fd8-b7cd-b7898e974eee", "metadata": {}, "outputs": [], "source": [ "def fetch_and_parse(instance_name: str, problem: str, parse_func: Callable):\n", " \"\"\"Generic function to fetch and parse data from QOBLIB repository.\n", "\n", " Args:\n", " instance_name: Name of the instance to fetch.\n", " problem: Category of the problem (e.g., '01-marketsplit', '07-independentset').\n", " parse_func: Function used to parse the downloaded file\n", " (e.g., parse_marketsplit_dat, parse_gph_file).\n", "\n", " Returns:\n", " Result of `parse_func` - either (np.ndarray, np.ndarray) for marketsplit\n", " or nx.Graph for MIS.\n", " \"\"\"\n", " base_url = (\n", " \"https://raw.githubusercontent.com/ZIB-AOPT/QOBLIB/refs/heads/main/\"\n", " )\n", " url = (\n", " base_url\n", " + problem\n", " + \"/instances/\"\n", " + instance_name\n", " + (\".dat\" if problem == \"01-marketsplit\" else \".gph\")\n", " )\n", "\n", " try:\n", " response = requests.get(url, timeout=30)\n", " response.raise_for_status()\n", "\n", " with tempfile.NamedTemporaryFile(\n", " mode=\"w\",\n", " suffix=\".dat\" if problem == \"01-marketsplit\" else \".gph\",\n", " delete=False,\n", " encoding=\"utf-8\",\n", " ) as temp_file:\n", " temp_file.write(response.text)\n", " temp_file_path = temp_file.name\n", "\n", " try:\n", " return parse_func(temp_file_path)\n", " finally:\n", " Path(temp_file_path).unlink(missing_ok=True)\n", "\n", " except requests.RequestException as e:\n", " print(f\"Error fetching data from repository: {e}\")\n", " except (ValueError, OSError) as e:\n", " print(f\"Error processing data: {e}\")\n", " return None\n", "\n", "\n", "def parse_marketsplit_dat(filename: str) -> tuple[np.ndarray, np.ndarray]:\n", " \"\"\"Parse a market split problem from a .dat file format.\n", "\n", " Args:\n", " filename: Path to the .dat file.\n", "\n", " Returns:\n", " Tuple of (A, b) where:\n", " - A: (m, n) array of coefficients.\n", " - b: (m,) array of target values.\n", "\n", " Raises:\n", " ValueError: If file format is invalid or file is empty.\n", " \"\"\"\n", " with Path(filename).open(encoding=\"utf-8\") as f:\n", " lines = [\n", " line.strip()\n", " for line in f\n", " if line.strip() and not line.startswith(\"#\")\n", " ]\n", "\n", " if not lines:\n", " raise ValueError(\"Empty or invalid .dat file\")\n", "\n", " # First line: m n (number of products and markets)\n", " try:\n", " m, n = map(int, lines[0].split())\n", " except (ValueError, IndexError) as e:\n", " raise ValueError(\n", " \"Invalid file format: first line must contain 'm n' integers\"\n", " ) from e\n", "\n", " if len(lines) < m + 1:\n", " raise ValueError(\n", " f\"File contains {len(lines)} lines but expected {m + 1} lines\"\n", " )\n", "\n", " # Next m lines: each row of A followed by corresponding element of b\n", " mat_a = []\n", " vec_b = []\n", "\n", " for i in range(1, m + 1):\n", " try:\n", " values = list(map(int, lines[i].split()))\n", " except ValueError as e:\n", " raise ValueError(f\"Invalid integer values in line {i + 1}\") from e\n", "\n", " if len(values) != n + 1:\n", " raise ValueError(\n", " f\"Line {i + 1} contains {len(values)} values but expected {n + 1}\"\n", " )\n", "\n", " mat_a.append(values[:-1]) # First n values: product sales per market\n", " vec_b.append(values[-1]) # Last value: target sales for this product\n", "\n", " return np.array(mat_a), np.array(vec_b)" ] }, { "cell_type": "markdown", "id": "9811ef6c-717e-4033-963d-3fd85790be23", "metadata": {}, "source": [ "定義が完了すると、これを使用してライブラリから特定の問題インスタンスを読み込む `load_marketsplit_problem` ことができます：\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "287f6c52-9b2a-46b7-994d-7005bd4ab1c6", "metadata": {}, "outputs": [], "source": [ "ms_instance = \"ms_04_050_001\"\n", "\n", "ms_problem = load_market_split_problem(ms_instance)" ] }, { "cell_type": "markdown", "id": "ac6f36e3", "metadata": {}, "source": [ "\n", "\n", "### ステップ2：JSON形式に変換する\n", "\n", "最初のステップで、この問題のQUBO形式を導き出しました。 それでは、オプティマイザ関数用にこれをJSON形式に変換しましょう：\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "fe1169b1-50a0-4edb-9db5-7c0d99ce9a68", "metadata": {}, "outputs": [], "source": [ "def optimization_problem_to_json(\n", " problem: OptimizationProblem,\n", ") -> dict[str, float]:\n", " \"\"\"\n", " Converts an unconstrained quadratic OptimizationProblem in terms of binary or spin variables\n", " to the JSON input format of the Parity Twine Qiskit Function.\n", "\n", " Args:\n", " problem: The optimization problem to convert to JSON.\n", "\n", " Returns:\n", " The JSON input format of the given problem.\n", " \"\"\"\n", " ising, constant = problem.to_ising()\n", " output = {\"()\": float(constant)}\n", " for op, coefficient in zip(ising.paulis, ising.coeffs, strict=True):\n", " # Invert the label strings because Qiskit has opposite convention\n", " qubits = tuple(\n", " num\n", " for num, pauli in enumerate(op.to_label()[::-1])\n", " if pauli == \"Z\"\n", " )\n", " output[str(qubits)] = float(coefficient)\n", " return output" ] }, { "cell_type": "markdown", "id": "9e374de6-384a-497e-bcf1-c8617c1945ec", "metadata": {}, "source": [ "「Market Split」問題のQUBOインスタンスは、次のようにJSON形式に変換されました：\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "4885df90-4d15-4bc7-8130-ec1d9ece7670", "metadata": {}, "outputs": [], "source": [ "json_ms_problem = optimization_problem_to_json(ms_problem)" ] }, { "attachments": {}, "cell_type": "markdown", "id": "b4d480b3", "metadata": {}, "source": [ "\n", "\n", "### ステップ3：Parity Twine Optimizer を使用して問題を解く\n", "\n", "市場分割問題を特定し、正しい形式に変換できたので、Twine Optimizerと選択した IBM® バックエンドを使用して解を求めることができます。\n", "\n", "この関数を実行するには、適切なバックエンドデバイスを選択してください。例えば、 `ibm_phoenix`。\n", "\n", "送信をさらに細かく制御したい `options` 場合は（任意）、以下を使用できます：\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "a3eaff0a-9c54-4ffc-b6b2-5d43c49e6a07", "metadata": {}, "outputs": [], "source": [ "options = {\n", " \"shots\": 100000,\n", " \"postprocessing_level\": 1,\n", " \"transpile_only\": False,\n", " \"job_tags\": [\"market_split\"],\n", "}" ] }, { "cell_type": "markdown", "id": "864629a2-34fe-473b-b9f1-277e0a99752d", "metadata": {}, "source": [ "ここで、 は回路の実行回数を指定する整数 `shots` であり、 は結果に後処理を適用するかどうかを決定 `postprocessing_level` し、\n", "`transpile_only`は問題が回路へのトランスパイルのみ（解かれることはない）であるかどうかを指定し、 は IBM Quantum® Platform 上でジョブを識別するために使用されるラベル `job_tags` である。\n", "\n", "オプティマイザーを実行します：\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "2c4a5ce3de728746", "metadata": {}, "outputs": [], "source": [ "function_job = function.run(\n", " problem=json_ms_problem,\n", " variable_type=\"spin\",\n", " backend_name=\"ibm_phoenix\",\n", " options=options,\n", ")\n", "print(f\"Job ID: {function_job.job_id}\")" ] }, { "cell_type": "markdown", "id": "e8e66a1efeef3757", "metadata": {}, "source": [ "ジョブのステータスを確認する：\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "be7bbe053da38198", "metadata": {}, "outputs": [], "source": [ "# Monitor the job status\n", "function_job.status()" ] }, { "cell_type": "markdown", "id": "fe4ea9784df0bcbb", "metadata": {}, "source": [ "結果を取得する：\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "9af5dddb30694451", "metadata": {}, "outputs": [], "source": [ "# Retrieve the job result if the status is DONE\n", "result = function_job.result()\n", "\n", "result" ] }, { "cell_type": "markdown", "id": "8b888ac0-c0eb-4849-be0d-4bf331707df5", "metadata": {}, "source": [ "結果は次のような形式になります：\n", "\n", "```\n", "{\n", " 'solution': {'0': 1, '1': -1, '10': 1, ... },\n", " 'objective_value': 1.0,\n", " 'solution_bitstring': '010000011101111011001001110010',\n", " 'metadata': {\n", " 'circuit_metrics': {\n", " 'depth': 309,\n", " 'gate_count': 3880,\n", " 'two_qubit_gate_depth': 116,\n", " 'two_qubit_gate_count': 899,\n", " 'num_qubits': 30,\n", " 'operations': {'sx': 1244, 'rz': 1227, 'cz': 899, 'delay': 473, 'measure': 30, 'x': 7},\n", " },\n", " 'solver_info': {\n", " 'variable_mapping': {'0': 0, '1': 1, '10': 2, ... },\n", " 'bitstring_distributions': {\n", " 'before_postprocessing': {'011101110010110111001110011000': 1, ...},\n", " 'after_postprocessing': {'011011110000110101001111011000': 1, ...}\n", " },\n", " 'best_parameters': {\n", " 'beta': [-0.18054534155552715],\n", " 'gamma': [1.4141236348317905]\n", " }\n", " },\n", " 'resource_usage': {\n", " 'RUNNING: MAPPING': {'CPU_TIME': 172.936},\n", " 'RUNNING: OPTIMIZING_FOR_HARDWARE': {'CPU_TIME': 0.272},\n", " 'RUNNING: WAITING_FOR_QPU': {'CPU_TIME': 7.798},\n", " 'RUNNING: EXECUTING_QPU': {'QPU_TIME': 30.0},\n", " 'RUNNING: POST_PROCESSING': {'CPU_TIME': 31.613},\n", " },\n", " }\n", "}\n", "```\n", "\n", "ここで、辞書 `solution` は問題で定義された量子ビットに対応し、それらの最適化されたスピン値を示す。\n", "`metadata` トランスピレーションに関する情報（2量子ビットゲートの数／深さ、使用されたゲート、アクティブな量子ビット）や、さまざまな実行時間を示しています。\n", "\n", "市場の分割問題において、解となるビット文字列は、市場を2つの独立した領域に分割するために用いられる2進割り当てベクトルを表す。 値が1の場合、その\n", "特定の市場は地域Aに割り当てられ、値が0の場合は地域Bに割り当てられます。最適解では、この組み合わせによって割り当てのバランスが取れ、つまり各製品について、両地域が会社の総需要の\n", "ちょうど半分ずつを受け取ることになります。\n", "\n" ] }, { "cell_type": "markdown", "id": "2cb5785c", "metadata": {}, "source": [ "\n", "\n", "## 次のステップ\n", "\n", "\n", " * この[フォーム](https://parityqc.com/products/parity-twine-optimizer/free-trial)に必要事項を記入し、当該機能へのアクセス権を申請してください。\n", " * このQiskit関数の [APIリファレンス](/docs/api/functions/parity-twine-optimizer)をご覧ください。\n", " * [ガイド](/docs/guides/parity-twine-optimizer)をお読みください。\n", " * 「Parity Twine Optimizer」をシェリントン・カークパトリック・モデルに適用する方法について、 [チュートリアル](/docs/tutorials/parity-twine-optimizer-sk)をお試しください。\n", " * [Drier ら（2025）による「量子アルゴリズムの接続性を考慮した合成」](https://arxiv.org/abs/2501.14020) に関するプレプリント（ ArXiv ）を参照のこと。\n", "\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 }