Das Market-Split-Problem mit Kipu Quantums Iskay Quantum Optimizer lösen

Hinweis

Qiskit Functions sind ein experimentelles Feature, das ausschließlich für Nutzer des IBM Quantum® Premium Plan, Flex Plan und On-Prem (über die IBM Quantum Platform API) verfügbar ist. Sie befinden sich im Vorschau-Status und können sich noch ändern.

Geschätzter Ressourcenverbrauch: 20 Sekunden auf einem Heron-r2-Prozessor. (HINWEIS: Dies ist nur eine Schätzung. Deine tatsächliche Laufzeit kann abweichen.)

Hintergrund

Dieses Tutorial zeigt, wie du das Market-Split-Problem mit Kipu Quantums Iskay Quantum Optimizer [1] lösen kannst. Das Market-Split-Problem ist eine praxisnahe Ressourcenallokationsaufgabe, bei der Märkte so in ausgeglichene Verkaufsregionen aufgeteilt werden müssen, dass exakte Nachfrageziele erreicht werden.

Die Herausforderung des Market-Split-Problems

Das Market-Split-Problem stellt eine deceptiv einfach wirkende, aber rechnerisch anspruchsvolle Herausforderung in der Ressourcenallokation dar. Stell dir ein Unternehmen mit $m$ Produkten vor, das in $n$ verschiedenen Märkten verkauft, wobei jeder Markt ein bestimmtes Produktpaket kauft (dargestellt durch die Spalten der Matrix $A$). Das geschäftliche Ziel ist es, diese Märkte in zwei ausgeglichene Verkaufsregionen aufzuteilen, sodass jede Region exakt die Hälfte der Gesamtnachfrage für jedes Produkt erhält.

Mathematische Formulierung:

Gesucht wird ein binärer Zuweisungsvektor $x$, wobei:

• $x_j = 1$ den Markt $j$ der Region A zuweist
• $x_j = 0$ den Markt $j$ der Region B zuweist
• Die Bedingung $Ax = b$ erfüllt sein muss, wobei $b$ die Zielverkaufszahlen repräsentiert (typischerweise die Hälfte der Gesamtnachfrage pro Produkt)

Kostenfunktion:

Um dieses Problem zu lösen, minimieren wir die quadrierte Nebenbedingungsverletzung:

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

wobei:

• $A_{ij}$ den Umsatz von Produkt $i$ in Markt $j$ darstellt
• $x_j \in \{0,1\}$ die binäre Zuweisung von Markt $j$ ist
• $b_i$ der Zielumsatz für Produkt $i$ in jeder Region ist
• Die Kosten genau dann null sind, wenn alle Nebenbedingungen erfüllt sind

Jeder Term in der Summe stellt die quadrierte Abweichung vom Zielumsatz für ein bestimmtes Produkt dar. Wenn wir diese Kostenfunktion ausklammern, erhalten wir:

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

Da $b^T b$ eine Konstante ist, ist das Minimieren von $C(x)$ äquivalent zum Minimieren der quadratischen Funktion $x^T A^T A x - 2b^T A x$, was genau ein QUBO-Problem (Quadratic Unconstrained Binary Optimization) ist.

Rechenkomplexität:

Trotz seiner einfachen geschäftlichen Interpretation zeigt dieses Problem eine bemerkenswerte rechnerische Unlösbarkeit:

• Scheitern bei kleinen Instanzen: Herkömmliche Mixed-Integer-Programming-Solver scheitern bereits bei Instanzen mit nur sieben Produkten bei einem Timeout von einer Stunde [4]
• Exponentielles Wachstum: Der Lösungsraum wächst exponentiell ($2^n$ mögliche Zuweisungen), was Brute-Force-Ansätze unpraktikabel macht

Diese schwerwiegende Rechenbarriere macht das Market-Split-Problem, kombiniert mit seiner praktischen Relevanz für Gebietsplanung und Ressourcenallokation, zu einem idealen Benchmark für Quantenoptimierungsalgorithmen [4].

Was macht Iskays Ansatz einzigartig?

Der Iskay Optimizer verwendet den bf-DCQO-Algorithmus (bias-field digitized counterdiabatic quantum optimization) [1], der einen bedeutenden Fortschritt in der Quantenoptimierung darstellt:

Circuit-Effizienz: Der bf-DCQO-Algorithmus erzielt eine bemerkenswerte Gate-Reduzierung [1]:

• Bis zu 10-mal weniger verschränkende Gates als Digital Quantum Annealing (DQA)
• Deutlich flachere Circuits ermöglichen:
  • Weniger Fehlerakkumulation während der Quantenausführung
  • Die Fähigkeit, größere Probleme auf aktueller Quantenhardware zu lösen
  • Keinen Bedarf an Fehlerminderungstechniken

Nicht-variationales Design: Im Gegensatz zu variationalen Algorithmen, die etwa 100 Iterationen benötigen, braucht bf-DCQO typischerweise nur ungefähr 10 Iterationen [1]. Dies wird erreicht durch:

• Intelligente Bias-Field-Berechnungen aus gemessenen Zustandsverteilungen
• Starten jeder Iteration aus einem Energiezustand nahe der vorherigen Lösung
• Integrierte klassische Nachbearbeitung mit lokaler Suche

Counterdiabatische Protokolle: Der Algorithmus enthält counterdiabatische Terme, die unerwünschte Quantenanregungen während kurzer Evolutionszeiten unterdrücken und es dem System ermöglichen, auch bei schnellen Übergängen nahe am Grundzustand zu bleiben [1].

Voraussetzungen

Bevor du mit diesem Tutorial beginnst, stelle sicher, dass du folgendes installiert hast:

• 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)

Du musst außerdem Zugang zur Iskay Quantum Optimizer Funktion aus dem Qiskit Functions Catalog beantragen.

Einrichtung

Importiere zunächst alle für dieses Tutorial benötigten Pakete.

# 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-Anmeldedaten konfigurieren

Gib deine IBM Quantum® Platform-Zugangsdaten an. Du benötigst:

• API-Token: Deinen 44-stelligen API-Schlüssel von der IBM Quantum Platform
• Instance CRN: Deinen IBM Cloud® Instance-Bezeichner

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

Schritt 1: Klassische Eingaben auf ein Quantenproblem abbilden

Wir beginnen damit, unser klassisches Problem auf eine quantenkompatible Darstellung abzubilden. Dieser Schritt umfasst:

1. Verbindung zum Iskay Quantum Optimizer herstellen
2. Das Market-Split-Problem laden und formulieren
3. Den bf-DCQO-Algorithmus verstehen, der es lösen wird

Verbindung zum Iskay Quantum Optimizer herstellen

Wir beginnen damit, eine Verbindung zum Qiskit Functions Catalog herzustellen und den Iskay Quantum Optimizer zu laden. Der Iskay Optimizer ist eine von Kipu Quantum bereitgestellte Quantenfunktion, die den bf-DCQO-Algorithmus zur Lösung von Optimierungsproblemen auf Quantenhardware implementiert.

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")

Das Problem laden und formulieren

Das Problemdatenformat verstehen

Probleminstanzen aus QOBLIB (Quantum Optimization Benchmarking Library) [2] werden in einem einfachen Textformat gespeichert. Schauen wir uns den tatsächlichen Inhalt unserer Zielinstanz ms_03_200_177.dat an:

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

Formatstruktur:

• Erste Zeile: 3 20

  • 3 = Anzahl der Produkte (Nebenbedingungen/Zeilen in Matrix $A$)
  • 20 = Anzahl der Märkte (Variablen/Spalten in Matrix $A$)

• Nächste 3 Zeilen: Koeffizientenmatrix $A$ und Zielvektor $b$

  • Jede Zeile hat 21 Zahlen: die ersten 20 sind Zeilenkoeffizienten, die letzte ist das Ziel
  • Zeile 2: 60 92 161 ... 51 | 1002
    • Erste 20 Zahlen: Wie viel von Produkt 1 jeder der 20 Märkte verkauft
    • Letzte Zahl (1002): Zielumsatz für Produkt 1 in einer Region
  • Zeile 3: 176 196 41 ... 46 | 879
    • Umsatz von Produkt 2 pro Markt und Ziel (879)
  • Zeile 4: 68 68 179 ... 95 | 1040
    • Umsatz von Produkt 3 pro Markt und Ziel (1040)

Geschäftliche Interpretation:

• Markt 0 verkauft: 60 Einheiten von Produkt 1, 176 Einheiten von Produkt 2, 68 Einheiten von Produkt 3
• Markt 1 verkauft: 92 Einheiten von Produkt 1, 196 Einheiten von Produkt 2, 68 Einheiten von Produkt 3
• Und so weiter für alle 20 Märkte...
• Ziel: Diese 20 Märkte in zwei Regionen aufteilen, wobei jede Region genau 1002 Einheiten von Produkt 1, 879 Einheiten von Produkt 2 und 1040 Einheiten von Produkt 3 erhält

QUBO-Transformation

Von Nebenbedingungen zu QUBO: die mathematische Transformation

Die Stärke der Quantenoptimierung liegt in der Transformation eingeschränkter Probleme in uneingeschränkte quadratische Formen [4]. Für das Market-Split-Problem wandeln wir die Gleichheitsnebenbedingungen

$Ax = b$

wobei $x ∈ \{0,1\}^n$, in ein QUBO um, indem wir Nebenbedingungsverletzungen bestrafen.

Die Strafmethode: Da $Ax = b$ exakt gelten muss, minimieren wir die quadrierte Verletzung: $f(x) = ||Ax - b||^2$

Dies ist genau dann null, wenn alle Nebenbedingungen erfüllt sind. Algebraisch ausgedrückt: $f(x) = (Ax - b)^T(Ax - b) = x^T A^T A x - 2b^T A x + b^T b$

QUBO-Zielfunktion: Da $b^T b$ konstant ist, wird unsere Optimierung zu: $\text{minimize} \quad Q(x) = x^T(A^T A)x - 2(A^T b)^T x$

Wichtige Erkenntnis: Diese Transformation ist exakt, nicht approximativ. Gleichheitsnebenbedingungen werden auf natürliche Weise in quadratische Form gebracht, ohne Hilfsvariablen oder Strafparameter zu benötigen – was diese Formulierung mathematisch elegant und rechnerisch effizient für Quantenlöser macht [4]. Wir verwenden die Klasse OptimizationProblem, um unser eingeschränktes Problem zu definieren, und konvertieren es dann mit OptimizationProblemToQubo ins QUBO-Format – beide aus dem Paket qiskit_addon_opt_mapper. Dies behandelt die strafbasierte Transformation automatisch.

Datenladerungs- und QUBO-Konversionsfunktionen implementieren

Wir definieren nun drei Hilfsfunktionen:

1. parse_marketsplit_dat() - Liest das .dat-Dateiformat und extrahiert die Matrizen $A$ und $b$
2. fetch_marketsplit_data() - Lädt Probleminstanzen direkt aus dem QOBLIB-Repository herunter

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

Die Probleminstanz laden

Jetzt laden wir die spezifische Probleminstanz ms_03_200_177.dat aus QOBLIB [2]. Diese Instanz hat:

• 3 Produkte (Nebenbedingungen)
• 20 Märkte (binäre Entscheidungsvariablen)
• Über 1 Million mögliche Marktzuweisungen ($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"
    )

In QUBO-Format konvertieren

Wir transformieren das eingeschränkte Optimierungsproblem nun ins QUBO-Format:

# 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 in das Iskay-Format konvertieren

Jetzt müssen wir das QUBO-Objekt in das vom Iskay Optimizer von Kipu Quantum benötigte Wörterbuchformat umwandeln.

Die Argumente problem und problem_type kodieren ein Optimierungsproblem der Form

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

wobei

$$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}$$

• Durch Wahl von problem_type = "binary" gibst du an, dass die Kostenfunktion im binary-Format vorliegt, d.h. $D = \{0, 1\}^{n}$, also in QUBO/HUBO-Formulierung.
• Durch Wahl von problem_type = "spin" liegt die Kostenfunktion in Ising-Formulierung vor, wobei $D = \{-1, 1\}^{n}$.

Die Koeffizienten des Problems sollen wie folgt in einem Wörterbuch kodiert sein:

$$\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}$$

Beachte, dass die Schlüssel des Wörterbuchs Zeichenketten sein müssen, die ein gültiges Tupel nicht-wiederholender ganzer Zahlen enthalten. Für binäre Probleme gilt:

$$x_i^2 = x_i$$

für $i=j$ (da $x_i \in \{0,1\}$ bedeutet $x_i \cdot x_i = x_i$). In deiner QUBO-Formulierung müssen daher, wenn du sowohl lineare Beiträge $b_i x_i$ als auch diagonale quadratische Beiträge $c_{i,i} x_i^2$ hast, diese Terme zu einem einzigen linearen Koeffizienten zusammengefasst werden:

Gesamtlinearer Koeffizient für Variable $x_i$: $b_i + c_{i,i}$

Das bedeutet:

• Lineare Terme wie "(i, )" enthalten: ursprünglichen linearen Koeffizienten + diagonalen quadratischen Koeffizienten
• Diagonale quadratische Terme wie "(i, i)" sollten NICHT im endgültigen Wörterbuch erscheinen
• Nur off-diagonale quadratische Terme wie "(i, j)" mit $i \neq j$ sollten als separate Einträge enthalten sein

Beispiel: Wenn dein QUBO $3x_1 + 2x_1^2 + 4x_1 x_2$ enthält, sollte das Iskay-Wörterbuch enthalten:

• "(0, )": 5.0 (Kombination $3 + 2 = 5$)
• "(0, 1)": 4.0 (off-diagonaler Term)

NICHT separate Einträge für "(0, )": 3.0 und "(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!")

Den bf-DCQO-Algorithmus verstehen

Bevor wir die Optimierung starten, lass uns den ausgefeilten Quantenalgorithmus verstehen, der Iskay antreibt: bf-DCQO (bias-field digitized counterdiabatic quantum optimization) [1].

Was ist bf-DCQO?

bf-DCQO basiert auf der Zeitentwicklung eines Quantensystems, bei der die Problemlösung im Grundzustand (niedrigster Energiezustand) des finalen Quanten-Hamiltonians kodiert ist [1]. Der Algorithmus adressiert eine grundlegende Herausforderung der Quantenoptimierung:

Die Herausforderung: Traditionelles adiabatisches Quantencomputing erfordert eine sehr langsame Evolution, um Grundzustandsbedingungen gemäß dem adiabatischen Theorem aufrechtzuerhalten. Das erfordert immer tiefere Quantencircuits mit wachsender Problemkomplexität, was zu mehr Gate-Operationen und akkumulierten Fehlern führt.

Die Lösung: bf-DCQO verwendet counterdiabatische Protokolle, um eine schnelle Evolution zu ermöglichen, während die Grundzustandstreue erhalten bleibt und die Schaltkreistiefe drastisch reduziert wird.

Mathematischer Rahmen

Der Algorithmus minimiert eine Kostenfunktion der Form:

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

wobei $D = \{0,1\}^n$ für binäre Variablen gilt und:

$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}$

Für unser Market-Split-Problem lautet die Kostenfunktion:

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

Die Rolle der counterdiabatischen Terme

Counterdiabatische Terme sind zusätzliche Terme, die in den zeitabhängigen Hamiltonian eingeführt werden, um unerwünschte Anregungen während der Quantenevolution zu unterdrücken. Hier ist, warum sie entscheidend sind:

Bei der adiabatischen Quantenoptimierung entwickeln wir das System gemäß einem zeitabhängigen Hamiltonian:

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

wobei $H_{\text{problem}}$ unser Optimierungsproblem kodiert. Um den Grundzustand während schneller Evolution aufrechtzuerhalten, fügen wir counterdiabatische Terme hinzu:

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

Diese counterdiabatischen Terme bewirken Folgendes:

1. Unterdrückung unerwünschter Übergänge: Verhindert, dass der Quantenzustand während schneller Evolution in angeregte Zustände springt
2. Ermöglichung kürzerer Evolutionszeiten: Erlaubt uns, den Endzustand viel schneller zu erreichen, ohne die Adiabatizität zu verletzen
3. Reduzierung der Schaltkreistiefe: Kürzere Evolution führt zu weniger Gates und weniger Fehlern

Der praktische Einfluss ist dramatisch: bf-DCQO verwendet bis zu 10-mal weniger verschränkende Gates als Digital Quantum Annealing [1], was es für heutige verrauschte Quantenhardware praktikabel macht.

Bias-Field iterative Optimierung

Im Gegensatz zu variationalen Algorithmen, die Schaltkreisparameter durch viele Iterationen optimieren, verwendet bf-DCQO einen Bias-Field-geführten Ansatz, der in etwa 10 Iterationen konvergiert [1]:

Iterationsprozess:

1. Initiale Quantenevolution: Starte mit einem Quantencircuit, der das counterdiabatische Evolutionsprotokoll implementiert

2. Messung: Messe den Quantenzustand, um eine Wahrscheinlichkeitsverteilung über Bitstrings zu erhalten

3. Bias-Field-Berechnung: Analysiere die Messstatistiken und berechne ein optimales Bias-Field $h_i$ für jedes Qubit: $h_i = \text{f}(\text{measurement statistics}, \text{previous solutions})$

4. Nächste Iteration: Das Bias-Field modifiziert den Hamiltonian für die nächste Iteration: $H_{\text{next}} = H_{\text{problem}} + \sum_i h_i \sigma_i^z$

   Dies erlaubt den Start nahe der zuvor gefundenen guten Lösung und führt effektiv eine Art "quantengestützte lokale Suche" durch

5. Konvergenz: Wiederhole, bis die Lösungsqualität sich stabilisiert oder eine maximale Anzahl von Iterationen erreicht ist

Hauptvorteil: Jede Iteration liefert bedeutsamen Fortschritt in Richtung der optimalen Lösung, indem sie Informationen aus vorherigen Messungen einbezieht – im Gegensatz zu variationalen Methoden, die den Parameterraum blind erkunden müssen.

Integrierte klassische Nachbearbeitung

Nachdem die Quantenoptimierung konvergiert, führt Iskay eine klassische lokale Suche als Nachbearbeitung durch:

• Bit-Flip-Erkundung: Systematisches oder zufälliges Umkehren von Bits in der besten gemessenen Lösung
• Energiebewertung: Berechnung von $C(x)$ für jede modifizierte Lösung
• Gierige Selektion: Akzeptiere Verbesserungen, die die Kostenfunktion senken
• Mehrere Durchläufe: Führe mehrere Durchläufe durch (gesteuert durch postprocessing_level)

Dieser hybride Ansatz kompensiert Bit-Flip-Fehler durch Hardwareunvollkommenheiten und Auslesefehler und gewährleistet hochwertige Lösungen auch auf verrauschten Quantengeräten.

Warum bf-DCQO auf aktueller Hardware glänzt

Der bf-DCQO-Algorithmus ist speziell dafür ausgelegt, auf heutigen verrauschten Quantengeräten mittlerer Größe (NISQ) zu glänzen [1]:

1. Fehlerresistenz: Weniger Gates (10-fache Reduzierung) bedeutet drastisch weniger Fehlerakkumulation
2. Keine Fehlermitigation erforderlich: Die inhärente Effizienz des Algorithmus macht teure Fehlermitigationstechniken überflüssig [1]
3. Skalierbarkeit: Kann Probleme mit bis zu 156 Qubits (156 binäre Variablen) mit direktem Qubit-Mapping verarbeiten [1]
4. Bewährte Leistung: Erreicht 100% Approximationsverhältnisse bei benchmark MaxCut- und HUBO-Instanzen [1]

Lass uns diesen leistungsstarken Algorithmus jetzt in Aktion an unserem Market-Split-Problem erleben!

Schritt 2: Problem für die Quantenhardware-Ausführung optimieren

Der bf-DCQO-Algorithmus verwaltet die Circuit-Optimierung automatisch und erstellt flache Quantencircuits mit counterdiabatischen Termen, die speziell für das Ziel-Backend ausgelegt sind.

Die Optimierung konfigurieren

Der Iskay Optimizer benötigt mehrere Schlüsselparameter, um dein Optimierungsproblem effektiv zu lösen. Schauen wir uns jeden Parameter und seine Rolle im Quantenoptimierungsprozess an:

Erforderliche Parameter

Parameter	Typ	Beschreibung	Beispiel
problem	Dict[str, float]	QUBO-Koeffizienten im String-Schlüssel-Format	{"()": -21.0, "(0,4)": 0.5, "(0,1)": 0.5}
problem_type	str	Formatangabe: "binary" für QUBO oder "spin" für Ising	"binary"
backend_name	str	Ziel-Quantengerät	"ibm_fez"

Wesentliche Konzepte

• Problemformat: Wir verwenden "binary", da unsere Variablen binär (0/1) sind und Marktzuweisungen darstellen.
• Backend-Auswahl: Wähle aus den verfügbaren QPUs (z.B. "ibm_fez") basierend auf deinen Anforderungen und deiner Rechenressourceninstanz.
• QUBO-Struktur: Unser Problem-Wörterbuch enthält die exakten Koeffizienten aus der mathematischen Transformation.

Erweiterte Optionen (optional)

Iskay bietet Feinabstimmungsmöglichkeiten über optionale Parameter. Während die Standardwerte für die meisten Probleme gut funktionieren, kannst du das Verhalten für spezifische Anforderungen anpassen:

Parameter	Typ	Standard	Beschreibung
shots	int	10000	Quantenmessungen pro Iteration (höher = genauer)
num_iterations	int	10	Algorithmus-Iterationen (mehr Iterationen können die Lösungsqualität verbessern)
use_session	bool	True	IBM Sessions für kürzere Wartezeiten verwenden
seed_transpiler	int	None	Für reproduzierbare Quantencircuit-Kompilierung setzen
direct_qubit_mapping	bool	False	Virtuelle Qubits direkt auf physische Qubits abbilden
job_tags	List[str]	None	Benutzerdefinierte Tags für die Job-Verfolgung
preprocessing_level	int	0	Vorverarbeitungsintensität des Problems (0–3) – Details unten
postprocessing_level	int	2	Verfeinerungsstufe der Lösung (0–2) – Details unten
transpilation_level	int	0	Transpiler-Optimierungsversuche (0–5) – Details unten
transpile_only	bool	False	Circuit-Optimierung analysieren, ohne vollständige Ausführung zu starten

Vorverarbeitungsstufen (0–3): Besonders wichtig für größere Probleme, die aktuell nicht in die Kohärenzzeiten der Hardware passen. Höhere Vorverarbeitungsstufen erzielen flachere Schaltkreistiefen durch Näherungen in der Problem-Transpilation:

• Stufe 0: Exakt, längere Circuits
• Stufe 1: Gute Balance zwischen Genauigkeit und Näherung; schneidet nur Gates mit Winkeln im untersten 10. Perzentil heraus
• Stufe 2: Etwas höhere Näherung; schneidet Gates mit Winkeln im untersten 20. Perzentil heraus und verwendet approximation_degree=0.95 bei der Transpilation
• Stufe 3: Maximale Näherungsstufe; schneidet Gates im untersten 30. Perzentil heraus und verwendet approximation_degree=0.90 bei der Transpilation

Transpilationsstufen (0–5): Steuern die erweiterten Transpiler-Optimierungsversuche für die Quantencircuit-Kompilierung. Dies kann zu einem erhöhten klassischen Overhead führen, und in manchen Fällen ändert sich die Schaltkreistiefe nicht. Der Standardwert 2 führt im Allgemeinen zum kleinsten Circuit und ist relativ schnell.

• Stufe 0: Optimierung des dekomponierten DCQO-Circuits (Layout, Routing, Scheduling)
• Stufe 1: Optimierung von PauliEvolutionGate und dann des dekomponierten DCQO-Circuits (max_trials=10)
• Stufe 2: Optimierung von PauliEvolutionGate und dann des dekomponierten DCQO-Circuits (max_trials=15)
• Stufe 3: Optimierung von PauliEvolutionGate und dann des dekomponierten DCQO-Circuits (max_trials=20)
• Stufe 4: Optimierung von PauliEvolutionGate und dann des dekomponierten DCQO-Circuits (max_trials=25)
• Stufe 5: Optimierung von PauliEvolutionGate und dann des dekomponierten DCQO-Circuits (max_trials=50)

Nachverarbeitungsstufen (0–2): Steuern den Umfang der klassischen Optimierung, die Bit-Flip-Fehler durch unterschiedlich viele gierige Durchläufe einer lokalen Suche kompensiert:

• Stufe 0: 1 Durchlauf
• Stufe 1: 2 Durchläufe
• Stufe 2: 3 Durchläufe

Nur-Transpilations-Modus: Jetzt für Benutzer verfügbar, die die Circuit-Optimierung analysieren möchten, ohne die vollständige Quantenalgorithmus-Ausführung zu starten.

Beispiel einer benutzerdefinierten Konfiguration

So könntest du Iskay mit anderen Einstellungen konfigurieren:

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
}

Für dieses Tutorial behalten wir die meisten Standardparameter bei und ändern nur die Anzahl der Bias-Field-Iterationen:

# 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")

Schritt 3: Mit Qiskit-Primitiven ausführen

Wir übermitteln unser Problem jetzt zur Ausführung auf IBM Quantum Hardware. Der bf-DCQO-Algorithmus wird:

1. Flache Quantencircuits mit counterdiabatischen Termen konstruieren
2. Ungefähr 10 Iterationen mit Bias-Field-Optimierung ausführen
3. Klassische Nachbearbeitung mit lokaler Suche durchführen
4. Die optimale Marktzuweisung zurückgeben

# 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"
)

Job-Status überwachen

Du kannst den aktuellen Status deines Optimierungsjobs überprüfen. Die möglichen Status sind:

• QUEUED: Job wartet in der Warteschlange
• RUNNING: Job wird gerade auf Quantenhardware ausgeführt
• DONE: Job erfolgreich abgeschlossen
• CANCELED: Job wurde abgebrochen
• ERROR: Job ist auf einen Fehler gestoßen

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

Auf Abschluss warten

Diese Zelle blockiert, bis der Job abgeschlossen ist. Der Optimierungsprozess umfasst:

• Wartezeit in der Warteschlange (warten auf Quantenhardware-Zugang)
• Ausführungszeit (Ausführen des bf-DCQO-Algorithmus mit ca. 10 Iterationen)
• Nachbearbeitungszeit (klassische lokale Suche)

Typische Abschlusszeiten liegen je nach Warteschlangenbedingungen zwischen wenigen Minuten und mehreren zehn Minuten.

# 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!")

Schritt 4: Ergebnis nachbearbeiten und im gewünschten klassischen Format zurückgeben

Wir verarbeiten die Quantenausführungsergebnisse jetzt nach. Dazu gehört:

• Analyse der Lösungsstruktur
• Validierung der Erfüllung von Nebenbedingungen
• Benchmarking gegen klassische Ansätze

Ergebnisse analysieren

Die Ergebnisstruktur verstehen

Iskay gibt ein umfassendes Ergebniswörterbuch zurück, das enthält:

• solution: Ein Wörterbuch, das Variablenindizes ihren optimalen Werten (0 oder 1) zuordnet
• solution_info: Detaillierte Informationen, darunter:
  • bitstring: Die optimale Zuweisung als binäre Zeichenkette
  • cost: Der Zielfunktionswert (sollte 0 bei perfekter Erfüllung der Nebenbedingungen sein)
  • mapping: Wie Bitstring-Positionen auf Problemvariablen abgebildet werden
  • seed_transpiler: Verwendeter Seed für Reproduzierbarkeit
• prob_type: Ob die Lösung im binären oder Spin-Format vorliegt

Schauen wir uns die vom Quantenoptimierer zurückgegebene Lösung an.

# 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("  ...")

Lösungsvalidierung

Jetzt validieren wir, ob die Quantenlösung die Market-Split-Nebenbedingungen erfüllt. Der Validierungsprozess prüft:

Was ist eine Nebenbedingungsverletzung?

• Für jedes Produkt $i$ berechnen wir den tatsächlichen Umsatz in Region A: $(Ax)_i$
• Wir vergleichen dies mit dem Zielumsatz $b_i$
• Die Verletzung ist die absolute Differenz: $|(Ax)_i - b_i|$
• Eine zulässige Lösung hat null Verletzungen für alle Produkte

Was wir erwarten:

• Idealfall: Gesamtverletzung = 0 (alle Nebenbedingungen perfekt erfüllt)
  • Region A erhält exakt 1002 Einheiten von Produkt 1, 879 Einheiten von Produkt 2 und 1040 Einheiten von Produkt 3
  • Region B erhält die verbleibenden Einheiten (ebenfalls 1002, 879 und 1040)
• Guter Fall: Gesamtverletzung ist klein (nahezu optimale Lösung)
• Schlechter Fall: Große Verletzungen zeigen an, dass die Lösung die Geschäftsanforderungen nicht erfüllt

Die Validierungsfunktion berechnet:

1. Tatsächliche Umsätze pro Produkt in jeder Region
2. Nebenbedingungsverletzungen für jedes Produkt
3. Marktverteilung zwischen Regionen

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)

Die Validierungsergebnisse interpretieren

Die Validierungsergebnisse zeigen, ob der Quantenoptimierer eine zulässige Lösung gefunden hat. Schauen wir uns Folgendes an:

Zulässigkeitsprüfung:

• is_feasible = True bedeutet, dass die Lösung alle Nebenbedingungen perfekt erfüllt (Gesamtverletzung = 0)
• is_feasible = False bedeutet, dass einige Nebenbedingungen verletzt sind

Umsatzanalyse:

• Vergleiche Soll- und Ist-Umsätze für jedes Produkt
• Bei einer perfekten Lösung: Ist = Soll für alle Produkte in beiden Regionen
• Die Differenz zeigt, wie nah wir an der gewünschten Marktaufteilung sind

Marktverteilung:

• Zeigt, wie viele Märkte jeder Region zugewiesen sind
• Es gibt keine Anforderung für gleich viele Märkte, nur dass die Umsatzziele erreicht werden

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")

Bewertung der Lösungsqualität

Anhand der obigen Validierungsergebnisse können wir die Qualität der Quantenlösung beurteilen:

Wenn is_feasible = True (Gesamtverletzung = 0):

• Der Quantenoptimierer hat erfolgreich eine optimale Lösung gefunden
• Alle Geschäftsanforderungen sind perfekt erfüllt
• Dies demonstriert Quantenüberlegenheit bei einem Problem, bei dem klassische Solver Schwierigkeiten haben [4]

Wenn is_feasible = False (Gesamtverletzung > 0):

• Die Lösung ist nahezu optimal, aber nicht perfekt
• Kleine Verletzungen können in der Praxis akzeptabel sein
• Erwäge die Anpassung der Optimiererparameter:
  • Erhöhe num_iterations für mehr Optimierungsdurchläufe
  • Erhöhe postprocessing_level für mehr klassische Verfeinerung
  • Erhöhe shots für bessere Messstatistiken

Interpretation der Kostenfunktion:

• Der cost-Wert aus solution_info entspricht $||Ax - b||^2$
• Kosten = 0 zeigt perfekte Erfüllung der Nebenbedingungen an
• Höhere Kostenwerte deuten auf größere Nebenbedingungsverletzungen hin

Fazit

Was wir erreicht haben

In diesem Tutorial haben wir erfolgreich:

1. Ein reales Optimierungsproblem geladen: Eine anspruchsvolle Market-Split-Instanz aus der QOBLIB-Benchmark-Bibliothek erhalten [2]
2. Ins QUBO-Format transformiert: Das eingeschränkte Problem in eine uneingeschränkte quadratische Formulierung umgewandelt [3]
3. Fortschrittliche Quantenalgorithmen genutzt: Kipu Quantums bf-DCQO-Algorithmus mit counterdiabatischen Termen verwendet [1]
4. Optimale Lösungen erhalten: Zulässige Lösungen gefunden, die alle Nebenbedingungen erfüllen

Wichtigste Erkenntnisse

Algorithmusinnovation: Der bf-DCQO-Algorithmus stellt einen bedeutenden Fortschritt dar [1]:

• 10-mal weniger Gates als digitales Quantenannealing
• Ungefähr 10 Iterationen statt ungefähr 100 bei variationalen Methoden
• Eingebaute Fehlerresistenz durch Circuit-Effizienz

Counterdiabatische Terme: Ermöglichen schnelle Quantenevolution unter Beibehaltung der Grundzustandstreue und machen Quantenoptimierung auf heutiger verrauschter Hardware praktikabel [1].

Bias-Field-Führung: Der iterative Bias-Field-Ansatz erlaubt es jeder Iteration, nahe zuvor gefundener guter Lösungen zu starten, und bietet so eine Form der quantengestützten lokalen Suche [1].

Nächste Schritte

Um dein Verständnis zu vertiefen und weiter zu erforschen:

1. Verschiedene Instanzen ausprobieren: Experimentiere mit anderen QOBLIB-Instanzen unterschiedlicher Größe
2. Parameter anpassen: Justiere num_iterations, preprocessing_level, postprocessing_level
3. Mit klassischen Methoden vergleichen: Benchmark gegen klassische Optimierungs-Solver
4. Andere Strategien ausprobieren: Versuche eine bessere Kodierung für das Problem zu finden oder formuliere es als HUBO (wenn möglich)
5. Auf deine Domäne anwenden: Passe die QUBO/HUBO-Formulierungstechniken an deine eigenen Optimierungsprobleme an

Referenzen

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

[4] Lodi, A., Tramontani, A., & Weninger, K. (2023). "The Intractable Decathlon: Benchmarking Hard Combinatorial Problems." INFORMS Journal on Computing.