Розв'яжіть задачу поділу ринку за допомогою 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: Визначення задачі як цільової функції

Отримай екземпляр задачі поділу ринку з 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 потрібні наступні функції парсингу для отримання та обробки даних задачі market split з 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 задачі Market Split тепер перетворено у формат JSON так:

json_ms_problem = optimization_problem_to_json(ms_problem)

Крок 3: Розв'язання задачі за допомогою Parity Twine Optimizer

Тепер, коли ти отримав задачу market split і перетворив її у потрібну форму, ти можеш знайти розв'язок за допомогою Twine Optimizer та обраного бекенда IBM®.

Щоб запустити функцію, обери відповідний бекенд-пристрій, наприклад, ibm_phoenix.

Ти можеш використати options для (додаткового) контролю над надсиланням завдання:

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

де shots — це ціле число, яке визначає кількість виконань ланцюга, postprocessing_level визначає, чи застосовується постобробка до результату, transpile_only визначає, чи задача лише транспілюється в ланцюг (а не розв'язується), а job_tags — це мітка, яка використовується для ідентифікації завдання на платформі IBM Quantum®.

Запусти оптимізатор:

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 відповідає кубітам, визначеним у задачі, і надає їхні оптимізовані значення спінів. metadata надає інформацію про транспіляцію (кількість/глибина двокубітних вентилів, використані вентилі, активні кубіти) та різні часи виконання.

У контексті задачі market split бітовий рядок розв'язку представляє вектор бінарного призначення, який використовується для поділу ринків на два окремі регіони. Значення 1 призначає конкретний ринок до Регіону A, тоді як значення 0 призначає його до Регіону B. Для оптимального розв'язку комбінація балансує поділ, тобто обидва регіони отримують рівно половину загального попиту компанії на кожен продукт.

Наступні кроки

Рекомендації

• Подай запит на доступ до функції, заповнивши цю форму.
• Відвідай довідник API для цієї функції Qiskit.
• Прочитай посібник.
• Спробуй туторіал із застосуванням Parity Twine Optimizer до моделі Шеррінгтона-Кіркпатріка.
• Переглянь препринт ArXiv Connectivity-aware Synthesis of Quantum Algorithms, Drier et al. (2025).