หา Maximum Independent Set ด้วย Aqarios Constrained Quantum Optimizer

หมายเหตุ

Qiskit Functions เป็นฟีเจอร์ทดลองที่ใช้ได้เฉพาะผู้ใช้แผน IBM Quantum® Premium Plan, Flex Plan และ On-Prem (ผ่าน IBM Quantum Platform API) เท่านั้น โดยอยู่ในสถานะ preview release และอาจมีการเปลี่ยนแปลงได้

ประมาณเวลาที่ใช้: 30 วินาที บนโปรเซสเซอร์ Heron r2 (หมายเหตุ: นี่เป็นเพียงการประมาณการเท่านั้น เวลาการทำงานจริงของคุณอาจแตกต่างกันไป)

ความเป็นมา

บทช่วยสอนนี้สาธิตวิธีการหา maximum independent set ของกราฟโดยใช้ Aqarios Constrained Quantum Optimizer [1] ซึ่งเป็นปัญหาการหาค่าเหมาะที่สุดเชิงการจัดที่มีเงื่อนไข (constrained combinatorial optimization) อินสแตนซ์หนึ่งจากไลบรารีเกณฑ์มาตรฐาน QOBLIB [2] ถูกกำหนดเป็นโปรแกรมเชิงเส้นแบบไบนารี (binary linear program) และส่งไปยัง Optimizer Application Function Optimizer จะจัดการการปรับสูตรใหม่ (reformulation) การสังเคราะห์วงจร การทำ transpilation และการทำ iterative warm starting ทั้งหมดภายในตัว (ดูรายละเอียดที่ [3])

บทช่วยสอนนี้ครอบคลุมขั้นตอนต่อไปนี้:

กำหนดปัญหาให้อยู่ในรูปโปรแกรมเชิงเส้นโดยใช้ OptimizationProblem จาก qiskit-addon-opt-mapper
รันการหาค่าเหมาะที่สุดเชิงควอนตัมโดยใช้ Aqarios Constrained Quantum Optimizer
ดึงผลลัพธ์และแสดงผลด้วยภาพ

ปัญหา Maximum Independent Set

ปัญหา Maximum Independent Set (MIS) เป็นความท้าทายพื้นฐานในสาขาการหาค่าเหมาะที่สุดเชิงการจัด กล่าวอย่างเป็นทางการ กำหนดกราฟ $G(V, E)$ เป้าหมายคือการหาสับเซตของจุดยอด (vertices) ที่ใหญ่ที่สุด $V_I \subset V$ โดยที่ไม่มีจุดยอดสองจุดใน $V_I$ เชื่อมกันด้วยเส้นเชื่อม (edge) ดังใน $\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{โดยที่} \quad x_u + x_v \leq 1 \quad \forall (u, v) \in E.

MIS มีการใช้งานจริงที่หลากหลาย ในการวางแผนเครือข่ายไร้สาย independent set สอดคล้องกับกลุ่มเครื่องส่งสัญญาณที่สามารถกระจายสัญญาณพร้อมกันได้โดยไม่รบกวนกัน ในการจัดตารางเวลา MIS ใช้จำลองกลุ่มงานที่ใหญ่ที่สุดที่สามารถทำงานพร้อมกันได้เมื่อมีความขัดแย้งด้านทรัพยากรแบบคู่ ส่วนในชีววิทยาเชิงคำนวณ MIS ใช้แทนกลุ่มโปรตีนที่ไม่มีปฏิสัมพันธ์ต่อกันในเครือข่ายหนึ่ง

แม้ว่าจะมีการกำหนดปัญหาที่เข้าใจง่าย แต่ MIS เป็นปัญหา NP-hard และแม้กระทั่งสำหรับกราฟที่มีจำนวนโหนดเพียงไม่กี่ร้อยโหนด อินสแตนซ์บางแบบก็ยากที่จะแก้ได้อย่างแม่นยำหรือด้วยวิธีฮิวริสติก [2] ปัญหานี้ยังก่อให้เกิดโครงสร้างเงื่อนไขแบบเบาบาง (sparse constraint) ที่เหมาะกับการนำไปใช้งานบนฮาร์ดแวร์สำหรับการหาค่าเหมาะที่สุดเชิงควอนตัม ทำให้เป็นเกณฑ์มาตรฐานที่น่าสนใจสำหรับอุปกรณ์ควอนตัมในระยะใกล้

Aqarios Constrained Quantum Optimizer

วิธีมาตรฐานในการฝังปัญหาไบนารีที่มีเงื่อนไขลงในการหาค่าเหมาะที่สุดเชิงควอนตัมคือการแปลงแบบจำลองให้อยู่ในรูปแบบไม่มีเงื่อนไขโดยการเพิ่มพจน์บทลงโทษ (penalty terms): เงื่อนไข $x_u + x_v \leq 1$ แต่ละข้อที่ถูกละเมิดจะเพิ่มค่า $2 x_u x_v$ ให้กับเป้าหมายการหาค่าต่ำสุด $-\sum_i x_i$ ขั้นตอนนี้ถูกจัดการโดยอัตโนมัติโดย Constrained Quantum Optimizer Qiskit Function

นอกเหนือจากการแปลงมาตรฐานนี้ optimizer ยังระบุ cliques ในกราฟเงื่อนไข 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$ การเพิ่มตัวแปร slack $y$ จะเปลี่ยนสิ่งนี้ให้เป็นสมการ $\sum_i x_i + y = 1$ ซึ่งอยู่ในรูปของเงื่อนไขแบบ one-hot ที่สามารถบังคับใช้ได้โดยตรงใน QAOA โดยใช้ XY-mixers [3] วิธีนี้ช่วยลดพื้นที่การค้นหาและหลีกเลี่ยงความจำเป็นในการใช้พจน์บทลงโทษสำหรับเงื่อนไขเหล่านั้น ทำให้คุณภาพของคำตอบดีขึ้น

นอกจากนี้ ตัวแปรที่เชื่อมต่อกับเพื่อนบ้านเพียงตัวเดียวเรียกว่าโหนด pendant และจะถูกกำหนดค่าแบบ deterministic โดยอัลกอริทึมก่อนการรันบนควอนตัม ซึ่งช่วยลดขนาดปัญหาที่แท้จริงลงไปอีก

Constrained Quantum Optimizer ใช้แนวทาง iterative warm-starting ที่เข้ากันได้กับ XY-mixers [1] ซึ่งจะค่อยๆ ลดพื้นที่การค้นหาลงโดยการปรับ bias การกระจายของสถานะควอนตัมให้ไปยังพื้นที่คำตอบที่มีแนวโน้มดีในแต่ละรอบซ้ำ วิธีนี้ทำให้สามารถใช้ fixed-angle QAOA parameters ได้ ซึ่งขจัดความจำเป็นในการฝึกพารามิเตอร์แบบ variational ความต้องการทรัพยากรควอนตัมทั้งหมดถูกกำหนดโดยจำนวนรอบของ warm-start เพียงอย่างเดียว ซึ่งหมายความว่าต้นทุนควอนตัมสามารถควบคุมได้อย่างตรงไปตรงมา

ข้อกำหนดเบื้องต้น

ก่อนเริ่มบทช่วยสอนนี้ ตรวจสอบให้แน่ใจว่าคุณได้ติดตั้งข้อกำหนดต่อไปนี้แล้ว:

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)

การตั้งค่า

นำเข้า dependencies ที่จำเป็นทั้งหมด

# 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

ขั้นแรก ให้ authenticate โดยใช้ IBM Quantum API key ของคุณ จากนั้นเลือก 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: แปลงอินพุตแบบคลาสสิกเป็นปัญหาควอนตัม

ปัญหาถูกกำหนดในรูปแบบ LP-file ซึ่งเป็นรูปแบบทั่วไปสำหรับปัญหาการหาค่าเหมาะที่สุดที่ใช้เป็นอินพุตของ Aqarios Constrained Quantum Optimizer นอกจาก LP-files แล้ว ฟังก์ชันนี้ยังรองรับ MPS-files และการแทนค่าแบบ Luna Model ดั้งเดิมอีกด้วย LP-file ถูกสร้างขึ้นผ่านขั้นตอนต่อไปนี้:

ดึงอินสแตนซ์กราฟจาก QOBLIB [2]
สร้างแบบจำลองปัญหาการหาค่าเหมาะที่สุด
สร้าง LP-file

โหลดกราฟอินสแตนซ์ของปัญหา

กราฟถูกกำหนดในรูปแบบ DIMACS .gph ซึ่งเป็นรูปแบบแบบบรรทัดต่อบรรทัด โดยบรรทัดที่ขึ้นต้นด้วย e กำหนดเส้นเชื่อม บรรทัดที่ขึ้นต้นด้วย p กำหนดส่วนหัวของปัญหา และบรรทัดที่ขึ้นต้นด้วย c เป็นความคิดเห็น:

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

ไฟล์ .gph สามารถดาวน์โหลดได้จาก repository ของ QOBLIB โดยใช้ฟังก์ชันต่อไปนี้ ซึ่งจะแปลงข้อมูลให้เป็นกราฟ NetworkX ด้วย โปรดสังเกตว่ารูปแบบ DIMACS ใช้การกำหนดหมายเลขโหนดแบบเริ่มที่ 1 (1-based) ซึ่งในที่นี้จะถูกแปลงเป็นการเริ่มที่ 0 (0-based indexing)

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.

ตัวอย่างนี้ใช้อินสแตนซ์ es60fst02 จาก QOBLIB ซึ่งเป็นกราฟที่มี 186 โหนดและ 280 เส้นเชื่อม ด้วยขั้นตอนการประมวลผลล่วงหน้า (preprocessing) ของ Constrained Quantum Optimizer อินสแตนซ์นี้สามารถแก้ได้บนอุปกรณ์ Heron ขนาด 156 qubit กราฟนี้สามารถแสดงผลด้วยภาพโดยใช้ 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

สร้างปัญหาการหาค่าเหมาะที่สุด

ปัญหา Maximum Independent Set สามารถกำหนดได้โดยตรงโดยใช้ 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 มีคลาสแอปพลิเคชันที่ implement ไว้ล่วงหน้าสำหรับปัญหา Maximum Independent Set ซึ่งช่วยลดความซับซ้อนของการกำหนดปัญหาข้างต้นให้เหลือเพียงการเรียกครั้งเดียว:

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

แปลงปัญหาให้เป็น LP-file

OptimizationProblem เองไม่รองรับการส่งออกเป็น LP-file แต่สามารถทำงานร่วมกับ DOcplex ซึ่งรองรับได้ การสร้างเนื้อหา LP-file ต้องใช้เพียงสองบรรทัดเท่านั้น:

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

รูปแบบนี้เป็นรูปแบบที่ Constrained Quantum Optimizer รองรับโดยตรง

ขั้นตอนที่ 2: ปรับปัญหาให้เหมาะสมสำหรับการรันบนฮาร์ดแวร์ควอนตัม

การสังเคราะห์วงจร การหาค่าเหมาะที่สุด และการทำ transpilation ทั้งหมดถูกจัดการโดยฟังก์ชันนี้โดยตรง ดู ส่วนอินพุต ใน API reference สำหรับอาร์กิวเมนต์ที่ใช้เรียกฟังก์ชันนี้

หากต้องการปรับแต่งพฤติกรรมของอัลกอริทึม ดู รายการตัวเลือก ใน API reference หากต้องการให้การแมป Circuit ทำซ้ำได้ในทุกการรัน ให้กำหนดค่าตัวเลือก seed_transpiler ให้คงที่

สำหรับข้อมูลเพิ่มเติม ดู คู่มือ Aqarios Constrained Quantum Optimizer และ API reference

ขั้นตอนที่ 3: รันโดยใช้ Qiskit primitives

ตอนนี้ LP-file สามารถส่งไปยัง optimizer ได้แล้ว:

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:
- ลดตัวแปรที่สามารถกำหนดค่าคงที่ได้
- หา cliques
- ระบุประเภทของเงื่อนไข
- ประเมินค่าสัมประสิทธิ์บทลงโทษสำหรับพจน์บทลงโทษ
- ใช้การแปลงเงื่อนไข
- สังเคราะห์วงจรด้วยวิธีการบังคับใช้เงื่อนไข
- การประมาณค่าปัญหาและการทำ transpilation
สายโซ่แบบขนานของลูปแบบทำซ้ำ (parallel chains of iterative loops):
- สุ่มตัวอย่างจากวงจรด้วยพารามิเตอร์ที่กำหนดตายตัว
- ใช้การประมวลผลภายหลัง (postprocessing)
- ประเมินและกำหนดความน่าจะเป็นของ warm-starting ใหม่
Postprocessing:
- หาตัวอย่างที่ดีที่สุดและตรวจสอบความเป็นไปได้เทียบกับปัญหาที่ป้อนเข้ามา

ติดตามความคืบหน้า

ดูส่วนต่อไปนี้ในหน้า Get started with Qiskit Functions เพื่อติดตามความคืบหน้าของงานของคุณ:

# Monitor the job status
job.status()

'QUEUED'

ขั้นตอนที่ 4: ประมวลผลภายหลังและส่งคืนผลลัพธ์ในรูปแบบคลาสสิกที่ต้องการ

ผลลัพธ์ที่ได้เป็น dictionary ซึ่งฟิลด์ต่างๆ ถูกอธิบายไว้ใน ส่วนผลลัพธ์ ของ API reference

เมื่อรายการ solutions มีมากกว่าหนึ่งรายการ แสดงว่าพบคำตอบที่เหมาะที่สุดแบบเสมอกัน (degenerate optima) หลายคำตอบ ในที่นี้จะพิจารณาเฉพาะคำตอบแรกเท่านั้น โดยอ้างอิงตามชื่อตัวแปร คำตอบชุดเดียวกันนี้ยังมีให้ในรูปแบบ bitstring ใน 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}

การแสดงผลด้วยภาพ

independent set ที่พบสามารถแสดงผลด้วยภาพได้โดยการเน้นโหนดที่ถูกเลือกไว้ในกราฟ:

# 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 ยังรองรับแบบจำลองที่สร้างด้วย Luna Model [4] ซึ่งเป็น modeling SDK ของ Aqarios หลังจากติดตั้งแพ็กเกจ PyPI luna-model แล้ว ให้นำเข้าดังนี้:

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 Constrained Quantum Optimizer สำหรับคำอธิบายโดยละเอียดของฟีเจอร์ทั้งหมดของฟังก์ชันนี้
สำรวจ API reference สำหรับรายการพารามิเตอร์อินพุตและฟิลด์ผลลัพธ์แบบเต็ม
ทดลองใช้ตัวเลือกของอัลกอริทึม (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

ความเป็นมา​

ปัญหา Maximum Independent Set​

Aqarios Constrained Quantum Optimizer​

ข้อกำหนดเบื้องต้น​

การตั้งค่า​

ขั้นตอนที่ 1: แปลงอินพุตแบบคลาสสิกเป็นปัญหาควอนตัม​

โหลดกราฟอินสแตนซ์ของปัญหา​

สร้างปัญหาการหาค่าเหมาะที่สุด​

ทางลัด​

แปลงปัญหาให้เป็น LP-file​

ขั้นตอนที่ 2: ปรับปัญหาให้เหมาะสมสำหรับการรันบนฮาร์ดแวร์ควอนตัม​

ขั้นตอนที่ 3: รันโดยใช้ Qiskit primitives​

ติดตามความคืบหน้า​

ขั้นตอนที่ 4: ประมวลผลภายหลังและส่งคืนผลลัพธ์ในรูปแบบคลาสสิกที่ต้องการ​

การแสดงผลด้วยภาพ​

ภาคผนวก: การกำหนดปัญหาด้วย Luna Model​

ขั้นตอนถัดไป​

เอกสารอ้างอิง​