Aqarios 제약 조건 기반 양자 최적화기를 사용하여 최대 독립 집합을 찾으세요

예상 실행 시간: Heron r2 프로세서에서 30초. (참고: 이는 단지 추정치일 뿐입니다. (실행 시간은 다를 수 있습니다.)

배경

이 튜토리얼에서는 Aqarios 제약 조건이 있는 양자 최적화기 [1] 를 사용하여 그래프의 최대 독립 집합을 구하는 방법을 설명하며, 이는 제약 조건이 있는 조합 최적화 문제입니다. QOBLIB [2] 벤치마크 라이브러리의 한 인스턴스는 이진 선형 계획 문제로 모델링되어 최적화기 응용 함수(Optimizer Application Function)로 전달됩니다. 최적화기는 모든 재구성, 회로 합성, 트랜스파일링 및 반복적 웜 스타트를 내부적으로 처리합니다(자세한 내용은 [3] 참조).

이 튜토리얼에서는 다음 단계를 다룹니다:

1. qiskit-addon-opt-mapper의 OptimizationProblem 기능을 사용하여 문제를 선형 계획 문제로 정의하십시오
2. Aqarios 제약 조건 기반 양자 최적화기를 사용하여 양자 최적화를 실행하십시오
3. 결과 가져오기 및 시각화하기

최대 독립 집합 문제

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

MIS는 다양한 분야에서 실질적으로 활용되고 있습니다. 무선 네트워크 설계에서, 독립 집합이란 서로 간섭 없이 모두 동시에 신호를 송신할 수 있는 송신기들의 집합을 의미합니다. 스케줄링에서, 이 모델은 자원 간 쌍대 충돌이 발생하는 상황에서 동시에 실행될 수 있는 가장 큰 작업 집합을 모델링합니다. 계산 생물학에서, 이는 네트워크 내에서 서로 상호작용하지 않는 단백질 집합을 포착한다.

직관적인 공식화에도 불구하고, MIS는 NP-어려운 문제이며, 노드가 수백 개에 불과한 그래프의 경우에도 특정 인스턴스는 정확한 해를 구하거나 휴리스틱 방법으로 해결하기가 어렵다 [2]. 또한 이 문제는 양자 최적화의 하드웨어 구현에 매우 적합한 희소 제약 구조를 생성하므로, 단기적인 양자 장치에 있어 매력적인 벤치마크가 됩니다.

Aqarios 제약 조건 기반 양자 최적화기

제약 조건이 있는 이진 문제를 양자 최적화에 포함시키는 일반적인 방법은 페널티 항을 추가하여 모델을 제약 조건이 없는 형식으로 변환하는 것입니다. 즉, 위반된 각 제약 조건 $x_u + x_v \leq 1$ 은 최소화 목표 $-\sum_i x_i$ 에 대해 $2 x_u x_v$ 의 가중치를 부여합니다. 이는 제약 조건이 있는 양자 최적화기(Constrained Quantum Optimizer) Qiskit 함수에 의해 자동으로 처리됩니다.

이러한 표준 변환 외에도, 최적화기는 제약 조건 그래프에서 클리크를 식별합니다. 클리크(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] 를 사용하여 QAOA에서 직접 적용할 수 있는 원-핫 제약 조건의 형태를 띠게 된다. 이를 통해 탐색 공간을 줄이고 해당 제약 조건에 대한 페널티 항을 적용할 필요가 없어지므로, 해의 품질이 향상됩니다.

또한, 단 하나의 인접 노드에만 연결된 변수들은 ‘펜던트 노드’라고 불리며, 양자 실행 전에 알고리즘에 의해 결정론적으로 고정되므로, 이로 인해 유효 문제 규모가 더욱 줄어듭니다.

제약 조건이 있는 양자 최적화기(Constrained Quantum Optimizer)는 XY-믹서 [1] 와 호환되는 반복적 웜 스타트(warm-starting) 접근법을 채택하며, 이는 반복 과정을 거치며 유망한 해 영역을 향해 양자 상태 분포를 편향시킴으로써 탐색 공간을 점진적으로 좁혀 나갑니다. 이를 통해 고정 각도의 QAOA 매개변수를 사용할 수 있게 되어, 변분 매개변수 학습의 필요성이 사라집니다. 필요한 총 양자 자원량은 전적으로 웜 스타트 반복 횟수에 의해 결정되므로, 양자 비용을 쉽게 제어할 수 있습니다.

요구사항

이 튜토리얼을 시작하기 전에 다음 필수 구성 요소가 설치되어 있는지 확인하십시오

• Qiskit Runtime (pip install qiskit-ibm-runtime)
• Qiskit Functions Catalog IBM 클라이언트 (pip install qiskit-ibm-catalog)
• Qiskit 애드온 최적화 매퍼 (pip install qiskit-addon-opt-mapper)
• Numpy (pip install numpy)
• Matplotlib (pip install matplotlib)
• NetworkX (pip install networkx)

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

• 루나 모델 (pip install luna-model)

설정

필요한 모든 종속성을 가져옵니다.

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 함수를 선택합니다. (이 코드는 이미 계정을 로컬 환경에 저장해 두었다고 가정합니다.)

catalog = QiskitFunctionsCatalog(channel="ibm_quantum_platform")

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

Output:

[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()

Output:

[<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단계: 고전적 입력을 양자 문제에 매핑하기

이 문제는 LP 파일로 정의되며, 이는 최적화 문제에 널리 사용되는 형식으로, Aqarios 제약 조건付き 양자 최적화기의 입력으로 사용됩니다. 이 기능은 LP 파일 외에도 MPS 파일과 Luna Model의 기본 표현 형식을 지원합니다. LP 파일은 다음 단계를 거쳐 생성됩니다:

1. QOBLIB [2] 에서 그래프 인스턴스를 가져옵니다
2. 최적화 문제를 수학적 모델로 표현한다
3. LP 파일 생성하기

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

그래프는 DIMACS .gph 형식으로 지정되며, 이는 줄 단위로 구성된 형식으로, 로 시작하는 줄은 e 에지를, 로 시작하는 줄은 문제 헤더를, 로 시작하는 줄은 주석을 나타냅니다 p``c :

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

다음 함수를 사용하면 QOBLIB 저장소에서 해당 파일을 .gph 다운로드할 수 있으며, 이 함수는 파일을 분석하여 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)

Output:

Loading graph with 186 nodes and 280 edges.

이 예제에서는 QOBLIB의 인스턴스 es60fst02 , 즉 186개의 노드와 280개의 간선을 가진 그래프를 사용합니다. 제약 조건이 있는 양자 최적화기(Constrained Quantum Optimizer)가 적용한 전처리 단계 덕분에, 이 문제는 156 큐비트 헤론(Heron) 장치에서 풀 수 있습니다. 이 그래프는 matplotlib을 사용하여 시각화할 수 있습니다:

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

Output:

최적화 문제를 수립하라

최대 독립 집합 문제는 를 사용하여 직접 정식화할 수 있다 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 최대 독립 집합(Maximum Independent Set) 문제를 해결하기 위해 미리 구현된 애플리케이션 클래스를 제공하며, 이를 통해 위의 문제 정형화를 단 한 번의 호출로 간소화할 수 있습니다:

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("...")

Output:

\ 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
...

이 형식은 Constrained Quantum Optimizer에서 기본으로 지원하는 형식입니다.

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

모든 회로 합성, 최적화 및 트랜스파일레이션은 이 함수가 기본적으로 처리합니다. 이 함수를 호출할 때 필요한 인자에 대해서는 API 참조 문서의 ‘입력’ 섹션을 참조하십시오.

알고리즘의 동작을 세부적으로 조정하려면 API 참조 문서의 ‘옵션’ 목록 을 참조하십시오.

자세한 내용은 Aqarios Constrained Quantum Optimizer 가이드 및 API 참조 문서를 참조하십시오.

3단계: Qiskit primitives를 사용하여 실행합니다

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

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

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

Output:

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

내부적으로 이 알고리즘은 다음과 같은 단계를 거칩니다:

1. 전처리 :
   • 수정 가능한 변수 줄이기
   • 파벌 찾기
   • 제약 조건 유형 파악하기
   • 벌칙 조항에 대한 벌칙 요인을 평가한다
   • 제약 변환 적용
   • 제약 조건 준수 기법을 활용한 회로 합성
   • 문제의 근사화 및 트랜스필레이션
2. 반복 루프의 병렬 체인 :
   • 고정된 매개변수를 가진 회로의 예시
   • 후처리 적용
   • 따뜻한 시작 확률을 평가하고 새로 설정합니다
3. 후처리 :
   • 최적의 예제를 찾아 입력 문제에 대한 실현 가능성을 확인하십시오

진행 상황 확인

작업 진행 상황을 모니터링하려면 ‘ Qiskit Functions 시작하기’ 페이지의 다음 섹션을 참조하십시오:

• 작업 상태 점검(O)
• 검색 결과

# Monitor the job status
job.status()

Output:

'QUEUED'

4단계: 후처리를 수행하고 원하는 기존 형식으로 결과를 반환합니다

결과 출력은 딕셔너리 형태이며, 해당 필드에 대한 설명은 API 참조 문서의 ‘출력’ 섹션에 나와 있습니다.

solutions 목록에 두 개 이상의 항목이 포함되어 있다면, 여러 개의 퇴화 최적값이 발견된 것입니다. 여기서는 첫 번째 해법만을 다룹니다:

# 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['obj_value'])} nodes and is {'feasible' if result['feasible'] else 'infeasible'}."
)
print("{" + " ".join(k[2:] for k, v in solution.items() if v == 1) + "}")

Output:

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:

부록: 루나 모델을 활용한 문제 정의

위에서 소개한 qiskit-addon-opt-mapper 접근 방식 외에도, Qiskit Function은 Aqarios의 모델링 SDK인 Luna Model [4] 로 생성된 모델도 지원합니다. PyPI 패키지를 luna-model 설치한 후, 다음과 같이 가져오십시오:

설정:

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(model=input_str, backend_name="ibm_fez")

다음 단계

참조

1. IBM Quantum, Aqarios 제약 조건 기반 양자 최적화기 가이드
2. Koch 외 (2026), 양자 최적화 벤치마킹 라이브러리 10.1038/s43588-026-00991-1
3. Bucher 외 (2026), *반복적 웜스타트 XY-믹서를 이용한 제약 조건이 있는 양자 최적화 *10.1088/1367-2630/ae8ea2
4. Aqarios GmbH, 루나 모델 문서