إيجاد المجموعة المستقلة القصوى باستخدام مُحسِّن أكاريوس الكمي المقيد

ملاحظة

Qiskit Functions هي ميزة تجريبية متاحة فقط لمستخدمي خطط IBM Quantum® Premium وFlex وOn-Prem (عبر واجهة برمجة تطبيقات IBM Quantum Platform). وهي حاليًا في مرحلة إصدار المعاينة (preview) وقابلة للتغيير.

التقدير التقريبي للاستخدام: 30 ثانية على معالج Heron r2. (ملاحظة: هذا تقدير فقط. قد يختلف وقت التشغيل الفعلي لديك.)

الخلفية

يوضح هذا الدرس التعليمي كيفية إيجاد المجموعة المستقلة القصوى لرسم بياني باستخدام مُحسِّن أكاريوس الكمي المقيد [1]، وهي مسألة تحسين تركيبي مقيدة. يتم صياغة مثال من مكتبة معايير QOBLIB [2] كبرنامج خطي ثنائي ويُمرَّر إلى دالة تطبيق المُحسِّن. يتعامل المُحسِّن داخليًا مع جميع عمليات إعادة الصياغة، وتوليف الدائرة، والترجمة، والبدء الدافئ التكراري (راجع [3] للتفاصيل).

يغطي هذا الدرس التعليمي الخطوات التالية:

تعريف المسألة كبرنامج خطي باستخدام OptimizationProblem من qiskit-addon-opt-mapper
تشغيل التحسين الكمي باستخدام مُحسِّن أكاريوس الكمي المقيد
استرجاع النتائج وتصويرها

مسألة المجموعة المستقلة القصوى

مسألة المجموعة المستقلة القصوى (MIS) هي تحدٍّ أساسي في التحسين التركيبي. بصياغة رسمية، بالنظر إلى رسم بياني $G(V, E)$ ، الهدف هو إيجاد أكبر مجموعة جزئية من الرؤوس $V_I \subset V$ بحيث لا يكون هناك رأسان في $V_I$ متصلَين بحافة، كما في $\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 نطاقًا واسعًا من التطبيقات العملية. في تخطيط الشبكات اللاسلكية، تقابل المجموعة المستقلة مجموعة من أجهزة الإرسال التي يمكنها جميعًا البث في آنٍ واحد دون تداخل متبادل. في الجدولة، تُمثّل أكبر مجموعة من المهام التي يمكن تنفيذها في وقت واحد نظرًا لتعارضات الموارد الثنائية. في البيولوجيا الحاسوبية، تلتقط مجموعات من البروتينات غير المتفاعلة فيما بينها ضمن شبكة.

على الرغم من صياغتها البديهية، فإن MIS مسألة من فئة NP-hard، وحتى بالنسبة للرسوم البيانية التي تحتوي على بضع مئات من العُقد، تصبح حالات معينة صعبة الحل بدقة أو بشكل تقريبي [2]. كما تنتج المسألة بنى قيود متناثرة تناسب جيدًا التطبيقات العتادية للتحسين الكمي، مما يجعلها معيارًا جذابًا للأجهزة الكمية قريبة المدى.

مُحسِّن أكاريوس الكمي المقيد

النهج المعتاد لتضمين مسألة ثنائية مقيدة في التحسين الكمي يحوّل النموذج إلى صيغة غير مقيدة بإضافة حدود عقابية: كل قيد منتهك $x_u + x_v \leq 1$ يساهم بـ $2 x_u x_v$ في هدف التقليل $-\sum_i x_i$ . يتم التعامل مع هذا تلقائيًا بواسطة دالة Qiskit الخاصة بالمُحسِّن الكمي المقيد.

بالإضافة إلى هذا التحويل المعتاد، يحدد المُحسِّن العُصب (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$ . إدخال متغير ترخي $y$ يحوّل هذا إلى معادلة $\sum_i x_i + y = 1$ ، والتي تأخذ شكل قيد "ساخن واحد" (one-hot) يمكن فرضه مباشرة في QAOA باستخدام مازجات XY [3]. هذا يقلل من فضاء البحث ويتجنب الحاجة إلى حدود عقابية لهذه القيود، مما يحسّن جودة الحل.

بالإضافة إلى ذلك، تُسمى المتغيرات المتصلة بجار واحد فقط عُقد متدلية (pendant)، ويتم تثبيتها بشكل حتمي بواسطة الخوارزمية قبل التنفيذ الكمي، مما يقلل أكثر من الحجم الفعلي للمسألة.

يستخدم المُحسِّن الكمي المقيد نهج البدء الدافئ التكراري المتوافق مع مازجات XY [1]، والذي يضيق تدريجيًا فضاء البحث عن طريق توجيه توزيع الحالة الكمية نحو مناطق الحلول الواعدة عبر التكرارات. هذا يتيح استخدام معاملات QAOA بزوايا ثابتة، مما يلغي الحاجة إلى التدريب التغايري للمعاملات. تُحدَّد متطلبات الموارد الكمية الإجمالية فقط من خلال عدد تكرارات البدء الدافئ، مما يجعل التحكم في التكلفة الكمية أمرًا مباشرًا.

المتطلبات

قبل البدء في هذا الدرس التعليمي، تأكد من أنك قمت بتثبيت المتطلبات التالية:

Qiskit Runtime (pip install qiskit-ibm-runtime)
عميل IBM لـ Qiskit Functions Catalog (pip install qiskit-ibm-catalog)
مُلحق Qiskit لمخطط التحسين (pip install qiskit-addon-opt-mapper)
Numpy (pip install numpy)
Matplotlib (pip install matplotlib)
NetworkX (pip install networkx)

اختياريًا، من أجل الملحق تحتاج إلى تثبيت

نموذج Luna (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 الخاص بك. ثم اختر دالة Qiskit كما يلي. (يفترض هذا الكود أنك قمت بالفعل بـحفظ حسابك في بيئتك المحلية.)

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، وهو تنسيق شائع لمسائل التحسين يُستخدم كمدخل لمُحسِّن أكاريوس الكمي المقيد. بالإضافة إلى ملفات LP، تدعم الدالة أيضًا ملفات MPS وتمثيلات نموذج Luna الأصلية. يتم توليد ملف 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.

يستخدم هذا المثال مثيل es60fst02 من QOBLIB، وهو رسم بياني يحتوي على 186 عقدة و280 حافة. وبفضل خطوات المعالجة المسبقة التي يستخدمها المُحسِّن الكمي المقيد، يمكن حل هذا المثيل على أجهزة Heron ذات 156 كيوبت. يمكن تصوير الرسم البياني باستخدام 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) للاطلاع على الوسائط التي يجب استخدامها لاستدعاء الدالة.

لضبط سلوك الخوارزمية بدقة، راجع قائمة الخيارات في مرجع واجهة برمجة التطبيقات. وإذا أردت أن يكون تعيين الدارة قابلاً لإعادة الإنتاج عبر التشغيلات، فثبّت الخيار seed_transpiler.

لمزيد من المعلومات، راجع دليل مُحسِّن أكاريوس الكمي المقيد ومرجع واجهة برمجة التطبيقات.

الخطوة 3: التنفيذ باستخدام بدائيات Qiskit

يمكن الآن إرسال ملف 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:
- إيجاد أفضل العينات والتحقق من استيفائها لقيود المسألة المُدخلة

مراقبة التقدم

راجع الأقسام التالية في صفحة البدء مع Qiskit Functions لمراقبة تقدم مهمتك:

# Monitor the job status
job.status()

'QUEUED'

الخطوة 4: المعالجة اللاحقة وإرجاع النتائج بالتنسيق الكلاسيكي المطلوب

ناتج النتيجة عبارة عن قاموس، تُوصف حقوله في قسم المخرجات من مرجع واجهة برمجة التطبيقات.

عندما تحتوي قائمة solutions على أكثر من إدخال واحد، فهذا يعني أنه تم العثور على عدة حلول مثلى متكافئة. يُؤخذ هنا الحل الأول فقط بعين الاعتبار، ويُشار إليه باسم المتغير. كما تتوفر الحلول نفسها على شكل سلاسل بتات في 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

بالإضافة إلى نهج qiskit-addon-opt-mapper الموضح أعلاه، تقبل دالة Qiskit أيضًا النماذج المُنشأة باستخدام نموذج Luna [4]، حزمة تطوير البرمجيات (SDK) الخاصة بالنمذجة من أكاريوس. بعد تثبيت حزمة 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")

الخطوات التالية

توصيات

راجع دليل مُحسِّن أكاريوس الكمي المقيد للحصول على شرح تفصيلي لجميع ميزات الدالة.
استكشف مرجع واجهة برمجة التطبيقات للاطلاع على القائمة الكاملة لمعاملات الإدخال وحقول الإخراج.
جرّب خيارات الخوارزمية (reps، num_parallel، shots، postprocessing_level) على مسألة التحسين الثنائي المقيد الخاصة بك لتقييم تأثيرها على جودة الحل ووقت التشغيل.

المراجع

IBM Quantum، دليل مُحسِّن أكاريوس الكمي المقيد
Koch et al. (2026)، مكتبة معايير التحسين الكمي 10.1038/s43588-026-00991-1
Bucher et al. (2026)، التحسين الكمي المقيد عبر مازجات XY للبدء الدافئ التكراري 10.1088/1367-2630/ae8ea2
Aqarios GmbH، توثيق نموذج Luna

الخلفية​

مسألة المجموعة المستقلة القصوى​

مُحسِّن أكاريوس الكمي المقيد​

المتطلبات​

الإعداد​

الخطوة 1: تعيين المدخلات الكلاسيكية إلى مسألة كمية​

تحميل رسم مثيل المسألة البياني​

بناء مسألة التحسين​

اختصار​

ترجمة المسألة إلى ملف LP​

الخطوة 2: تحسين المسألة لتنفيذها على العتاد الكمي​

الخطوة 3: التنفيذ باستخدام بدائيات Qiskit​

مراقبة التقدم​

الخطوة 4: المعالجة اللاحقة وإرجاع النتائج بالتنسيق الكلاسيكي المطلوب​

التصوير​

الملحق: صياغة المسألة باستخدام نموذج Luna​

الخطوات التالية​

المراجع​