פתרון בעיית חלוקת השוק עם ParityQC Parity Twine Optimizer

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

תוצאות למידה

קבלה ועיצוב של בעיית חלוקת השוק מ-QOBLIB - Quantum Optimization Benchmarking Library.
הגדרה ושימוש ב-Parity Twine Optimizer לפתרון מופע של בעיית חלוקת שוק.
למידה כיצד לבחור אפשרויות עבור Parity Twine Optimizer ואילו תוצאות מופקות.

רקע

מדריך זה מדגים כיצד לפתור את בעיית חלוקת השוק באמצעות ParityQC Parity Twine Optimizer.

מופע הבעיה מתקבל מ-QOBLIB - Quantum Optimization Benchmarking Library.

בעיית חלוקת השוק

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

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

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

ניסוח מתמטי

יהי $A$ מטריצת $m \times n$ המייצגת את הביקוש למוצרים על פני השווקים, כאשר $A_{ij}$ הוא הביקוש למוצר $i$ בשוק $j$ .

מוגדר וקטור הקצאה בינארי, $x = [x_1, x_2, \dots, x_n]^T \in \{0, 1\}^n$ , כאשר:

$x_j = 1$ מקצה את שוק $j$ לאזור A.
$x_j = 0$ מקצה את שוק $j$ לאזור B.

יהי $d = [d_1, d_2, \dots, d_m]^T$ וקטור הביקוש הכולל לכל מוצר, המחושב כ- $d = A \cdot \mathbf{1}$ . נפח המכירות היעד לכל אזור עבור מוצר $i$ הוא בדיוק $\frac{d_i}{2}$ .

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

$A x = \frac{1}{2} A \mathbf{1} = b.$

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

$\min_{x} \left\Vert{} A x - b \right\Vert{}^2 = \sum_{i=1}^{m} \left( \sum_{j=1}^{n} A_{ij} x_j - b\right)^2.$

פיתוח ביטוי זה נותן צורה השקולה לבעיית אופטימיזציה בינארית ריבועית ללא אילוצים (QUBO).

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

דרישות

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

Qiskit Functions Catalog IBM Client (pip install qiskit-ibm-catalog)
Qiskit addon Optimization Mapper (pip install qiskit_addon_opt_mapper)
NumPy (pip install numpy)

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

הגדרה

(קוד זה מניח שכבר שמרתם את החשבון שלכם בסביבה המקומית שלכם.)

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

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

_needed = {"numpy": "numpy", "qiskit_addon_opt_mapper": "qiskit-addon-opt-mapper", "qiskit_ibm_catalog": "qiskit-ibm-catalog", "requests": "requests"}
_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 tempfile

from collections.abc import Callable
from pathlib import Path

import numpy as np
import requests

from qiskit_addon_opt_mapper import OptimizationProblem
from qiskit_addon_opt_mapper.converters import OptimizationProblemToQubo
from qiskit_ibm_catalog import QiskitFunctionsCatalog

טענו את Parity Twine Optimizer מקטלוג Qiskit Functions:

catalog = QiskitFunctionsCatalog(channel="ibm_quantum_platform")
function = catalog.load("parityqc/parity-twine-optimizer")

שלב 1: הגדרת הבעיה כפונקציית מטרה

קבלו מופע של בעיית חלוקת השוק (market split) מ-QOBLIB - Quantum Optimization Benchmarking Library באופן הבא.

הפונקציה load_market_split_problem מאחזרת בעיה נתונה מ-QOBLIB וממירה אותה לבעיית QUBO.

def load_market_split_problem(instance_name: str) -> OptimizationProblem:
    """Load and formulate a market split optimization problem from an QOBLIB instance.

    The QOBLIB library can be found here:
    https://github.com/ZIB-AOPT/QOBLIB.

    Args:
        instance_name: Name of the market split instance to load as specified by the .dat file
            in the QOBLIB repo.

    Returns:
        The output OptimizationProblem containing the loaded market split problem.
    """

    problem_matrix, problem_vector = fetch_and_parse(
        instance_name, "01-marketsplit", parse_marketsplit_dat
    )

    # Create optimization problem
    optimization_problem = OptimizationProblem(instance_name)

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

    # Add equality constraints (one for each product)
    for idx, rhs in enumerate(problem_vector):
        optimization_problem.linear_constraint(
            problem_matrix[idx, :], sense="==", rhs=rhs
        )

    # Convert to QUBO with penalty parameter
    return OptimizationProblemToQubo(penalty=1).convert(optimization_problem)

הפונקציה load_market_split_problem דורשת את פונקציות הניתוח (parser) הבאות כדי לאחזר ולעבד את נתוני בעיית חלוקת השוק מ-QOBLIB.

def fetch_and_parse(instance_name: str, problem: str, parse_func: Callable):
    """Generic function to fetch and parse data from QOBLIB repository.

    Args:
        instance_name: Name of the instance to fetch.
        problem: Category of the problem (e.g., '01-marketsplit', '07-independentset').
        parse_func: Function used to parse the downloaded file
            (e.g., parse_marketsplit_dat, parse_gph_file).

    Returns:
        Result of `parse_func` - either (np.ndarray, np.ndarray) for marketsplit
        or nx.Graph for MIS.
    """
    base_url = (
        "https://raw.githubusercontent.com/ZIB-AOPT/QOBLIB/refs/heads/main/"
    )
    url = (
        base_url
        + problem
        + "/instances/"
        + instance_name
        + (".dat" if problem == "01-marketsplit" else ".gph")
    )

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

        with tempfile.NamedTemporaryFile(
            mode="w",
            suffix=".dat" if problem == "01-marketsplit" else ".gph",
            delete=False,
            encoding="utf-8",
        ) as temp_file:
            temp_file.write(response.text)
            temp_file_path = temp_file.name

        try:
            return parse_func(temp_file_path)
        finally:
            Path(temp_file_path).unlink(missing_ok=True)

    except requests.RequestException as e:
        print(f"Error fetching data from repository: {e}")
    except (ValueError, OSError) as e:
        print(f"Error processing data: {e}")
        return None

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

    Args:
        filename: Path to the .dat file.

    Returns:
        Tuple of (A, b) where:
            - A: (m, n) array of coefficients.
            - b: (m,) array of target values.

    Raises:
        ValueError: If file format is invalid or file is empty.
    """
    with Path(filename).open(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)
    try:
        m, n = map(int, lines[0].split())
    except (ValueError, IndexError) as e:
        raise ValueError(
            "Invalid file format: first line must contain 'm n' integers"
        ) from e

    if len(lines) < m + 1:
        raise ValueError(
            f"File contains {len(lines)} lines but expected {m + 1} lines"
        )

    # Next m lines: each row of A followed by corresponding element of b
    mat_a = []
    vec_b = []

    for i in range(1, m + 1):
        try:
            values = list(map(int, lines[i].split()))
        except ValueError as e:
            raise ValueError(f"Invalid integer values in line {i + 1}") from e

        if len(values) != n + 1:
            raise ValueError(
                f"Line {i + 1} contains {len(values)} values but expected {n + 1}"
            )

        mat_a.append(values[:-1])  # First n values: product sales per market
        vec_b.append(values[-1])  # Last value: target sales for this product

    return np.array(mat_a), np.array(vec_b)

לאחר ההגדרה, ניתן להשתמש ב-load_marketsplit_problem כדי לטעון מופע ספציפי של בעיה מהספרייה:

ms_instance = "ms_04_050_001"

ms_problem = load_market_split_problem(ms_instance)

שלב 2: המרה לפורמט JSON

בשלב הראשון, קיבלתם את צורת ה-QUBO של הבעיה. כעת, המירו אותה לפורמט JSON עבור פונקציית האופטימיזציה:

def optimization_problem_to_json(
    problem: OptimizationProblem,
) -> dict[str, float]:
    """
    Converts an unconstrained quadratic OptimizationProblem in terms of binary or spin variables
    to the JSON input format of the Parity Twine Qiskit Function.

    Args:
        problem: The optimization problem to convert to JSON.

    Returns:
        The JSON input format of the given problem.
    """
    ising, constant = problem.to_ising()
    output = {"()": float(constant)}
    for op, coefficient in zip(ising.paulis, ising.coeffs, strict=True):
        # Invert the label strings because Qiskit has opposite convention
        qubits = tuple(
            num
            for num, pauli in enumerate(op.to_label()[::-1])
            if pauli == "Z"
        )
        output[str(qubits)] = float(coefficient)
    return output

מופע ה-QUBO של בעיית חלוקת השוק מומר כעת לפורמט JSON כך:

json_ms_problem = optimization_problem_to_json(ms_problem)

שלב 3: פתרון הבעיה באמצעות Parity Twine Optimizer

כעת, לאחר שקיבלתם את בעיית חלוקת השוק והמרתם אותה לצורה הנכונה, תוכלו למצוא פתרון באמצעות Twine Optimizer ו-backend נבחר של IBM®.

כדי להריץ את הפונקציה, בחרו backend מתאים; לדוגמה, ibm_phoenix.

תוכלו להשתמש ב-options לשליטה נוספת (אופציונלית) בשליחה:

options = {
    "shots": 100000,
    "postprocessing_level": 1,
    "transpile_only": False,
    "job_tags": ["market_split"],
}

כאשר shots הוא מספר שלם המציין את מספר הרצות המעגל, postprocessing_level קובע האם מבוצע עיבוד-שלאחר (post-processing) על התוצאה, transpile_only מציין האם הבעיה רק מתורגמת (transpiled) למעגל (ולא נפתרת), ו-job_tags הוא התווית המשמשת לזיהוי העבודה (job) ב-IBM Quantum® Platform.

הריצו את האופטימייזר:

function_job = function.run(
    problem=json_ms_problem,
    variable_type="spin",
    backend_name="ibm_phoenix",
    options=options,
)
print(f"Job ID: {function_job.job_id}")

בדקו את סטטוס העבודה:

# Monitor the job status
function_job.status()

אחזרו את התוצאות:

# Retrieve the job result if the status is DONE
result = function_job.result()

result

התוצאה היא בצורה:

{
    'solution': {'0': 1, '1': -1, '10': 1, ... },
    'objective_value':  1.0,
    'solution_bitstring': '010000011101111011001001110010',
    'metadata': {
        'circuit_metrics': {
            'depth': 309,
            'gate_count': 3880,
            'two_qubit_gate_depth': 116,
            'two_qubit_gate_count': 899,
            'num_qubits': 30,
            'operations': {'sx': 1244, 'rz': 1227, 'cz': 899, 'delay': 473, 'measure': 30, 'x': 7},
        },
        'solver_info': {
            'variable_mapping': {'0': 0, '1': 1, '10': 2, ... },
            'bitstring_distributions': {
                'before_postprocessing': {'011101110010110111001110011000': 1, ...},
                'after_postprocessing': {'011011110000110101001111011000': 1, ...}
            },
            'best_parameters': {
                'beta': [-0.18054534155552715],
                'gamma': [1.4141236348317905]
            }
        },
        'resource_usage': {
            'RUNNING: MAPPING': {'CPU_TIME': 172.936},
            'RUNNING: OPTIMIZING_FOR_HARDWARE': {'CPU_TIME': 0.272},
            'RUNNING: WAITING_FOR_QPU': {'CPU_TIME': 7.798},
            'RUNNING: EXECUTING_QPU': {'QPU_TIME': 30.0},
            'RUNNING: POST_PROCESSING': {'CPU_TIME': 31.613},
        },
    }
}

כאשר המילון solution תואם לקיוביטים המוגדרים בבעיה ונותן את ערכי הספין (spin) המאופטמים שלהם. metadata נותן מידע על התרגום (transpilation) (ספירת/עומק שערי שני-קיוביטים, שערים בשימוש, קיוביטים פעילים), וזמני ריצה שונים.

בהקשר של בעיית חלוקת השוק, מחרוזת הביטים (bitstring) של הפתרון מייצגת וקטור הקצאה בינארי המשמש לחלוקת השווקים לשני אזורים נפרדים. ערך של 1 מקצה שוק ספציפי לאזור A, בעוד שערך של 0 מקצה אותו לאזור B. עבור הפתרון האופטימלי, השילוב מאזן את הפיצול, כלומר שני האזורים מקבלים בדיוק מחצית מסך הביקוש של החברה לכל מוצר.

הצעדים הבאים

המלצות

בקשו גישה לפונקציה על ידי מילוי טופס זה.
בקרו במדריך העזר (API reference) עבור Qiskit Function זה.
קראו את המדריך.
נסו את המדריך (tutorial) ליישום Parity Twine Optimizer על מודל שרינגטון-קירקפטריק (Sherrington-Kirkpatrick).
עיינו בטיוטת ArXiv Connectivity-aware Synthesis of Quantum Algorithms, Drier et al. (2025).

תוצאות למידה​

רקע​

בעיית חלוקת השוק​

ניסוח מתמטי​

דרישות​

הגדרה​

שלב 1: הגדרת הבעיה כפונקציית מטרה​

שלב 2: המרה לפורמט JSON​

שלב 3: פתרון הבעיה באמצעות Parity Twine Optimizer​

הצעדים הבאים​