حل مسألة المجموعة المستقلة العظمى بمتغيرات أكثر من الكيوبتات باستخدام SQOA Solver من JIJ

ملاحظة

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

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

الخلفية

يوضح هذا الدرس كيفية استخدام SQOA Solver، وهي Qiskit Function من JIJ، لحل مسألة المجموعة المستقلة العظمى (MIS) بعدد من المتغيرات الثنائية يفوق عدد كيوبتات QPU المختار. الخطوات الأساسية هي تحميل نسخة MIS من Quantum Optimization Benchmarking Library (QOBLIB) [1]، وصياغتها بصيغة التحسين الثنائي التربيعي غير المقيَّد (QUBO) باستخدام qiskit-addon-opt-mapper، وإرسالها إلى SQOA Solver للتنفيذ على QPU من IBM®، ثم التحقق من الحل المُعاد.

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

المجموعة المستقلة هي مجموعة جزئية من العقد في رسم بياني بحيث لا تشترك أي عقدتين مختارتين في حافة. والمجموعة المستقلة العظمى (MIS) هي مجموعة مستقلة بأكبر عدد ممكن من العقد. من تطبيقات MIS الجدولة وتخصيص الموارد وتصميم الشبكات.

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

الصياغة الرياضية

بالنظر إلى رسم بياني غير موجّه $G = (V, E)$، عيّن متغيرًا ثنائيًا $x_v$ لكل عقدة $v$:

• $x_v = 1$ إذا كانت العقدة $v$ مختارة.

• $x_v = 0$ otherwise.

تعظّم الصياغة الخطية الثنائية عدد العقد المختارة مع منع اختيار طرفي أي حافة معًا:

$$\begin{aligned} \max_{x} \quad & \sum_{v \in V} x_v \\ \text{subject to} \quad & x_v + x_w \leq 1 && \forall (v,w) \in E, \\ & x_v \in \{0,1\} && \forall v \in V. \end{aligned}$$

تحسب دالة الهدف العقد المختارة. وتضمن قيود الحواف معًا أن تشكّل العقد المختارة مجموعة مستقلة.

يستخدم هذا الدرس الصياغة الثنائية غير المقيَّدة من QOBLIB، التي تستبدل قيود الحواف بعقوبات تربيعية:

$$\max_{x \in \{0,1\}^{|V|}} \quad \sum_{v \in V} x_v - 2 \sum_{(v,w) \in E} x_v x_w.$$

كلما اختير طرفا حافة معًا، يطرح الحد الثاني اثنين من دالة الهدف. تجعل هذه العقوبة الاختيار المتعارض أقل تفضيلًا من الإبقاء على أحد الطرفين فقط. ودالة الهدف الناتجة هي QUBO، وهي صيغة الإدخال التي يقبلها SQOA Solver.

لماذا نستخدم SQOA Solver؟

تخصص كثير من مناهج التحسين الكمي كيوبتًا واحدًا لكل متغير ثنائي، لذا قد تحدّ سعة العتاد الكمي مباشرةً من حجم المسألة. يجمع SQOA Solver بين عدة تقنيات للاختزال والحوسبة الهجينة لتخفيف هذا القيد:

• يمكنه معالجة مسائل بمتغيرات ثنائية أكثر من كيوبتات QPU. يطبّق presolve قواعد اختزال يمكنها تثبيت المتغيرات وتبسيط QUBO المتبقية مع الحفاظ على حل أمثل واحد على الأقل. وتجريبيًا، يمكن لـ presolve أيضًا أن يجعل QUBO المتبقية أكثر تخلخلًا، مما يفيد الترميز المعتمد على QRAC الذي يليه.

  يستخدم الحلّال بعد ذلك ترميزًا معتمدًا على QRAC مشتقًا من Quantum Random Access Optimization (QRAO) [3] لتمثيل عدة متغيرات (حتى ثلاثة) لا يوجد بينها تفاعل QUBO مباشر على الكيوبت نفسه.

  يعتمد الاختزال الناتج عن presolve والترميز على بنية المسألة. فمثلًا، في هذا الدرس تستخدم مسألة من 200 متغير 67 كيوبتًا فقط.

• يمكن أن يكون أقل حساسية لضجيج العتاد. يستخدم القطري الكمي المعتمد على العينات [4]، [5] الـ QPU لأخذ عينات من سلاسل البتات لكنه يجري القطرنة بشكل كلاسيكي. وهذا يتجنب تقييمات QPU المتكررة لتحديث المعاملات المتغيرة، ويمكن أن يقلل أثر الضجيج على سير عمل التحسين.

• يؤتمت سير العمل من presolve حتى المعالجة اللاحقة. تقدّم نسخة QUBO بصيغة صحيحة وتختار backend. بعد ذلك يشغّل SQOA Solver سير العمل كاملًا تلقائيًا. فهو يطبّق presolve، ويربط المتغيرات الكلاسيكية بمسألة كمية مخففة، وينشئ دوائر أخذ العينات ويحوّلها، وينفذ أخذ العينات الكمي والقطرنة الكلاسيكية، ويقرّب التعيين ويحسّنه، ثم يعيد بناء الحل الكلاسيكي ويقيّمه.

المتطلبات

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

• عميل Qiskit Functions Catalog (pip install qiskit-ibm-catalog).

• إضافة Qiskit لمحوّل التحسين، وتُستخدم لصياغة المسألة (pip install qiskit-addon-opt-mapper).

• NetworkX وMatplotlib، وتُستخدمان للتعامل مع الرسم البياني ورسمه (pip install networkx matplotlib).

تحتاج أيضًا إلى صلاحية الوصول إلى SQOA Solver من Qiskit Functions Catalog. املأ النموذج لطلب الوصول إلى الدالة.

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

_needed = {"matplotlib": "matplotlib", "networkx": "networkx", "ommx": "ommx", "ommx_quantum_benchmarks": "ommx-quantum-benchmarks", "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")

# %pip install qiskit-ibm-catalog qiskit-addon-opt-mapper networkx matplotlib

الإعداد

أولًا، استورد الحزم والأدوات المطلوبة.

import urllib.request

import matplotlib.pyplot as plt
import networkx as nx
from qiskit_addon_opt_mapper import OptimizationProblem
from qiskit_addon_opt_mapper.converters import OptimizationProblemToQubo
from qiskit_ibm_catalog import QiskitFunctionsCatalog

يقبل SQOA Solver مسألة QUBO كقاموس معاملات بصيغة السلاسل النصية للصفوف التي تستخدمها دوال التحسين من IBM®. عرّف دالة مساعدة تحوّل QUBO التي يعيدها OptimizationProblemToQubo إلى هذه الصيغة.

يعيد المحوّل دائمًا مسألة تصغير، وهذا يتوافق مع طريقة معاملة SQOA Solver لمسألة بصيغة قاموس. تستخدم المفاتيح فهارس متغيرات QUBO، ويحصل كل متغير على حد خطي، حتى لو كان معامله صفرًا، بحيث يغطي الحل المُعاد جميع المتغيرات.

def to_problem_dict(qubo: OptimizationProblem) -> dict[str, float]:
    """Convert a QUBO from OptimizationProblemToQubo to the SQOA Solver dictionary format."""
    objective = qubo.objective
    payload = {"()": objective.constant}
    # Keep every variable in the problem, even with a zero linear coefficient.
    payload.update({f"({i},)": 0.0 for i in range(qubo.get_num_vars())})
    for i, coefficient in objective.linear.to_dict().items():
        payload[f"({i},)"] += coefficient
    for (i, j), coefficient in objective.quadratic.to_dict().items():
        # Fold a binary diagonal term x_i * x_i = x_i into the linear term.
        key = f"({i},)" if i == j else f"({i}, {j})"
        payload[key] = payload.get(key, 0.0) + coefficient
    return {key: float(value) for key, value in payload.items()}

الخطوة 1: ربط المدخلات الكلاسيكية بمسألة كمية

يقبل SQOA Solver مسألة QUBO وينفذ الربط الكمي داخل الدالة. في هذا الدرس، تنزّل نسخة MIS من QOBLIB وتصوغها كـ QUBO باستخدام qiskit-addon-opt-mapper. تغطي هذه الخطوة ما يلي:

• الاتصال بـ SQOA Solver.

• فهم إطار عمل SQOA.

• تحميل نسخة المسألة.

• صياغة QUBO وتحويلها للإرسال.

الاتصال بـ SQOA Solver

اتصل بـ Qiskit Functions Catalog ببيانات اعتماد IBM Quantum Platform الخاصة بك، ثم حمّل SQOA Solver. يفترض الكود التالي أنك حفظت حسابك في بيئتك المحلية بالفعل.

إذا فشل الاتصال، فتأكد من أن مسؤول حساب IBM Quantum Platform لديك قد منح مثيل الخدمة المختار حق الوصول إلى SQOA Solver.

catalog = QiskitFunctionsCatalog(channel="ibm_quantum_platform")
solver = catalog.load("jij/sqoa-solver")

فهم إطار عمل SQOA

تجمع خوارزمية التحسين الكمي المعتمدة على العينات مع الاسترخاء الكمي (SQOA-QR) [2] بين Quantum Random Access Optimization (QRAO) والقطرنة الكمية المعتمدة على العينات:

1. الاسترخاء الكمي والترميز: يحوّل SQOA Solver مسألة QUBO إلى دالة هدف إيزينغ للتصغير بالصيغة $c + \sum_i h_i z_i + \sum_{i<j} J_{ij} z_i z_j$، حيث $z_i \in \{-1, +1\}$. ثم يربط QRAO [3] كل متغير سبين بمراقَب باولي. وبالنسبة لترميز $(3,1)$-QRAC المستخدم هنا، فإن الهاميلتوني المخفف هو

   $$\widetilde{H} = cI + \sum_i \sqrt{k_i} h_i P_{f(i)} + \sum_{i<j} \sqrt{k_i k_j} J_{ij} P_{f(i)} P_{f(j)},$$

   حيث $I$ هو مؤثر الوحدة، و$f(i)$ يعيّن المتغير $i$ إلى كيوبت وإلى واحد من $X$ أو $Y$ أو $Z$، و$k_i \in \{1,2,3\}$ هو عدد المتغيرات المربوطة بالكيوبت نفسه الذي يرتبط به $i$. وعندما يحتوي كلا الكيوبتين المعنيين على ثلاثة متغيرات، يصبح عاملا القياس الخطي والتربيعي $\sqrt{3}$ و$3$ على التوالي.

   تُعيَّن للمتغيرات التي تتشارك كيوبتًا مراقَبات باولي مختلفة غير تبادلية. تبقى المتغيرات المتفاعلة في QUBO على كيوبتات مختلفة، بينما يمكن للمتغيرات التي لا تفاعل مباشر بينها في QUBO أن تتشارك كيوبتًا. لذلك يعتمد الانخفاض في عدد الكيوبتات على بنية المسألة.

2. أخذ العينات الكمي: يأخذ معالج كمي عينات من سلاسل البتات من دوائر مصممة لاستكشاف الحالات منخفضة الطاقة للهاميلتوني المخفف.

3. القطرنة المعتمدة على العينات: يسقط الحلّال الهاميلتوني المخفف على الفضاء الجزئي الممتد بحالات الأساس المستخرجة من سلاسل البتات المأخوذة، ويقطّر الهاميلتوني المسقَط بشكل كلاسيكي [4]، [5]. بالنسبة لمجموعة ثابتة من سلاسل البتات المأخوذة، ليكن $\mathcal{S}_r$ الفضاء الجزئي الممتد بـ $r$ حالة أساس مختلفة، بحيث $\dim(\mathcal{S}_r) \leq r$. وطاقة حالته الأرضية المقدّرة هي:

   $$E_r = \min_{\substack{|\psi\rangle \in \mathcal{S}_r \\ \langle\psi|\psi\rangle=1}} \langle\psi|\widetilde{H}|\psi\rangle, \qquad \mathcal{S}_r \subseteq \mathcal{S}_{r'} \Longrightarrow E_{\mathrm{exact}} \leq E_{r'} \leq E_r \quad (r' \geq r),$$

   حيث $E_{\mathrm{exact}}$ هي طاقة الحالة الأرضية للهاميلتوني المخفف الكامل. لذلك، لا يمكن لفضاء جزئي محتفَظ به أكبر أن يزيد طاقة الحالة الأرضية المقدّرة.

   يفترض هذا الترتيب نتيجة أخذ العينات نفسها ويتعلق بطاقة الهاميلتوني المخفف قبل التقريب. ولا يضمن نظريًا حلًا كلاسيكيًا مُعادًا أفضل. ومع ذلك، في QRAO يُتوقع استدلاليًا أن توفر حالة أقل طاقة حلًا كلاسيكيًا أفضل.

4. التقريب: تُحوَّل الحالة المخففة الناتجة عن القطرنة إلى تعيين ثنائي كلاسيكي.

يحيط SQOA Solver هذا الإطار بمعالجة كلاسيكية. قبل الربط الكمي، يطبّق presolve قواعد اختزال يمكنها تثبيت المتغيرات وتبسيط QUBO المتبقية مع الحفاظ على حل أمثل واحد على الأقل. وبعد القطرنة والتقريب، يحسّن بحث محلي كلاسيكي التعيين، ويعيد OMMX بناء الحل الكامل ويقيّمه.

تحميل النسخة

توزّع QOBLIB كل نسخة MIS كرسم بياني بصيغة DIMACS .gph، وهي صيغة قائمة على الأسطر يحدد فيها السطر الذي يبدأ بـ p عدد العقد والحواف، ويعرّف كل سطر يبدأ بـ e حافة.

تنشر QOBLIB أيضًا حلًا مرجعيًا أمثل أو الأفضل المعروف لكل نسخة. تنزّل الدوال التالية كليهما من مستودع QOBLIB. تُرقّم DIMACS العقد بدءًا من 1، لذلك يُعاد ترقيم الرسم البياني ليبدأ من 0.

إذا أردت البدء برسمك البياني الخاص بدلًا من ذلك، فتخطَّ التنزيل وصُغ المسألة من رسم NetworkX البياني بالطريقة نفسها.

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

def fetch_qoblib_graph(name: str) -> nx.Graph:
    """Download a QOBLIB independent-set instance as a NetworkX graph."""
    with urllib.request.urlopen(
        f"{QOBLIB_URL}/instances/{name}.gph"
    ) as response:
        lines = response.read().decode().splitlines()
    graph = nx.Graph()
    for fields in map(str.split, lines):
        if fields and fields[0] == "p":
            # Header: p edge <number of nodes> <number of edges>
            graph.add_nodes_from(range(int(fields[2])))
        elif fields and fields[0] == "e":
            # DIMACS labels nodes from 1; relabel them to start from 0.
            graph.add_edge(int(fields[1]) - 1, int(fields[2]) - 1)
    return graph

def fetch_reference_objective(name: str) -> float:
    """Read the objective value of the QOBLIB reference solution."""
    with urllib.request.urlopen(
        f"{QOBLIB_URL}/solutions/{name}.opt.sol"
    ) as response:
        for line in response.read().decode().splitlines():
            if line.startswith("# Objective value"):
                return float(line.split("=")[1])
    raise ValueError(f"No objective value found for {name}.")

INSTANCE_NAME = "gen200_p0-9_44"
G = fetch_qoblib_graph(INSTANCE_NAME)
reference_objective = fetch_reference_objective(INSTANCE_NAME)

ستستخدم قيمة دالة الهدف للحل المرجعي لاحقًا لتقييم نتيجة SQOA Solver. يحل هذا الدرس هذه المسألة على جهاز بـ 156 كيوبتًا.

print(
    f"{INSTANCE_NAME}: {G.number_of_nodes()} nodes, {G.number_of_edges()} edges"
)
print(f"Reference objective: {reference_objective:g}")

gen200_p0-9_44: 200 nodes, 1990 edges
Reference objective: 44

تصوّر الرسم البياني. ستستخدمه لاحقًا أيضًا للتحقق من أن العقد التي يعيدها SQOA Solver تشكّل مجموعة مستقلة.

layout = nx.forceatlas2_layout(
    G, max_iter=500, scaling_ratio=3.0, gravity=1.0, seed=7
)
node_size = max(8, min(60, 4000 / max(G.number_of_nodes(), 1)))

fig, ax = plt.subplots(figsize=(9, 7))
nx.draw_networkx_edges(G, layout, ax=ax, alpha=0.2, width=0.6)
nx.draw_networkx_nodes(
    G, layout, node_size=node_size, node_color="lightgray", ax=ax
)
ax.set_title(
    f"{INSTANCE_NAME}: {G.number_of_nodes()} nodes, {G.number_of_edges()} edges"
)
ax.set_axis_off()
plt.show()

صياغة QUBO

ابنِ الصياغة الخطية الثنائية من قسم الخلفية كـ OptimizationProblem بمتغير ثنائي واحد لكل عقدة، ودالة هدف تحسب العقد المختارة، وقيد واحد لكل حافة. ثم حوّلها باستخدام OptimizationProblemToQubo.

بوزن عقوبة قدره 2، يستبدل المحوّل كل قيد حافة بحد العقوبة $2 x_v x_w$ ويحوّل التعظيم إلى تصغير، فتكون المسألة المحوَّلة هي الصياغة الثنائية غير المقيَّدة من QOBLIB بإشارة معكوسة. فهارس متغيرات QUBO هي تسميات عقد الرسم البياني. وتبني فئة التطبيق IndependentSet في qiskit_addon_opt_mapper.applications النموذج المقيَّد نفسه باستخدام IndependentSet(G).to_optimization_problem().

أخيرًا، حوّل QUBO إلى صيغة القاموس باستخدام to_problem_dict(). ولأن المسألة QUBO ثنائية، يعلن الطلب في الخطوة 2 مجال متغيراتها بالقيمة "binary". تجري الدالة presolve والربط الكمي وبناء الدوائر بعد الإرسال.

mis = OptimizationProblem(INSTANCE_NAME)
mis.binary_var_list(G.number_of_nodes(), name="x")
mis.maximize(linear={v: 1 for v in G.nodes})
for u, v in G.edges:
    mis.linear_constraint({u: 1, v: 1}, "<=", 1)

converter = OptimizationProblemToQubo(penalty=2)
qubo = converter.convert(mis)
problem_dict = to_problem_dict(qubo)

print(f"QUBO variables: {qubo.get_num_vars()}")
print(f"Dictionary entries: {len(problem_dict)}")

QUBO variables: 200
Dictionary entries: 2191

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

ينفذ SQOA Solver الربط الكمي وتحضير العتاد داخل الدالة. فهو يطبّق أولًا presolve على QUBO، ثم يربط المتغيرات المتبقية بهاميلتوني مخفف باستخدام ترميز معتمد على QRAC.

لأخذ العينات الكمي، ينشئ دوائر مبنية على الهاميلتوني المخفف ويحوّلها للـ backend المختار. يعتمد الانخفاض في حجم المسألة وعدد الكيوبتات الناتج عن presolve والترميز على المسألة، لذا اضبط الحلّال دون افتراض عامل اختزال ثابت.

اضبط مدخلات الحلّال

يتطلب SQOA Solver مدخلين:

• problem، وهو القاموس من الخطوة 1.

• variable_type، وقيمته "binary" لهذه QUBO.

ويقبل أيضًا مدخلين اختياريين:

• يحدد backend_name الـ QPU. وعند حذفه أو عندما يكون None، تختار الدالة أقل QPU تشغيلي ازدحامًا ويمكن لمثيلك الوصول إليه.

• options هو قاموس يتحكم في ميزانية أخذ العينات (shots)، والبذرة الكلاسيكية (seed)، واستخدام الجلسة (session)، والبحث المحلي الكلاسيكي (postprocessing_level)، ووسوم المهام (job_tags). إذا زدت shots، يمكن أن تتحسن إحصاءات أخذ العينات.

لمعرفة جميع المدخلات وقيمها الافتراضية وقواعد التحقق، راجع مرجع API.

يسمّي هذا الدرس الـ backend صراحةً، ويستخدم القيم الافتراضية لـ shots وsession وpostprocessing_level، ويضبط البذرة الكلاسيكية. اجمع المدخلات في قاموس لتتمكن من تمريرها إلى solver.run() في الخطوة 3.

# ibm_fez has 156 qubits
backend_name = (
    "ibm_fez"  # Omit this key or pass None for automatic selection.
)

sqoa_input = {
    "problem": problem_dict,
    "variable_type": "binary",
    "backend_name": backend_name,
}

sqoa_input["options"] = {
    "shots": 4096,
    "seed": 42,
    "session": False,
    "postprocessing_level": 1,
}

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

أرسل المهمة باستخدام اتصال SQOA Solver الذي أنشأته في الخطوة 1. تشغّل الدالة Sampler من IBM Quantum على الـ backend المختار، وتجمع سلاسل البتات المقاسة، ثم تواصل بالقطرنة الكلاسيكية والمعالجة اللاحقة. أنت تتعامل مع مهمة دالة واحدة.

job = solver.run(**sqoa_input)
print(f"Job ID: {job.job_id}")

Job ID: dcee8e26-b8ac-4dd7-a76e-5adb5bc388e5

للتحقق من حالة عبء العمل، راجع التحقق من حالة المهمة. داخليًا، تمر الدالة بمراحل الربط وتحسين العتاد وانتظار الطابور وتنفيذ QPU والمعالجة اللاحقة.

job.status()

'INITIALIZING'

يتوقف job.result() حتى تكتمل المهمة ويعيد قاموسًا يحتوي على الحل وقيمة دالة الهدف وجدواه وبيانات وصفية تحمل معلومات الحلّال واستخدام الموارد. للتعريف الكامل للمدخلات والمخرجات، راجع مرجع API.

result = job.result()

الخطوة 4: المعالجة اللاحقة للنتيجة وتحويلها إلى صيغة كلاسيكية

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

افحص النتيجة

يحتوي قاموس النتيجة على أربعة حقول من المستوى الأعلى:

• solution هو التعيين الكامل للمتغيرات، ومفتاحه x_i، حيث i هو فهرس المتغير (مثلًا x_17). في هذا الدرس، فهرس المتغير هو تسمية العقدة.

• objective_value هي قيمة دالة الهدف لذلك التعيين مقيَّمة على القاموس المرسَل، أي على QUBO التصغير.

• يشير feasible إلى مجال المتغيرات فقط، لأن القاموس لا يحتوي على قيود.

• يحتوي metadata على solver_info وresource_usage. يسجل solver_info قيمة seed الفعلية للتشغيل. وإذا جرى البحث المحلي الكلاسيكي، يسجل solver_info أيضًا التعيين المقرَّب الذي سبق ذلك التحسين في solution_before_postprocessing.

solver_info = result["metadata"]["solver_info"]

print(f"Result fields: {list(result)}")
print(f"Solution entries: {len(result['solution'])}")
print(f"First entries: {dict(list(result['solution'].items())[:3])}")
print(f"Objective value: {result['objective_value']}")
print(f"Feasible: {result['feasible']}")
print(f"Solver-info fields: {list(solver_info)}")
print(f"Effective seed: {solver_info['seed']}")
print(f"Resource-usage phases: {list(result['metadata']['resource_usage'])}")

Result fields: ['solution', 'objective_value', 'feasible', 'metadata']
Solution entries: 200
First entries: {'x_0': 0.0, 'x_1': 0.0, 'x_2': 1.0}
Objective value: -35.0
Feasible: True
Solver-info fields: ['seed', 'solution_before_postprocessing']
Effective seed: 42
Resource-usage phases: ['RUNNING: MAPPING', 'RUNNING: OPTIMIZING_FOR_HARDWARE', 'RUNNING: WAITING_FOR_QPU', 'RUNNING: EXECUTING_QPU', 'RUNNING: POST_PROCESSING']

اربط الحل بالرسم البياني

اجمع القيم المُعادة بترتيب فهارس المتغيرات، واربطها بمتغيرات المسألة الأصلية باستخدام interpret(). العقد المختارة هي المتغيرات ذات القيمة 1، ويتحقق is_feasible() من التعيين مقابل قيود الحواف في المسألة الأصلية.

x_qubo = [result["solution"][f"x_{i}"] for i in range(qubo.get_num_vars())]
x = converter.interpret(x_qubo)
selected_nodes = [node for node, value in enumerate(x) if value > 0.5]

print(f"Selected nodes: {len(selected_nodes)}")
print(f"Satisfies every edge constraint: {mis.is_feasible(x)}")

Selected nodes: 35
Satisfies every edge constraint: True

قارن مع الحل قبل المعالجة اللاحقة

ولأن postprocessing_level يساوي 1، يسجل solver_info أيضًا التعيين المقرَّب السابق للبحث المحلي الكلاسيكي في solution_before_postprocessing. ويستخدم المفاتيح نفسها المستخدمة في solution.

قيّمه على QUBO لترى مقدار تحسين النتيجة بفضل التنقيح. كلتا القيمتين هما قيمتا دالة الهدف لـ QUBO التصغير المرسَلة، لذا فالقيمة الأقل أفضل. يُحذف الحقل عندما لا يجري البحث المحلي، مثلًا عندما يثبّت presolve كل متغير.

before = solver_info.get("solution_before_postprocessing")
if before is None:
    print("The classical local search did not run for this problem.")
else:
    x_before = [before[f"x_{i}"] for i in range(qubo.get_num_vars())]
    changed = sum(
        before[key] != value for key, value in result["solution"].items()
    )
    print(
        f"Objective before local search: {qubo.objective.evaluate(x_before)}"
    )
    print(f"Objective after local search: {result['objective_value']}")
    print(f"Variables changed by local search: {changed}")

Objective before local search: -12.0
Objective after local search: -35.0
Variables changed by local search: 19

تحقق من قيد الاستقلال

لأن QUBO تمثّل التجاور عبر حدود العقوبة بدلًا من قيود صريحة، فقد تختار النتيجة الاستدلالية عقدًا متجاورة. افحص العقد المُعادة مباشرةً مقابل الرسم البياني. وللمقارنة والتصوير في الأقسام التالية، انسخ المجموعة المُعادة وأزل بجشع أحد طرفي كل تعارض مكتشَف.

returned_set = set(selected_nodes)
conflicts = [
    (u, v) for u, v in G.edges if u in returned_set and v in returned_set
]
print(f"Conflicting edges in the returned set: {len(conflicts)}")

independent_set = returned_set.copy()
for u, v in conflicts:
    if u in independent_set and v in independent_set:
        # Drop the endpoint that has more selected neighbors.
        drop = max(
            (u, v),
            key=lambda node: sum(nb in independent_set for nb in G[node]),
        )
        independent_set.remove(drop)

assert all(
    not (u in independent_set and v in independent_set) for u, v in G.edges
)
print(f"Independent set size after repair: {len(independent_set)}")

Conflicting edges in the returned set: 0
Independent set size after repair: 35

قارن مع الحل المرجعي

في الخطوة 1، نزّلت قيمة دالة الهدف لـ الحل المرجعي في QOBLIB. قد تكون الحلول المرجعية في QOBLIB مثلى أو الأفضل المعروفة، لذا قارن بقيمة دالة الهدف المرجعية دون افتراض أنها دائمًا أمثل مؤكَّد.

في مسألة التعظيم هذه، تعني النسبة 1.0 أن النتيجة المصلَّحة تطابق قيمة دالة الهدف المرجعية.

ratio_to_reference = len(independent_set) / reference_objective

print(f"Reference objective: {reference_objective:g}")
print(f"Ratio to reference: {ratio_to_reference:.3f}")

Reference objective: 44
Ratio to reference: 0.795

تصوّر النتيجة

ارسم الرسم البياني مرة أخرى مع إبراز المجموعة المستقلة المصلَّحة. لا تشترك أي عقدتين مبرزتين في حافة.

fig, ax = plt.subplots(figsize=(9, 7))
nx.draw_networkx_edges(G, layout, ax=ax, alpha=0.2, width=0.6)
nx.draw_networkx_nodes(
    G,
    layout,
    nodelist=[v for v in G if v not in independent_set],
    node_size=node_size,
    node_color="lightgray",
    ax=ax,
)
nx.draw_networkx_nodes(
    G,
    layout,
    nodelist=sorted(independent_set),
    node_size=node_size * 1.4,
    node_color="tab:blue",
    ax=ax,
)
ax.set_title(
    f"Independent set size: {len(independent_set)} "
    f"(reference: {reference_objective:g})"
)
ax.set_axis_off()
plt.show()

اقرأ استخدام الموارد

تبلّغ البيانات الوصفية للنتيجة عن CPU_TIME للمراحل غير RUNNING: EXECUTING_QPU، عندما يكون متاحًا. ويمكن لمرحلة RUNNING: EXECUTING_QPU أن تبلّغ عن QPU_TIME، وهو استخدام QPU الذي تعيده Quantum Compute، إذا كان الاستخدام النهائي متاحًا لكل مهمة Quantum Compute.

usage = result["metadata"]["resource_usage"]

for phase, metrics in usage.items():
    line = f"{phase:36s}"
    if "CPU_TIME" in metrics:
        line += f" CPU {metrics['CPU_TIME']:8.1f} s"
    if "QPU_TIME" in metrics:
        line += f" QPU {metrics['QPU_TIME']:8.1f} s"
    print(line)

RUNNING: MAPPING                     CPU     11.8 s
RUNNING: OPTIMIZING_FOR_HARDWARE     CPU     15.4 s
RUNNING: WAITING_FOR_QPU             CPU     16.5 s
RUNNING: EXECUTING_QPU               QPU      3.0 s
RUNNING: POST_PROCESSING             CPU     55.8 s

الخلاصة

في هذا الدرس التعليمي، نزّلتَ نسخة مسألة MIS من QOBLIB، وصغتها على شكل QUBO باستخدام qiskit-addon-opt-mapper، واتصلتَ بـ SQOA Solver، وضبطتَ حمل العمل وأرسلته، وأعدتَ ربط التعيين المُرجَع بالرسم البياني، وتحققتَ من العُقد المختارة مقابل الرسم البياني الأصلي.

كما قارنتَ النتيجة بالحل المرجعي من QOBLIB، وفحصتَ مساهمة المعالجة اللاحقة الكلاسيكية، وراجعتَ استهلاك الموارد في كل مرحلة من مراحل التنفيذ.

يجمع SQOA Solver بين المعالجة المسبقة (presolve)، وQRAO مع ترميز قائم على QRAC، وبناء دوائر أخذ العينات، والتحويل (transpilation) المراعي للعتاد، والقطرنة المعتمدة على العينات، والتقريب، والتحسين الكلاسيكي. يمكن لهذا سير العمل أن يربط عددًا أكبر من المتغيرات الثنائية مما يتيحه ترميز متغير واحد لكل كيوبت. يعتمد مقدار التقليل الناتج عن المعالجة المسبقة والترميز على بنية المسألة، وتعتمد جودة الحل على العينات التي يتم الحصول عليها.

يتحكم الإعدادان shots وpostprocessing_level في ميزانية أخذ العينات الكمومية وفي التحسين الكلاسيكي على التوالي، دون تغيير سير عمل الإرسال.

ملحق: إرسال المسألة كنسخة OMMX

يقبل SQOA Solver أيضًا ommx.v1.Instance من حزمة OMMX SDK. توزّع حزمة OMMX Quantum Benchmarks مسائل QOBLIB على شكل نسخ OMMX مع حلولها المرجعية، لذا يمكنك تحميل QUBO نفسه دون صياغته بنفسك.

مع مدخل OMMX، تُحسب objective_value وفق مفهوم النسخة، وتحتوي النتيجة أيضًا على ommx.v1.Solution القياسي. ثبّت الحزمة، التي تثبّت أيضًا OMMX SDK:

# %pip install ommx-quantum-benchmarks

حمّل النموذج binary_unconstrained من النسخة نفسها. يطبع محمّل مجموعة البيانات رسائل التقدم، لذا يلتقطها الكود للحفاظ على إيجاز المخرجات.

%%capture
from ommx_quantum_benchmarks.qoblib import IndependentSet

ommx_instance, _ = IndependentSet()("binary_unconstrained", INSTANCE_NAME)

يتلقى SQOA Solver نسخة OMMX على شكل سلسلة Base64 قياسية مع الحشو، ويُرجع الحل القياسي بالصيغة نفسها. عرّف دالتين مساعدتين لهذا التحويل:

• تُسلسِل to_problem_payload() الكائن ommx.v1.Instance إلى السلسلة التي تمررها كـ problem.

• تفك to_ommx_solution() ترميز ommx.v1.Solution القياسي من النتيجة.

import base64

from ommx.v1 import Instance, Solution

def to_problem_payload(instance: Instance) -> str:
    """Serialize an OMMX instance into the `problem` string for SQOA Solver."""
    return base64.b64encode(instance.to_bytes()).decode()

def to_ommx_solution(result: dict) -> Solution:
    """Decode the canonical OMMX solution from a SQOA Solver result."""
    payload = result["metadata"]["solver_info"]["ommx_solution"]
    return Solution.from_bytes(base64.b64decode(payload, validate=True))

أرسل النسخة بالمدخلات نفسها كما سبق، مع استبدال problem فقط. ثم فك ترميز الحل القياسي واقرأ العُقد المختارة بحسب اسم المتغير.

ommx_job = solver.run(
    **{**sqoa_input, "problem": to_problem_payload(ommx_instance)}
)
ommx_result = ommx_job.result()

ommx_solution = to_ommx_solution(ommx_result)
x_values = ommx_solution.extract_decision_variables("x")
ommx_nodes = sorted(
    node for (node,), value in x_values.items() if value > 0.5
)

print(f"Objective value: {ommx_result['objective_value']}")
print(f"Selected nodes: {len(ommx_nodes)}")

Objective value: 35.0
Selected nodes: 35

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

توصيات

• طبّق سير العمل على مسائل QUBO الخاصة بك. ابنِ OptimizationProblem كما هو موضح في دليل SQOA Solver. تبقى خطوات التحويل والإرسال كما هي، لكن كيّف التحقق مع بنية مسألتك.
• أرسل المسألة كنسخة OMMX، كما هو موضح في الملحق. راجع مرجع API لمعرفة صيغ المسائل المقبولة والحقول المُرجَعة.
• استكشف نسخًا أخرى من مسائل المجموعة المستقلة في مستودع QOBLIB أو عبر OMMX Quantum Benchmarks.
• تعرّف أكثر على النمذجة باستخدام qiskit-addon-opt-mapper أو JijModeling وعلى تبادل المسائل عبر OMMX.

المراجع

[1] Koch, T., Bernal Neira, D. E., Chen, Y., Cortiana, G., Egger, D. J., Heese, R., Hegade, N. N., Gomez Cadavid, A., Huang, R., Itoko, T., et al. (2026). Quantum optimization benchmarking library: The intractable decathlon. Nature Computational Science, 6, 653–671. DOI, arXiv:2504.03832

[2] Matsuyama, H., & Yamashiro, Y. (2025). Sampling-based quantum optimization algorithm with quantum relaxation. 2025 IEEE International Conference on Quantum Computing and Engineering (QCE), 1, 2323–2333. DOI, arXiv:2504.12629

[3] Fuller, B., Hadfield, C., Glick, J. R., Imamichi, T., Itoko, T., Thompson, R. J., Jiao, Y., Kagele, M. M., Blom-Schieber, A. W., Raymond, R., et al. (2024). Approximate solutions of combinatorial problems via quantum relaxations. IEEE Transactions on Quantum Engineering, 5, 1–15. DOI, arXiv:2111.03167

[4] Kanno, K., Kohda, M., Imai, R., Koh, S., Mitarai, K., Mizukami, W., & Nakagawa, Y. O. (2026). Quantum-selected configuration interaction: Classical diagonalization of Hamiltonians in subspaces selected by quantum computers. Physical Review Research, 8(2), 023268. DOI, arXiv:2302.11320

[5] Robledo-Moreno, J., Motta, M., Haas, H., Javadi-Abhari, A., Jurcevic, P., Kirby, W., et al. (2025). Chemistry beyond the scale of exact diagonalization on a quantum-centric supercomputer. Science Advances, 11(25), eadu9991. DOI, arXiv:2405.05068