{ "cells": [ { "cell_type": "markdown", "id": "e1dea188", "metadata": {}, "source": [ "---\n", "title: \"Aqarios 제약 조건 기반 양자 최적화기를 사용하여 최대 독립 집합을 찾으세요\"\n", "description: \"반복적 웜 스타팅(warm-starting)과 XY-믹서를 기반으로 하는 Aqarios Constrained Quantum Optimizer를 사용하여, IBM Quantum 하드웨어에서 최대 독립 집합(Maximum Independent Set) 문제를 해결합니다\"\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를 통해 이용) Plan 사용자만 이용할 수 있는 실험적 기능입니다. 이 기능들은 현재 미리보기 버전 상태이며, 변경될 수 있습니다.\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 제약 조건이 있는 양자 최적화기](/docs/guides/aqarios-constrained-quantum-optimizer)[ \\[1\\]](#references) 를 사용하여 그래프의 최대 독립 집합을 구하는 방법을 설명하며, 이는 제약 조건이 있는 조합 최적화 문제입니다.\n", "QOBLIB [\\[2\\]](#references) 벤치마크 라이브러리의 한 인스턴스는 이진 선형 계획 문제로 모델링되어 최적화기 응용 함수(Optimizer Application Function)로 전달됩니다.\n", "최적화기는 모든 재구성, 회로 합성, 트랜스파일링 및 반복적 웜 스타트를 내부적으로 처리합니다(자세한 내용은 [\\[3\\]](#references) 참조).\n", "\n", "이 튜토리얼에서는 다음 단계를 다룹니다:\n", "\n", "1. [qiskit-addon-opt-mapper의 ](https://github.com/qiskit/qiskit-addon-opt-mapper)`OptimizationProblem` 기능을 사용하여 문제를 선형 계획 문제로 정의하십시오\n", "2. Aqarios 제약 조건 기반 양자 최적화기를 사용하여 양자 최적화를 실행하십시오\n", "3. 결과 가져오기 및 시각화하기\n", "\n", "\n", "\n", "### 최대 독립 집합 문제\n", "\n", "최대 독립 집합(MIS) 문제는 조합 최적화 분야의 근본적인 과제이다.\n", "형식적으로, 그래프 $G(V, E)$ 가 주어졌을 때, 목표는 $V_I$ 내의 어떤 두 정점도 $\\nexists (u, v) \\in E : v \\in V_I \\wedge u \\in V_I$ 와 같이 변으로 연결되지 않는 최대의 정점 부분집합 $V_I \\subset V$ 을 찾는 것입니다.\n", "각 정점에는 이진 결정 변수 $x_i \\in \\{0, 1\\}$ 가 할당되며, 각 변에 대해 $x_u + x_v \\leq 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는 다양한 분야에서 실질적으로 활용되고 있습니다. 무선 네트워크 설계에서, 독립 집합이란 서로 간섭 없이 모두 동시에 신호를 송신할 수 있는 송신기들의 집합을 의미합니다. 스케줄링에서, 이 모델은 자원 간 쌍대 충돌이 발생하는 상황에서 동시에 실행될 수 있는 가장 큰 작업 집합을 모델링합니다. 계산 생물학에서, 이는 네트워크 내에서 서로 상호작용하지 않는 단백질 집합을 포착한다.\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", "이러한 표준 변환 외에도, 최적화기는 제약 조건 그래프에서 **클리크를** 식별합니다. 클리크(clique)란 모든 노드 쌍이 변을 공유하는 노드 집합 $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", "제약 조건이 있는 양자 최적화기(Constrained Quantum Optimizer)는 XY-믹서 [\\[1\\]](#references) 와 호환되는 **반복적 웜 스타트(warm-starting)** 접근법을 채택하며, 이는 반복 과정을 거치며 유망한 해 영역을 향해 양자 상태 분포를 편향시킴으로써 탐색 공간을 점진적으로 좁혀 나갑니다. 이를 통해 **고정 각도의 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 애드온 최적화 매퍼 (`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 제약 조건付き 양자 최적화기의 입력으로 사용됩니다. 이 기능은 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", "다음 함수를 사용하면 QOBLIB 저장소에서 해당 파일을 `.gph` 다운로드할 수 있으며, 이 함수는 파일을 분석하여 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`. 각 그래프 노드는 이진 결정 변수가 되며, 각 간선은 양 끝점 중 기껏해야 하나만 선택되도록 보장하는 제약 조건을 도입합니다:\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/) 최대 독립 집합(Maximum Independent Set) 문제를 해결하기 위해 미리 구현된 애플리케이션 클래스를 제공하며, 이를 통해 위의 문제 정형화를 단 한 번의 호출로 간소화할 수 있습니다:\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 파일 내보내기 기능을 지원하지 않지만, 해당 기능을 지원하는 [DOcplex와](https://www.ibm.com/docs/de/icos/22.1.2?topic=docplex-python-modeling-api) 상호 운용이 가능합니다. LP 파일 내용을 생성하는 데는 단 두 줄만 필요합니다:\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", "* [작업 상태 점검(O)](/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 제약 조건 기반 양자 최적화기 가이드*](/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, [*루나 모델 문서*](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 }