{ "cells": [ { "cell_type": "markdown", "id": "title", "metadata": {}, "source": [ "---\n", "title: \"Risolvi il problema della frammentazione del mercato con Iskay Quantum Optimizer di Kipu Quantum\"\n", "description: \"Scopri come risolvere il problema della divisione del mercato utilizzando Iskay Quantum Optimizer con l'algoritmo bf-DCQO su un hardware IBM Quantum\"\n", "---\n", "\n", "\n", "\n", "# Risolvi il problema della frammentazione del mercato con Iskay Quantum Optimizer di 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 sono una funzione sperimentale disponibile solo per gli utenti di IBM Quantum® Premium Plan, Flex Plan e On-Prem (tramite IBM Quantum Platform API) Plan. Sono in stato di anteprima e sono soggetti a modifiche.\n", "\n", "\n", "*Stima di utilizzo: 20 secondi su un processore Heron r2. (NOTA: questa è solo una stima. Il tempo di esecuzione potrebbe variare)*\n", "\n" ] }, { "cell_type": "markdown", "id": "background", "metadata": {}, "source": [ "\n", "\n", "## Sfondo\n", "\n", "Questa esercitazione mostra come risolvere il problema del Market Split utilizzando [l'ottimizzatore quantistico Iskay di Kipu Quantum](/docs/guides/kipu-optimization) [\\[1\\]](#references). Il problema della suddivisione del mercato rappresenta una sfida reale di allocazione delle risorse, in cui i mercati devono essere suddivisi in regioni di vendita bilanciate per soddisfare obiettivi di domanda precisi.\n", "\n", "\n", "\n", "### La sfida della divisione del mercato\n", "\n", "Il problema della divisione del mercato presenta una sfida ingannevolmente semplice ma computazionalmente formidabile nell'allocazione delle risorse. Si consideri un'azienda con $m$ prodotti venduti in $n$ mercati diversi, dove ogni mercato acquista uno specifico pacchetto di prodotti (rappresentato dalle colonne della matrice $A$ ). L'obiettivo aziendale è quello di suddividere questi mercati in due regioni di vendita equilibrate, in modo che ogni regione riceva esattamente la metà della domanda totale di ogni prodotto.\n", "\n", "**Formulazione matematica:**\n", "\n", "Cerchiamo un vettore di assegnazione binaria $x$, dove:\n", "\n", "* $x_j = 1$ assegna il mercato $j$ alla Regione A\n", "* $x_j = 0$ assegna il mercato $j$ alla Regione B\n", "* Il vincolo $Ax = b$ deve essere soddisfatto, dove $b$ rappresenta il target di vendita (tipicamente la metà della domanda totale per prodotto)\n", "\n", "**Funzione di costo:**\n", "\n", "Per risolvere questo problema, minimizziamo la violazione del vincolo al quadrato:\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", "dove:\n", "\n", "* $A_{ij}$ rappresenta le vendite del prodotto $i$ nel mercato $j$\n", "* $x_j \\in \\{0,1\\}$ è l'assegnazione binaria del mercato $j$\n", "* $b_i$ è l'obiettivo di vendita per il prodotto $i$ in ogni regione\n", "* Il costo è uguale a zero proprio quando tutti i vincoli sono soddisfatti\n", "\n", "Ogni termine della somma rappresenta lo scarto quadratico rispetto alle vendite target per un determinato prodotto. Espandendo questa funzione di costo, si ottiene:\n", "\n", "$C(x) = x^T A^T A x - 2b^T A x + b^T b$\n", "\n", "Poiché $b^T b$ è una costante, la minimizzazione di $C(x)$ è equivalente alla minimizzazione della funzione quadratica $x^T A^T A x - 2b^T A x$, che è esattamente un problema QUBO (Quadratic Unconstrained Binary Optimization).\n", "\n", "**Complessità computazionale:**\n", "\n", "Nonostante la sua semplice interpretazione commerciale, questo problema presenta una notevole intrattabilità computazionale:\n", "\n", "* **Fallimento su piccola scala** : I solutori convenzionali di programmazione integrale mista falliscono su istanze con appena sette prodotti con un timeout di un'ora [\\[4\\]](#references)\n", "* **Crescita esponenziale** : Lo spazio delle soluzioni cresce in modo esponenziale ( $2^n$ assegnazioni possibili), rendendo inapplicabili gli approcci di forza bruta\n", "\n", "Questo grave ostacolo computazionale, unito alla sua rilevanza pratica per la pianificazione del territorio e l'allocazione delle risorse, rende il problema del Market Split un benchmark ideale per gli algoritmi di ottimizzazione quantistica [\\[4\\]](#references).\n", "\n", "\n", "\n", "### Cosa rende unico l'approccio di Iskay?\n", "\n", "L'ottimizzatore Iskay utilizza l'algoritmo **bf-DCQO (bias-field digitized counterdiabatic quantum optimization)** [\\[1\\]](#references), che rappresenta un significativo progresso nell'ottimizzazione quantistica:\n", "\n", "**Efficienza del circuito** : L'algoritmo bf-DCQO ottiene una notevole riduzione dei gate [\\[1\\]](#references) :\n", "\n", "* Fino a **10 volte meno porte di entanglement** rispetto al Digital Quantum Annealing (DQA)\n", "* I circuiti significativamente meno profondi consentono l'abilitazione:\n", " * Minore accumulo di errori durante l'esecuzione quantistica\n", " * Capacità di affrontare problemi più grandi sull'attuale hardware quantistico\n", " * Non sono necessarie tecniche di mitigazione degli errori\n", "\n", "**Progettazione non variazionale** : A differenza degli algoritmi variazionali che richiedono circa 100 iterazioni, il bf-DCQO ne richiede in genere solo **circa 10** [\\[1\\]](#references). Questo obiettivo viene raggiunto attraverso:\n", "\n", "* Calcoli intelligenti del campo di polarizzazione a partire dalle distribuzioni di stato misurate\n", "* Iniziare ogni iterazione da uno stato energetico prossimo alla soluzione precedente\n", "* Postelaborazione classica integrata con la ricerca locale\n", "\n", "**Protocolli controdiabatici** : L'algoritmo incorpora termini controdiabatici che sopprimono le eccitazioni quantistiche indesiderate durante i brevi tempi di evoluzione, consentendo al sistema di rimanere vicino allo stato fondamentale anche con transizioni rapide [\\[1\\]](#references).\n", "\n" ] }, { "cell_type": "markdown", "id": "requirements", "metadata": {}, "source": [ "\n", "\n", "## Requisiti\n", "\n", "Prima di iniziare questa esercitazione, assicuratevi di aver installato quanto segue:\n", "\n", "* Qiskit IBM Runtime (`pip install qiskit-ibm-runtime`)\n", "* Qiskit Functions (`pip install qiskit-ibm-catalog`)\n", "* NumPy (`pip install numpy`)\n", "* Richieste (`pip install requests`)\n", "* Opt Mapper Qiskit addon (`pip install qiskit-addon-opt-mapper`)\n", "\n", "È inoltre necessario ottenere l'accesso alla [funzione Iskay Quantum Optimizer](/functions?id=kipu-quantum-iskay-quantum-optimizer) dal sito Qiskit Functions Catalog.\n", "\n" ] }, { "cell_type": "markdown", "id": "setup", "metadata": {}, "source": [ "\n", "\n", "## Configura\n", "\n", "Per prima cosa, importare tutti i pacchetti necessari per questa esercitazione.\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", "### Configura le credenziali dell' IBM Quantum\n", "\n", "Definite le vostre [IBM Quantum® Platform](/) credenziali. Saranno necessari:\n", "\n", "* **Token API** : La chiave API di 44 caratteri da IBM Quantum Platform\n", "* **CRN dell'istanza** : l'identificativo dell'istanza IBM Cloud®\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", "## Fase 1: mappare gli input classici su un problema quantistico\n", "\n", "Cominciamo con la mappatura del nostro problema classico in una rappresentazione compatibile con quella quantistica. Questa fase prevede:\n", "\n", "1. Collegamento all'ottimizzatore quantistico Iskay\n", "2. Caricamento e formulazione del problema del Market Split\n", "3. Capire l'algoritmo bf-DCQO che lo risolverà\n", "\n", "\n", "\n", "### Connettiti a Iskay Quantum Optimizer\n", "\n", "Si inizia stabilendo una connessione al sito Qiskit Functions Catalog e caricando l'Iskay Quantum Optimizer. L'Iskay Optimizer è una funzione quantistica fornita da Kipu Quantum che implementa l'algoritmo bf-DCQO per la risoluzione di problemi di ottimizzazione su hardware quantistico.\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", "### Caricare e formulare il problema\n", "\n", "\n", "\n", "#### Comprendere il formato dei dati problematici\n", "\n", "Le istanze dei problemi di QOBLIB (Quantum Optimization Benchmarking Library) [\\[2\\]](#references) sono memorizzate in un semplice formato di testo. Esaminiamo il contenuto effettivo della nostra istanza di destinazione `ms_03_200_177.dat`:\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", "**Struttura del formato:**\n", "\n", "* **Prima riga:** `3 20`\n", " * `3` = numero di prodotti (vincoli/riga della matrice $A$ )\n", " * `20` = numero di mercati (variabili/colonne della matrice $A$ )\n", "\n", "* **Le 3 righe successive:** Matrice dei coefficienti $A$ e vettore target $b$\n", " * Ogni riga ha 21 numeri: i primi 20 sono i coefficienti di riga, l'ultimo è il target\n", " * Linea 2: `60 92 161 ... 51 | 1002`\n", " * I primi 20 numeri: Quantità di prodotto 1 venduta da ognuno dei 20 mercati\n", " * Ultimo numero (1002): Vendite target per il prodotto 1 in una regione\n", " * Linea 3: `176 196 41 ... 46 | 879`\n", " * Vendite del prodotto 2 per mercato e obiettivo (879)\n", " * Linea 4: `68 68 179 ... 95 | 1040`\n", " * Vendite del prodotto 3 per mercato e target (1040)\n", "\n", "**Interpretazione commerciale:**\n", "\n", "* Il mercato 0 vende: 60 unità del prodotto 1, 176 unità del prodotto 2, 68 unità del prodotto 3\n", "* Il mercato 1 vende: 92 unità del prodotto 1, 196 unità del prodotto 2, 68 unità del prodotto 3\n", "* E così via per tutti i 20 mercati...\n", "* **Obiettivo** : dividere questi 20 mercati in due regioni, dove ogni regione riceve esattamente 1002 unità del prodotto 1, 879 unità del prodotto 2 e 1040 unità del prodotto 3\n", "\n", "\n", "\n", "#### Trasformazione QUBO\n", "\n", "\n", "\n", "## Dai vincoli al QUBO: la trasformazione matematica\n", "\n", "La potenza dell'ottimizzazione quantistica sta nel trasformare i problemi vincolati in forme quadratiche non vincolate [\\[4\\]](#references). Per il problema della suddivisione del mercato, convertiamo i vincoli di uguaglianza in\n", "\n", "$Ax = b$\n", "\n", "dove $x ∈ \\{0,1\\}^n$, in un QUBO penalizzando le violazioni dei vincoli.\n", "\n", "**Il metodo della penalità:** Poiché è necessario che $Ax = b$ sia esattamente valido, minimizziamo la violazione al quadrato: $f(x) = ||Ax - b||^2$\n", "\n", "Questo valore è pari a zero proprio quando tutti i vincoli sono soddisfatti. Espansione algebrica: $f(x) = (Ax - b)^T(Ax - b) = x^T A^T A x - 2b^T A x + b^T b$\n", "\n", "**Obiettivo QUBO:** Dato che $b^T b$ è costante, la nostra ottimizzazione diventa: $\\text{minimize} \\quad Q(x) = x^T(A^T A)x - 2(A^T b)^T x$\n", "\n", "**Un'intuizione chiave:** Questa trasformazione è esatta, non approssimativa. I vincoli di uguaglianza quadrano naturalmente in forma quadratica senza richiedere variabili ausiliarie o parametri di penalità, rendendo questa formulazione matematicamente elegante e computazionalmente efficiente per i solutori quantistici [\\[4\\]](#references). Utilizzeremo la classe `OptimizationProblem` per definire il nostro problema vincolato, quindi lo convertiremo in formato QUBO utilizzando `OptimizationProblemToQubo`, entrambi dal pacchetto **qiskit\\_addon\\_opt\\_mapper**. In questo modo si gestisce automaticamente la trasformazione basata sulle penalità.\n", "\n" ] }, { "cell_type": "markdown", "id": "functions_intro", "metadata": {}, "source": [ "\n", "\n", "### Implementare le funzioni di caricamento dei dati e conversione QUBO\n", "\n", "Definiamo ora tre funzioni di utilità:\n", "\n", "1. `parse_marketsplit_dat()` - Analizza il formato del file `.dat` ed estrae le matrici $A$ e $b$\n", "2. `fetch_marketsplit_data()` - Scarica le istanze del problema direttamente dal repository QOBLIB\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", "### Carica l'istanza del problema\n", "\n", "Ora carichiamo l'istanza del problema specifico `ms_03_200_177.dat` dal QOBLIB \\[2]. Questa istanza ha:\n", "\n", "* 3 prodotti (vincoli)\n", "* 20 mercati (variabili decisionali binarie)\n", "* Oltre 1 milione di possibili incarichi di mercato da esplorare ( $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", "### Converti in formato QUBO\n", "\n", "Trasformiamo ora il problema di ottimizzazione vincolata in formato QUBO:\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", "### Converti QUBO in formato Iskay\n", "\n", "Ora dobbiamo convertire l'oggetto QUBO nel formato del dizionario richiesto dall'ottimizzatore Iskay di Kipu Quantum.\n", "\n", "Gli argomenti `problem` e `problem_type` codificano un problema di ottimizzazione della forma\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", "Dove\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", "* Scegliendo `problem_type = \"binary\"`, si specifica che la funzione di costo è nel formato `binary` , il che significa che $D = \\{0, 1\\}^{n}$, come dire, la funzione di costo è scritta nella formulazione QUBO/HUBO.\n", "* D'altra parte, scegliendo `problem_type = \"spin\"`, la funzione di costo è scritta nella formulazione di Ising, dove $D = \\{-1, 1\\}^{n}$.\n", "\n", "I coefficienti del problema devono essere codificati in un dizionario come segue:\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", "Si noti che le chiavi del dizionario devono essere stringhe contenenti una tupla valida di numeri interi non ripetuti. Per i problemi binari, sappiamo che:\n", "\n", "$$\n", "x_i^2 = x_i\n", "$$\n", "\n", "per $i=j$ (poiché $x_i \\in \\{0,1\\}$ significa $x_i \\cdot x_i = x_i$ ). Quindi, nella formulazione QUBO, se si hanno sia contributi lineari $b_i x_i$ sia contributi quadratici diagonali $c_{i,i} x_i^2$, questi termini devono essere combinati in un unico coefficiente lineare:\n", "\n", "**Coefficiente lineare totale per la variabile $x_i$** : $b_i + c_{i,i}$\n", "\n", "Questo significa che:\n", "\n", "* I termini lineari come `\"(i, )\"` contengono: coefficiente lineare originale + coefficiente quadratico diagonale\n", "* I termini quadratici diagonali come `\"(i, i)\"` **NON** devono comparire nel dizionario finale\n", "* Solo i termini quadratici fuori diagonale come `\"(i, j)\"` dove $i \\neq j$ devono essere inclusi come voci separate\n", "\n", "**Esempio:** Se il vostro QUBO ha $3x_1 + 2x_1^2 + 4x_1 x_2$, il dizionario Iskay dovrebbe contenere:\n", "\n", "* `\"(0, )\"`: `5.0` (che combina $3 + 2 = 5$ )\n", "* `\"(0, 1)\"`: `4.0` (termine fuori diagonale)\n", "\n", "**NON sono** voci separate per `\"(0, )\"`: `3.0` e `\"(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", "### Comprendere l'algoritmo bf-DCQO\n", "\n", "Prima di eseguire l'ottimizzazione, cerchiamo di capire il sofisticato algoritmo quantistico che alimenta Iskay: **bf-DCQO (bias-field digitized counterdiabatic quantum optimization)** [\\[1\\]](#references).\n", "\n", "\n", "\n", "#### Che cos'è il bf-DCQO?\n", "\n", "il bf-DCQO si basa sull'evoluzione temporale di un sistema quantistico in cui la soluzione del problema è codificata nello **stato fondamentale** (stato a più bassa energia) dell'hamiltoniana quantistica finale [\\[1\\]](#references). L'algoritmo affronta una sfida fondamentale nell'ottimizzazione quantistica:\n", "\n", "**La sfida** : l'informatica quantistica adiabatica tradizionale richiede un'evoluzione molto lenta per mantenere le condizioni dello stato fondamentale secondo il teorema adiabatico. Ciò richiede circuiti quantistici sempre più profondi man mano che la complessità del problema aumenta, con conseguente aumento delle operazioni di gate e degli errori accumulati.\n", "\n", "**La soluzione** : bf-DCQO utilizza protocolli controdiabatici per consentire una rapida evoluzione mantenendo la fedeltà allo stato di massa, riducendo drasticamente la profondità del circuito.\n", "\n", "\n", "\n", "#### Struttura matematica\n", "\n", "L'algoritmo minimizza una funzione di costo della forma:\n", "\n", "$\\min_{(x_1,x_2,...,x_n) \\in D} C(x_1,x_2,...,x_n)$\n", "\n", "dove $D = \\{0,1\\}^n$ per le variabili binarie e:\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", "Per il nostro problema di Market Split, la funzione di costo è:\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", "#### Il ruolo dei termini controdiabetici\n", "\n", "I **termini controdiabatici** sono termini aggiuntivi introdotti nell'hamiltoniana dipendente dal tempo che sopprimono le eccitazioni indesiderate durante l'evoluzione quantistica. Ecco perché sono fondamentali:\n", "\n", "Nell'ottimizzazione quantistica adiabatica, il sistema evolve secondo un'hamiltoniana dipendente dal tempo:\n", "\n", "$H(t) = \\left(1 - \\frac{t}{T}\\right) H_{\\text{initial}} + \\frac{t}{T} H_{\\text{problem}}$\n", "\n", "dove $H_{\\text{problem}}$ codifica il nostro problema di ottimizzazione. Per mantenere lo stato fondamentale durante l'evoluzione rapida, aggiungiamo termini controdiabatici:\n", "\n", "$H_{\\text{CD}}(t) = H(t) + H_{\\text{counter}}(t)$\n", "\n", "Questi termini controdiabatici svolgono le seguenti funzioni:\n", "\n", "1. **Sopprimere le transizioni indesiderate** : Impedire che lo stato quantico salti a stati eccitati durante l'evoluzione rapida\n", "2. **Consentono tempi di evoluzione più brevi** : Permettono di raggiungere lo stato finale molto più velocemente senza violare l'adiabaticità\n", "3. **Riduzione della profondità del circuito** : Un'evoluzione più breve porta a un minor numero di porte e a un minor numero di errori\n", "\n", "L'impatto pratico è drammatico: bf-DCQO utilizza fino a **10 volte meno porte di entanglement** rispetto al Digital Quantum Annealing [\\[1\\]](#references), rendendolo pratico per l'hardware quantistico rumoroso di oggi.\n", "\n", "\n", "\n", "#### Ottimizzazione iterativa del campo di distorsione\n", "\n", "A differenza degli algoritmi variazionali che ottimizzano i parametri del circuito attraverso molte iterazioni, bf-DCQO utilizza un **approccio guidato dal campo di polarizzazione** che converge in circa 10 iterazioni \\[:]\n", "\n", "**Processo di iterazione:**\n", "\n", "1. **Evoluzione quantistica iniziale** : Iniziare con un circuito quantistico che implementa il protocollo di evoluzione controdiabatica\n", "\n", "2. **Misura** : Misurare lo stato quantistico per ottenere una distribuzione di probabilità sulle stringhe di bit\n", "\n", "3. **Calcolo del campo di polarizzazione** : Analizzare le statistiche di misura e calcolare un campo di polarizzazione ottimale $h_i$ per ogni qubit: $h_i = \\text{f}(\\text{measurement statistics}, \\text{previous solutions})$\n", "\n", "4. **Iterazione successiva** : Il campo bias modifica l'Hamiltoniana per l'iterazione successiva: $H_{\\text{next}} = H_{\\text{problem}} + \\sum_i h_i \\sigma_i^z$\n", "\n", " Questo permette di iniziare vicino alla soluzione buona trovata in precedenza, eseguendo di fatto una forma di \"ricerca locale quantistica\"\n", "\n", "5. **Convergenza** : Ripetere fino a quando la qualità della soluzione si stabilizza o viene raggiunto un numero massimo di iterazioni\n", "\n", "**Vantaggio chiave** : Ogni iterazione fornisce un progresso significativo verso la soluzione ottimale incorporando le informazioni delle misure precedenti, a differenza dei metodi variazionali che devono esplorare lo spazio dei parametri alla cieca.\n", "\n", "\n", "\n", "#### Post-elaborazione classica integrata\n", "\n", "Dopo la convergenza dell'ottimizzazione quantistica, Iskay esegue la classica post-elaborazione **della ricerca locale** :\n", "\n", "* **Esplorazione con salto mortale dei bit** : Capovolgere sistematicamente o casualmente i bit nella migliore soluzione misurata\n", "* **Valutazione energetica** : Calcolare $C(x)$ per ogni soluzione modificata\n", "* **Selezione avida** : Accettare i miglioramenti che riducono la funzione di costo\n", "* **Passaggi multipli** : Esegue più passate (controllate da `postprocessing_level`)\n", "\n", "Questo approccio ibrido compensa gli errori di bit-flip dovuti alle imperfezioni dell'hardware e agli errori di lettura, garantendo soluzioni di alta qualità anche su dispositivi quantistici rumorosi.\n", "\n", "\n", "\n", "#### Perché bf-DCQO eccelle sull'hardware attuale\n", "\n", "L'algoritmo bf-DCQO è stato progettato specificamente per eccellere sugli attuali dispositivi quantistici rumorosi su scala intermedia (NISQ) [\\[1\\]](#references) :\n", "\n", "1. **Resilienza agli errori** : Un minor numero di gate (riduzione di 10 volte) significa un accumulo di errori drasticamente inferiore\n", "2. **Non è necessaria la mitigazione degli errori** : L'efficienza intrinseca dell'algoritmo elimina la necessità di costose tecniche di mitigazione degli errori [\\[1\\]](#references)\n", "3. **Scalabilità** : Può gestire problemi fino a 156 qubit (156 variabili binarie) con la mappatura diretta dei qubit [\\[1\\]](#references)\n", "4. **Prestazioni comprovate** : Raggiunge rapporti di approssimazione del 100% su istanze benchmark MaxCut e HUBO [\\[1\\]](#references)\n", "\n", "Vediamo ora questo potente algoritmo in azione sul nostro problema di Market Split!\n", "\n" ] }, { "cell_type": "markdown", "id": "step4", "metadata": {}, "source": [ "\n", "\n", "## Fase 2: Ottimizzazione del problema per l'esecuzione su hardware quantistico\n", "\n", "L'algoritmo bf-DCQO gestisce automaticamente l'ottimizzazione dei circuiti, creando circuiti quantistici poco profondi con termini controdiabatici specificamente progettati per il backend di destinazione.\n", "\n", "\n", "\n", "### Configurare l'ottimizzazione\n", "\n", "L'ottimizzatore Iskay richiede alcuni parametri chiave per risolvere efficacemente il problema di ottimizzazione. Esaminiamo ogni parametro e il suo ruolo nel processo di ottimizzazione quantistica:\n", "\n", "\n", "\n", "#### Parametri obbligatori\n", "\n", "| Parametro | Tipo | Descrizione | Esempio |\n", "| ------------------------------------------------------------ | ------------------ | --------------------------------------------------------------- | ------------------------------------------- |\n", "| **problema** | `Dict[str, float]` | Coefficienti QUBO in formato stringa-chiave | `{\"()\": -21.0, \"(0,4)\": 0.5, \"(0,1)\": 0.5}` |\n", "| **tipo di problema** | `str` | Specifica del formato: `\"binary\"` per QUBO o `\"spin\"` per Ising | `\"binary\"` |\n", "| **nome\\_del\\_titolo\\_del\\_titolo\\_del\\_titolo\\_del\\_titolo** | `str` | Dispositivo quantistico target | `\"ibm_fez\"` |\n", "\n", "\n", "\n", "#### Concetti essenziali\n", "\n", "* **Formato del problema** : Utilizziamo `\"binary\"` poiché le nostre variabili sono binarie (0/1) e rappresentano le assegnazioni di mercato.\n", "* **Selezione del backend** : Scegliere tra le QPU disponibili (ad esempio, `\"ibm_fez\"`) in base alle proprie esigenze e all'istanza di risorse di calcolo.\n", "* **Struttura QUBO** : Il nostro dizionario dei problemi contiene i coefficienti esatti della trasformazione matematica.\n", "\n", "\n", "\n", "#### Opzioni avanzate (facoltative)\n", "\n", "Iskay offre capacità di regolazione fine attraverso parametri opzionali. Anche se le impostazioni predefinite funzionano bene per la maggior parte dei problemi, è possibile personalizzare il comportamento in base a requisiti specifici:\n", "\n", "| Parametro | Tipo | Predefinito | Descrizione |\n", "| ----------------------------- | ----------- | ----------- | ------------------------------------------------------------------------------------------------------ |\n", "| **Shot** | `int` | 10000 | Misurazioni quantistiche per iterazione (più alte = più precise) |\n", "| **num\\_iterazioni** | `int` | 10 | Iterazioni dell'algoritmo (un numero maggiore di iterazioni può migliorare la qualità della soluzione) |\n", "| **utilizzare la sessione** | `bool` | Vero | Utilizzare le sessioni di IBM per ridurre i tempi di coda |\n", "| **seme\\_trasparente** | `int` | Nessuna | Set per la compilazione di circuiti quantistici riproducibili |\n", "| **mappatura diretta** | `bool` | No | Mappare i qubit virtuali direttamente ai qubit fisici |\n", "| **tag\\_lavoro** | `List[str]` | Nessuna | Tag personalizzati per il monitoraggio dei lavori |\n", "| **preelaborazione\\_livello** | `int` | 0 | Intensità di pre-elaborazione del problema (0-3) - vedi dettagli sotto |\n", "| **postelaborazione\\_livello** | `int` | 2 | Livello di affinamento della soluzione (0-2) - vedi dettagli sotto |\n", "| **livello di transpilazione** | `int` | 0 | Prove di ottimizzazione dei transpiler (0-5) - vedere i dettagli qui sotto |\n", "| **solo transpile** | `bool` | No | Analizzare l'ottimizzazione del circuito senza eseguire l'esecuzione completa |\n", "\n", "**Livelli di preelaborazione (0-3)** : Particolarmente importante per i problemi più grandi che attualmente non possono essere soddisfatti dai tempi di coerenza dell'hardware. Livelli di preelaborazione più elevati consentono di ottenere profondità circuitali minori mediante approssimazioni nella trasposizione del problema:\n", "\n", "* **Livello 0** : circuiti esatti e più lunghi\n", "* **Livello 1** : Buon equilibrio tra accuratezza e approssimazione, tagliando solo le porte con angoli nel 10 percentile più basso\n", "* **Livello 2** : approssimazione leggermente superiore, tagliando le porte con angoli nel 20 percentile più basso e utilizzando `approximation_degree=0.95` nella trasposizione\n", "* **Livello 3** : livello di massima approssimazione, che prevede l'eliminazione delle porte nel 30° percentile più basso e l'utilizzo di `approximation_degree=0.90` nella trasposizione\n", "\n", "**Livelli di transpilazione (0-5)** : Controlla i processi di ottimizzazione avanzata del transpiler per la compilazione dei circuiti quantistici. Ciò può comportare un aumento dell'overhead classico e, in alcuni casi, potrebbe non modificare la profondità del circuito. Il valore predefinito `2` in genere porta al circuito più piccolo ed è relativamente veloce.\n", "\n", "* **Livello 0** : Ottimizzazione del circuito DCQO decomposto (layout, routing, schedulazione)\n", "* **Livello 1** : Ottimizzazione di `PauliEvolutionGate` e quindi del circuito DCQO scomposto ( max\\_trials=10 )\n", "* **Livello 2** : Ottimizzazione di `PauliEvolutionGate` e quindi del circuito DCQO scomposto ( max\\_trials=15 )\n", "* **Livello 3** : Ottimizzazione di `PauliEvolutionGate` e quindi del circuito DCQO scomposto ( max\\_trials=20 )\n", "* **Livello 4** : Ottimizzazione di `PauliEvolutionGate` e quindi del circuito DCQO scomposto ( max\\_trials=25 )\n", "* **Livello 5** : Ottimizzazione di `PauliEvolutionGate` e quindi del circuito DCQO scomposto ( max\\_trials=50 )\n", "\n", "**Livelli di post-elaborazione (0-2)** : Controlla la quantità di ottimizzazione classica, compensando gli errori di bit-flip con un numero diverso di passaggi di ricerca locale:\n", "\n", "* **Livello 0** : 1 passaggio\n", "* **Livello 1** : 2 pass\n", "* **Livello 2** : 3 passaggi\n", "\n", "**Modalità Transpile-only** : Ora disponibile per gli utenti che desiderano analizzare l'ottimizzazione dei circuiti senza eseguire l'intero algoritmo quantistico.\n", "\n", "\n", "\n", "#### Esempio di configurazione personalizzata\n", "\n", "Ecco come si potrebbe configurare Iskay con diverse impostazioni:\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": [ "Per questa esercitazione, manterremo la maggior parte dei parametri predefiniti e modificheremo solo il numero di iterazioni del campo di polarizzazione:\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", "## Passaggio 3: eseguire utilizzando Qiskit primitives\n", "\n", "Ora sottoponiamo il nostro problema all'esecuzione su hardware IBM Quantum. L'algoritmo bf-DCQO:\n", "\n", "1. Costruire circuiti quantistici poco profondi con termini controdiabatici\n", "2. Eseguire circa 10 iterazioni con l'ottimizzazione del campo di polarizzazione\n", "3. Eseguire una post-elaborazione classica con ricerca locale\n", "4. Restituire l'assegnazione ottimale del mercato\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", "### Monitorare lo stato del lavoro\n", "\n", "È possibile controllare lo stato attuale del lavoro di ottimizzazione. Gli stati possibili sono:\n", "\n", "* `QUEUED`: Il lavoro è in attesa nella coda\n", "* `RUNNING`: Il lavoro è attualmente in esecuzione sull'hardware quantistico\n", "* `DONE`: Lavoro completato con successo\n", "* `CANCELED`: Il lavoro è stato annullato\n", "* `ERROR`: Il lavoro ha riscontrato un errore\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", "### Attendere il completamento\n", "\n", "Questa cella si blocca fino al completamento del lavoro. Il processo di ottimizzazione comprende:\n", "\n", "* Tempo di coda (attesa per l'accesso all'hardware quantistico)\n", "* Tempo di esecuzione (esecuzione dell'algoritmo bf-DCQO con circa 10 iterazioni)\n", "* Tempo di post-elaborazione (ricerca locale classica)\n", "\n", "I tempi di completamento tipici variano da pochi minuti a decine di minuti, a seconda delle condizioni della coda.\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", "## Fase 4: Post-elaborazione e restituzione del risultato nel formato classico desiderato\n", "\n", "Ora elaboriamo i risultati dell'esecuzione quantistica. Ciò comprende:\n", "\n", "* Analisi della struttura della soluzione\n", "* Convalida della soddisfazione dei vincoli\n", "* Benchmarking rispetto agli approcci classici\n", "\n", "\n", "\n", "### Analizza i risultati\n", "\n", "\n", "\n", "#### Comprendere la struttura dei risultati\n", "\n", "Iskay restituisce un dizionario di risultati completo contenente:\n", "\n", "* **`solution`**: Un dizionario che mappa gli indici delle variabili ai loro valori ottimali (0 o 1)\n", "* **`solution_info`**: Informazioni dettagliate, tra cui:\n", " * `bitstring`: L'assegnazione ottimale come stringa binaria\n", " * `cost`: Il valore della funzione obiettivo (dovrebbe essere 0 per una perfetta soddisfazione dei vincoli)\n", " * `mapping`: Come le posizioni delle bitstringhe si adattano alle variabili del problema\n", " * `seed_transpiler`: Seme utilizzato per la riproducibilità\n", "* **`prob_type`**: Se la soluzione è in formato binario o di spin\n", "\n", "Esaminiamo la soluzione restituita dall'ottimizzatore quantistico.\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", "#### Convalida della Soluzione\n", "\n", "Ora verifichiamo se la soluzione quantistica soddisfa i vincoli del Market Split. Il processo di convalida controlla:\n", "\n", "**Che cos'è una violazione dei vincoli?**\n", "\n", "* Per ciascun prodotto $i$, calcoliamo le vendite effettive nella Regione A: $(Ax)_i$\n", "* Confrontiamo questo dato con l'obiettivo di vendita $b_i$\n", "* La **violazione** è la differenza assoluta: $|(Ax)_i - b_i|$\n", "* Una **soluzione fattibile** ha violazioni pari a zero per tutti i prodotti\n", "\n", "**Cosa ci aspettiamo:**\n", "\n", "* **Caso ideale** : Violazione totale = 0 (tutti i vincoli sono perfettamente soddisfatti)\n", " * La regione A riceve esattamente 1002 unità del prodotto 1, 879 unità del prodotto 2 e 1040 unità del prodotto 3\n", " * La Regione B ottiene le unità rimanenti (rispettivamente 1002, 879 e 1040)\n", "* **Caso positivo** : La violazione totale è piccola (soluzione quasi ottimale)\n", "* **Caso scadente** : Grandi violazioni indicano che la soluzione non soddisfa i requisiti aziendali\n", "\n", "La funzione di convalida calcolerà:\n", "\n", "1. Vendite effettive per prodotto in ogni regione\n", "2. Violazioni dei vincoli per ogni prodotto\n", "3. Distribuzione del mercato tra le regioni\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", "#### Interpretare i risultati della convalida\n", "\n", "I risultati della convalida mostrano se l'ottimizzatore quantistico ha trovato una soluzione fattibile. Esaminiamo quanto segue:\n", "\n", "**Verifica della fattibilità:**\n", "\n", "* **`is_feasible = True`** significa che la soluzione soddisfa perfettamente tutti i vincoli (violazione totale = 0)\n", "* **`is_feasible = False`** significa che alcuni vincoli sono violati\n", "\n", "**Analisi delle vendite:**\n", "\n", "* Confrontare le vendite target con quelle effettive per ogni prodotto\n", "* Per una soluzione perfetta: Effettivo = Obiettivo per tutti i prodotti in entrambe le regioni\n", "* La differenza indica quanto siamo vicini alla suddivisione del mercato desiderata\n", "\n", "**Distribuzione sul mercato:**\n", "\n", "* Mostra il numero di mercati assegnati a ciascuna regione\n", "* Non è richiesto un numero uguale di mercati, ma solo il raggiungimento degli obiettivi di vendita\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", "#### Valutazione della qualità della soluzione\n", "\n", "Sulla base dei risultati della convalida di cui sopra, possiamo valutare la qualità della soluzione quantistica:\n", "\n", "**Se `is_feasible = True` (violazione totale = 0):**\n", "\n", "* L'ottimizzatore quantistico ha trovato con successo una soluzione ottimale\n", "* Tutti i vincoli aziendali sono perfettamente soddisfatti\n", "* Questo dimostra il vantaggio quantistico in un problema in cui i risolutori classici hanno difficoltà [\\[4\\]](#references)\n", "\n", "**Se `is_feasible = False` (violazione totale > 0):**\n", "\n", "* La soluzione è quasi ottimale, ma non perfetta\n", "* Piccole violazioni possono essere accettabili nella pratica\n", "* Considerare la possibilità di regolare i parametri dell'ottimizzatore:\n", " * Aumentare `num_iterations` per un maggior numero di passaggi di ottimizzazione\n", " * Aumentare `postprocessing_level` per una raffinatezza più classica\n", " * Aumentare `shots` per migliorare le statistiche di misura\n", "\n", "**Interpretazione della funzione di costo:**\n", "\n", "* Il valore di `cost` da `solution_info` è uguale a $||Ax - b||^2$\n", "* Costo = 0 indica la perfetta soddisfazione dei vincoli\n", "* Valori di costo più elevati indicano violazioni di vincoli maggiori\n", "\n" ] }, { "cell_type": "markdown", "id": "conclusion", "metadata": {}, "source": [ "\n", "\n", "## Conclusione\n", "\n", "\n", "\n", "### Cosa abbiamo realizzato\n", "\n", "In questa esercitazione, abbiamo avuto successo:\n", "\n", "1. **Caricamento di un problema di ottimizzazione reale** : ottenuta un'istanza di Market Split dalla libreria di benchmark QOBLIB \\[2]\n", "2. **Trasformato in formato QUBO** : Conversione del problema vincolato in una formulazione quadratica non vincolata \\[3]\n", "3. **Sfruttare algoritmi quantistici avanzati** : Utilizzato l'algoritmo bf-DCQO di Kipu Quantum con termini controdiabatici \\[1]\n", "4. **Ottenere soluzioni ottimali** : Trovato soluzioni fattibili che soddisfano tutti i vincoli\n", "\n", "\n", "\n", "### Punti chiave\n", "\n", "**Innovazione dell'algoritmo** : L'algoritmo bf-DCQO rappresenta un progresso significativo [\\[1\\]](#references) :\n", "\n", "* **10 volte meno porte** rispetto all'annealing quantistico digitale\n", "* **Circa 10 iterazioni** invece di circa 100 per i metodi variazionali\n", "* **Resilienza agli errori incorporata** grazie all'efficienza del circuito\n", "\n", "**Termini controdiabatici** : Consentono una rapida evoluzione quantistica mantenendo la fedeltà allo stato fondamentale, rendendo l'ottimizzazione quantistica pratica sull'hardware rumoroso di oggi [\\[1\\]](#references).\n", "\n", "**Guida del campo di polarizzazione** : L'approccio iterativo del campo di polarizzazione consente a ogni iterazione di iniziare in prossimità di soluzioni buone trovate in precedenza, fornendo una forma di ricerca locale potenziata dal punto di vista quantistico [\\[1\\]](#references).\n", "\n", "\n", "\n", "### Passi successivi\n", "\n", "Per approfondire la comprensione ed esplorare ulteriormente:\n", "\n", "1. **Provare diverse istanze** : Sperimentare con altre istanze di QOBLIB di dimensioni diverse\n", "2. **Sintonizzare i parametri** : Regolare `num_iterations`, `preprocessing_level`, `postprocessing_level`\n", "3. **Confronto con i classici** : Benchmark rispetto ai solutori di ottimizzazione classici\n", "4. **Provare diverse strategie** : Cercare di trovare una migliore codifica del problema o formularlo come HUBO (se possibile)\n", "5. **Applicare al proprio dominio** : Adattare le tecniche di formulazione QUBO/HUBO ai vostri problemi di ottimizzazione\n", "\n", "\n", "\n", "### Riferimenti\n", "\n", "\\[1] IBM Quantum. \"[Ottimizzazione quantistica di Kipu](/docs/guides/kipu-optimization) \" *IBM Quantum Documentazione*.\n", "\n", "\\[2] QOBLIB - Quantum Optimization Benchmarking Library. Istituto Zuse di Berlino (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. e Du, Y. (2019). \"Quantum bridge analytics I: un tutorial sulla formulazione e l'uso dei modelli QUBO\" *4OR: A Quarterly Journal of Operations Research*, 17(4), 335-371.\n", "\n", "\\[4] Lodi, A., Tramontani, A. e Weninger, K. (2023). \"Il decathlon intrattabile: Benchmarking Hard Combinatorial Problems\" *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 }