Aqarios 제약 양자 최적화기로 최대 독립 집합 찾기

참고

Qiskit Functions는 IBM Quantum® Premium Plan, Flex Plan, On-Prem(IBM Quantum Platform API를 통한) Plan 사용자에게만 제공되는 실험적 기능입니다. 이 기능은 프리뷰 릴리스 상태이며 변경될 수 있습니다.

사용량 추정치: Heron r2 프로세서에서 30초. (참고: 이는 추정치일 뿐이며, 실제 실행 시간은 다를 수 있습니다.)

배경

이 튜토리얼에서는 Aqarios 제약 양자 최적화기 [1]를 사용하여 그래프의 최대 독립 집합을 찾는 방법을 보여줍니다. 이는 제약이 있는 조합 최적화 문제입니다. QOBLIB [2] 벤치마크 라이브러리의 인스턴스를 이진 선형 프로그램으로 정식화하여 Optimizer Application Function에 전달합니다. 최적화기는 모든 재정식화, 회로 합성, 트랜스파일, 그리고 반복적 웜스타팅을 내부적으로 처리합니다 (자세한 내용은 [3] 참조).

이 튜토리얼은 다음 단계들을 다룹니다.

qiskit-addon-opt-mapper의 OptimizationProblem을 사용하여 문제를 선형 프로그램으로 정의합니다
Aqarios 제약 양자 최적화기를 사용하여 양자 최적화를 실행합니다
결과를 가져와 시각화해요

최대 독립 집합 문제

최대 독립 집합(Maximum Independent Set, MIS) 문제는 조합 최적화의 근본적인 과제입니다. 공식적으로, 그래프 $G(V, E)$ 가 주어졌을 때, 목표는 $V_I$ 내 어떤 두 정점도 에지로 연결되지 않도록 하는 가장 큰 정점 부분집합 $V_I \subset V$ 를 찾는 것입니다. 이는 $\nexists (u, v) \in E : v \in V_I \wedge u \in V_I$ 로 표현됩니다. 각 정점에는 이진 결정 변수 $x_i \in \{0, 1\}$ 가 할당되며, 각 에지에 대해 제약 조건 $x_u + x_v \leq 1$ 이 도입되어 각 에지의 양 끝점 중 최대 하나만 선택되도록 보장합니다. 따라서 이 문제는 다음과 같은 최대화 문제로 표현될 수 있습니다.

\max_{x_i} \sum_{i \in V} x_i \qquad\text{(가장 큰 집합 찾기)}\\ \text{s.t.} \quad x_u + x_v \leq 1 \quad \forall (u, v) \in E.

MIS는 폭넓은 실제 응용 분야를 갖고 있습니다. 무선 네트워크 계획에서, 독립 집합은 상호 간섭 없이 동시에 방송할 수 있는 송신기 그룹에 해당합니다. 스케줄링에서는, 쌍별 자원 충돌이 있는 상황에서 동시에 실행할 수 있는 최대 작업 집합을 모델링합니다. 계산 생물학에서는, 네트워크에서 서로 상호작용하지 않는 단백질 집합을 나타내요.

직관적인 정식화에도 불구하고, MIS는 NP-난해(NP-hard)이며, 노드가 수백 개에 불과한 그래프에서도 특정 인스턴스는 정확하게 또는 휴리스틱하게 풀기 어려워집니다 [2]. 이 문제는 또한 양자 최적화의 하드웨어 구현에 적합한 희소 제약 구조를 가지고 있어, 근시일 내 양자 장치를 위한 매력적인 벤치마크가 됩니다.

Aqarios 제약 양자 최적화기

제약이 있는 이진 문제를 양자 최적화에 임베딩하는 표준적인 접근법은 페널티 항을 추가하여 모델을 제약 없는 형태로 변환합니다. 위반된 각 제약 조건 $x_u + x_v \leq 1$ 은 최소화 목적함수 $-\sum_i x_i$ 에 $2 x_u x_v$ 를 기여합니다. 이는 제약 양자 최적화기 Qiskit Function에 의해 자동으로 처리됩니다.

이 표준 변환을 넘어서, 최적화기는 제약 그래프 내에서 **클리크(cliques)**를 식별합니다. 클리크는 모든 노드 쌍이 에지를 공유하는 노드 집합 $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$ 로 대체할 수 있습니다. 여유 변수(slack variable) $y$ 를 도입하면 이는 등식 $\sum_i x_i + y = 1$ 이 되며, 이는 QAOA에서 XY-믹서를 사용하여 직접 적용할 수 있는 원-핫(one-hot) 제약 조건의 형태를 취합니다 [3]. 이는 탐색 공간을 줄이고 해당 제약 조건에 대한 페널티 항의 필요성을 없애 해의 품질을 향상시킵니다.

또한, 단 하나의 이웃과만 연결된 변수는 펜던트(pendant) 노드라고 불리며, 양자 실행 전에 알고리즘에 의해 결정론적으로 고정되어 유효 문제 크기를 더욱 줄입니다.

제약 양자 최적화기는 XY-믹서와 호환되는 반복적 웜스타팅(iterative warm-starting) 접근법을 사용합니다 [1]. 이는 반복(iteration)을 거듭하며 양자 상태 분포를 유망한 해 영역 쪽으로 점진적으로 편향시켜 탐색 공간을 좁혀 나갑니다. 이를 통해 **고정 각도 QAOA 파라미터(fixed-angle QAOA parameters)**를 사용할 수 있어 변분 파라미터 훈련이 필요 없게 됩니다. 전체 양자 자원 요구량은 오직 웜스타트 반복 횟수에 의해서만 결정되므로, 양자 비용을 간단하게 제어할 수 있습니다.

요구 사항

이 튜토리얼을 시작하기 전에, 다음 요구 사항이 설치되어 있는지 확인하세요.

Qiskit Runtime (pip install qiskit-ibm-runtime)
Qiskit Functions Catalog IBM Client (pip install qiskit-ibm-catalog)
Qiskit Addon Optimization Mapper (pip install qiskit-addon-opt-mapper)
Numpy (pip install numpy)
Matplotlib (pip install matplotlib)
NetworkX (pip install networkx)

선택 사항으로, 부록을 위해서는 다음을 설치해야 합니다.

Luna Model (pip install luna-model)

설정

필요한 모든 종속성을 임포트합니다.

# Added by doQumentation — installs the packages this notebook needs if they are missing
import importlib.util

_needed = {"luna_model": "luna-model", "networkx": "networkx", "numpy": "numpy", "qiskit_addon_opt_mapper": "qiskit-addon-opt-mapper", "qiskit_ibm_catalog": "qiskit-ibm-catalog"}
_missing = [pip for module, pip in _needed.items()
            if importlib.util.find_spec(module) is None]
# One at a time, so a package that fails to install does not block the others
for _pip in _missing:
    %pip install -q {_pip}
if not _missing:
    print("\u2713 All required packages are installed")

import networkx as nx
import urllib.request

from qiskit_ibm_catalog import QiskitFunctionsCatalog

from qiskit_addon_opt_mapper import OptimizationProblem
from qiskit_addon_opt_mapper.applications import IndependentSet
from qiskit_addon_opt_mapper.translators import to_docplex_mp

먼저, IBM Quantum API 키를 사용하여 인증합니다. 그런 다음, 다음과 같이 Qiskit Function을 선택합니다. (이 코드는 이미 로컬 환경에 계정을 저장했다고 가정합니다.)

catalog = QiskitFunctionsCatalog(channel="ibm_quantum_platform")

# Verify that you have access to the function
catalog.list()

[QiskitFunction(aqarios/constrained-quantum-optimizer)]

# Load the function
optimizer = catalog.load("aqarios/constrained-quantum-optimizer")

# Check the list of backends you have access to
catalog.backends()

[<IBMBackend('ibm_pittsburgh')>,
 <IBMBackend('ibm_boston')>,
 <IBMBackend('ibm_phoenix')>,
 <IBMBackend('ibm_fez')>,
 <IBMBackend('ibm_miami')>,
 <IBMBackend('ibm_marrakesh')>,
 <IBMBackend('ibm_kingston')>]

# Select the backend you want to use
backend = catalog.backend("ibm_pittsburgh")

1단계: 고전 입력을 양자 문제로 매핑

이 문제는 최적화 문제에 흔히 쓰이는 형식이자 Aqarios 제약 양자 최적화기의 입력으로 사용되는 LP-파일로 정식화됩니다. LP-파일 외에도, 이 함수는 MPS-파일과 네이티브 Luna Model 표현도 지원합니다. LP-파일은 다음 단계를 거쳐 생성됩니다.

QOBLIB [2]에서 그래프 인스턴스를 가져옵니다
최적화 문제를 모델링합니다
LP-파일을 생성합니다

문제 인스턴스 그래프 불러오기

그래프는 DIMACS .gph 형식으로 지정됩니다. 이는 e로 시작하는 줄이 에지를 정의하고, p로 시작하는 줄이 문제 헤더를 정의하며, c로 시작하는 줄은 주석인 줄 기반 형식입니다.

c some-comment
p edge 3 2
e 1 2
e 2 3
...

.gph 파일은 다음 함수를 사용하여 QOBLIB 저장소에서 다운로드할 수 있으며, 이 함수는 파일을 NetworkX 그래프로 파싱하기도 합니다. DIMACS 형식은 1부터 시작하는 노드 라벨링을 사용하며, 여기서는 이를 0부터 시작하는 인덱싱으로 변환합니다.

URL_BASE = "https://raw.githubusercontent.com/ZIB-AOPT/QOBLIB/refs/heads/main/07-independentset/instances/"

def fetch_qoblib_graph(name: str) -> nx.Graph:
    """Fetch and parse the QOBLIB graph file."""
    # Download the .gph file
    file, _ = urllib.request.urlretrieve(URL_BASE + f"{name}.gph")
    with open(file) as f:
        # Read the file contents
        lines = f.readlines()

    # Skip comments
    lines = [line for line in lines if not line.startswith("c")]

    # Read graph definition
    _, _, num_nodes, num_edges = lines[0].split()
    print(f"Loading graph with {num_nodes} nodes and {num_edges} edges.")

    # Parse edge information
    # The .gph format starts node labeling with 1; we need 0 here, so we subtract one.
    split_edges = (line.split() for line in lines[1:])
    edges = [(int(u) - 1, int(v) - 1) for _, u, v in split_edges]

    return nx.Graph(edges)

graph_name = "es60fst02"
graph = fetch_qoblib_graph(graph_name)

Loading graph with 186 nodes and 280 edges.

이 예제에서는 QOBLIB의 es60fst02 인스턴스를 사용합니다. 이는 노드 186개, 에지 280개로 이루어진 그래프입니다. 제약 양자 최적화기가 사용하는 전처리 단계 덕분에, 이 인스턴스는 156큐비트 Heron 장치에서 풀 수 있습니다. 이 그래프는 matplotlib을 사용하여 시각화할 수 있습니다.

# Keep layout for later reuse
layout = nx.spring_layout(graph, seed=1)
nx.draw(graph, layout, node_size=40)

Output of the previous code cell

최적화 문제 구성하기

최대 독립 집합 문제는 OptimizationProblem을 사용하여 직접 정식화할 수 있습니다. 각 그래프 노드는 이진 결정 변수가 되고, 각 에지는 양 끝점 중 최대 하나만 선택되도록 보장하는 제약 조건을 도입합니다.

# Create an OptimizationProblem instance
mis_problem = OptimizationProblem("MIS")

# Add a binary variable for each node
x = mis_problem.binary_var_list(graph.number_of_nodes())

# Maximize the sum of all node variables
mis_problem.maximize(linear={xi.name: 1 for xi in x})

# Add '<= 1' constraints for each edge
for u, v in graph.edges:
    mis_problem.linear_constraint({x[u].name: 1, x[v].name: 1}, "<=", 1)

지름길

qiskit-addon-opt-mapper 패키지는 최대 독립 집합 문제를 위해 미리 구현된 애플리케이션 클래스를 제공하며, 이를 통해 위의 정식화를 단 한 번의 호출로 단순화할 수 있습니다.

mis = IndependentSet(graph)
mis_problem = mis.to_optimization_problem()

문제를 LP-파일로 변환하기

OptimizationProblem 자체는 LP-파일 내보내기를 지원하지 않지만, 이를 지원하는 DOcplex와 상호 운용됩니다. LP-파일 내용을 생성하는 데는 단 두 줄이면 충분합니다.

mp_model = to_docplex_mp(mis_problem)
lp_str = mp_model.export_as_lp_string()

print("\n".join(lp_str.split("\n")[:60]))
print("...")

\ This file has been generated by DOcplex
\ ENCODING=ISO-8859-1
\Problem name: Independent set

Maximize
 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
      + x_12 + x_13 + x_14 + x_15 + x_16 + x_17 + x_18 + x_19 + x_20 + x_21
      + x_22 + x_23 + x_24 + x_25 + x_26 + x_27 + x_28 + x_29 + x_30 + x_31
      + x_32 + x_33 + x_34 + x_35 + x_36 + x_37 + x_38 + x_39 + x_40 + x_41
      + x_42 + x_43 + x_44 + x_45 + x_46 + x_47 + x_48 + x_49 + x_50 + x_51
      + x_52 + x_53 + x_54 + x_55 + x_56 + x_57 + x_58 + x_59 + x_60 + x_61
      + x_62 + x_63 + x_64 + x_65 + x_66 + x_67 + x_68 + x_69 + x_70 + x_71
      + x_72 + x_73 + x_74 + x_75 + x_76 + x_77 + x_78 + x_79 + x_80 + x_81
      + x_82 + x_83 + x_84 + x_85 + x_86 + x_87 + x_88 + x_89 + x_90 + x_91
      + x_92 + x_93 + x_94 + x_95 + x_96 + x_97 + x_98 + x_99 + x_100 + x_101
      + x_102 + x_103 + x_104 + x_105 + x_106 + x_107 + x_108 + x_109 + x_110
      + x_111 + x_112 + x_113 + x_114 + x_115 + x_116 + x_117 + x_118 + x_119
      + x_120 + x_121 + x_122 + x_123 + x_124 + x_125 + x_126 + x_127 + x_128
      + x_129 + x_130 + x_131 + x_132 + x_133 + x_134 + x_135 + x_136 + x_137
      + x_138 + x_139 + x_140 + x_141 + x_142 + x_143 + x_144 + x_145 + x_146
      + x_147 + x_148 + x_149 + x_150 + x_151 + x_152 + x_153 + x_154 + x_155
      + x_156 + x_157 + x_158 + x_159 + x_160 + x_161 + x_162 + x_163 + x_164
      + x_165 + x_166 + x_167 + x_168 + x_169 + x_170 + x_171 + x_172 + x_173
      + x_174 + x_175 + x_176 + x_177 + x_178 + x_179 + x_180 + x_181 + x_182
      + x_183 + x_184 + x_185
Subject To
 c0: x_60 + x_61 <= 1
 c1: x_14 + x_60 <= 1
 c2: x_7 + x_60 <= 1
 c3: x_7 + x_61 <= 1
 c4: x_61 + x_62 <= 1
 c5: x_61 + x_64 <= 1
 c6: x_14 + x_62 <= 1
 c7: x_62 + x_65 <= 1
 c8: x_23 + x_63 <= 1
 c9: x_53 + x_63 <= 1
 c10: x_39 + x_63 <= 1
 c11: x_7 + x_68 <= 1
 c12: x_18 + x_68 <= 1
 c13: x_68 + x_69 <= 1
 c14: x_68 + x_72 <= 1
 c15: x_64 + x_65 <= 1
 c16: x_64 + x_69 <= 1
 c17: x_65 + x_66 <= 1
 c18: x_51 + x_53 <= 1
 c19: x_69 + x_73 <= 1
 c20: x_66 + x_67 <= 1
 c21: x_42 + x_66 <= 1
 c22: x_67 + x_75 <= 1
 c23: x_43 + x_67 <= 1
 c24: x_42 + x_75 <= 1
 c25: x_75 + x_83 <= 1
 c26: x_12 + x_51 <= 1
 c27: x_18 + x_70 <= 1
 c28: x_18 + x_26 <= 1
 c29: x_70 + x_71 <= 1
 c30: x_70 + x_76 <= 1
 c31: x_71 + x_72 <= 1
 c32: x_72 + x_73 <= 1
 c33: x_72 + x_78 <= 1
...

이 형식은 제약 양자 최적화기에 네이티브한 형식입니다.

2단계: 양자 하드웨어 실행을 위한 문제 최적화

회로 합성, 최적화, 트랜스파일은 모두 함수가 자체적으로 처리해요. 함수를 호출할 때 사용할 인자에 대해서는 API 레퍼런스의 입력 섹션을 참조하세요.

알고리즘의 동작을 세부 조정하려면, API 레퍼런스의 옵션 목록을 참조하세요. 실행 간에 회로 매핑을 재현 가능하게 하려면 seed_transpiler 옵션을 고정하세요.

더 자세한 정보는 Aqarios 제약 양자 최적화기 가이드와 API 레퍼런스를 참조하세요.

3단계: Qiskit 기본 요소(primitives)를 사용하여 실행

이제 LP-파일을 최적화기에 제출할 수 있습니다.

job = optimizer.run(problem=lp_str, backend_name=backend.name)

print(f"Job ID: {job.job_id}")

Job ID: 87ec08b9-6275-40fa-be94-340a0a916bf1

내부적으로, 알고리즘은 다음 단계들을 거쳐 진행됩니다.

Preprocessing:
- 고정 가능한 변수 줄이기
- 클리크 찾기
- 제약 조건 유형 식별하기
- 페널티 항에 대한 페널티 계수 평가하기
- 제약 조건 변환 적용하기
- 제약 조건을 강제하는 방법으로 회로 합성하기
- 문제 근사 및 트랜스파일
반복 루프의 병렬 체인:
- 고정된 파라미터로 회로에서 샘플링하기
- 후처리 적용하기
- 새로운 웜스타팅 확률 평가 및 설정하기
Postprocessing:
- 최선의 샘플을 찾고 입력 문제에 대한 실현 가능성 확인하기

진행 상황 모니터링하기

작업의 진행 상황을 모니터링하려면 Get started with Qiskit Functions 페이지의 다음 섹션을 참조하세요.

# Monitor the job status
job.status()

'QUEUED'

4단계: 후처리 및 원하는 고전 형식으로 결과 반환

결과 출력은 딕셔너리이며, 그 필드들은 API 레퍼런스의 출력 섹션에 설명되어 있습니다.

solutions 목록에 항목이 두 개 이상 포함되어 있으면, 여러 개의 축퇴된(degenerate) 최적해가 발견된 것입니다. 여기서는 변수 이름으로 접근하는 첫 번째 해만 고려합니다. 같은 해들은 solution_bitstrings에 비트스트링으로도 제공되며, 여기서 metadata.solver_info.variable_mapping이 각 변수의 문자 위치를 알려 줍니다.

# Retrieve the job result
result = job.result()

# Retrieve the first solution from the result
solution = result["solutions"][0]

print(f"The found maximum independent set of {graph_name} contains:", end=" ")
print(
    f"{int(result['objective_value'])} nodes and is {'feasible' if result['feasible'] else 'infeasible'}."
)
print("{" + " ".join(k[2:] for k, v in solution.items() if v == 1) + "}")

The found maximum independent set of es60fst02 contains: 88 nodes and is feasible.
{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}

시각화

식별된 독립 집합은 그래프에서 선택된 노드를 강조 표시하여 시각화할 수 있습니다.

# Color all selected nodes in orange
node_map = {
    int(k.split("_")[1]): "tab:orange" if v else "tab:blue"
    for k, v in solution.items()
}
node_colors = [node_map[k] for k in graph.nodes]

# Draw with the same layout used before
nx.draw(graph, layout, node_size=40, node_color=node_colors)

Output of the previous code cell

부록: Luna Model을 사용한 문제 서술

위에서 살펴본 qiskit-addon-opt-mapper 접근법 외에도, 이 Qiskit Function은 Aqarios의 모델링 SDK인 Luna Model [4]로 생성한 모델도 받아들입니다. luna-model PyPI 패키지를 설치한 후, 다음과 같이 임포트합니다.

Setup:

from luna_model import Model, Sense
import numpy as np

그런 다음 모델은 qiskit-addon-opt-mapper와 동일한 방식으로 그래프로부터 구성됩니다. 모델 구성하기:

edges = np.array(graph.edges)

# Create the optimization model with a name
model = Model(name=f"MIS-{graph_name}", sense=Sense.MAX)
# Add binary variables
x = model.add_variables("x", graph.number_of_nodes())
# Set the objective
model.objective = x.sum()

# Use numpy like batch generation of constraints
model.add_constraints(x[edges].sum(axis=1) <= 1)

input_str = model.encode_b64()

# optimizer.run(problem=input_str, backend_name="ibm_fez")

다음 단계

권장 사항

모든 함수 기능에 대한 자세한 설명은 Aqarios 제약 양자 최적화기 가이드를 참조하세요.
입력 파라미터와 출력 필드의 전체 목록은 API 레퍼런스에서 확인하세요.
여러분만의 제약이 있는 이진 최적화 문제에 알고리즘 옵션(reps, num_parallel, shots, postprocessing_level)을 적용해 보고, 해의 품질과 실행 시간에 미치는 영향을 평가해 보세요.

참고 문헌

IBM Quantum, Aqarios Constrained Quantum Optimizer Guide
Koch et al. (2026), The Quantum Optimization Benchmarking Library 10.1038/s43588-026-00991-1
Bucher et al. (2026), Constrained Quantum Optimization via Iterative Warm-Start XY-Mixers 10.1088/1367-2630/ae8ea2
Aqarios GmbH, Luna Model Docs

배경​

최대 독립 집합 문제​

Aqarios 제약 양자 최적화기​

요구 사항​

설정​

1단계: 고전 입력을 양자 문제로 매핑​

문제 인스턴스 그래프 불러오기​

최적화 문제 구성하기​

지름길​

문제를 LP-파일로 변환하기​

2단계: 양자 하드웨어 실행을 위한 문제 최적화​

3단계: Qiskit 기본 요소(primitives)를 사용하여 실행​

진행 상황 모니터링하기​

4단계: 후처리 및 원하는 고전 형식으로 결과 반환​

시각화​

부록: Luna Model을 사용한 문제 서술​

다음 단계​

참고 문헌​

배경