פתרון בעיית פיצול השוק עם Iskay Quantum Optimizer של Kipu Quantum

הערה

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

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

רקע

מדריך זה מדגים כיצד לפתור את בעיית פיצול השוק באמצעות Iskay quantum optimizer של Kipu Quantum [1]. בעיית פיצול השוק מייצגת אתגר אמיתי של הקצאת משאבים, שבו יש לחלק שווקים לאזורי מכירה מאוזנים כדי לעמוד ביעדי ביקוש מדויקים.

אתגר פיצול השוק

בעיית פיצול השוק מציגה אתגר שנראה פשוט אך קשה חישובית בתחום הקצאת משאבים. נתונה חברה עם $m$ מוצרים הנמכרים ב-$n$ שווקים שונים, כאשר כל שוק רוכש חבילת מוצרים ספציפית (המיוצגת על ידי עמודות המטריצה $A$). יעד העסק הוא לחלק את השווקים הללו לשני אזורי מכירה מאוזנים, כך שכל אזור יקבל בדיוק מחצית מהביקוש הכולל לכל מוצר.

ניסוח מתמטי:

אנחנו מחפשים וקטור השמה בינארי $x$, שבו:

• $x_j = 1$ משייך את שוק $j$ לאזור A
• $x_j = 0$ משייך את שוק $j$ לאזור B
• האילוץ $Ax = b$ חייב להתקיים, כאשר $b$ מייצג את יעדי המכירות (בדרך כלל מחצית מהביקוש הכולל לכל מוצר)

פונקציית העלות:

לפתרון הבעיה, אנחנו ממזערים את הפרת האילוץ בריבוע:

$C(x) = ||Ax - b||^2 = \sum_{i=1}^{m} \left(\sum_{j=1}^{n} A_{ij}x_j - b_i\right)^2$

כאשר:

• $A_{ij}$ מייצג את המכירות של מוצר $i$ בשוק $j$
• $x_j \in \{0,1\}$ הוא ההשמה הבינארית של שוק $j$
• $b_i$ הוא יעד המכירות למוצר $i$ בכל אזור
• העלות שווה לאפס בדיוק כאשר כל האילוצים מתקיימים

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

$C(x) = x^T A^T A x - 2b^T A x + b^T b$

מאחר ש-$b^T b$ הוא קבוע, מיזור $C(x)$ שקול למיזור הפונקציה הריבועית $x^T A^T A x - 2b^T A x$, שהיא בדיוק בעיית QUBO (אופטימיזציה בינארית ריבועית ללא אילוצים).

מורכבות חישובית:

למרות הפרשנות העסקית הפשוטה שלה, הבעיה מציגה קושי חישובי ניכר:

• כישלון בקנה מידה קטן: פותרי תכנות שלם מעורב (Mixed Integer Programming) קונבנציונליים נכשלים על מופעים עם כמה שבעה מוצרים בלבד תחת פסק זמן של שעה אחת [4]
• גידול אקספוננציאלי: מרחב הפתרונות גדל באופן אקספוננציאלי ($2^n$ השמות אפשריות), מה שהופך גישות כוח גס לבלתי ישימות

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

מה הופך את גישת Iskay לייחודית?

מייעל Iskay משתמש באלגוריתם bf-DCQO (אופטימיזציה קוונטית קאונטר-דיאבטית דיגיטלית עם שדה הטיה) [1], המהווה התקדמות משמעותית באופטימיזציה קוונטית:

יעילות מעגל: אלגוריתם bf-DCQO משיג צמצום שערים משמעותי [1]:

• עד 10 פעמים פחות שערי סיבוך מאשר Digital Quantum Annealing (DQA)
• מעגלים רדודים משמעותית מאפשרים:
  • פחות הצטברות שגיאות במהלך הביצוע הקוונטי
  • יכולת להתמודד עם בעיות גדולות יותר על חומרה קוונטית נוכחית
  • אין צורך בטכניקות הפחתת שגיאות

עיצוב לא-ווריאציוני: בניגוד לאלגוריתמים ווריאציוניים הדורשים כ-100 איטרציות, bf-DCQO בדרך כלל זקוק רק לכ-10 איטרציות [1]. זה מושג באמצעות:

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

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

דרישות מקדימות

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

• Qiskit IBM Runtime (pip install qiskit-ibm-runtime)
• Qiskit Functions (pip install qiskit-ibm-catalog)
• NumPy (pip install numpy)
• Requests (pip install requests)
• Opt Mapper Qiskit addon (pip install qiskit-addon-opt-mapper)

כמו כן, יש להשיג גישה לפונקציית Iskay Quantum Optimizer מקטלוג פונקציות Qiskit.

הגדרה

ראשית, ייבא את כל החבילות הנדרשות למדריך זה.

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit-addon-opt-mapper qiskit-ibm-catalog requests

import os
import tempfile
import time
from typing import Tuple, Optional

import numpy as np
import requests

from qiskit_ibm_catalog import QiskitFunctionsCatalog

from qiskit_addon_opt_mapper import OptimizationProblem
from qiskit_addon_opt_mapper.converters import OptimizationProblemToQubo

print("All required libraries imported successfully")

הגדרת פרטי גישה ל-IBM Quantum

הגדר את פרטי הגישה ל-IBM Quantum® Platform. תזדקק ל:

• API Token: מפתח ה-API בן 44 התווים שלך מ-IBM Quantum Platform
• Instance CRN: מזהה מופע IBM Cloud® שלך

token = "<YOUR_API_KEY>"
instance = "<YOUR_INSTANCE_CRN>"

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

אנחנו מתחילים במיפוי הבעיה הקלאסית שלנו לייצוג תואם-קוונטי. שלב זה כולל:

1. התחברות ל-Iskay Quantum Optimizer
2. טעינת בעיית פיצול השוק וניסוחה
3. הבנת אלגוריתם bf-DCQO שיפתור אותה

התחברות ל-Iskay Quantum Optimizer

אנחנו מתחילים בביסוס חיבור לקטלוג פונקציות Qiskit וטעינת Iskay Quantum Optimizer. מייעל Iskay הוא פונקציה קוונטית שסופקה על ידי Kipu Quantum ומממשת את אלגוריתם bf-DCQO לפתרון בעיות אופטימיזציה על חומרה קוונטית.

catalog = QiskitFunctionsCatalog(token=token, instance=instance)
iskay_solver = catalog.load("kipu-quantum/iskay-quantum-optimizer")

print("Iskay optimizer loaded successfully")
print("Ready to solve optimization problems using bf-DCQO algorithm")

טעינת הבעיה וניסוחה

הבנת פורמט נתוני הבעיה

מופעי בעיות מ-QOBLIB (ספריית בנצ'מרקים לאופטימיזציה קוונטית) [2] מאוחסנים בפורמט טקסט פשוט. בואו נבחן את התוכן הממשי של מופע היעד שלנו ms_03_200_177.dat:

3 20
60   92  161   53   97    2   75   81    6  139  132   45  108  112  181   93  152  200  164   51 1002
176  196   41  143    2   88    0   79   10   71   75  148   82  135   34  187   33  155   58   46  879
68   68  179  173  127  163   48   49   99   78   44   52  173  131   73  198   84  109  180   95 1040

מבנה הפורמט:

• שורה ראשונה: 3 20

  • 3 = מספר המוצרים (אילוצים/שורות במטריצה $A$)
  • 20 = מספר השווקים (משתנים/עמודות במטריצה $A$)

• 3 השורות הבאות: מטריצת המקדמים $A$ וקטור היעד $b$

  • כל שורה מכילה 21 מספרים: 20 הראשונים הם מקדמי השורה, האחרון הוא היעד
  • שורה 2: 60 92 161 ... 51 | 1002
    • 20 המספרים הראשונים: כמה ממוצר 1 כל אחד מ-20 השווקים מוכר
    • המספר האחרון (1002): יעד המכירות למוצר 1 באזור אחד
  • שורה 3: 176 196 41 ... 46 | 879
    • מכירות מוצר 2 לשוק ויעד (879)
  • שורה 4: 68 68 179 ... 95 | 1040
    • מכירות מוצר 3 לשוק ויעד (1040)

פרשנות עסקית:

• שוק 0 מוכר: 60 יחידות של מוצר 1, 176 יחידות של מוצר 2, 68 יחידות של מוצר 3
• שוק 1 מוכר: 92 יחידות של מוצר 1, 196 יחידות של מוצר 2, 68 יחידות של מוצר 3
• וכך הלאה עבור כל 20 השווקים...
• מטרה: לפצל 20 שווקים אלו לשני אזורים שבהם כל אזור מקבל בדיוק 1002 יחידות של מוצר 1, 879 יחידות של מוצר 2 ו-1040 יחידות של מוצר 3

המרה ל-QUBO

מאילוצים ל-QUBO: הטרנספורמציה המתמטית

כוחה של האופטימיזציה הקוונטית טמון בהמרת בעיות עם אילוצים לצורות ריבועיות ללא אילוצים [4]. עבור בעיית פיצול השוק, אנחנו ממירים את אילוצי השוויון

$Ax = b$

כאשר $x ∈ \{0,1\}^n$, ל-QUBO על ידי הטלת קנס על הפרות אילוצים.

שיטת הקנס: מכיוון שעלינו ש-$Ax = b$ יתקיים במדויק, אנחנו ממזערים את ההפרה בריבוע: $f(x) = ||Ax - b||^2$

זה שווה לאפס בדיוק כאשר כל האילוצים מתקיימים. הרחבה אלגברית: $f(x) = (Ax - b)^T(Ax - b) = x^T A^T A x - 2b^T A x + b^T b$

יעד QUBO: מאחר ש-$b^T b$ קבוע, האופטימיזציה שלנו הופכת ל: $\text{minimize} \quad Q(x) = x^T(A^T A)x - 2(A^T b)^T x$

תובנה מרכזית: טרנספורמציה זו היא מדויקת, לא משוערת. אילוצי שוויון מתרבעים באופן טבעי לצורה ריבועית ללא צורך במשתנים עזר או פרמטרי קנס — מה שהופך ניסוח זה לאלגנטי מתמטית ויעיל חישובית עבור פותרים קוונטיים [4]. נשתמש במחלקה OptimizationProblem להגדרת בעייתנו עם אילוצים, ולאחר מכן נמיר אותה לפורמט QUBO באמצעות OptimizationProblemToQubo, שניהם מחבילת qiskit_addon_opt_mapper. זה מטפל אוטומטית בטרנספורמציה מבוססת הקנס.

מימוש פונקציות טעינת נתונים והמרת QUBO

כעת נגדיר שתי פונקציות עזר:

1. parse_marketsplit_dat() - מנתחת את פורמט קובץ ה-.dat ומחלצת מטריצות $A$ ו-$b$
2. fetch_marketsplit_data() - מורידה מופעי בעיות ישירות מהמאגר של QOBLIB

def parse_marketsplit_dat(filename: str) -> Tuple[np.ndarray, np.ndarray]:
    """
    Parse a market split problem from a .dat file format.

    Parameters
    ----------
    filename : str
        Path to the .dat file containing the market split problem data.

    Returns
    -------
    A : np.ndarray
        Coefficient matrix of shape (m, n) where m is the number of products
        and n is the number of markets.
    b : np.ndarray
        Target vector of shape (m,) containing the target sales per product.
    """
    with open(filename, "r", encoding="utf-8") as f:
        lines = [
            line.strip()
            for line in f
            if line.strip() and not line.startswith("#")
        ]

    if not lines:
        raise ValueError("Empty or invalid .dat file")

    # First line: m n (number of products and markets)
    m, n = map(int, lines[0].split())

    # Next m lines: each row of A followed by corresponding element of b
    A, b = [], []
    for i in range(1, m + 1):
        values = list(map(int, lines[i].split()))
        A.append(values[:-1])  # First n values: product sales per market
        b.append(values[-1])  # Last value: target sales for this product

    return np.array(A, dtype=np.int32), np.array(b, dtype=np.int32)

def fetch_marketsplit_data(
    instance_name: str = "ms_03_200_177.dat",
) -> Tuple[Optional[np.ndarray], Optional[np.ndarray]]:
    """
    Fetch market split data directly from the QOBLIB repository.

    Parameters
    ----------
    instance_name : str
        Name of the .dat file to fetch (default: "ms_03_200_177.dat").

    Returns
    -------
    A : np.ndarray or None
        Coefficient matrix if successful, None if failed.
    b : np.ndarray or None
        Target vector if successful, None if failed.
    """
    url = f"https://git.zib.de/qopt/qoblib-quantum-optimization-benchmarking-library/-/raw/main/01-marketsplit/instances/{instance_name}"

    try:
        response = requests.get(url, timeout=30)
        response.raise_for_status()

        with tempfile.NamedTemporaryFile(
            mode="w", suffix=".dat", delete=False, encoding="utf-8"
        ) as f:
            f.write(response.text)
            temp_path = f.name

        try:
            return parse_marketsplit_dat(temp_path)
        finally:
            os.unlink(temp_path)
    except Exception as e:
        print(f"Error: {e}")
        return None, None

טעינת מופע הבעיה

כעת נטעין את מופע הבעיה הספציפי ms_03_200_177.dat מ-QOBLIB [2]. למופע זה:

• 3 מוצרים (אילוצים)
• 20 שווקים (משתני החלטה בינאריים)
• למעלה ממיליון השמות שוק אפשריות לחקור ($2^{20} = 1,048,576$)

# Load the problem instance
instance_name = "ms_03_200_177.dat"
A, b = fetch_marketsplit_data(instance_name=instance_name)

if A is not None:
    print("Successfully loaded problem instance from QOBLIB")
    print("\nProblem Instance Analysis:")
    print("=" * 50)
    print(f"Coefficient Matrix A: {A.shape[0]} × {A.shape[1]}")
    print(f"   → {A.shape[0]} products (constraints)")
    print(f"   → {A.shape[1]} markets (decision variables)")
    print(f"Target Vector b: {b}")
    print("   → Target sales per product for each region")
    print(
        f"Solution Space: 2^{A.shape[1]} = {2**A.shape[1]:,} possible assignments"
    )

המרה לפורמט QUBO

כעת נמיר את בעיית האופטימיזציה עם האילוצים לפורמט QUBO:

# Create optimization problem
ms = OptimizationProblem(instance_name.replace(".dat", ""))

# Add binary variables (one for each market)
ms.binary_var_list(A.shape[1])

# Add equality constraints (one for each product)
for idx, rhs in enumerate(b):
    ms.linear_constraint(A[idx, :], sense="==", rhs=rhs)

# Convert to QUBO with penalty parameter
qubo = OptimizationProblemToQubo(penalty=1).convert(ms)

print("QUBO Conversion Complete:")
print("=" * 50)
print(f"Number of variables: {qubo.get_num_vars()}")
print(f"Constant term: {qubo.objective.constant}")
print(f"Linear terms: {len(qubo.objective.linear.to_dict())}")
print(f"Quadratic terms: {len(qubo.objective.quadratic.to_dict())}")

המרת QUBO לפורמט Iskay

כעת עלינו להמיר את אובייקט ה-QUBO לפורמט מילון הנדרש על ידי Iskay Optimizer של Kipu Quantum.

הארגומנטים problem ו-problem_type מקודדים בעיית אופטימיזציה בצורה

$$\begin{align} \min_{(x_1, x_2, \ldots, x_n) \in D} C(x_1, x_2, \ldots, x_n) \nonumber \end{align}$$

כאשר

$$C(x_1, ... , x_n) = a + \sum_{i} b_i x_i + \sum_{i, j} c_{i, j} x_i x_j + ... + \sum_{k_1, ..., k_m} g_{k_1, ..., k_m} x_{k_1} ... x_{k_m}$$

• על ידי בחירת problem_type = "binary", מציינים שפונקציית העלות היא בפורמט binary, כלומר ש-$D = \{0, 1\}^{n}$, כלומר פונקציית העלות כתובה בניסוח QUBO/HUBO.
• לעומת זאת, על ידי בחירת problem_type = "spin", פונקציית העלות כתובה בניסוח Ising, שבו $D = \{-1, 1\}^{n}$.

מקדמי הבעיה יש לקודד במילון באופן הבא:

$$\begin{align} \nonumber &\texttt{\{} \\ \nonumber &\texttt{"()"}&: \quad &a, \\ \nonumber &\texttt{"(i,)"}&: \quad &b_i, \\ \nonumber &\texttt{"(i, j)"}&: \quad &c_{i, j}, \quad (i \neq j) \\ \nonumber &\quad \vdots \\ \nonumber &\texttt{"(} k_1, ..., k_m \texttt{)"}&: \quad &g_{k_1, ..., k_m}, \quad (k_1 \neq k_2 \neq \dots \neq k_m) \\ \nonumber &\texttt{\}} \end{align}$$

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

$$x_i^2 = x_i$$

עבור $i=j$ (מאחר ש-$x_i \in \{0,1\}$ פירושו $x_i \cdot x_i = x_i$). לכן, בניסוח ה-QUBO שלך, אם יש לך גם תרומות לינאריות $b_i x_i$ וגם תרומות ריבועיות אלכסוניות $c_{i,i} x_i^2$, יש לשלב את האיברים הללו למקדם לינארי יחיד:

מקדם לינארי כולל למשתנה $x_i$: $b_i + c_{i,i}$

פירוש הדבר:

• איברים לינאריים כגון "(i, )" מכילים: מקדם לינארי מקורי + מקדם ריבועי אלכסוני
• איברים ריבועיים אלכסוניים כגון "(i, i)" לא אמורים להופיע במילון הסופי
• רק איברים ריבועיים לא-אלכסוניים כגון "(i, j)" שבהם $i \neq j$ יש לכלול כערכים נפרדים

דוגמה: אם ה-QUBO שלך מכיל $3x_1 + 2x_1^2 + 4x_1 x_2$, מילון Iskay אמור להכיל:

• "(0, )": 5.0 (שילוב $3 + 2 = 5$)
• "(0, 1)": 4.0 (איבר לא-אלכסוני)

ולא ערכים נפרדים עבור "(0, )": 3.0 ו-"(0, 0)": 2.0.

# Convert QUBO to Iskay dictionary format:

# Create empty Iskay input dictionary
iskay_input_problem = {}

# Convert QUBO to Iskay dictionary format
iskay_input_problem = {"()": qubo.objective.constant}

for i in range(qubo.get_num_vars()):
    for j in range(i, qubo.get_num_vars()):
        if i == j:
            # Add linear term (including diagonal quadratic contribution)
            iskay_input_problem[f"({i}, )"] = float(
                qubo.objective.linear.to_dict().get(i)
            ) + float(qubo.objective.quadratic.to_dict().get((i, i)))
        else:
            # Add off-diagonal quadratic term
            iskay_input_problem[f"({i}, {j})"] = float(
                qubo.objective.quadratic.to_dict().get((i, j))
            )

# Display Iskay dictionary summary
print("Iskay Dictionary Format:")
print("=" * 50)
print(f"Total coefficients: {len(iskay_input_problem)}")
print(f"  • Constant term: {iskay_input_problem['()']}")
print(
    f"  • Linear terms: {sum(1 for k in iskay_input_problem.keys() if k != '()' and ', )' in k)}"
)
print(
    f"  • Quadratic terms: {sum(1 for k in iskay_input_problem.keys() if k != '()' and ', )' not in k)}"
)
print("\nSample coefficients:")

# Get first 10 and last 5 items properly
items = list(iskay_input_problem.items())
first_10 = list(enumerate(items[:10]))
last_5 = list(enumerate(items[-5:], start=len(items) - 5))

for i, (key, value) in first_10 + last_5:
    coeff_type = (
        "constant"
        if key == "()"
        else "linear"
        if ", )" in key
        else "quadratic"
    )
    print(f"  {key}: {value} ({coeff_type})")
print("  ...")
print("\n✓ Problem ready for Iskay optimizer!")

הבנת אלגוריתם bf-DCQO

לפני שנריץ את האופטימיזציה, בואו נבין את האלגוריתם הקוונטי המתוחכם המניע את Iskay: bf-DCQO (אופטימיזציה קוונטית קאונטר-דיאבטית דיגיטלית עם שדה הטיה) [1].

מהו bf-DCQO?

bf-DCQO מבוסס על התפתחות זמן של מערכת קוונטית שבה פתרון הבעיה מקודד במצב הבסיסי (מצב האנרגיה הנמוכה ביותר) של ההמילטוניאן הקוונטי הסופי [1]. האלגוריתם מתמודד עם אתגר בסיסי באופטימיזציה קוונטית:

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

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

מסגרת מתמטית

האלגוריתם ממזער פונקציית עלות בצורה:

$\min_{(x_1,x_2,...,x_n) \in D} C(x_1,x_2,...,x_n)$

כאשר $D = \{0,1\}^n$ עבור משתנים בינאריים ו:

$C(x) = a + \sum_i b_i x_i + \sum_{i,j} c_{ij} x_i x_j + ... + \sum g_{k_1,...,k_m} x_{k_1}...x_{k_m}$

עבור בעיית פיצול השוק שלנו, פונקציית העלות היא:

$C(x) = ||Ax - b||^2 = x^T A^T A x - 2 b^T A x + b^T b$

תפקיד האיברים הקאונטר-דיאבטיים

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

באופטימיזציה קוונטית אדיאבטית, מפתחים את המערכת בהתאם להמילטוניאן תלוי-זמן:

$H(t) = \left(1 - \frac{t}{T}\right) H_{\text{initial}} + \frac{t}{T} H_{\text{problem}}$

כאשר $H_{\text{problem}}$ מקודד את בעיית האופטימיזציה שלנו. כדי לשמור על מצב הבסיסי במהלך התפתחות מהירה, מוסיפים איברים קאונטר-דיאבטיים:

$H_{\text{CD}}(t) = H(t) + H_{\text{counter}}(t)$

האיברים הקאונטר-דיאבטיים הללו מבצעים את הפעולות הבאות:

1. דיכוי מעברים לא רצויים: מונעים ממצב הקוונטי לקפוץ למצבים מעוררים במהלך התפתחות מהירה
2. אפשרות לזמני התפתחות קצרים יותר: מאפשרים להגיע למצב הסופי מהר יותר מבלי להפר את האדיאבטיות
3. צמצום עומק המעגל: התפתחות קצרה יותר מובילה לפחות שערים ופחות שגיאות

ההשפעה המעשית היא דרמטית: bf-DCQO משתמש עד 10 פעמים פחות שערי סיבוך מאשר Digital Quantum Annealing [1], מה שהופך אותו לפרקטי עבור החומרה הקוונטית הרועשת של ימינו.

אופטימיזציה איטרטיבית עם שדה הטיה

בניגוד לאלגוריתמים ווריאציוניים המייעלים פרמטרי מעגל דרך איטרציות רבות, bf-DCQO משתמש בגישה מונחית-שדה-הטיה המתכנסת בכ-10 איטרציות [1]:

תהליך האיטרציה:

1. התפתחות קוונטית ראשונית: התחלה עם מעגל קוונטי המממש את פרוטוקול ההתפתחות הקאונטר-דיאבטי

2. מדידה: מדידת המצב הקוונטי לקבלת התפלגות הסתברות על פני מחרוזות סיביות

3. חישוב שדה הטיה: ניתוח סטטיסטיקות המדידה וחישוב שדה הטיה אופטימלי $h_i$ לכל Qubit: $h_i = \text{f}(\text{measurement statistics}, \text{previous solutions})$

4. איטרציה הבאה: שדה ההטיה משנה את ההמילטוניאן עבור האיטרציה הבאה: $H_{\text{next}} = H_{\text{problem}} + \sum_i h_i \sigma_i^z$

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

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

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

עיבוד קלאסי לאחר-עיבוד משולב

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

• חקירת היפוך סיביות: היפוך שיטתי או אקראי של סיביות בפתרון הנמדד הטוב ביותר
• הערכת אנרגיה: חישוב $C(x)$ לכל פתרון שונה
• בחירה חמדנית: קבלת שיפורים המורידים את פונקציית העלות
• מעברים מרובים: ביצוע מספר מעברים (נשלט על ידי postprocessing_level)

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

מדוע bf-DCQO מצטיין על חומרה נוכחית

אלגוריתם bf-DCQO תוכנן במיוחד להצטיין על מכשירי NISQ (קוונטיים בקנה מידה בינוני עם רעש) של ימינו [1]:

1. עמידות בפני שגיאות: פחות שערים (צמצום פי 10) פירושו הצטברות שגיאות קטנה דרמטית
2. אין צורך בהפחתת שגיאות: היעילות המובנית של האלגוריתם מבטלת את הצורך בטכניקות יקרות להפחתת שגיאות [1]
3. יכולת סקלאביליות: יכול לטפל בבעיות עם עד 156 Qubit (156 משתנים בינאריים) עם מיפוי ישיר של Qubit [1]
4. ביצועים מוכחים: משיג יחסי קירוב של 100% על מופעי MaxCut ו-HUBO לבנצ'מרק [1]

כעת בואו נראה את האלגוריתם החזק הזה בפעולה על בעיית פיצול השוק שלנו!

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

אלגוריתם bf-DCQO מטפל אוטומטית באופטימיזציה של המעגלים, ויוצר מעגלים קוונטיים רדודים עם איברים קאונטרדיאבטיים המותאמים במיוחד ל-Backend הנבחר.

הגדרת האופטימיזציה

מייעל Iskay דורש מספר פרמטרים מרכזיים כדי לפתור את בעיית האופטימיזציה שלכם ביעילות. נבחן כל פרמטר ואת תפקידו בתהליך האופטימיזציה הקוונטית:

פרמטרים נדרשים

פרמטר	סוג	תיאור	דוגמה
problem	Dict[str, float]	מקדמי QUBO בפורמט מפתח מחרוזת	{"()": -21.0, "(0,4)": 0.5, "(0,1)": 0.5}
problem_type	str	מפרט הפורמט: "binary" עבור QUBO או "spin" עבור Ising	"binary"
backend_name	str	המכשיר הקוונטי היעד	"ibm_fez"

מושגים בסיסיים

• פורמט הבעיה: אנחנו משתמשים ב-"binary" מאחר שהמשתנים שלנו הם בינאריים (0/1), המייצגים השמות לשווקים.
• בחירת Backend: בחרו מבין ה-QPU הזמינים (לדוגמה, "ibm_fez") בהתאם לצרכים ולמשאבי המחשוב הזמינים.
• מבנה ה-QUBO: מילון הבעיה שלנו מכיל את המקדמים המדויקים מהטרנספורמציה המתמטית.

אפשרויות מתקדמות (אופציונלי)

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

פרמטר	סוג	ברירת מחדל	תיאור
shots	int	10000	מדידות קוונטיות לאיטרציה (גבוה יותר = מדויק יותר)
num_iterations	int	10	איטרציות אלגוריתם (איטרציות נוספות יכולות לשפר את איכות הפתרון)
use_session	bool	True	שימוש ב-IBM Sessions לצמצום זמני תור
seed_transpiler	int	None	הגדרה לקומפילציה רבייצרית של מעגלים קוונטיים
direct_qubit_mapping	bool	False	מיפוי Qubit וירטואלי ישירות ל-Qubit פיזי
job_tags	List[str]	None	תגיות מותאמות אישית למעקב אחר משימות
preprocessing_level	int	0	עוצמת עיבוד מקדים של הבעיה (0-3) - ראו פרטים להלן
postprocessing_level	int	2	רמת עידון הפתרון (0-2) - ראו פרטים להלן
transpilation_level	int	0	ניסיונות אופטימיזציית Transpiler (0-5) - ראו פרטים להלן
transpile_only	bool	False	ניתוח אופטימיזציית המעגל ללא הרצת הביצוע המלא

רמות עיבוד מקדים (0-3): חשוב במיוחד לבעיות גדולות יותר שאינן מתאימות כרגע לזמני הקוהרנטיות של החומרה. רמות עיבוד מקדים גבוהות יותר משיגות עומקי מעגל רדודים יותר באמצעות קירובים בטרנספילציית הבעיה:

• רמה 0: מעגלים מדויקים וארוכים יותר
• רמה 1: איזון טוב בין דיוק לקירוב, תוך גזירת שערים בלבד עם זוויות בפרצנטיל הנמוך ביותר של 10%
• רמה 2: קירוב מעט גבוה יותר, גזירת שערים עם זוויות בפרצנטיל הנמוך ביותר של 20% ושימוש ב-approximation_degree=0.95 בטרנספילציה
• רמה 3: רמת קירוב מקסימלית, גזירת שערים בפרצנטיל הנמוך ביותר של 30% ושימוש ב-approximation_degree=0.90 בטרנספילציה

רמות טרנספילציה (0-5): שולטות בניסיונות אופטימיזציה מתקדמים של ה-Transpiler לקומפילציית מעגלים קוונטיים. תהליך זה עלול להגדיל את העומס הקלאסי, ובמקרים מסוימים עשוי שלא לשנות את עומק המעגל. ערך ברירת המחדל 2 מוביל בדרך כלל למעגל הקטן ביותר ומהיר יחסית.

• רמה 0: אופטימיזציה של מעגל DCQO המפורק (פריסה, ניתוב, תזמון)
• רמה 1: אופטימיזציה של PauliEvolutionGate ולאחר מכן מעגל DCQO המפורק (max_trials=10)
• רמה 2: אופטימיזציה של PauliEvolutionGate ולאחר מכן מעגל DCQO המפורק (max_trials=15)
• רמה 3: אופטימיזציה של PauliEvolutionGate ולאחר מכן מעגל DCQO המפורק (max_trials=20)
• רמה 4: אופטימיזציה של PauliEvolutionGate ולאחר מכן מעגל DCQO המפורק (max_trials=25)
• רמה 5: אופטימיזציה של PauliEvolutionGate ולאחר מכן מעגל DCQO המפורק (max_trials=50)

רמות עיבוד לאחר הביצוע (0-2): שולטות בכמות האופטימיזציה הקלאסית, המפצה על שגיאות היפוך סיביות עם מספר שונה של מעברי חיפוש מקומי תאב-בצע (greedy):

• רמה 0: מעבר אחד
• רמה 1: 2 מעברים
• רמה 2: 3 מעברים

מצב Transpile בלבד: זמין כעת למשתמשים המעוניינים לנתח את אופטימיזציית המעגל מבלי להריץ את ביצוע האלגוריתם הקוונטי המלא.

דוגמת תצורה מותאמת אישית

הנה דוגמה לאופן שבו ניתן להגדיר את Iskay עם הגדרות שונות:

custom_options = {
    "shots": 15_000,                                        # Higher shot count for better statistics
    "num_iterations": 12,                                   # More iterations for solution refinement
    "preprocessing_level": 1,                               # Light preprocessing for problem simplification
    "postprocessing_level": 2,                              # Maximum postprocessing for solution quality
    "transpilation_level": 3,                               # Using higher transpilation level for circuit optimization
    "seed_transpiler": 42,                                  # Fixed seed for reproducible results
    "job_tags": ["market_split"]                            # Custom tracking tags
}

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

# Specify the target backend
backend_name = "ibm_fez"

# Set the number of bias-field iterations and set a tag to identify the jobs
options = {
    "num_iterations": 3,  # Change number of bias-field iterations
    "job_tags": ["market_split_example"],  # Tag to identify jobs
}

# Configure Iskay optimizer
iskay_input = {
    "problem": iskay_input_problem,
    "problem_type": "binary",
    "backend_name": backend_name,
    "options": options,
}

print("Iskay Optimizer Configuration:")
print("=" * 40)
print(f"  Backend: {backend_name}")
print(f"  Problem: {len(iskay_input['problem'])} terms")
print("  Algorithm: bf-DCQO")

שלב 3: ביצוע באמצעות Qiskit Primitives

כעת אנחנו שולחים את הבעיה שלנו להרצה על חומרה של IBM Quantum. אלגוריתם bf-DCQO יבצע את הפעולות הבאות:

1. בניית מעגלים קוונטיים רדודים עם איברים קאונטרדיאבטיים
2. ביצוע כ-10 איטרציות עם אופטימיזציית שדה הטיה
3. ביצוע עיבוד לאחר ביצוע קלאסי עם חיפוש מקומי
4. החזרת השמת השוק האופטימלית

# Submit the optimization job
print("Submitting optimization job to Kipu Quantum...")
print(
    f"Problem size: {A.shape[1]} variables, {len(iskay_input['problem'])} terms"
)
print(
    "Algorithm: bf-DCQO (bias-field digitized counterdiabatic quantum optimization)"
)

job = iskay_solver.run(**iskay_input)

print("\nJob successfully submitted!")
print(f"Job ID: {job.job_id}")
print("Optimization in progress...")
print(
    f"The bf-DCQO algorithm will efficiently explore {2**A.shape[1]:,} possible assignments"
)

מעקב אחר סטטוס המשימה

ניתן לבדוק את הסטטוס הנוכחי של משימת האופטימיזציה שלכם. הסטטוסים האפשריים הם:

• QUEUED: המשימה ממתינה בתור
• RUNNING: המשימה מבוצעת כרגע על חומרה קוונטית
• DONE: המשימה הושלמה בהצלחה
• CANCELED: המשימה בוטלה
• ERROR: המשימה נתקלה בשגיאה

# Check job status
print(f"Job status: {job.status()}")

המתנה לסיום

תא זה ייחסם עד לסיום המשימה. תהליך האופטימיזציה כולל:

• זמן תור (המתנה לגישה לחומרה קוונטית)
• זמן ביצוע (הרצת אלגוריתם bf-DCQO עם כ-10 איטרציות)
• זמן עיבוד לאחר ביצוע (חיפוש מקומי קלאסי)

זמני השלמה אופייניים נעים בין מספר דקות לעשרות דקות בהתאם לתנאי התור.

# Wait for job completion
while True:
    status = job.status()
    print(
        f"Waiting for job {job.job_id} to complete... (status: {status})",
        end="\r",
        flush=True,
    )
    if status in ["DONE", "CANCELED", "ERROR"]:
        print(
            f"\nJob {job.job_id} completed with status: {status}" + " " * 20
        )
        break
    time.sleep(30)

# Retrieve the optimization results
result = job.result()
print("\nOptimization complete!")

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

כעת אנחנו מבצעים עיבוד לאחר ביצוע של תוצאות הביצוע הקוונטי. תהליך זה כולל:

• ניתוח מבנה הפתרון
• אימות עמידה בקאונסטריינטים
• השוואה לגישות קלאסיות

ניתוח התוצאות

הבנת מבנה התוצאה

Iskay מחזירה מילון תוצאות מקיף המכיל:

• solution: מילון הממפה אינדקסים של משתנים לערכים האופטימליים שלהם (0 או 1)
• solution_info: מידע מפורט הכולל:
  • bitstring: ההשמה האופטימלית כמחרוזת בינארית
  • cost: ערך פונקציית המטרה (אמור להיות 0 לסיפוק קאונסטריינטים מושלם)
  • mapping: כיצד מיקומי המחרוזת הבינארית ממופים למשתני הבעיה
  • seed_transpiler: הזרע שנוצר לצורך יכולת שחזור
• prob_type: האם הפתרון נמצא בפורמט בינארי או ספין

נבחן את הפתרון שהוחזר על ידי המייעל הקוונטי.

# Display the optimization results
print("Optimization Results")
print("=" * 50)
print(f"Problem Type: {result['prob_type']}")
print("\nSolution Info:")
print(f"  Bitstring: {result['solution_info']['bitstring']}")
print(f"  Cost: {result['solution_info']['cost']}")
print("\nSolution (first 10 variables):")
for i, (var, val) in enumerate(list(result["solution"].items())[:10]):
    print(f"  {var}: {val}")
print("  ...")

אימות הפתרון

כעת אנחנו מאמתים האם הפתרון הקוונטי עומד בקאונסטריינטים של בעיית פיצול השוק. תהליך האימות בודק:

מהי הפרת קאונסטריינט?

• עבור כל מוצר $i$, אנחנו מחשבים את המכירות בפועל באזור A: $(Ax)_i$
• אנחנו משווים זאת למכירות היעד $b_i$
• ההפרה היא ההפרש המוחלט: $|(Ax)_i - b_i|$
• פתרון ישים הוא כזה שאין בו הפרות עבור כל המוצרים

מה אנחנו מצפים:

• מקרה אידיאלי: סך ההפרות = 0 (כל הקאונסטריינטים מסופקים בצורה מושלמת)
  • אזור A מקבל בדיוק 1002 יחידות של מוצר 1, 879 יחידות של מוצר 2, ו-1040 יחידות של מוצר 3
  • אזור B מקבל את היחידות הנותרות (גם כן 1002, 879 ו-1040 בהתאמה)
• מקרה טוב: סך ההפרות קטן (פתרון קרוב לאופטימלי)
• מקרה גרוע: הפרות גדולות מעידות שהפתרון אינו עומד בדרישות העסקיות

פונקציית האימות תחשב:

1. מכירות בפועל לכל מוצר בכל אזור
2. הפרות קאונסטריינטים לכל מוצר
3. חלוקת השוק בין האזורים

def validate_solution(A, b, solution):
    """Validate market split solution."""
    x = np.array(solution)
    region_a = A @ x
    region_b = A @ (1 - x)
    violations = np.abs(region_a - b)

    return {
        "target": b,
        "region_a": region_a,
        "region_b": region_b,
        "violations": violations,
        "total_violation": np.sum(violations),
        "is_feasible": np.sum(violations) == 0,
        "region_a_markets": int(np.sum(x)),
        "region_b_markets": len(x) - int(np.sum(x)),
    }

# Convert bitstring to list of integers and validate
optimal_assignment = [
    int(bit) for bit in result["solution_info"]["bitstring"]
]
validation = validate_solution(A, b, optimal_assignment)

פרשנות תוצאות האימות

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

בדיקת ישימות:

• is_feasible = True פירושו שהפתרון מספק את כל הקאונסטריינטים בצורה מושלמת (סך הפרות = 0)
• is_feasible = False פירושו שחלק מהקאונסטריינטים הופרו

ניתוח מכירות:

• השוואת מכירות יעד מול מכירות בפועל לכל מוצר
• לפתרון מושלם: בפועל = יעד לכל המוצרים בשני האזורים
• ההפרש מעיד עד כמה אנחנו קרובים לחלוקת השוק הרצויה

חלוקת השוק:

• מראה כמה שווקים מוקצים לכל אזור
• אין דרישה למספר שווקים שווה, רק שיעדי המכירות יושגו

print("Solution Validation")
print("=" * 50)
print(f"Feasible solution: {validation['is_feasible']}")
print(f"Total constraint violation: {validation['total_violation']}")

print("\nSales Analysis (Target vs Actual):")
for i, (target, actual_a, actual_b) in enumerate(
    zip(validation["target"], validation["region_a"], validation["region_b"])
):
    violation_a = abs(actual_a - target)
    violation_b = abs(actual_b - target)
    print(f"  Product {i+1}:")
    print(f"    Target: {target}")
    print(f"    Region A: {actual_a} (violation: {violation_a})")
    print(f"    Region B: {actual_b} (violation: {violation_b})")

print("\nMarket Distribution:")
print(f"  Region A: {validation['region_a_markets']} markets")
print(f"  Region B: {validation['region_b_markets']} markets")

הערכת איכות הפתרון

על בסיס תוצאות האימות לעיל, ניתן להעריך את איכות הפתרון הקוונטי:

אם is_feasible = True (סך הפרות = 0):

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

אם is_feasible = False (סך הפרות > 0):

• הפתרון קרוב לאופטימלי אך אינו מושלם
• הפרות קטנות עשויות להיות מקובלות בפועל
• שקלו להתאים פרמטרים של המייעל:
  • הגדלת num_iterations לעוד מעברי אופטימיזציה
  • הגדלת postprocessing_level לעידון קלאסי נוסף
  • הגדלת shots לסטטיסטיקת מדידה טובה יותר

פרשנות פונקציית העלות:

• ערך ה-cost מתוך solution_info שווה ל-$||Ax - b||^2$
• עלות = 0 מעידה על סיפוק קאונסטריינטים מושלם
• ערכי עלות גבוהים יותר מעידים על הפרות קאונסטריינטים גדולות יותר

סיכום

מה השגנו

במדריך זה הצלחנו:

1. לטעון בעיית אופטימיזציה אמיתית: קבלנו מופע מאתגר של פיצול שוק ממאגר הבנצ'מרקינג QOBLIB [2]
2. להמיר לפורמט QUBO: המרת הבעיה המוגבלת לניסוח ריבועי ללא אילוצים [3]
3. לנצל אלגוריתמים קוונטיים מתקדמים: שימוש באלגוריתם bf-DCQO של Kipu Quantum עם איברים קאונטרדיאבטיים [1]
4. לקבל פתרונות אופטימליים: מציאת פתרונות ישימים העומדים בכל הקאונסטריינטים

תובנות מרכזיות

חדשנות אלגוריתמית: אלגוריתם bf-DCQO מייצג התקדמות משמעותית [1]:

• פחות שערים פי 10 בהשוואה לאניליינג קוונטי דיגיטלי
• כ-10 איטרציות במקום כ-100 לשיטות ווריאציוניות
• עמידות מובנית בפני שגיאות דרך יעילות המעגל

איברים קאונטרדיאבטיים: מאפשרים אבולוציה קוונטית מהירה תוך שמירה על נאמנות המצב הבסיסי, מה שהופך את האופטימיזציה הקוונטית לפרקטית על חומרה רועשת של ימינו [1].

הנחיית שדה הטיה: הגישה האיטרטיבית של שדה הטיה מאפשרת לכל איטרציה להתחיל קרוב לפתרונות טובים שנמצאו קודם לכן, ומספקת סוג של חיפוש מקומי מוגבר קוונטית [1].

צעדים הבאים

כדי להעמיק את ההבנה ולחקור עוד:

1. נסו מופעים שונים: התנסו במופעים אחרים של QOBLIB בגדלים שונים
2. כוונון פרמטרים: התאימו num_iterations, preprocessing_level, postprocessing_level
3. השוואה עם קלאסי: בצעו בנצ'מרק מול פותרי אופטימיזציה קלאסיים
4. נסו אסטרטגיות שונות: נסו למצוא קידוד טוב יותר לבעיה או לנסח אותה כ-HUBO (אם אפשרי)
5. יישום בתחום שלכם: הסתגלו את טכניקות הניסוח של QUBO/HUBO לבעיות האופטימיזציה שלכם

מקורות

[1] IBM Quantum. "Kipu Quantum Optimization." IBM Quantum Documentation.

[2] QOBLIB - Quantum Optimization Benchmarking Library. Zuse Institute Berlin (ZIB). https://git.zib.de/qopt/qoblib-quantum-optimization-benchmarking-library

[3] Glover, F., Kochenberger, G., & Du, Y. (2019). "Quantum bridge analytics I: a tutorial on formulating and using QUBO models." 4OR: A Quarterly Journal of Operations Research, 17(4), 335-371.