Lösen Sie das Problem der Marktsplittung mit dem Iskay Quantum Optimizer von Kipu Quantum

Geschätzte Nutzungsdauer: 20 Sekunden auf einem Heron r2 Prozessor. (HINWEIS: Dies ist nur eine Schätzung. Ihre Laufzeit kann variieren.)

Hintergrund

Dieses Tutorial zeigt, wie man das Problem der Marktaufteilung mit dem Iskay-Quantenoptimierer von Kipu Quantum [1] löst. Das Problem der Marktaufteilung stellt eine reale Herausforderung für die Ressourcenzuteilung dar, bei der Märkte in ausgewogene Verkaufsregionen aufgeteilt werden müssen, um genaue Nachfrageziele zu erreichen.

Die Herausforderung der Marktsplittung

Das Problem der Marktaufteilung stellt eine täuschend einfache, aber rechnerisch anspruchsvolle Herausforderung bei der Ressourcenzuweisung dar. Nehmen wir an, ein Unternehmen hat $m$ Produkte, die auf $n$ verschiedenen Märkten verkauft werden, wobei jeder Markt ein bestimmtes Produktbündel kauft (dargestellt durch die Spalten der Matrix $A$ ). Das Unternehmensziel besteht darin, diese Märkte in zwei ausgewogene Verkaufsregionen aufzuteilen, so dass jede Region genau die Hälfte der Gesamtnachfrage nach jedem Produkt erhält.

Mathematische Formulierung:

Wir suchen einen binären Zuweisungsvektor $x$, wobei:

• $x_j = 1$ weist den Markt $j$ der Region A zu
• $x_j = 0$ weist den Markt $j$ der Region B zu
• Die Bedingung $Ax = b$ muss erfüllt sein, wobei $b$ den Zielabsatz darstellt (in der Regel die Hälfte der Gesamtnachfrage pro Produkt)

Kostenfunktion:

Um dieses Problem zu lösen, minimieren wir die quadrierte Verletzung der Nebenbedingung:

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

Dabei gilt:

• $A_{ij}$ steht für die Verkäufe des Produkts $i$ auf dem Markt $j$
• $x_j \in \{0,1\}$ ist die binäre Zuordnung des Marktes $j$
• $b_i$ ist der Zielumsatz für das Produkt $i$ in jeder Region
• Die Kosten sind genau dann gleich Null, wenn alle Nebenbedingungen erfüllt sind

Jeder Term in der Summe stellt die quadrierte Abweichung vom Umsatzziel für ein bestimmtes Produkt dar. Wenn wir diese Kostenfunktion erweitern, 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 die Minimierung von $C(x)$ gleichbedeutend mit der Minimierung der quadratischen Funktion $x^T A^T A x - 2b^T A x$, was genau ein QUBO-Problem (Quadratic Unconstrained Binary Optimization) ist.

Rechnerische Komplexität:

Trotz seiner einfachen betriebswirtschaftlichen Auslegung weist dieses Problem eine bemerkenswerte rechnerische Unlösbarkeit auf:

• Versagen auf kleiner Ebene : Konventionelle Mixed Integer Programming-Löser versagen bei Instanzen mit nur sieben Produkten unter einer Zeitüberschreitung von einer Stunde [4]
• Exponentielles Wachstum : Der Lösungsraum wächst exponentiell ( $2^n$ mögliche Zuordnungen), so dass Brute-Force-Ansätze nicht durchführbar sind

Diese hohe Berechnungshürde in Verbindung mit der praktischen Relevanz für die Gebietsplanung und Ressourcenzuweisung macht das Marktaufteilungsproblem zu einem idealen Maßstab für Quantenoptimierungsalgorithmen [4].

Was macht Iskays Ansatz so einzigartig?

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

Effizienz der Schaltung : Der bf-DCQO-Algorithmus erreicht eine bemerkenswerte Gatterreduzierung [1] :

• Bis zu 10 Mal weniger Verschränkungsgatter als bei Digital Quantum Annealing (DQA)
• Erheblich flachere Schaltkreise ermöglichen:
  • Weniger Fehlerakkumulation während der Quantenausführung
  • Fähigkeit, größere Probleme auf aktueller Quanten-Hardware zu bewältigen
  • Keine Notwendigkeit für Fehlerbegrenzungstechniken

Nicht-variationsbasierter Entwurf : Im Gegensatz zu Variationsalgorithmen, die etwa 100 Iterationen erfordern, benötigt bf-DCQO typischerweise nur etwa 10 Iterationen [1]. Dies wird erreicht durch:

• Intelligente Bias-Field-Berechnungen aus gemessenen Zustandsverteilungen
• Jede Iteration beginnt mit einem Energiezustand nahe der vorherigen Lösung
• Integriertes klassisches Post-Processing mit lokaler Suche

Gegendiabatische Protokolle : Der Algorithmus enthält kontradiabatische Terme, die unerwünschte Quantenanregungen während kurzer Entwicklungszeiten unterdrücken, so dass das System auch bei schnellen Übergängen in der Nähe des Grundzustands bleibt [1].

Anforderungen

Vergewissern Sie sich vor Beginn dieses Tutorials, dass Sie die folgenden Komponenten installiert haben:

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

Sie müssen auch Zugang zur Iskay Quantum Optimizer Funktion von Qiskit Functions Catalog erhalten.

Einrichtung

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

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

Definieren Sie Ihre IBM Quantum® Platform berechtigungsnachweise. Sie benötigen:

• API-Token : Ihr 44-stelliger API-Schlüssel aus IBM Quantum Platform
• Instanz-CRN : Ihr IBM Cloud® Instanz-Identifikator

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

Schritt 1: Klassische Eingaben einem Quantenproblem zuordnen

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

1. Verbinden mit dem Iskay Quantum Optimizer
2. Belastung und Formulierung des Marktaufteilungsproblems
3. Verstehen des bf-DCQO-Algorithmus, der die Aufgabe lösen wird

Verbinden Sie sich mit Iskay Quantum Optimizer

Wir beginnen damit, eine Verbindung zu Qiskit Functions Catalog herzustellen und den Iskay Quantum Optimizer zu laden. Der Iskay Optimizer ist eine Quantenfunktion von Kipu Quantum, 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 Problem mit dem Datenformat verstehen

Probleminstanzen aus QOBLIB (Quantum Optimization Benchmarking Library) [2] sind 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

Struktur des Formats:

• Erste Zeile: 3 20

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

• Die nächsten 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
    • Die ersten 20 Zahlen: Wie viel von Produkt 1 wird auf jedem der 20 Märkte verkauft?
    • Letzte Zahl (1002): Umsatzziel für Produkt 1 in einer Region
  • Zeile 3: 176 196 41 ... 46 | 879
    • Produkt 2 Umsatz nach Markt und Ziel (879)
  • Zeile 4: 68 68 179 ... 95 | 1040
    • Produkt 3 Umsatz nach Markt und Ziel (1040)

Geschäftsinterpretation:

• 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 : Aufteilung dieser 20 Märkte in zwei Regionen, 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 Einschränkungen zu QUBO: die mathematische Transformation

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

$Ax = b$

wobei $x ∈ \{0,1\}^n$, in ein QUBO umgewandelt wird, indem Verstöße gegen Beschränkungen bestraft werden.

Die Strafmethode: Da wir $Ax = b$ genau einhalten müssen, minimieren wir die quadrierte Verletzung: $f(x) = ||Ax - b||^2$

Diese ist genau dann gleich Null, wenn alle Bedingungen erfüllt sind. Algebraisches Expandieren: $f(x) = (Ax - b)^T(Ax - b) = x^T A^T A x - 2b^T A x + b^T b$

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

Wichtige Erkenntnis: Diese Transformation ist exakt, nicht annähernd. Gleichheitsbedingungen lassen sich auf natürliche Weise in quadratische Form bringen, ohne dass Hilfsvariablen oder Strafparameter erforderlich sind, 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 in das QUBO-Format, beides aus dem Paket qiskit_addon_opt_mapper. Dadurch wird die strafpunktbasierte Umwandlung automatisch durchgeführt.

Implementierung von Datenlade- und QUBO-Konvertierungsfunktionen

Wir definieren nun drei Nutzenfunktionen:

1. parse_marketsplit_dat() - Analysiert das Dateiformat .dat und extrahiert die Matrizen $A$ und $b$
2. fetch_marketsplit_data() - Lädt problematische Instanzen 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

Laden Sie die Probleminstanz

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

• 3 Produkte (Zwänge)
• 20 Märkte (binäre Entscheidungsvariablen)
• Über 1 Million möglicher Marktzuordnungen zu erkunden ( $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"
    )

In das QUBO-Format konvertieren

Wir transformieren nun das eingeschränkte Optimierungsproblem in das 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

Nun müssen wir das QUBO-Objekt in das für den Iskay-Optimierer von Kipu Quantum erforderliche Wörterbuchformat umwandeln.

Die Argumente problem und problem_type kodieren ein Optimierungsproblem der Form

wo

• Wenn Sie problem_type = "binary" wählen, geben Sie an, dass die Kostenfunktion das Format binary hat, was bedeutet, dass $D = \{0, 1\}^{n}$ die Kostenfunktion in der QUBO/HUBO-Formulierung geschrieben wird.
• Andererseits wird die Kostenfunktion durch die Wahl von problem_type = "spin" in der Ising-Formel geschrieben, wobei $D = \{-1, 1\}^{n}$.

Die Koeffizienten des Problems sollten wie folgt in einem Wörterbuch kodiert werden:

Beachten Sie, dass die Schlüssel des Wörterbuchs Zeichenketten sein müssen, die ein gültiges Tupel von sich nicht wiederholenden ganzen Zahlen enthalten. Für binäre Probleme wissen wir das:

für $i=j$ (denn $x_i \in \{0,1\}$ bedeutet $x_i \cdot x_i = x_i$ ). Wenn Sie also in Ihrer QUBO-Formulierung sowohl lineare Beiträge $b_i x_i$ als auch diagonale quadratische Beiträge $c_{i,i} x_i^2$ haben, müssen diese Begriffe zu einem einzigen linearen Koeffizienten zusammengefasst werden:

Linearer Gesamtkoeffizient für die Variable $x_i$ : $b_i + c_{i,i}$

Das bedeutet:

• Lineare Terme wie "(i, )" enthalten: ursprünglicher linearer Koeffizient + diagonaler quadratischer Koeffizient
• Diagonale quadratische Begriffe wie "(i, i)" sollten NICHT im endgültigen Wörterbuch erscheinen
• Nur außendiagonale quadratische Terme wie "(i, j)" und $i \neq j$ sollten als separate Einträge aufgenommen werden

Beispiel: Wenn Ihr QUBO $3x_1 + 2x_1^2 + 4x_1 x_2$ hat, sollte das Iskay-Wörterbuch Folgendes enthalten:

• "(0, )": 5.0 (kombiniert $3 + 2 = 5$ )
• "(0, 1)" 4.0 (nicht diagonaler Term)

KEINE separaten 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: "
    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!")

Den bf-DCQO-Algorithmus verstehen

Bevor wir die Optimierung durchführen, sollten wir den hochentwickelten Quantenalgorithmus verstehen, der Iskay antreibt: bf-DCQO (bias-field digitized counterdiabatic quantum optimization) [1].

Was ist bf-DCQO?

bf-DCQO basiert auf der zeitlichen Entwicklung eines Quantensystems, wobei die Problemlösung im Grundzustand (niedrigster Energiezustand) des endgültigen Quanten-Hamiltonians kodiert ist [1]. Der Algorithmus adressiert eine grundlegende Herausforderung in der Quantenoptimierung:

Die Herausforderung : Das herkömmliche adiabatische Quantencomputing erfordert eine sehr langsame Entwicklung, um den Grundzustand gemäß dem adiabatischen Theorem zu erhalten. Dies erfordert immer tiefere Quantenschaltungen, da die Komplexität des Problems zunimmt, was zu mehr Gatteroperationen und akkumulierten Fehlern führt.

Die Lösung : bf-DCQO verwendet kontradiabatische Protokolle, um eine schnelle Entwicklung unter Beibehaltung der Grundzustandstreue zu ermöglichen und die Schaltungstiefe drastisch zu reduzieren.

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 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 Marktaufteilungsproblem 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 gegen-diabetischen Begriffe

Gegendiabatische Terme sind zusätzliche Terme, die in den zeitabhängigen Hamiltonian eingeführt werden und unerwünschte Anregungen während der Quantenentwicklung unterdrücken. Hier ist der Grund, warum sie so wichtig 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 der schnellen Entwicklung aufrechtzuerhalten, fügen wir gegendiabatische Terme hinzu:

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

Diese gegendiabatischen Terme bewirken Folgendes:

1. Unerwünschte Übergänge unterdrücken : Verhindern, dass der Quantenzustand während der schnellen Entwicklung in angeregte Zustände springt
2. Ermöglicht kürzere Entwicklungszeiten : Wir können den Endzustand viel schneller erreichen, ohne die Adiabatizität zu verletzen
3. Verringerung der Schaltungstiefe : Eine kürzere Entwicklung führt zu weniger Gattern und weniger Fehlern

Die praktischen Auswirkungen sind dramatisch: bf-DCQO benötigt bis zu 10-mal weniger Verschränkungsgatter als Digital Quantum Annealing [1], was es für die heutige verrauschte Quantenhardware praktikabel macht.

Iterative Optimierung mit Bias-Feld

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

Iterationsprozess:

1. Anfängliche Quantenevolution : Beginnen Sie mit einer Quantenschaltung, die das gegendiabatische Evolutionsprotokoll implementiert

2. Messung : Messung des Quantenzustands, um eine Wahrscheinlichkeitsverteilung über Bitstrings zu erhalten

3. Berechnung des Bias-Feldes : Analysieren Sie die Messstatistiken und berechnen Sie ein optimales Bias-Feld $h_i$ für jedes Qubit: $h_i = \text{f}(\text{measurement statistics}, \text{previous solutions})$

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

   Dies ermöglicht es, in der Nähe der zuvor gefundenen guten Lösung zu beginnen und so eine Art "lokale Quantensuche" durchzuführen

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

Der entscheidende Vorteil : Jede Iteration liefert sinnvolle Fortschritte auf dem Weg zur optimalen Lösung, indem sie Informationen aus früheren Messungen einbezieht, im Gegensatz zu Variationsmethoden, die den Parameterraum blind erkunden müssen.

Integrierte klassische Nachbearbeitung

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

• Bit-flip Exploration : Systematisches oder zufälliges Umdrehen von Bits in der besten gemessenen Lösung
• Bewertung der Energie : Berechnen Sie $C(x)$ für jede modifizierte Lösung
• Gierige Auswahl : Akzeptieren Sie Verbesserungen, die die Kostenfunktion senken
• Mehrere Durchgänge : Mehrere Durchgänge durchführen (gesteuert durch postprocessing_level)

Dieser hybride Ansatz kompensiert Bit-Flip-Fehler aufgrund von Hardware-Unzulänglichkeiten und Auslesefehlern und gewährleistet so qualitativ hochwertige Lösungen selbst auf verrauschten Quantengeräten.

Warum bf-DCQO auf aktueller Hardware herausragende Leistungen erbringt

Der bf-DCQO-Algorithmus wurde speziell entwickelt, um auf den heutigen verrauschten Quantengeräten im mittleren Maßstab (NISQ) zu glänzen [1] :

1. Fehlerunempfindlichkeit : Weniger Gatter (10-fache Reduktion) bedeutet drastisch weniger Fehlerakkumulation
2. Keine Fehlerbegrenzung erforderlich : Die inhärente Effizienz des Algorithmus macht teure Techniken zur Fehlerbegrenzung überflüssig [1]
3. Skalierbarkeit : Kann Probleme mit bis zu 156 Qubits (156 binäre Variablen) mit direktem Qubit-Mapping behandeln [1]
4. Bewährte Leistung : Erzielt 100%ige Annäherungsraten bei den Benchmark-Instanzen MaxCut und HUBO [1]

Sehen wir uns nun diesen leistungsstarken Algorithmus in Aktion bei unserem Marktaufteilungsproblem an!

Schritt 2: Optimierung des Problems für die Ausführung auf Quantenhardware

Der bf-DCQO-Algorithmus sorgt automatisch für die Optimierung der Schaltkreise und erzeugt flache Quantenschaltungen mit gegendiabatischen Termen, die speziell für das Ziel-Backend entwickelt wurden.

Konfigurieren Sie die Optimierung

Der Iskay-Optimierer benötigt mehrere Schlüsselparameter, um Ihr Optimierungsproblem effektiv zu lösen. Untersuchen wir die einzelnen Parameter und ihre Rolle im Quantenoptimierungsprozess:

Erforderliche Parameter

Wesentliche Konzepte

• Problemformat : Wir verwenden "binary" , da unsere Variablen binär (0/1) sind und Marktzuweisungen darstellen.
• Auswahl des Backends : Wählen Sie zwischen den verfügbaren QPUs (z. B. "ibm_fez") je nach Bedarf und Rechenressourceninstanz.
• QUBO-Struktur : Unser Problemwörterbuch enthält die genauen Koeffizienten der mathematischen Transformation.

Erweiterte Optionen (optional)

Iskay bietet Feinabstimmungsmöglichkeiten durch optionale Parameter. Während die Standardeinstellungen für die meisten Probleme gut geeignet sind, können Sie das Verhalten für bestimmte Anforderungen anpassen:

Vorverarbeitungsstufen (0-3) : Besonders wichtig für größere Probleme, die derzeit nicht in die Kohärenzzeiten der Hardware passen. Höhere Vorverarbeitungsstufen erreichen geringere Schaltungstiefen durch Näherungen bei der Problemtranspilation:

• Stufe 0 : Genaue, längere Schaltungen
• Stufe 1 : Gutes Gleichgewicht zwischen Genauigkeit und Annäherung, wobei nur die Tore mit Winkeln im untersten 10-Perzentil ausgeschnitten werden
• Stufe 2 : Etwas stärkere Annäherung, Ausschneiden der Gates mit Winkeln im untersten 20-Perzentil und Verwendung von approximation_degree=0.95 bei der Transpilierung
• Stufe 3 : Maximale Annäherung, Ausschneiden der Gates im untersten 30-Perzentil und Verwendung von approximation_degree=0.90 bei der Transpilierung

Transpilierungsebenen (0-5) : Steuern Sie die erweiterten Transpiler-Optimierungsversuche für die Kompilierung von Quantenschaltungen. Dies kann zu einem Anstieg des klassischen Overheads führen, und in einigen Fällen ändert sich die Schaltungstiefe dadurch nicht. Der Standardwert 2 führt im Allgemeinen zum kleinsten Schaltkreis und ist relativ schnell.

• Ebene 0 : Optimierung der zerlegten DCQO-Schaltung (Layout, Routing, Scheduling)
• Ebene 1 : Optimierung von PauliEvolutionGate und dann der zerlegten DCQO-Schaltung ( max_trials=10 )
• Ebene 2 : Optimierung von PauliEvolutionGate und dann der zerlegten DCQO-Schaltung ( max_trials=15 )
• Ebene 3 : Optimierung von PauliEvolutionGate und dann der zerlegten DCQO-Schaltung ( max_trials=20 )
• Ebene 4 : Optimierung von PauliEvolutionGate und dann der zerlegten DCQO-Schaltung ( max_trials=25 )
• Ebene 5 : Optimierung von PauliEvolutionGate und dann der zerlegten DCQO-Schaltung ( max_trials=50 )

Nachbearbeitungsstufen (0-2) : Steuerung des Umfangs der klassischen Optimierung, Kompensation von Bit-Flip-Fehlern mit einer unterschiedlichen Anzahl von gierigen Durchläufen einer lokalen Suche:

• Stufe 0 : 1 Durchgang
• Stufe 1 : 2 Pässe
• Stufe 2 : 3 Pässe

Transpile-only-Modus : Jetzt verfügbar für Benutzer, die die Schaltkreisoptimierung analysieren möchten, ohne den gesamten Quantenalgorithmus auszuführen.

Beispiel für eine benutzerdefinierte Konfiguration

Hier sehen Sie, wie Sie Iskay mit verschiedenen Einstellungen konfigurieren könnten:

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"]
}

In diesem Tutorial werden wir die meisten Standardparameter beibehalten und nur die Anzahl der Iterationen des Bias-Feldes ändern:

# 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 primitives “ ausführen

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

1. Konstruktion von flachen Quantenkreisen mit gegendiabatischen Termen
2. Führen Sie ca. 10 Iterationen mit Bias-Field-Optimierung durch
3. Klassische Nachbearbeitung mit lokaler Suche durchführen
4. Rückgabe der optimalen Marktzuordnung

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

Auftragsstatus überwachen

Sie können den aktuellen Status Ihres Optimierungsauftrags überprüfen. Gültige Statusangaben sind:

• QUEUED: Der Auftrag wartet in der Warteschlange
• RUNNING: Job wird derzeit auf Quanten-Hardware ausgeführt
• DONE: Auftrag erfolgreich abgeschlossen
• CANCELED: Auftrag wurde storniert
• ERROR: Job ist auf einen Fehler gestoßen

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

Warten Sie, bis der Vorgang abgeschlossen ist

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

• Warteschlangenzeit (Warten auf Quanten-Hardwarezugriff)
• Ausführungszeit (Ausführung des bf-DCQO-Algorithmus mit etwa 10 Iterationen)
• Nachbearbeitungszeit (klassische lokale Suche)

Je nach den Bedingungen in der Warteschlange liegen die typischen Bearbeitungszeiten zwischen einigen Minuten und mehreren Dutzend 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: Nachbearbeitung und Rückgabe des Ergebnisses im gewünschten klassischen Format

Die Ergebnisse der Quantenausführung werden nun nachbearbeitet. Diese beinhalten:

• Analysieren der Lösungsstruktur
• Validierung der Erfüllung einer Bedingung
• Benchmarking mit klassischen Ansätzen

Ergebnisse analysieren

Die Ergebnisstruktur verstehen

Iskay liefert ein umfassendes Ergebniswörterbuch mit:

• solution: Ein Wörterbuch, das die Indizes der Variablen auf ihre optimalen Werte (0 oder 1) abbildet
• solution_info: Detaillierte Informationen, einschließlich:
  • bitstring: Die optimale Zuordnung als binäre Zeichenkette
  • cost: Der Wert der Zielfunktion (sollte bei perfekter Erfüllung der Nebenbedingungen 0 sein)
  • mapping: Wie Bitstring-Positionen auf Problemvariablen abgebildet werden
  • seed_transpiler: Für die Reproduzierbarkeit verwendetes Saatgut
• prob_type: Ob die Lösung im Binär- oder Spin-Format vorliegt

Untersuchen wir die Lösung, die der Quantenoptimierer liefert.

# 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ösungsprüfung

Nun überprüfen wir, ob die Quantenlösung die Marktaufteilungsbedingungen erfüllt. Der Validierungsprozess prüft:

Was ist eine Beschränkungsverletzung?

• Für jedes Produkt $i$ berechnen wir den tatsächlichen Absatz in der Region A: $(Ax)_i$
• Wir vergleichen dies mit dem angestrebten Umsatz $b_i$
• Der Verstoß ist der absolute Unterschied: $|(Ax)_i - b_i|$
• Eine praktikable Lösung hat für alle Produkte null Verstöße

Was wir erwarten:

• Idealfall : Gesamtübertretung = 0 (alle Nebenbedingungen perfekt erfüllt)
  • Region A erhält genau 1002 Einheiten von Produkt 1, 879 Einheiten von Produkt 2 und 1040 Einheiten von Produkt 3
  • Region B erhält die restlichen Einheiten (ebenfalls 1002, 879 bzw. 1040)
• Guter Fall : Die Gesamtverletzung ist gering (nahezu optimale Lösung)
• Schlechter Fall : Große Verstöße deuten darauf hin, dass die Lösung die Geschäftsanforderungen nicht erfüllt

Die Validierungsfunktion wird berechnet:

1. Tatsächlicher Umsatz pro Produkt in jeder Region
2. Verstöße gegen Beschränkungen für jedes Produkt
3. Marktverteilung zwischen den 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 Quantum Optimizer eine praktikable Lösung gefunden hat. Betrachten wir das Folgende:

Durchführbarkeitsprüfung:

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

Verkaufsanalyse:

• Vergleich von Soll- und Ist-Verkäufen für jedes Produkt
• Für eine perfekte Lösung: Ist = Soll für alle Produkte in beiden Regionen
• Die Differenz zeigt an, wie nahe wir dem gewünschten Marktsplit sind

Vertrieb auf dem Markt:

• Zeigt an, wie viele Märkte den einzelnen Regionen zugeordnet sind
• Es ist nicht erforderlich, dass die Anzahl der Märkte gleich ist, sondern nur, dass die Verkaufsziele 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 bewerten:

Wenn is_feasible = True (Gesamtübertretung = 0):

• Der Quantum Optimizer hat erfolgreich eine optimale Lösung gefunden
• Alle geschäftlichen Zwänge werden perfekt erfüllt
• Dies zeigt den Quantenvorteil bei einem Problem, bei dem klassische Löser Schwierigkeiten haben [4]

Wenn is_feasible = False (Gesamtübertretung > 0):

• Die Lösung ist nahezu optimal, aber nicht perfekt
• Geringe Verstöße können in der Praxis akzeptabel sein
• Erwägen Sie eine Anpassung der Optimierungsparameter:
  • Erhöhen Sie num_iterations für weitere Optimierungsläufe
  • Erhöhen Sie postprocessing_level für mehr klassische Veredelung
  • Erhöhen Sie shots für bessere Messstatistiken

Interpretation der Kostenfunktion:

• Der Wert cost von solution_info ist gleich $||Ax - b||^2$
• Kosten = 0 bedeutet vollkommene Erfüllung einer Bedingung
• Höhere Kostenwerte deuten auf größere Verstöße gegen Beschränkungen hin

Fazit

Was wir erreicht haben

In diesem Tutorium werden wir erfolgreich sein:

1. Laden eines realen Optimierungsproblems : Abrufen einer anspruchsvollen Marktaufteilungsinstanz aus der QOBLIB-Benchmark-Bibliothek [2]
2. In das QUBO-Format umgewandelt : Umwandlung des eingeschränkten Problems in eine uneingeschränkte quadratische Formulierung [3]
3. Nutzung fortgeschrittener Quantenalgorithmen : Verwendung des bf-DCQO-Algorithmus von Kipu Quantum mit gegendiabatischen Termen [1]
4. Erzielung optimaler Lösungen : Gefundene machbare Lösungen, die alle Nebenbedingungen erfüllen

Kernaspekte

Neuartiger Algorithmus : Der bf-DCQO-Algorithmus stellt eine bedeutende Weiterentwicklung dar [1] :

• 10-mal weniger Gatter als beim digitalen Quanten Annealing
• Etwa 10 Iterationen anstelle von etwa 100 bei Variationsmethoden
• Eingebaute Fehlerresistenz durch Schaltungseffizienz

Gegendiabatische Terme : Ermöglichen eine schnelle Quantenevolution unter Beibehaltung der Grundzustandstreue und machen die Quantenoptimierung auf der heutigen verrauschten Hardware praktisch [1].

Bias-Feld-Lenkung : Der iterative Bias-Field-Ansatz ermöglicht es, bei jeder Iteration in der Nähe von zuvor gefundenen guten Lösungen zu beginnen, was eine Form der quantengestützten lokalen Suche darstellt [1].

Nächste Schritte

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

1. Probieren Sie verschiedene Instanzen aus : Experimentieren Sie mit anderen QOBLIB-Instanzen unterschiedlicher Größe
2. Parameter abstimmen : num_iterations, preprocessing_level einstellen, postprocessing_level
3. Vergleich mit klassischer Optimierung: Benchmarking mit klassischen Optimierungslösern
4. Probieren Sie verschiedene Strategien aus : Versuchen Sie, eine bessere Kodierung für das Problem zu finden oder es als HUBO zu formulieren (wenn möglich)
5. Anwendung auf Ihren Bereich : Anpassung der QUBO/HUBO-Formulierungstechniken an Ihre eigenen Optimierungsprobleme

Referenzen

[1] IBM Quantum. "Kipu-Quanten-Optimierung " IBM Quantum Dokumentation.

[2] QOBLIB - Quantenoptimierungs-Benchmarking-Bibliothek. Zuse-Institut 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). "Der intraktable Zehnkampf: Benchmarking schwerer kombinatorischer Probleme" INFORMS Journal on Computing.