פתרון בעיית קבוצה בלתי תלויה מקסימלית עם יותר משתנים מ-Qubits באמצעות 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) עם יותר משתנים בינאריים ממספר ה-Qubits ב-QPU שנבחר. השלבים הבסיסיים הם לטעון מופע MIS מתוך Quantum Optimization Benchmarking Library (QOBLIB) [1], לנסח אותו בצורת אופטימיזציה בינארית ריבועית ללא אילוצים (QUBO) באמצעות qiskit-addon-opt-mapper, לשלוח אותו ל-SQOA Solver להרצה על QPU של IBM®, ולאמת את הפתרון שמוחזר.

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

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

MIS היא בעיה NP-קשה. בחיפוש ממצה, כל צומת נוסף מכפיל את מספר תת-הקבוצות שיש לשקול, ולכן גישה זו אינה מעשית אפילו עבור גרפים בגודל בינוני. 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?

גישות רבות לאופטימיזציה קוונטית מקצות Qubit אחד לכל משתנה בינארי, ולכן קיבולת החומרה הקוונטית יכולה להגביל ישירות את גודל הבעיה. SQOA Solver משלב כמה טכניקות הקטנה וחישוב היברידי כדי להקל על המגבלה הזו:

• הוא יכול להתמודד עם בעיות שיש בהן יותר משתנים בינאריים מ-Qubits ב-QPU. Presolve מפעיל כללי הקטנה שיכולים לקבע משתנים ולפשט את ה-QUBO שנותר, תוך שמירה על לפחות פתרון אופטימלי אחד. מבחינה אמפירית, presolve יכול גם להפוך את ה-QUBO שנותר לדליל יותר, מה שעוזר לקידוד מבוסס QRAC שבא אחריו.

  לאחר מכן הפותר משתמש בקידוד מבוסס QRAC שנגזר מ-Quantum Random Access Optimization (QRAO) [3] כדי לייצג כמה משתנים (עד שלושה) ללא אינטראקציית QUBO ישירה על אותו Qubit.

  ההקטנות שמתקבלות מ-presolve ומהקידוד תלויות במבנה הבעיה. לדוגמה, במדריך הזה בעיה בת 200 משתנים משתמשת ב-67 Qubits בלבד.

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

• הוא מבצע אוטומציה של זרימת העבודה מ-presolve ועד לעיבוד לאחר. אתם מספקים מופע QUBO בפורמט נכון ובוחרים Backend. SQOA Solver מריץ אז את כל זרימת העבודה באופן אוטומטי. הוא מפעיל presolve, ממפה את המשתנים הקלאסיים לבעיה קוונטית רפויה, בונה ומבצע transpile למעגלי הדגימה, מבצע דגימה קוונטית ואלכסון קלאסי, מעגל ומשכלל את ההשמה, ומשחזר ומעריך את הפתרון הקלאסי.

דרישות

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

• לקוח Qiskit Functions Catalog (pip install qiskit-ibm-catalog).

• Qiskit addon optimization mapper, המשמש לניסוח הבעיה (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 כמילון מקדמים בפורמט tuple-string שבו משתמשות פונקציות האופטימיזציה של 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

Sampling-based Quantum Optimization Algorithm with Quantum Relaxation (SQOA-QR) [2] משלב Quantum Random Access Optimization (QRAO) עם אלכסון קוונטי מבוסס דגימות:

1. הרפיה קוונטית וקידוד: SQOA Solver ממיר את ה-QUBO לפונקציית מטרה של מינימיזציית Ising מהצורה $c + \sum_i h_i z_i + \sum_{i<j} J_{ij} z_i z_j$, כאשר $z_i \in \{-1, +1\}$. לאחר מכן QRAO [3] ממפה כל משתנה ספין לאובזרבבל של Pauli. עבור קידוד $(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$ ל-Qubit ולאחד מ-$X$, $Y$ או $Z$, ו-$k_i \in \{1,2,3\}$ הוא מספר המשתנים הממופים לאותו Qubit כמו $i$. כששני ה-Qubits הרלוונטיים מכילים שלושה משתנים כל אחד, גורמי הקנה מידה הליניארי והריבועי הופכים ל-$\sqrt{3}$ ו-$3$, בהתאמה.

   משתנים החולקים Qubit מוקצים לאובזרבבלים של Pauli שאינם מתחלפים. משתנים שיש ביניהם אינטראקציה ב-QUBO נשמרים על Qubits שונים, ואילו משתנים ללא אינטראקציית QUBO ישירה יכולים לחלוק Qubit. לכן ההקטנה במספר ה-Qubits תלויה במבנה הבעיה.

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

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.

לצורך דגימה קוונטית, הוא בונה מעגלים המבוססים על ההמילטוניאן הרפוי ומבצע להם transpile עבור ה-Backend שנבחר. ההקטנות בגודל הבעיה ובמספר ה-Qubits מ-presolve ומהקידוד תלויות בבעיה, ולכן הגדירו את הפותר בלי להניח גורם הקטנה קבוע.

הגדרת קלטי הפותר

SQOA Solver דורש שני קלטים:

• problem, המילון משלב 1.

• variable_type, שהוא "binary" עבור ה-QUBO הזה.

הוא מקבל גם שני קלטים אופציונליים:

• backend_name בוחר את ה-QPU. כשהוא מושמט או שווה ל-None, הפונקציה בוחרת את ה-QPU הפעיל הפנוי ביותר שנגיש למופע שלכם.

• options הוא מילון ששולט בתקציב הדגימה (shots), בזרע הקלאסי (seed), בשימוש ב-Session (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: הרצה באמצעות פרימיטיבים

שולחים את העבודה עם החיבור ל-SQOA Solver שנוצר בשלב 1. הפונקציה מריצה את הפרימיטיב IBM Quantum Sampler על ה-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, בניית מעגלי דגימה, טרנספילציה מותאמת חומרה, אלכסון מבוסס דגימות, עיגול ושיפור קלאסי. תהליך עבודה זה יכול למפות יותר משתנים בינאריים ממה שקידוד של משתנה אחד לכל Qubit היה מאפשר. כמות הצמצום שמתקבלת מ-presolve ומהקידוד תלויה במבנה הבעיה, ואיכות הפתרון תלויה בדגימות שהתקבלו.

ההגדרות shots ו-postprocessing_level שולטות בתקציב הדגימה הקוונטית ובשיפור הקלאסי, בהתאמה, בלי לשנות את תהליך השליחה.

נספח: שליחת הבעיה כמופע OMMX

SQOA Solver מקבל גם ommx.v1.Instance מ-SDK של OMMX. החבילה OMMX Quantum Benchmarks מפיצה את בעיות QOBLIB כמופעי OMMX יחד עם פתרונות הייחוס שלהן, כך שאפשר לטעון את אותו QUBO בלי לנסח אותו בעצמך.

עם קלט OMMX, הערך objective_value מחושב לפי המופע, והתוצאה מכילה גם את ommx.v1.Solution הקנוני. התקן את החבילה, שמתקינה גם את ה-SDK של OMMX:

# %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