מציאת הקבוצה הבלתי-תלויה המקסימלית עם Aqarios Constrained Quantum Optimizer

הערה

Qiskit Functions הן תכונה ניסיונית הזמינה רק למשתמשי IBM Quantum® בתוכנית Premium Plan, Flex Plan, ו-On-Prem (דרך IBM Quantum Platform API). הן נמצאות במעמד גרסת תצוגה מקדימה (preview) וכפופות לשינויים.

הערכת שימוש: 30 שניות על מעבד Heron r2. (הערה: זוהי הערכה בלבד. זמן הריצה שלכם עשוי להשתנות.)

רקע

מדריך זה מדגים כיצד למצוא את הקבוצה הבלתי-תלויה המקסימלית של גרף באמצעות Aqarios Constrained Quantum Optimizer [1], בעיית אופטימיזציה קומבינטורית מוגבלת. מופע מספריית המידוד QOBLIB [2] מנוסח כתוכנית לינארית בינארית ומועבר לפונקציית היישום של האופטימייזר. האופטימייזר מטפל באופן פנימי בכל שלבי הניסוח מחדש, סינתזת המעגל, הטרנספילציה וההתחלה החמה האיטרטיבית (ראו [3] לפרטים).

המדריך מכסה את השלבים הבאים:

הגדרת הבעיה כתוכנית לינארית באמצעות OptimizationProblem מ-qiskit-addon-opt-mapper
הרצת האופטימיזציה הקוונטית באמצעות Aqarios Constrained Quantum Optimizer
אחזור והדמיה של התוצאות

בעיית הקבוצה הבלתי-תלויה המקסימלית

בעיית הקבוצה הבלתי-תלויה המקסימלית (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{s.t.} \quad x_u + x_v \leq 1 \quad \forall (u, v) \in E.

ל-MIS יש מגוון רחב של יישומים מעשיים. בתכנון רשתות אלחוטיות, קבוצה בלתי-תלויה מתאימה לקבוצת משדרים שיכולים לשדר כולם בו-זמנית ללא הפרעה הדדית. בתזמון, היא מדגמת את האוסף הגדול ביותר של משימות שיכולות לפעול בו-זמנית בהינתן קונפליקטים זוגיים במשאבים. בביולוגיה חישובית, היא לוכדת קבוצות של חלבונים שאינם מתקשרים זה עם זה ברשת.

למרות הניסוח האינטואיטיבי שלה, בעיית MIS היא NP-קשה, ואפילו עבור גרפים עם מאות בודדות של צמתים, מופעים מסוימים הופכים קשים לפתרון באופן מדויק או היוריסטי [2]. הבעיה גם יוצרת מבני אילוצים דלילים המתאימים היטב למימושי חומרה של אופטימיזציה קוונטית, מה שהופך אותה לאמת מידה אטרקטיבית עבור התקנים קוונטיים בטווח הקרוב.

Aqarios Constrained Quantum Optimizer

הגישה הסטנדרטית לשילוב בעיה בינארית מוגבלת באופטימיזציה קוונטית ממירה את המודל לפורמט בלתי-מוגבל על ידי הוספת איברי קנס: כל אילוץ מופר $x_u + x_v \leq 1$ תורם $2 x_u x_v$ ליעד המינימיזציה $-\sum_i x_i$ . זה מטופל אוטומטית על ידי Constrained Quantum Optimizer 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) $y$ הופכת זאת לשוויון $\sum_i x_i + y = 1$ , שלובש צורה של אילוץ one-hot שניתן לאכוף ישירות ב-QAOA באמצעות מערבלי XY (XY-mixers) [3]. זה מצמצם את מרחב החיפוש ומונע את הצורך באיברי קנס עבור אילוצים אלו, ומשפר את איכות הפתרון.

בנוסף, משתנים המחוברים לשכן יחיד בלבד נקראים צמתי pendant ומקובעים באופן דטרמיניסטי על ידי האלגוריתם לפני הביצוע הקוונטי, מה שמצמצם עוד יותר את גודל הבעיה האפקטיבי.

ה-Constrained Quantum Optimizer מיישם גישת התחלה חמה איטרטיבית (iterative warm-starting) התואמת למערבלי XY [1], אשר מצמצמת בהדרגה את מרחב החיפוש על ידי הטיית התפלגות המצב הקוונטי לעבר אזורי פתרון מבטיחים לאורך האיטרציות. זה מאפשר שימוש בפרמטרים של QAOA בזווית קבועה, ומייתר את הצורך באימון פרמטרים ואריאציוני. דרישות המשאב הקוונטי הכולל נקבעות אך ורק על ידי מספר איטרציות ההתחלה החמה, כלומר קל לשלוט בעלות הקוונטית.

דרישות

לפני תחילת המדריך, ודאו שהתקנתם את הדרישות הבאות:

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

ראשית, בצעו אימות באמצעות מפתח ה-API של IBM Quantum שלכם. לאחר מכן, בחרו את 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, פורמט נפוץ לבעיות אופטימיזציה המשמש כקלט ל-Aqarios Constrained Quantum Optimizer. מלבד קובצי 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.

דוגמה זו משתמשת במופע es60fst02 מ-QOBLIB, גרף עם 186 צמתים ו-280 קשתות. הודות לשלבי העיבוד המקדים המיושמים על ידי ה-Constrained Quantum Optimizer, ניתן לפתור מופע זה על התקני 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
...

פורמט זה מובנה ל-Constrained Quantum Optimizer.

שלב 2: אופטימיזציה של הבעיה לביצוע על חומרה קוונטית

כל סינתזת המעגל, האופטימיזציה והטרנספילציה מטופלות באופן מובנה על ידי הפונקציה. ראו את חלק הקלטים בהפניית ה-API לארגומנטים שאיתם יש לקרוא לפונקציה.

כדי לכוונן במדויק את התנהגות האלגוריתם, ראו את רשימת האפשרויות בהפניית ה-API. אם אתם רוצים שמיפוי המעגל יהיה ניתן לשחזור בין הרצות, קבעו את האפשרות seed_transpiler.

למידע נוסף, ראו את מדריך Aqarios Constrained Quantum Optimizer ואת הפניית ה-API.

שלב 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:
- מציאת הדגימות הטובות ביותר ובדיקת ישימות ביחס לבעיית הקלט

מעקב אחר ההתקדמות

ראו את הסעיפים הבאים בעמוד Get started with Qiskit Functions כדי לעקוב אחר התקדמות המשימה שלכם:

# Monitor the job status
job.status()

'QUEUED'

שלב 4: עיבוד לאחר-ביצוע והחזרת התוצאות בפורמט הקלאסי הרצוי

פלט התוצאה הוא מילון, ששדותיו מתוארים בחלק הפלטים של הפניית ה-API.

כאשר רשימת 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 Model

בנוסף לגישת qiskit-addon-opt-mapper שהוצגה לעיל, Qiskit Function מקבלת גם מודלים שנוצרו עם Luna Model [4], ה-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 לרשימה המלאה של פרמטרי הקלט ושדות הפלט.
נסו את אפשרויות האלגוריתם (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 Constrained Quantum Optimizer​

דרישות​

הגדרה​

שלב 1: מיפוי קלטים קלאסיים לבעיה קוונטית​

טעינת גרף מופע הבעיה​

בניית בעיית האופטימיזציה​

קיצור דרך​

תרגום הבעיה לקובץ LP​

שלב 2: אופטימיזציה של הבעיה לביצוע על חומרה קוונטית​

שלב 3: ביצוע באמצעות פרימיטיבים של Qiskit​

מעקב אחר ההתקדמות​

שלב 4: עיבוד לאחר-ביצוע והחזרת התוצאות בפורמט הקלאסי הרצוי​

הדמיה​

נספח: ניסוח הבעיה עם Luna Model​

צעדים הבאים​

מקורות​

רקע