Розв'язання проблеми розподілу ринку за допомогою квантового оптимізатора Iskay від Kipu Quantum

Примітка

Функції Qiskit є експериментальною можливістю, доступною лише для користувачів IBM Quantum® Premium Plan, Flex Plan та On-Prem (через IBM Quantum Platform API) Plan. Вони знаходяться у статусі попереднього випуску і можуть змінюватися.

Оцінка використання: 20 секунд на процесорі Heron r2. (ПРИМІТКА: Це лише оцінка. Твій час виконання може відрізнятися.)

Передумови

Цей посібник демонструє, як розв'язати проблему розподілу ринку, використовуючи квантовий оптимізатор Iskay від 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 (Quadratic Unconstrained Binary Optimization — квадратична необмежена бінарна оптимізація).

Обчислювальна складність:

Незважаючи на просту бізнес-інтерпретацію, ця проблема демонструє видатну обчислювальну нерозв'язність:

• Невдача на малому масштабі: Звичайні розв'язувачі змішаного цілочисельного програмування зазнають невдачі на екземплярах з усього сімома продуктами при таймауті в одну годину [4]
• Експоненційне зростання: Простір розв'язків зростає експоненційно ($2^n$ можливих призначень), що робить підходи грубої сили нездійсненними

Ця серйозна обчислювальна перешкода в поєднанні з її практичною релевантністю для планування територій і розподілу ресурсів робить проблему розподілу ринку ідеальним еталоном для квантових алгоритмів оптимізації [4].

Що робить підхід Iskay унікальним?

Оптимізатор Iskay використовує алгоритм bf-DCQO (bias-field digitized counterdiabatic quantum optimization — цифрова контрадіабатична квантова оптимізація з полем зміщення) [1], який представляє значний прогрес у квантовій оптимізації:

Ефективність схеми: Алгоритм bf-DCQO досягає видатного зменшення кількості вентилів [1]:

• До 10 разів менше заплутуючих вентилів, ніж цифрове квантове відпалювання (DQA)
• Значно менш глибокі схеми забезпечують:
  • Менше накопичення помилок під час квантового виконання
  • Можливість вирішувати більші проблеми на поточному квантовому обладnanні
  • Відсутність потреби в методах пом'якшення помилок

Неваріаційний дизайн: На відміну від варіаційних алгоритмів, що вимагають приблизно 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 з каталогу функцій 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: Твій 44-символьний API ключ з IBM Quantum Platform
• Instance CRN: Твій ідентифікатор екземпляра IBM Cloud®

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

Крок 1: Відображення класичних вхідних даних на квантову задачу

Ми починаємо з відображення нашої класичної задачі на квантово-сумісне представлення. Цей крок включає:

1. Підключення до квантового оптимізатора Iskay
2. Завантаження та формулювання проблеми розподілу ринку
3. Розуміння алгоритму bf-DCQO, який її розв'яже

Підключення до квантового оптимізатора Iskay

Ми починаємо зі встановлення з'єднання з каталогом функцій Qiskit та завантаження квантового оптимізатора Iskay. Оптимізатор Iskay є квантовою функцією, наданою Kipu Quantum, яка реалізує алгоритм bf-DCQO для розв'язання задач оптимізації на квантовому обладnanні.

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 (Quantum Optimization Benchmarking Library — бібліотека тестування квантової оптимізації) [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]. Для задачі Market Split ми перетворюємо обмеження рівності

$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 ринків (бінарні змінні рішення)
• Понад 1 мільйон можливих призначень ринків для дослідження ($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: "
        f"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", функція вартості записана у формулюванні Ізінга, де $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: "
    f"{sum(1 for k in iskay_input_problem.keys() if k != '()' and ', )' in k)}"
)
print(
    f"  • Quadratic terms: "
    f"{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 (bias-field digitized counterdiabatic quantum optimization) [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}$

Для нашої задачі Market Split функція вартості має вигляд:

$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$ для кожного кубіта: $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 кубітів (156 бінарних змінних) з прямим відображенням кубітів [1]
4. Доведена продуктивність: Досягає 100% коефіцієнтів наближення на еталонних екземплярах MaxCut та HUBO [1]

Крок 2: Оптимізація задачі для виконання на квантовому обладнанні

Алгоритм bf-DCQO автоматично обробляє оптимізацію схем, створюючи неглибокі квантові схеми з контрадіабатичними членами, спеціально розробленими для цільового бекенду.

Налаштування оптимізації

Оптимізатор 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), що представляють призначення ринків.
• Вибір бекенду: Вибирай між доступними QPU (наприклад, "ibm_fez") на основі твоїх потреб та екземпляра обчислювального ресурсу.
• Структура QUBO: Наш словник задачі містить точні коефіцієнти з математичного перетворення.

Розширені опції (необов'язкові)

Iskay надає можливості тонкого налаштування через необов'язкові параметри. Хоча значення за замовчуванням добре працюють для більшості задач, ти можеш налаштувати поведінку для конкретних вимог:

Параметр	Тип	За замовчуванням	Опис
shots	int	10000	Квантові вимірювання на ітерацію (більше = точніше)
num_iterations	int	10	Ітерації алгоритму (більше ітерацій може покращити якість розв'язку)
use_session	bool	True	Використовувати сесії IBM для зменшення часу очікування в черзі
seed_transpiler	int	None	Встановити для відтворюваної компіляції квантових схем
direct_qubit_mapping	bool	False	Відображати віртуальні кубіти безпосередньо на фізичні кубіти
job_tags	List[str]	None	Власні теги для відстеження завдань
preprocessing_level	int	0	Інтенсивність попередньої обробки задачі (0-3) - деталі нижче
postprocessing_level	int	2	Рівень уточнення розв'язку (0-2) - деталі нижче
transpilation_level	int	0	Спроби оптимізації транспайлера (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): Контролюють розширені спроби оптимізації транспайлера для компіляції квантових схем. Це може призвести до збільшення класичних витрат, і в деяких випадках це може не змінити глибину схеми. Значення за замовчуванням 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): Контролюють обсяг класичної оптимізації, компенсуючи помилки зміни бітів різною кількістю жадібних проходів локального пошуку:

• Рівень 0: 1 прохід
• Рівень 1: 2 проходи
• Рівень 2: 3 проходи

Режим лише транспіляції: Тепер доступний для користувачів, які хочуть проаналізувати оптимізацію схеми без виконання повного квантового алгоритму.

Приклад власної конфігурації

Ось як ти можеш налаштувати Iskay з різними параметрами:

custom_options = {
    # Higher shot count for better statistics
    "shots": 15_000,

    # More iterations for solution refinement
    "num_iterations": 12,

    # Light preprocessing for problem simplification
    "preprocessing_level": 1,

    # Maximum postprocessing for solution quality
    "postprocessing_level": 2,

    # Using higher transpilation level for circuit optimization
    "transpilation_level": 3,

    # Fixed seed for reproducible results
    "seed_transpiler": 42,

    # Custom tracking tags
    "job_tags": ["market_split"]
}

Для цього посібника ми збережемо більшість параметрів за замовчуванням і змінимо лише кількість ітерацій поля зміщення:

# 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

Тепер ми надсилаємо нашу задачу для виконання на обладнанні 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 "
    f"{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.