{ "cells": [ { "cell_type": "markdown", "id": "title", "metadata": {}, "source": [ "---\n", "title: \"Lösen Sie das Problem der Marktsplittung mit dem Iskay Quantum Optimizer von Kipu Quantum\"\n", "description: \"Erfahren Sie, wie Sie das Problem der Marktsplittung mit dem Iskay Quantum Optimizer und dem bf-DCQO-Algorithmus auf der Hardware „ IBM Quantum ” lösen können\"\n", "---\n", "\n", "\n", "\n", "# Lösen Sie das Problem der Marktsplittung mit dem Iskay Quantum Optimizer von Kipu Quantum\n", "\n", "{/* cspell:ignore adiabaticity, HUBO, bitflip, metaheuristic, fontweight, fontsize, QOBLIB, Zuse, Kochenberger, Tramontani, Weninger, edgecolor, nonumber */}\n", "\n" ] }, { "cell_type": "markdown", "id": "note", "metadata": {}, "source": [ "\n", " Qiskit Functions sind eine experimentelle Funktion, die nur für Nutzer der Pläne IBM Quantum® Premium Plan, Flex Plan und On-Prem (über IBM Quantum Platform API) verfügbar ist. Sie befinden sich im Status einer Vorabversion und können sich noch ändern.\n", "\n", "\n", "*Geschätzte Nutzungsdauer: 20 Sekunden auf einem Heron r2 Prozessor. (HINWEIS: Dies ist nur eine Schätzung. Ihre Laufzeit kann variieren.)*\n", "\n" ] }, { "cell_type": "markdown", "id": "background", "metadata": {}, "source": [ "\n", "\n", "## Hintergrund\n", "\n", "Dieses Tutorial zeigt, wie man das Problem der Marktaufteilung mit dem [Iskay-Quantenoptimierer von Kipu Quantum](/docs/guides/kipu-optimization) [\\[1\\]](#references) 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.\n", "\n", "\n", "\n", "### Die Herausforderung der Marktsplittung\n", "\n", "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.\n", "\n", "**Mathematische Formulierung:**\n", "\n", "Wir suchen einen binären Zuweisungsvektor $x$, wobei:\n", "\n", "* $x_j = 1$ weist den Markt $j$ der Region A zu\n", "* $x_j = 0$ weist den Markt $j$ der Region B zu\n", "* Die Bedingung $Ax = b$ muss erfüllt sein, wobei $b$ den Zielabsatz darstellt (in der Regel die Hälfte der Gesamtnachfrage pro Produkt)\n", "\n", "**Kostenfunktion:**\n", "\n", "Um dieses Problem zu lösen, minimieren wir die quadrierte Verletzung der Nebenbedingung:\n", "\n", "$C(x) = ||Ax - b||^2 = \\sum_{i=1}^{m} \\left(\\sum_{j=1}^{n} A_{ij}x_j - b_i\\right)^2$\n", "\n", "Dabei gilt:\n", "\n", "* $A_{ij}$ steht für die Verkäufe des Produkts $i$ auf dem Markt $j$\n", "* $x_j \\in \\{0,1\\}$ ist die binäre Zuordnung des Marktes $j$\n", "* $b_i$ ist der Zielumsatz für das Produkt $i$ in jeder Region\n", "* Die Kosten sind genau dann gleich Null, wenn alle Nebenbedingungen erfüllt sind\n", "\n", "Jeder Term in der Summe stellt die quadrierte Abweichung vom Umsatzziel für ein bestimmtes Produkt dar. Wenn wir diese Kostenfunktion erweitern, erhalten wir:\n", "\n", "$C(x) = x^T A^T A x - 2b^T A x + b^T b$\n", "\n", "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.\n", "\n", "**Rechnerische Komplexität:**\n", "\n", "Trotz seiner einfachen betriebswirtschaftlichen Auslegung weist dieses Problem eine bemerkenswerte rechnerische Unlösbarkeit auf:\n", "\n", "* **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\\]](#references)\n", "* **Exponentielles Wachstum** : Der Lösungsraum wächst exponentiell ( $2^n$ mögliche Zuordnungen), so dass Brute-Force-Ansätze nicht durchführbar sind\n", "\n", "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\\]](#references).\n", "\n", "\n", "\n", "### Was macht Iskays Ansatz so einzigartig?\n", "\n", "Der Iskay-Optimierer verwendet den **bf-DCQO-Algorithmus (bias-field digitized counterdiabatic quantum optimization)** [\\[1\\]](#references), der einen bedeutenden Fortschritt in der Quantenoptimierung darstellt:\n", "\n", "**Effizienz der Schaltung** : Der bf-DCQO-Algorithmus erreicht eine bemerkenswerte Gatterreduzierung [\\[1\\]](#references) :\n", "\n", "* Bis zu **10 Mal weniger Verschränkungsgatter** als bei Digital Quantum Annealing (DQA)\n", "* Erheblich flachere Schaltkreise ermöglichen:\n", " * Weniger Fehlerakkumulation während der Quantenausführung\n", " * Fähigkeit, größere Probleme auf aktueller Quanten-Hardware zu bewältigen\n", " * Keine Notwendigkeit für Fehlerbegrenzungstechniken\n", "\n", "**Nicht-variationsbasierter Entwurf** : Im Gegensatz zu Variationsalgorithmen, die etwa 100 Iterationen erfordern, benötigt bf-DCQO typischerweise nur **etwa 10 Iterationen** [\\[1\\]](#references). Dies wird erreicht durch:\n", "\n", "* Intelligente Bias-Field-Berechnungen aus gemessenen Zustandsverteilungen\n", "* Jede Iteration beginnt mit einem Energiezustand nahe der vorherigen Lösung\n", "* Integriertes klassisches Post-Processing mit lokaler Suche\n", "\n", "**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\\]](#references).\n", "\n" ] }, { "cell_type": "markdown", "id": "requirements", "metadata": {}, "source": [ "\n", "\n", "## Anforderungen\n", "\n", "Vergewissern Sie sich vor Beginn dieses Tutorials, dass Sie die folgenden Komponenten installiert haben:\n", "\n", "* Qiskit IBM Laufzeit (`pip install qiskit-ibm-runtime`)\n", "* Qiskit Functions (`pip install qiskit-ibm-catalog`)\n", "* NumPy (`pip install numpy`)\n", "* Anfragen (`pip install requests`)\n", "* Opt Mapper Qiskit Zusatzprogramm (`pip install qiskit-addon-opt-mapper`)\n", "\n", "Sie müssen auch Zugang zur [Iskay Quantum Optimizer Funktion](/functions?id=kipu-quantum-iskay-quantum-optimizer) von Qiskit Functions Catalog erhalten.\n", "\n" ] }, { "cell_type": "markdown", "id": "setup", "metadata": {}, "source": [ "\n", "\n", "## Einrichtung\n", "\n", "Importieren Sie zunächst alle für dieses Tutorial benötigten Pakete.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "imports", "metadata": {}, "outputs": [], "source": [ "import os\n", "import tempfile\n", "import time\n", "from typing import Tuple, Optional\n", "\n", "import numpy as np\n", "import requests\n", "\n", "from qiskit_ibm_catalog import QiskitFunctionsCatalog\n", "\n", "from qiskit_addon_opt_mapper import OptimizationProblem\n", "from qiskit_addon_opt_mapper.converters import OptimizationProblemToQubo\n", "\n", "print(\"All required libraries imported successfully\")" ] }, { "cell_type": "markdown", "id": "credentials", "metadata": {}, "source": [ "\n", "\n", "### IBM Quantum -Anmeldedaten konfigurieren\n", "\n", "Definieren Sie Ihre [IBM Quantum® Platform](/) berechtigungsnachweise. Sie benötigen:\n", "\n", "* **API-Token** : Ihr 44-stelliger API-Schlüssel aus IBM Quantum Platform\n", "* **Instanz-CRN** : Ihr IBM Cloud® Instanz-Identifikator\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "creds", "metadata": {}, "outputs": [], "source": [ "token = \"\"\n", "instance = \"\"" ] }, { "cell_type": "markdown", "id": "step1", "metadata": {}, "source": [ "\n", "\n", "## Schritt 1: Klassische Eingaben einem Quantenproblem zuordnen\n", "\n", "Wir beginnen damit, unser klassisches Problem auf eine quantenkompatible Darstellung abzubilden. Dieser Schritt umfasst:\n", "\n", "1. Verbinden mit dem Iskay Quantum Optimizer\n", "2. Belastung und Formulierung des Marktaufteilungsproblems\n", "3. Verstehen des bf-DCQO-Algorithmus, der die Aufgabe lösen wird\n", "\n", "\n", "\n", "### Verbinden Sie sich mit Iskay Quantum Optimizer\n", "\n", "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.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "load_solver", "metadata": {}, "outputs": [], "source": [ "catalog = QiskitFunctionsCatalog(token=token, instance=instance)\n", "iskay_solver = catalog.load(\"kipu-quantum/iskay-quantum-optimizer\")\n", "\n", "print(\"Iskay optimizer loaded successfully\")\n", "print(\"Ready to solve optimization problems using bf-DCQO algorithm\")" ] }, { "cell_type": "markdown", "id": "step2", "metadata": {}, "source": [ "\n", "\n", "### Das Problem laden und formulieren\n", "\n", "\n", "\n", "#### Das Problem mit dem Datenformat verstehen\n", "\n", "Probleminstanzen aus QOBLIB (Quantum Optimization Benchmarking Library) [\\[2\\]](#references) sind in einem einfachen Textformat gespeichert. Schauen wir uns den tatsächlichen Inhalt unserer Zielinstanz `ms_03_200_177.dat` an:\n", "\n", "```text\n", "3 20\n", "60 92 161 53 97 2 75 81 6 139 132 45 108 112 181 93 152 200 164 51 1002\n", "176 196 41 143 2 88 0 79 10 71 75 148 82 135 34 187 33 155 58 46 879\n", "68 68 179 173 127 163 48 49 99 78 44 52 173 131 73 198 84 109 180 95 1040\n", "```\n", "\n", "**Struktur des Formats:**\n", "\n", "* **Erste Zeile:** `3 20`\n", " * `3` = Anzahl der Produkte (Nebenbedingungen/Zeilen in der Matrix $A$ )\n", " * `20` = Anzahl der Märkte (Variablen/Spalten in der Matrix $A$ )\n", "\n", "* **Die nächsten 3 Zeilen:** Koeffizientenmatrix $A$ und Zielvektor $b$\n", " * Jede Zeile hat 21 Zahlen: die ersten 20 sind Zeilenkoeffizienten, die letzte ist das Ziel\n", " * Zeile 2: `60 92 161 ... 51 | 1002`\n", " * Die ersten 20 Zahlen: Wie viel von Produkt 1 wird auf jedem der 20 Märkte verkauft?\n", " * Letzte Zahl (1002): Umsatzziel für Produkt 1 in einer Region\n", " * Zeile 3: `176 196 41 ... 46 | 879`\n", " * Produkt 2 Umsatz nach Markt und Ziel (879)\n", " * Zeile 4: `68 68 179 ... 95 | 1040`\n", " * Produkt 3 Umsatz nach Markt und Ziel (1040)\n", "\n", "**Geschäftsinterpretation:**\n", "\n", "* Markt 0 verkauft: 60 Einheiten von Produkt 1, 176 Einheiten von Produkt 2, 68 Einheiten von Produkt 3\n", "* Markt 1 verkauft: 92 Einheiten von Produkt 1, 196 Einheiten von Produkt 2, 68 Einheiten von Produkt 3\n", "* Und so weiter für alle 20 Märkte...\n", "* **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\n", "\n", "\n", "\n", "#### QUBO-Transformation\n", "\n", "\n", "\n", "## Von Einschränkungen zu QUBO: die mathematische Transformation\n", "\n", "Die Stärke der Quantenoptimierung liegt in der Umwandlung eingeschränkter Probleme in uneingeschränkte quadratische Formen [\\[4\\]](#references). Für das Market-Split-Problem wandeln wir die Gleichheitsrestriktionen um\n", "\n", "$Ax = b$\n", "\n", "wobei $x ∈ \\{0,1\\}^n$, in ein QUBO umgewandelt wird, indem Verstöße gegen Beschränkungen bestraft werden.\n", "\n", "**Die Strafmethode:** Da wir $Ax = b$ genau einhalten müssen, minimieren wir die quadrierte Verletzung: $f(x) = ||Ax - b||^2$\n", "\n", "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$\n", "\n", "**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$\n", "\n", "**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\\]](#references). 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.\n", "\n" ] }, { "cell_type": "markdown", "id": "functions_intro", "metadata": {}, "source": [ "\n", "\n", "### Implementierung von Datenlade- und QUBO-Konvertierungsfunktionen\n", "\n", "Wir definieren nun drei Nutzenfunktionen:\n", "\n", "1. `parse_marketsplit_dat()` - Analysiert das Dateiformat `.dat` und extrahiert die Matrizen $A$ und $b$\n", "2. `fetch_marketsplit_data()` - Lädt problematische Instanzen direkt aus dem QOBLIB-Repository herunter\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "functions", "metadata": {}, "outputs": [], "source": [ "def parse_marketsplit_dat(filename: str) -> Tuple[np.ndarray, np.ndarray]:\n", " \"\"\"\n", " Parse a market split problem from a .dat file format.\n", "\n", " Parameters\n", " ----------\n", " filename : str\n", " Path to the .dat file containing the market split problem data.\n", "\n", " Returns\n", " -------\n", " A : np.ndarray\n", " Coefficient matrix of shape (m, n) where m is the number of products\n", " and n is the number of markets.\n", " b : np.ndarray\n", " Target vector of shape (m,) containing the target sales per product.\n", " \"\"\"\n", " with open(filename, \"r\", encoding=\"utf-8\") as f:\n", " lines = [\n", " line.strip()\n", " for line in f\n", " if line.strip() and not line.startswith(\"#\")\n", " ]\n", "\n", " if not lines:\n", " raise ValueError(\"Empty or invalid .dat file\")\n", "\n", " # First line: m n (number of products and markets)\n", " m, n = map(int, lines[0].split())\n", "\n", " # Next m lines: each row of A followed by corresponding element of b\n", " A, b = [], []\n", " for i in range(1, m + 1):\n", " values = list(map(int, lines[i].split()))\n", " A.append(values[:-1]) # First n values: product sales per market\n", " b.append(values[-1]) # Last value: target sales for this product\n", "\n", " return np.array(A, dtype=np.int32), np.array(b, dtype=np.int32)\n", "\n", "\n", "def fetch_marketsplit_data(\n", " instance_name: str = \"ms_03_200_177.dat\",\n", ") -> Tuple[Optional[np.ndarray], Optional[np.ndarray]]:\n", " \"\"\"\n", " Fetch market split data directly from the QOBLIB repository.\n", "\n", " Parameters\n", " ----------\n", " instance_name : str\n", " Name of the .dat file to fetch (default: \"ms_03_200_177.dat\").\n", "\n", " Returns\n", " -------\n", " A : np.ndarray or None\n", " Coefficient matrix if successful, None if failed.\n", " b : np.ndarray or None\n", " Target vector if successful, None if failed.\n", " \"\"\"\n", " url = f\"https://git.zib.de/qopt/qoblib-quantum-optimization-benchmarking-library/-/raw/main/01-marketsplit/instances/{instance_name}\"\n", "\n", " try:\n", " response = requests.get(url, timeout=30)\n", " response.raise_for_status()\n", "\n", " with tempfile.NamedTemporaryFile(\n", " mode=\"w\", suffix=\".dat\", delete=False, encoding=\"utf-8\"\n", " ) as f:\n", " f.write(response.text)\n", " temp_path = f.name\n", "\n", " try:\n", " return parse_marketsplit_dat(temp_path)\n", " finally:\n", " os.unlink(temp_path)\n", " except Exception as e:\n", " print(f\"Error: {e}\")\n", " return None, None" ] }, { "cell_type": "markdown", "id": "load_intro", "metadata": {}, "source": [ "\n", "\n", "### Laden Sie die Probleminstanz\n", "\n", "Nun laden wir die spezifische Probleminstanz `ms_03_200_177.dat` aus QOBLIB \\[2]. Diese Instanz hat:\n", "\n", "* 3 Produkte (Zwänge)\n", "* 20 Märkte (binäre Entscheidungsvariablen)\n", "* Über 1 Million möglicher Marktzuordnungen zu erkunden ( $2^{20} = 1,048,576$ )\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "load", "metadata": {}, "outputs": [], "source": [ "# Load the problem instance\n", "instance_name = \"ms_03_200_177.dat\"\n", "A, b = fetch_marketsplit_data(instance_name=instance_name)\n", "\n", "if A is not None:\n", " print(\"Successfully loaded problem instance from QOBLIB\")\n", " print(\"\\nProblem Instance Analysis:\")\n", " print(\"=\" * 50)\n", " print(f\"Coefficient Matrix A: {A.shape[0]} × {A.shape[1]}\")\n", " print(f\" → {A.shape[0]} products (constraints)\")\n", " print(f\" → {A.shape[1]} markets (decision variables)\")\n", " print(f\"Target Vector b: {b}\")\n", " print(\" → Target sales per product for each region\")\n", " print(\n", " f\"Solution Space: \"\n", " f\"2^{A.shape[1]} = {2**A.shape[1]:,} possible assignments\"\n", " )" ] }, { "cell_type": "markdown", "id": "convert_intro", "metadata": {}, "source": [ "\n", "\n", "### In das QUBO-Format konvertieren\n", "\n", "Wir transformieren nun das eingeschränkte Optimierungsproblem in das QUBO-Format:\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "convert", "metadata": {}, "outputs": [], "source": [ "# Create optimization problem\n", "ms = OptimizationProblem(instance_name.replace(\".dat\", \"\"))\n", "\n", "# Add binary variables (one for each market)\n", "ms.binary_var_list(A.shape[1])\n", "\n", "# Add equality constraints (one for each product)\n", "for idx, rhs in enumerate(b):\n", " ms.linear_constraint(A[idx, :], sense=\"==\", rhs=rhs)\n", "\n", "# Convert to QUBO with penalty parameter\n", "qubo = OptimizationProblemToQubo(penalty=1).convert(ms)\n", "\n", "print(\"QUBO Conversion Complete:\")\n", "print(\"=\" * 50)\n", "print(f\"Number of variables: {qubo.get_num_vars()}\")\n", "print(f\"Constant term: {qubo.objective.constant}\")\n", "print(f\"Linear terms: {len(qubo.objective.linear.to_dict())}\")\n", "print(f\"Quadratic terms: {len(qubo.objective.quadratic.to_dict())}\")" ] }, { "cell_type": "markdown", "id": "1d307072", "metadata": {}, "source": [ "\n", "\n", "### QUBO in das Iskay-Format konvertieren\n", "\n", "Nun müssen wir das QUBO-Objekt in das für den Iskay-Optimierer von Kipu Quantum erforderliche Wörterbuchformat umwandeln.\n", "\n", "Die Argumente `problem` und `problem_type` kodieren ein Optimierungsproblem der Form\n", "\n", "$$\n", "\\begin{align}\n", "\\min_{(x_1, x_2, \\ldots, x_n) \\in D} C(x_1, x_2, \\ldots, x_n) \\nonumber\n", "\\end{align}\n", "$$\n", "\n", "wo\n", "\n", "$$\n", "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}\n", "$$\n", "\n", "* 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.\n", "* Andererseits wird die Kostenfunktion durch die Wahl von `problem_type = \"spin\"` in der Ising-Formel geschrieben, wobei $D = \\{-1, 1\\}^{n}$.\n", "\n", "Die Koeffizienten des Problems sollten wie folgt in einem Wörterbuch kodiert werden:\n", "\n", "$$\n", "\\begin{align} \\nonumber\n", "&\\texttt{\\{} \\\\ \\nonumber\n", "&\\texttt{\"()\"}&: \\quad &a, \\\\ \\nonumber\n", "&\\texttt{\"(i,)\"}&: \\quad &b_i, \\\\ \\nonumber\n", "&\\texttt{\"(i, j)\"}&: \\quad &c_{i, j}, \\quad (i \\neq j) \\\\ \\nonumber\n", "&\\quad \\vdots \\\\ \\nonumber\n", "&\\texttt{\"(} k_1, ..., k_m \\texttt{)\"}&: \\quad &g_{k_1, ..., k_m}, \\quad (k_1 \\neq k_2 \\neq \\dots \\neq k_m) \\\\ \\nonumber\n", "&\\texttt{\\}}\n", "\\end{align}\n", "$$\n", "\n", "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:\n", "\n", "$$\n", "x_i^2 = x_i\n", "$$\n", "\n", "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:\n", "\n", "**Linearer Gesamtkoeffizient für die Variable $x_i$** : $b_i + c_{i,i}$\n", "\n", "Das bedeutet:\n", "\n", "* Lineare Terme wie `\"(i, )\"` enthalten: ursprünglicher linearer Koeffizient + diagonaler quadratischer Koeffizient\n", "* Diagonale quadratische Begriffe wie `\"(i, i)\"` sollten **NICHT** im endgültigen Wörterbuch erscheinen\n", "* Nur außendiagonale quadratische Terme wie `\"(i, j)\"` und $i \\neq j$ sollten als separate Einträge aufgenommen werden\n", "\n", "**Beispiel:** Wenn Ihr QUBO $3x_1 + 2x_1^2 + 4x_1 x_2$ hat, sollte das Iskay-Wörterbuch Folgendes enthalten:\n", "\n", "* `\"(0, )\"`: `5.0` (kombiniert $3 + 2 = 5$ )\n", "* `\"(0, 1)\"` `4.0` (nicht diagonaler Term)\n", "\n", "**KEINE** separaten Einträge für `\"(0, )\"`: `3.0` und `\"(0, 0)\"`: `2.0`.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "57eda6fd", "metadata": {}, "outputs": [], "source": [ "# Convert QUBO to Iskay dictionary format:\n", "\n", "# Create empty Iskay input dictionary\n", "iskay_input_problem = {}\n", "\n", "# Convert QUBO to Iskay dictionary format\n", "iskay_input_problem = {\"()\": qubo.objective.constant}\n", "\n", "for i in range(qubo.get_num_vars()):\n", " for j in range(i, qubo.get_num_vars()):\n", " if i == j:\n", " # Add linear term (including diagonal quadratic contribution)\n", " iskay_input_problem[f\"({i}, )\"] = float(\n", " qubo.objective.linear.to_dict().get(i)\n", " ) + float(qubo.objective.quadratic.to_dict().get((i, i)))\n", " else:\n", " # Add off-diagonal quadratic term\n", " iskay_input_problem[f\"({i}, {j})\"] = float(\n", " qubo.objective.quadratic.to_dict().get((i, j))\n", " )\n", "\n", "# Display Iskay dictionary summary\n", "print(\"Iskay Dictionary Format:\")\n", "print(\"=\" * 50)\n", "print(f\"Total coefficients: {len(iskay_input_problem)}\")\n", "print(f\" • Constant term: {iskay_input_problem['()']}\")\n", "print(\n", " f\" • Linear terms: \"\n", " f\"{sum(1 for k in iskay_input_problem.keys() if k != '()' and ', )' in k)}\"\n", ")\n", "print(\n", " f\" • Quadratic terms: \"\n", " f\"{sum(1 for k in iskay_input_problem.keys() if k != '()' and ', )' not in k)}\"\n", ")\n", "print(\"\\nSample coefficients:\")\n", "\n", "# Get first 10 and last 5 items properly\n", "items = list(iskay_input_problem.items())\n", "first_10 = list(enumerate(items[:10]))\n", "last_5 = list(enumerate(items[-5:], start=len(items) - 5))\n", "\n", "for i, (key, value) in first_10 + last_5:\n", " coeff_type = (\n", " \"constant\"\n", " if key == \"()\"\n", " else \"linear\"\n", " if \", )\" in key\n", " else \"quadratic\"\n", " )\n", " print(f\" {key}: {value} ({coeff_type})\")\n", "print(\" ...\")\n", "print(\"\\n✓ Problem ready for Iskay optimizer!\")" ] }, { "cell_type": "markdown", "id": "step3", "metadata": {}, "source": [ "\n", "\n", "### Den bf-DCQO-Algorithmus verstehen\n", "\n", "Bevor wir die Optimierung durchführen, sollten wir den hochentwickelten Quantenalgorithmus verstehen, der Iskay antreibt: **bf-DCQO (bias-field digitized counterdiabatic quantum optimization)** [\\[1\\]](#references).\n", "\n", "\n", "\n", "#### Was ist bf-DCQO?\n", "\n", "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\\]](#references). Der Algorithmus adressiert eine grundlegende Herausforderung in der Quantenoptimierung:\n", "\n", "**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.\n", "\n", "**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.\n", "\n", "\n", "\n", "#### Mathematischer Rahmen\n", "\n", "Der Algorithmus minimiert eine Kostenfunktion der Form:\n", "\n", "$\\min_{(x_1,x_2,...,x_n) \\in D} C(x_1,x_2,...,x_n)$\n", "\n", "wobei $D = \\{0,1\\}^n$ für binäre Variablen und:\n", "\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}$\n", "\n", "Für unser Marktaufteilungsproblem lautet die Kostenfunktion:\n", "\n", "$C(x) = ||Ax - b||^2 = x^T A^T A x - 2 b^T A x + b^T b$\n", "\n", "\n", "\n", "#### Die Rolle der gegen-diabetischen Begriffe\n", "\n", "**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:\n", "\n", "Bei der adiabatischen Quantenoptimierung entwickeln wir das System gemäß einem zeitabhängigen Hamiltonian:\n", "\n", "$H(t) = \\left(1 - \\frac{t}{T}\\right) H_{\\text{initial}} + \\frac{t}{T} H_{\\text{problem}}$\n", "\n", "wobei $H_{\\text{problem}}$ unser Optimierungsproblem kodiert. Um den Grundzustand während der schnellen Entwicklung aufrechtzuerhalten, fügen wir gegendiabatische Terme hinzu:\n", "\n", "$H_{\\text{CD}}(t) = H(t) + H_{\\text{counter}}(t)$\n", "\n", "Diese gegendiabatischen Terme bewirken Folgendes:\n", "\n", "1. **Unerwünschte Übergänge unterdrücken** : Verhindern, dass der Quantenzustand während der schnellen Entwicklung in angeregte Zustände springt\n", "2. **Ermöglicht kürzere Entwicklungszeiten** : Wir können den Endzustand viel schneller erreichen, ohne die Adiabatizität zu verletzen\n", "3. **Verringerung der Schaltungstiefe** : Eine kürzere Entwicklung führt zu weniger Gattern und weniger Fehlern\n", "\n", "Die praktischen Auswirkungen sind dramatisch: bf-DCQO benötigt bis zu **10-mal weniger Verschränkungsgatter** als Digital Quantum Annealing [\\[1\\]](#references), was es für die heutige verrauschte Quantenhardware praktikabel macht.\n", "\n", "\n", "\n", "#### Iterative Optimierung mit Bias-Feld\n", "\n", "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] :\n", "\n", "**Iterationsprozess:**\n", "\n", "1. **Anfängliche Quantenevolution** : Beginnen Sie mit einer Quantenschaltung, die das gegendiabatische Evolutionsprotokoll implementiert\n", "\n", "2. **Messung** : Messung des Quantenzustands, um eine Wahrscheinlichkeitsverteilung über Bitstrings zu erhalten\n", "\n", "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})$\n", "\n", "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$\n", "\n", " Dies ermöglicht es, in der Nähe der zuvor gefundenen guten Lösung zu beginnen und so eine Art \"lokale Quantensuche\" durchzuführen\n", "\n", "5. **Konvergenz** : Wiederholen, bis sich die Lösungsqualität stabilisiert oder eine maximale Anzahl von Iterationen erreicht ist\n", "\n", "**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.\n", "\n", "\n", "\n", "#### Integrierte klassische Nachbearbeitung\n", "\n", "Nachdem die Quantenoptimierung konvergiert, führt Iskay eine klassische **lokale Suche** durch:\n", "\n", "* **Bit-flip Exploration** : Systematisches oder zufälliges Umdrehen von Bits in der besten gemessenen Lösung\n", "* **Bewertung der Energie** : Berechnen Sie $C(x)$ für jede modifizierte Lösung\n", "* **Gierige Auswahl** : Akzeptieren Sie Verbesserungen, die die Kostenfunktion senken\n", "* **Mehrere Durchgänge** : Mehrere Durchgänge durchführen (gesteuert durch `postprocessing_level`)\n", "\n", "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.\n", "\n", "\n", "\n", "#### Warum bf-DCQO auf aktueller Hardware herausragende Leistungen erbringt\n", "\n", "Der bf-DCQO-Algorithmus wurde speziell entwickelt, um auf den heutigen verrauschten Quantengeräten im mittleren Maßstab (NISQ) zu glänzen [\\[1\\]](#references) :\n", "\n", "1. **Fehlerunempfindlichkeit** : Weniger Gatter (10-fache Reduktion) bedeutet drastisch weniger Fehlerakkumulation\n", "2. **Keine Fehlerbegrenzung erforderlich** : Die inhärente Effizienz des Algorithmus macht teure Techniken zur Fehlerbegrenzung überflüssig [\\[1\\]](#references)\n", "3. **Skalierbarkeit** : Kann Probleme mit bis zu 156 Qubits (156 binäre Variablen) mit direktem Qubit-Mapping behandeln [\\[1\\]](#references)\n", "4. **Bewährte Leistung** : Erzielt 100%ige Annäherungsraten bei den Benchmark-Instanzen MaxCut und HUBO [\\[1\\]](#references)\n", "\n", "Sehen wir uns nun diesen leistungsstarken Algorithmus in Aktion bei unserem Marktaufteilungsproblem an!\n", "\n" ] }, { "cell_type": "markdown", "id": "step4", "metadata": {}, "source": [ "\n", "\n", "## Schritt 2: Optimierung des Problems für die Ausführung auf Quantenhardware\n", "\n", "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.\n", "\n", "\n", "\n", "### Konfigurieren Sie die Optimierung\n", "\n", "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:\n", "\n", "\n", "\n", "#### Erforderliche Parameter\n", "\n", "| Parameter | Typ | Beschreibung | Beispiel |\n", "| ------------------------ | ------------------ | --------------------------------------------------------- | ------------------------------------------- |\n", "| **trat ein Problem auf** | `Dict[str, float]` | QUBO-Koeffizienten im String-Key-Format | `{\"()\": -21.0, \"(0,4)\": 0.5, \"(0,1)\": 0.5}` |\n", "| **problem\\_typ** | `str` | Formatangabe: `\"binary\"` für QUBO oder `\"spin\"` für Ising | `\"binary\"` |\n", "| **backend\\_name** | `str` | Ziel-Quantengerät | `\"ibm_fez\"` |\n", "\n", "\n", "\n", "#### Wesentliche Konzepte\n", "\n", "* **Problemformat** : Wir verwenden `\"binary\"` , da unsere Variablen binär (0/1) sind und Marktzuweisungen darstellen.\n", "* **Auswahl des Backends** : Wählen Sie zwischen den verfügbaren QPUs (z. B. `\"ibm_fez\"`) je nach Bedarf und Rechenressourceninstanz.\n", "* **QUBO-Struktur** : Unser Problemwörterbuch enthält die genauen Koeffizienten der mathematischen Transformation.\n", "\n", "\n", "\n", "#### Erweiterte Optionen (optional)\n", "\n", "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:\n", "\n", "| Parameter | Typ | Standard | Beschreibung |\n", "| -------------------------- | ----------- | -------- | ------------------------------------------------------------------------------------ |\n", "| **Shots** | `int` | 10.000 | Quantenmessungen pro Iteration (höher = genauer) |\n", "| **num\\_iterations** | `int` | 10 | Iterationen des Algorithmus (mehr Iterationen können die Lösungsqualität verbessern) |\n", "| **nutzen\\_session** | `bool` | Ja | Verwenden Sie IBM Sitzungen für kürzere Wartezeiten |\n", "| **seed\\_transpiler** | `int` | Keine | Set für die reproduzierbare Zusammenstellung von Quantenschaltungen |\n", "| **direkt\\_qubit\\_mapping** | `bool` | Falsch | Virtuelle Qubits direkt auf physikalische Qubits abbilden |\n", "| **job\\_tags** | `List[str]` | Keine | Benutzerdefinierte Tags für die Auftragsverfolgung |\n", "| **vorverarbeitung\\_level** | `int` | 0 | Intensität der Problembearbeitung (0-3) - siehe Details unten |\n", "| **nachbearbeitung\\_level** | `int` | 2 | Verfeinerungsgrad der Lösung (0-2) - siehe Details unten |\n", "| **transpilation\\_level** | `int` | 0 | Versuche zur Optimierung von Transpilern (0-5) - siehe Einzelheiten unten |\n", "| **transpile\\_only** | `bool` | Falsch | Analyse der Schaltungsoptimierung ohne vollständige Ausführung |\n", "\n", "**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:\n", "\n", "* **Stufe 0** : Genaue, längere Schaltungen\n", "* **Stufe 1** : Gutes Gleichgewicht zwischen Genauigkeit und Annäherung, wobei nur die Tore mit Winkeln im untersten 10-Perzentil ausgeschnitten werden\n", "* **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\n", "* **Stufe 3** : Maximale Annäherung, Ausschneiden der Gates im untersten 30-Perzentil und Verwendung von `approximation_degree=0.90` bei der Transpilierung\n", "\n", "**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.\n", "\n", "* **Ebene 0** : Optimierung der zerlegten DCQO-Schaltung (Layout, Routing, Scheduling)\n", "* **Ebene 1** : Optimierung von `PauliEvolutionGate` und dann der zerlegten DCQO-Schaltung ( max\\_trials=10 )\n", "* **Ebene 2** : Optimierung von `PauliEvolutionGate` und dann der zerlegten DCQO-Schaltung ( max\\_trials=15 )\n", "* **Ebene 3** : Optimierung von `PauliEvolutionGate` und dann der zerlegten DCQO-Schaltung ( max\\_trials=20 )\n", "* **Ebene 4** : Optimierung von `PauliEvolutionGate` und dann der zerlegten DCQO-Schaltung ( max\\_trials=25 )\n", "* **Ebene 5** : Optimierung von `PauliEvolutionGate` und dann der zerlegten DCQO-Schaltung ( max\\_trials=50 )\n", "\n", "**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:\n", "\n", "* **Stufe 0** : 1 Durchgang\n", "* **Stufe 1** : 2 Pässe\n", "* **Stufe 2** : 3 Pässe\n", "\n", "**Transpile-only-Modus** : Jetzt verfügbar für Benutzer, die die Schaltkreisoptimierung analysieren möchten, ohne den gesamten Quantenalgorithmus auszuführen.\n", "\n", "\n", "\n", "#### Beispiel für eine benutzerdefinierte Konfiguration\n", "\n", "Hier sehen Sie, wie Sie Iskay mit verschiedenen Einstellungen konfigurieren könnten:\n", "\n", "```python\n", "custom_options = {\n", " # Higher shot count for better statistics\n", " \"shots\": 15_000,\n", "\n", " # More iterations for solution refinement\n", " \"num_iterations\": 12,\n", "\n", " # Light preprocessing for problem simplification\n", " \"preprocessing_level\": 1,\n", "\n", " # Maximum postprocessing for solution quality\n", " \"postprocessing_level\": 2,\n", "\n", " # Using higher transpilation level for circuit optimization\n", " \"transpilation_level\": 3,\n", "\n", " # Fixed seed for reproducible results\n", " \"seed_transpiler\": 42,\n", "\n", " # Custom tracking tags\n", " \"job_tags\": [\"market_split\"]\n", "}\n", "```\n", "\n" ] }, { "cell_type": "markdown", "id": "86e2b10d", "metadata": {}, "source": [ "In diesem Tutorial werden wir die meisten Standardparameter beibehalten und nur die Anzahl der Iterationen des Bias-Feldes ändern:\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "config", "metadata": {}, "outputs": [], "source": [ "# Specify the target backend\n", "backend_name = \"ibm_fez\"\n", "\n", "# Set the number of bias-field iterations and set a tag to identify the jobs\n", "options = {\n", " \"num_iterations\": 3, # Change number of bias-field iterations\n", " \"job_tags\": [\"market_split_example\"], # Tag to identify jobs\n", "}\n", "\n", "# Configure Iskay optimizer\n", "iskay_input = {\n", " \"problem\": iskay_input_problem,\n", " \"problem_type\": \"binary\",\n", " \"backend_name\": backend_name,\n", " \"options\": options,\n", "}\n", "\n", "print(\"Iskay Optimizer Configuration:\")\n", "print(\"=\" * 40)\n", "print(f\" Backend: {backend_name}\")\n", "print(f\" Problem: {len(iskay_input['problem'])} terms\")\n", "print(\" Algorithm: bf-DCQO\")" ] }, { "cell_type": "markdown", "id": "submit_intro", "metadata": {}, "source": [ "\n", "\n", "## Schritt 3: Mit „ Qiskit primitives “ ausführen\n", "\n", "Wir unterbreiten nun unser Problem zur Ausführung auf IBM Quantum Hardware. Der bf-DCQO-Algorithmus wird:\n", "\n", "1. Konstruktion von flachen Quantenkreisen mit gegendiabatischen Termen\n", "2. Führen Sie ca. 10 Iterationen mit Bias-Field-Optimierung durch\n", "3. Klassische Nachbearbeitung mit lokaler Suche durchführen\n", "4. Rückgabe der optimalen Marktzuordnung\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "run", "metadata": {}, "outputs": [], "source": [ "# Submit the optimization job\n", "print(\"Submitting optimization job to Kipu Quantum...\")\n", "print(\n", " f\"Problem size: {A.shape[1]} variables, {len(iskay_input['problem'])} terms\"\n", ")\n", "print(\n", " \"Algorithm: bf-DCQO (bias-field digitized counterdiabatic quantum optimization)\"\n", ")\n", "\n", "job = iskay_solver.run(**iskay_input)\n", "\n", "print(\"\\nJob successfully submitted!\")\n", "print(f\"Job ID: {job.job_id}\")\n", "print(\"Optimization in progress...\")\n", "print(\n", " f\"The bf-DCQO algorithm will efficiently explore \"\n", " f\"{2**A.shape[1]:,} possible assignments\"\n", ")" ] }, { "cell_type": "markdown", "id": "status_intro", "metadata": {}, "source": [ "\n", "\n", "### Auftragsstatus überwachen\n", "\n", "Sie können den aktuellen Status Ihres Optimierungsauftrags überprüfen. Gültige Statusangaben sind:\n", "\n", "* `QUEUED`: Der Auftrag wartet in der Warteschlange\n", "* `RUNNING`: Job wird derzeit auf Quanten-Hardware ausgeführt\n", "* `DONE`: Auftrag erfolgreich abgeschlossen\n", "* `CANCELED`: Auftrag wurde storniert\n", "* `ERROR`: Job ist auf einen Fehler gestoßen\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "status", "metadata": {}, "outputs": [], "source": [ "# Check job status\n", "print(f\"Job status: {job.status()}\")" ] }, { "cell_type": "markdown", "id": "wait_intro", "metadata": {}, "source": [ "\n", "\n", "### Warten Sie, bis der Vorgang abgeschlossen ist\n", "\n", "Diese Zelle wird blockiert, bis der Auftrag abgeschlossen ist. Der Optimierungsprozess umfasst:\n", "\n", "* Warteschlangenzeit (Warten auf Quanten-Hardwarezugriff)\n", "* Ausführungszeit (Ausführung des bf-DCQO-Algorithmus mit etwa 10 Iterationen)\n", "* Nachbearbeitungszeit (klassische lokale Suche)\n", "\n", "Je nach den Bedingungen in der Warteschlange liegen die typischen Bearbeitungszeiten zwischen einigen Minuten und mehreren Dutzend Minuten.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "wait", "metadata": {}, "outputs": [], "source": [ "# Wait for job completion\n", "while True:\n", " status = job.status()\n", " print(\n", " f\"Waiting for job {job.job_id} to complete... (status: {status})\",\n", " end=\"\\r\",\n", " flush=True,\n", " )\n", " if status in [\"DONE\", \"CANCELED\", \"ERROR\"]:\n", " print(\n", " f\"\\nJob {job.job_id} completed with status: {status}\" + \" \" * 20\n", " )\n", " break\n", " time.sleep(30)\n", "\n", "# Retrieve the optimization results\n", "result = job.result()\n", "print(\"\\nOptimization complete!\")" ] }, { "cell_type": "markdown", "id": "step5", "metadata": {}, "source": [ "\n", "\n", "## Schritt 4: Nachbearbeitung und Rückgabe des Ergebnisses im gewünschten klassischen Format\n", "\n", "Die Ergebnisse der Quantenausführung werden nun nachbearbeitet. Diese beinhalten:\n", "\n", "* Analysieren der Lösungsstruktur\n", "* Validierung der Erfüllung einer Bedingung\n", "* Benchmarking mit klassischen Ansätzen\n", "\n", "\n", "\n", "### Ergebnisse analysieren\n", "\n", "\n", "\n", "#### Die Ergebnisstruktur verstehen\n", "\n", "Iskay liefert ein umfassendes Ergebniswörterbuch mit:\n", "\n", "* **`solution`**: Ein Wörterbuch, das die Indizes der Variablen auf ihre optimalen Werte (0 oder 1) abbildet\n", "* **`solution_info`**: Detaillierte Informationen, einschließlich:\n", " * `bitstring`: Die optimale Zuordnung als binäre Zeichenkette\n", " * `cost`: Der Wert der Zielfunktion (sollte bei perfekter Erfüllung der Nebenbedingungen 0 sein)\n", " * `mapping`: Wie Bitstring-Positionen auf Problemvariablen abgebildet werden\n", " * `seed_transpiler`: Für die Reproduzierbarkeit verwendetes Saatgut\n", "* **`prob_type`**: Ob die Lösung im Binär- oder Spin-Format vorliegt\n", "\n", "Untersuchen wir die Lösung, die der Quantenoptimierer liefert.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "results", "metadata": {}, "outputs": [], "source": [ "# Display the optimization results\n", "print(\"Optimization Results\")\n", "print(\"=\" * 50)\n", "print(f\"Problem Type: {result['prob_type']}\")\n", "print(\"\\nSolution Info:\")\n", "print(f\" Bitstring: {result['solution_info']['bitstring']}\")\n", "print(f\" Cost: {result['solution_info']['cost']}\")\n", "print(\"\\nSolution (first 10 variables):\")\n", "for i, (var, val) in enumerate(list(result[\"solution\"].items())[:10]):\n", " print(f\" {var}: {val}\")\n", "print(\" ...\")" ] }, { "cell_type": "markdown", "id": "validation_intro", "metadata": {}, "source": [ "\n", "\n", "#### Lösungsprüfung\n", "\n", "Nun überprüfen wir, ob die Quantenlösung die Marktaufteilungsbedingungen erfüllt. Der Validierungsprozess prüft:\n", "\n", "**Was ist eine Beschränkungsverletzung?**\n", "\n", "* Für jedes Produkt $i$ berechnen wir den tatsächlichen Absatz in der Region A: $(Ax)_i$\n", "* Wir vergleichen dies mit dem angestrebten Umsatz $b_i$\n", "* Der **Verstoß** ist der absolute Unterschied: $|(Ax)_i - b_i|$\n", "* Eine **praktikable Lösung** hat für alle Produkte null Verstöße\n", "\n", "**Was wir erwarten:**\n", "\n", "* **Idealfall** : Gesamtübertretung = 0 (alle Nebenbedingungen perfekt erfüllt)\n", " * Region A erhält genau 1002 Einheiten von Produkt 1, 879 Einheiten von Produkt 2 und 1040 Einheiten von Produkt 3\n", " * Region B erhält die restlichen Einheiten (ebenfalls 1002, 879 bzw. 1040)\n", "* **Guter Fall** : Die Gesamtverletzung ist gering (nahezu optimale Lösung)\n", "* **Schlechter Fall** : Große Verstöße deuten darauf hin, dass die Lösung die Geschäftsanforderungen nicht erfüllt\n", "\n", "Die Validierungsfunktion wird berechnet:\n", "\n", "1. Tatsächlicher Umsatz pro Produkt in jeder Region\n", "2. Verstöße gegen Beschränkungen für jedes Produkt\n", "3. Marktverteilung zwischen den Regionen\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "validate", "metadata": {}, "outputs": [], "source": [ "def validate_solution(A, b, solution):\n", " \"\"\"Validate market split solution.\"\"\"\n", " x = np.array(solution)\n", " region_a = A @ x\n", " region_b = A @ (1 - x)\n", " violations = np.abs(region_a - b)\n", "\n", " return {\n", " \"target\": b,\n", " \"region_a\": region_a,\n", " \"region_b\": region_b,\n", " \"violations\": violations,\n", " \"total_violation\": np.sum(violations),\n", " \"is_feasible\": np.sum(violations) == 0,\n", " \"region_a_markets\": int(np.sum(x)),\n", " \"region_b_markets\": len(x) - int(np.sum(x)),\n", " }\n", "\n", "\n", "# Convert bitstring to list of integers and validate\n", "optimal_assignment = [\n", " int(bit) for bit in result[\"solution_info\"][\"bitstring\"]\n", "]\n", "validation = validate_solution(A, b, optimal_assignment)" ] }, { "cell_type": "markdown", "id": "validation_results_intro", "metadata": {}, "source": [ "\n", "\n", "#### Die Validierungsergebnisse interpretieren\n", "\n", "Die Validierungsergebnisse zeigen, ob der Quantum Optimizer eine praktikable Lösung gefunden hat. Betrachten wir das Folgende:\n", "\n", "**Durchführbarkeitsprüfung:**\n", "\n", "* **`is_feasible = True`** bedeutet, dass die Lösung alle Nebenbedingungen perfekt erfüllt (Gesamtverletzung = 0)\n", "* **`is_feasible = False`** bedeutet, dass einige Beschränkungen verletzt werden\n", "\n", "**Verkaufsanalyse:**\n", "\n", "* Vergleich von Soll- und Ist-Verkäufen für jedes Produkt\n", "* Für eine perfekte Lösung: Ist = Soll für alle Produkte in beiden Regionen\n", "* Die Differenz zeigt an, wie nahe wir dem gewünschten Marktsplit sind\n", "\n", "**Vertrieb auf dem Markt:**\n", "\n", "* Zeigt an, wie viele Märkte den einzelnen Regionen zugeordnet sind\n", "* Es ist nicht erforderlich, dass die Anzahl der Märkte gleich ist, sondern nur, dass die Verkaufsziele erreicht werden\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "display_validation", "metadata": {}, "outputs": [], "source": [ "print(\"Solution Validation\")\n", "print(\"=\" * 50)\n", "print(f\"Feasible solution: {validation['is_feasible']}\")\n", "print(f\"Total constraint violation: {validation['total_violation']}\")\n", "\n", "print(\"\\nSales Analysis (Target vs Actual):\")\n", "for i, (target, actual_a, actual_b) in enumerate(\n", " zip(validation[\"target\"], validation[\"region_a\"], validation[\"region_b\"])\n", "):\n", " violation_a = abs(actual_a - target)\n", " violation_b = abs(actual_b - target)\n", " print(f\" Product {i+1}:\")\n", " print(f\" Target: {target}\")\n", " print(f\" Region A: {actual_a} (violation: {violation_a})\")\n", " print(f\" Region B: {actual_b} (violation: {violation_b})\")\n", "\n", "print(\"\\nMarket Distribution:\")\n", "print(f\" Region A: {validation['region_a_markets']} markets\")\n", "print(f\" Region B: {validation['region_b_markets']} markets\")" ] }, { "cell_type": "markdown", "id": "interpretation", "metadata": {}, "source": [ "\n", "\n", "#### Bewertung der Lösungsqualität\n", "\n", "Anhand der obigen Validierungsergebnisse können wir die Qualität der Quantenlösung bewerten:\n", "\n", "**Wenn `is_feasible = True` (Gesamtübertretung = 0):**\n", "\n", "* Der Quantum Optimizer hat erfolgreich eine optimale Lösung gefunden\n", "* Alle geschäftlichen Zwänge werden perfekt erfüllt\n", "* Dies zeigt den Quantenvorteil bei einem Problem, bei dem klassische Löser Schwierigkeiten haben [\\[4\\]](#references)\n", "\n", "**Wenn `is_feasible = False` (Gesamtübertretung > 0):**\n", "\n", "* Die Lösung ist nahezu optimal, aber nicht perfekt\n", "* Geringe Verstöße können in der Praxis akzeptabel sein\n", "* Erwägen Sie eine Anpassung der Optimierungsparameter:\n", " * Erhöhen Sie `num_iterations` für weitere Optimierungsläufe\n", " * Erhöhen Sie `postprocessing_level` für mehr klassische Veredelung\n", " * Erhöhen Sie `shots` für bessere Messstatistiken\n", "\n", "**Interpretation der Kostenfunktion:**\n", "\n", "* Der Wert `cost` von `solution_info` ist gleich $||Ax - b||^2$\n", "* Kosten = 0 bedeutet vollkommene Erfüllung einer Bedingung\n", "* Höhere Kostenwerte deuten auf größere Verstöße gegen Beschränkungen hin\n", "\n" ] }, { "cell_type": "markdown", "id": "conclusion", "metadata": {}, "source": [ "\n", "\n", "## Fazit\n", "\n", "\n", "\n", "### Was wir erreicht haben\n", "\n", "In diesem Tutorium werden wir erfolgreich sein:\n", "\n", "1. **Laden eines realen Optimierungsproblems** : Abrufen einer anspruchsvollen Marktaufteilungsinstanz aus der QOBLIB-Benchmark-Bibliothek \\[2]\n", "2. **In das QUBO-Format umgewandelt** : Umwandlung des eingeschränkten Problems in eine uneingeschränkte quadratische Formulierung \\[3]\n", "3. **Nutzung fortgeschrittener Quantenalgorithmen** : Verwendung des bf-DCQO-Algorithmus von Kipu Quantum mit gegendiabatischen Termen \\[1]\n", "4. **Erzielung optimaler Lösungen** : Gefundene machbare Lösungen, die alle Nebenbedingungen erfüllen\n", "\n", "\n", "\n", "### Kernaspekte\n", "\n", "**Neuartiger Algorithmus** : Der bf-DCQO-Algorithmus stellt eine bedeutende Weiterentwicklung dar [\\[1\\]](#references) :\n", "\n", "* **10-mal weniger Gatter** als beim digitalen Quanten Annealing\n", "* **Etwa 10 Iterationen** anstelle von etwa 100 bei Variationsmethoden\n", "* **Eingebaute Fehlerresistenz** durch Schaltungseffizienz\n", "\n", "**Gegendiabatische Terme** : Ermöglichen eine schnelle Quantenevolution unter Beibehaltung der Grundzustandstreue und machen die Quantenoptimierung auf der heutigen verrauschten Hardware praktisch [\\[1\\]](#references).\n", "\n", "**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\\]](#references).\n", "\n", "\n", "\n", "### Nächste Schritte\n", "\n", "Um Ihr Verständnis zu vertiefen und weiter zu erforschen:\n", "\n", "1. **Probieren Sie verschiedene Instanzen aus** : Experimentieren Sie mit anderen QOBLIB-Instanzen unterschiedlicher Größe\n", "2. **Parameter abstimmen** : `num_iterations`, `preprocessing_level` einstellen, `postprocessing_level`\n", "3. **Vergleich mit klassischer** Optimierung: Benchmarking mit klassischen Optimierungslösern\n", "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)\n", "5. **Anwendung auf Ihren Bereich** : Anpassung der QUBO/HUBO-Formulierungstechniken an Ihre eigenen Optimierungsprobleme\n", "\n", "\n", "\n", "### Referenzen\n", "\n", "\\[1] IBM Quantum. \"[Kipu-Quanten-Optimierung](/docs/guides/kipu-optimization) \" *IBM Quantum Dokumentation*.\n", "\n", "\\[2] QOBLIB - Quantenoptimierungs-Benchmarking-Bibliothek. Zuse-Institut Berlin (ZIB). [https://git.zib.de/qopt/qoblib-quantum-optimization-benchmarking-library](https://git.zib.de/qopt/qoblib-quantum-optimization-benchmarking-library)\n", "\n", "\\[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.\n", "\n", "\\[4] Lodi, A., Tramontani, A., & Weninger, K. (2023). \"Der intraktable Zehnkampf: Benchmarking schwerer kombinatorischer Probleme\" *INFORMS Journal on Computing*.\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "id": "a1b8767d", "source": "© IBM Corp., 2017-2026" } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3" }, "hours": 1, "qpuSeconds": 20 }, "nbformat": 4, "nbformat_minor": 5 }