Risolvere il problema Market Split con l'Iskay Quantum Optimizer di Kipu Quantum

Nota

Le Qiskit Functions sono una funzionalità sperimentale disponibile solo per gli utenti del Piano Premium, Piano Flex e Piano On-Prem (tramite API IBM Quantum Platform) di IBM Quantum®. Sono in stato di rilascio di anteprima e soggette a modifiche.

Stima di utilizzo: 20 secondi su un processore Heron r2. (NOTA: Questa è solo una stima. Il tempo di esecuzione effettivo potrebbe variare.)

Contesto

Questo tutorial dimostra come risolvere il problema Market Split utilizzando l'ottimizzatore quantistico Iskay di Kipu Quantum [1]. Il problema Market Split rappresenta una sfida di allocazione delle risorse reale in cui i mercati devono essere partizionati in regioni di vendita bilanciate per soddisfare obiettivi di domanda esatti.

La sfida del Market Split

Il problema Market Split presenta una sfida di allocazione delle risorse apparentemente semplice ma computazionalmente formidabile. Considerate un'azienda con $m$ prodotti venduti in $n$ mercati diversi, dove ogni mercato acquista un pacchetto specifico di prodotti (rappresentato dalle colonne della matrice $A$). L'obiettivo aziendale è partizionare questi mercati in due regioni di vendita bilanciate in modo tale che ogni regione riceva esattamente metà della domanda totale per ogni prodotto.

Formulazione matematica:

Cerchiamo un vettore di assegnazione binario $x$, dove:

• $x_j = 1$ assegna il mercato $j$ alla Regione A
• $x_j = 0$ assegna il mercato $j$ alla Regione B
• Il vincolo $Ax = b$ deve essere soddisfatto, dove $b$ rappresenta le vendite obiettivo (tipicamente metà della domanda totale per prodotto)

Funzione di costo:

Per risolvere questo problema, minimizziamo la violazione al quadrato dei vincoli:

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

dove:

• $A_{ij}$ rappresenta le vendite del prodotto $i$ nel mercato $j$
• $x_j \in \{0,1\}$ è l'assegnazione binaria del mercato $j$
• $b_i$ è l'obiettivo di vendite per il prodotto $i$ in ogni regione
• Il costo è uguale a zero precisamente quando tutti i vincoli sono soddisfatti

Ogni termine nella somma rappresenta la deviazione al quadrato dall'obiettivo di vendite per un particolare prodotto. Quando espandiamo questa funzione di costo, otteniamo:

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

Poiché $b^T b$ è una costante, minimizzare $C(x)$ è equivalente a minimizzare la funzione quadratica $x^T A^T A x - 2b^T A x$, che è esattamente un problema QUBO (Quadratic Unconstrained Binary Optimization).

Complessità computazionale:

Nonostante la sua interpretazione aziendale diretta, questo problema presenta una notevole intrattabilità computazionale:

• Fallimento su piccola scala: I risolutori convenzionali di Mixed Integer Programming falliscono su istanze con appena sette prodotti con un timeout di un'ora [4]
• Crescita esponenziale: Lo spazio delle soluzioni cresce esponenzialmente ($2^n$ assegnazioni possibili), rendendo infeasibili gli approcci di forza bruta

Questa severa barriera computazionale, combinata con la sua rilevanza pratica per la pianificazione territoriale e l'allocazione delle risorse, rende il problema Market Split un benchmark ideale per gli algoritmi di ottimizzazione quantistica [4].

Cosa rende unico l'approccio di Iskay?

L'ottimizzatore Iskay utilizza l'algoritmo bf-DCQO (bias-field digitized counterdiabatic quantum optimization) [1], che rappresenta un significativo progresso nell'ottimizzazione quantistica:

Efficienza dei circuiti: L'algoritmo bf-DCQO ottiene una notevole riduzione delle porte [1]:

• Fino a 10 volte meno porte di entanglement rispetto al Digital Quantum Annealing (DQA)
• Circuiti significativamente meno profondi consentono:
  • Minore accumulo di errori durante l'esecuzione quantistica
  • Capacità di affrontare problemi più grandi sull'hardware quantistico attuale
  • Nessuna necessità di tecniche di mitigazione degli errori

Design non variazionale: A differenza degli algoritmi variazionali che richiedono circa 100 iterazioni, bf-DCQO tipicamente necessita di sole circa 10 iterazioni [1]. Questo è ottenuto attraverso:

• Calcoli intelligenti del campo di bias dalle distribuzioni degli stati misurati
• Avvio di ogni iterazione da uno stato energetico vicino alla soluzione precedente
• Post-elaborazione classica integrata con ricerca locale

Protocolli controdiabatici: L'algoritmo incorpora termini controdiabatici che sopprimono eccitazioni quantistiche indesiderate durante tempi di evoluzione brevi, consentendo al sistema di rimanere vicino allo stato fondamentale anche con transizioni rapide [1].

Requisiti

Prima di iniziare questo tutorial, assicurati di avere installato quanto segue:

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

Dovrete anche ottenere l'accesso alla funzione Iskay Quantum Optimizer dal Catalogo delle Qiskit Functions.

Configurazione

Per prima cosa, importate tutti i pacchetti necessari per questo tutorial.

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit-addon-opt-mapper qiskit-ibm-catalog requests

import os
import tempfile
import time
from typing import Tuple, Optional

import numpy as np
import requests

from qiskit_ibm_catalog import QiskitFunctionsCatalog

from qiskit_addon_opt_mapper import OptimizationProblem
from qiskit_addon_opt_mapper.converters import OptimizationProblemToQubo

print("All required libraries imported successfully")

Configurare le credenziali IBM Quantum

Definisci le tue credenziali IBM Quantum® Platform. Avrai bisogno di:

• API Token: La tua chiave API di 44 caratteri da IBM Quantum Platform
• Instance CRN: Il tuo identificatore di istanza IBM Cloud®

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

Passaggio 1: Mappare gli input classici a un problema quantistico

Iniziamo mappando il nostro problema classico a una rappresentazione compatibile con il quantistico. Questo passaggio comporta:

1. Connettersi all'Iskay Quantum Optimizer
2. Caricare e formulare il problema Market Split
3. Comprendere l'algoritmo bf-DCQO che lo risolverà

Connettersi all'Iskay Quantum Optimizer

Iniziamo stabilendo una connessione al Catalogo delle Qiskit Functions e caricando l'Iskay Quantum Optimizer. L'Iskay Optimizer è una funzione quantistica fornita da Kipu Quantum che implementa l'algoritmo bf-DCQO per risolvere problemi di ottimizzazione su hardware quantistico.

catalog = QiskitFunctionsCatalog(token=token, instance=instance)
iskay_solver = catalog.load("kipu-quantum/iskay-quantum-optimizer")

print("Iskay optimizer loaded successfully")
print("Ready to solve optimization problems using bf-DCQO algorithm")

Caricare e formulare il problema

Comprendere il formato dei dati del problema

Le istanze di problemi da QOBLIB (Quantum Optimization Benchmarking Library) [2] sono memorizzate in un semplice formato di testo. Esaminiamo il contenuto effettivo della nostra istanza target ms_03_200_177.dat:

3 20
60   92  161   53   97    2   75   81    6  139  132   45  108  112  181   93  152  200  164   51 1002
176  196   41  143    2   88    0   79   10   71   75  148   82  135   34  187   33  155   58   46  879
68   68  179  173  127  163   48   49   99   78   44   52  173  131   73  198   84  109  180   95 1040

Struttura del formato:

• Prima riga: 3 20

  • 3 = numero di prodotti (vincoli/righe nella matrice $A$)
  • 20 = numero di mercati (variabili/colonne nella matrice $A$)

• Prossime 3 righe: Matrice dei coefficienti $A$ e vettore obiettivo $b$

  • Ogni riga ha 21 numeri: i primi 20 sono i coefficienti di riga, l'ultimo è l'obiettivo
  • Riga 2: 60 92 161 ... 51 | 1002
    • Primi 20 numeri: Quanto del Prodotto 1 vende ciascuno dei 20 mercati
    • Ultimo numero (1002): Vendite obiettivo per il Prodotto 1 in una regione
  • Riga 3: 176 196 41 ... 46 | 879
    • Vendite del Prodotto 2 per mercato e obiettivo (879)
  • Riga 4: 68 68 179 ... 95 | 1040
    • Vendite del Prodotto 3 per mercato e obiettivo (1040)

Interpretazione aziendale:

• Il Mercato 0 vende: 60 unità del Prodotto 1, 176 unità del Prodotto 2, 68 unità del Prodotto 3
• Il Mercato 1 vende: 92 unità del Prodotto 1, 196 unità del Prodotto 2, 68 unità del Prodotto 3
• E così via per tutti i 20 mercati...
• Obiettivo: Dividere questi 20 mercati in due regioni dove ogni regione ottiene esattamente 1002 unità del Prodotto 1, 879 unità del Prodotto 2 e 1040 unità del Prodotto 3

Trasformazione QUBO

Dai vincoli al QUBO: la trasformazione matematica

Il potere dell'ottimizzazione quantistica risiede nel trasformare problemi vincolati in forme quadratiche non vincolate [4]. Per il problema Market Split, convertiamo i vincoli di uguaglianza

$Ax = b$

dove $x ∈ \{0,1\}^n$, in un QUBO penalizzando le violazioni dei vincoli.

Il metodo della penalità: Poiché abbiamo bisogno che $Ax = b$ valga esattamente, minimizziamo la violazione al quadrato: $f(x) = ||Ax - b||^2$

Questo è uguale a zero precisamente quando tutti i vincoli sono soddisfatti. Espandendo algebricamente: $f(x) = (Ax - b)^T(Ax - b) = x^T A^T A x - 2b^T A x + b^T b$

Obiettivo QUBO: Poiché $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$

Intuizione chiave: Questa trasformazione è esatta, non approssimata. I vincoli di uguaglianza si elevano naturalmente al quadrato in forma quadratica senza richiedere variabili ausiliarie o parametri di penalità - rendendo questa formulazione matematicamente elegante e computazionalmente efficiente per i risolutori quantistici [4]. Useremo la classe OptimizationProblem per definire il nostro problema vincolato, quindi lo convertiremo in formato QUBO usando OptimizationProblemToQubo, entrambi dal pacchetto qiskit_addon_opt_mapper. Questo gestisce automaticamente la trasformazione basata su penalità.

Implementare le funzioni di caricamento dati e conversione QUBO

Ora definiamo tre funzioni di utilità:

1. parse_marketsplit_dat() - Analizza il formato del file .dat ed estrae le matrici $A$ e $b$
2. fetch_marketsplit_data() - Scarica istanze di problemi direttamente dal repository QOBLIB

def parse_marketsplit_dat(filename: str) -> Tuple[np.ndarray, np.ndarray]:
    """
    Parse a market split problem from a .dat file format.

    Parameters
    ----------
    filename : str
        Path to the .dat file containing the market split problem data.

    Returns
    -------
    A : np.ndarray
        Coefficient matrix of shape (m, n) where m is the number of products
        and n is the number of markets.
    b : np.ndarray
        Target vector of shape (m,) containing the target sales per product.
    """
    with open(filename, "r", encoding="utf-8") as f:
        lines = [
            line.strip()
            for line in f
            if line.strip() and not line.startswith("#")
        ]

    if not lines:
        raise ValueError("Empty or invalid .dat file")

    # First line: m n (number of products and markets)
    m, n = map(int, lines[0].split())

    # Next m lines: each row of A followed by corresponding element of b
    A, b = [], []
    for i in range(1, m + 1):
        values = list(map(int, lines[i].split()))
        A.append(values[:-1])  # First n values: product sales per market
        b.append(values[-1])  # Last value: target sales for this product

    return np.array(A, dtype=np.int32), np.array(b, dtype=np.int32)

def fetch_marketsplit_data(
    instance_name: str = "ms_03_200_177.dat",
) -> Tuple[Optional[np.ndarray], Optional[np.ndarray]]:
    """
    Fetch market split data directly from the QOBLIB repository.

    Parameters
    ----------
    instance_name : str
        Name of the .dat file to fetch (default: "ms_03_200_177.dat").

    Returns
    -------
    A : np.ndarray or None
        Coefficient matrix if successful, None if failed.
    b : np.ndarray or None
        Target vector if successful, None if failed.
    """
    url = f"https://git.zib.de/qopt/qoblib-quantum-optimization-benchmarking-library/-/raw/main/01-marketsplit/instances/{instance_name}"

    try:
        response = requests.get(url, timeout=30)
        response.raise_for_status()

        with tempfile.NamedTemporaryFile(
            mode="w", suffix=".dat", delete=False, encoding="utf-8"
        ) as f:
            f.write(response.text)
            temp_path = f.name

        try:
            return parse_marketsplit_dat(temp_path)
        finally:
            os.unlink(temp_path)
    except Exception as e:
        print(f"Error: {e}")
        return None, None

Caricare l'istanza del problema

Ora carichiamo l'istanza specifica del problema ms_03_200_177.dat da QOBLIB [2]. Questa istanza ha:

• 3 prodotti (vincoli)
• 20 mercati (variabili decisionali binarie)
• Oltre 1 milione di possibili assegnazioni di mercato da esplorare ($2^{20} = 1,048,576$)

# Load the problem instance
instance_name = "ms_03_200_177.dat"
A, b = fetch_marketsplit_data(instance_name=instance_name)

if A is not None:
    print("Successfully loaded problem instance from QOBLIB")
    print("\nProblem Instance Analysis:")
    print("=" * 50)
    print(f"Coefficient Matrix A: {A.shape[0]} × {A.shape[1]}")
    print(f"   → {A.shape[0]} products (constraints)")
    print(f"   → {A.shape[1]} markets (decision variables)")
    print(f"Target Vector b: {b}")
    print("   → Target sales per product for each region")
    print(
        f"Solution Space: 2^{A.shape[1]} = {2**A.shape[1]:,} possible assignments"
    )

Convertire in formato QUBO

Ora trasformiamo il problema di ottimizzazione vincolato in formato QUBO:

# Create optimization problem
ms = OptimizationProblem(instance_name.replace(".dat", ""))

# Add binary variables (one for each market)
ms.binary_var_list(A.shape[1])

# Add equality constraints (one for each product)
for idx, rhs in enumerate(b):
    ms.linear_constraint(A[idx, :], sense="==", rhs=rhs)

# Convert to QUBO with penalty parameter
qubo = OptimizationProblemToQubo(penalty=1).convert(ms)

print("QUBO Conversion Complete:")
print("=" * 50)
print(f"Number of variables: {qubo.get_num_vars()}")
print(f"Constant term: {qubo.objective.constant}")
print(f"Linear terms: {len(qubo.objective.linear.to_dict())}")
print(f"Quadratic terms: {len(qubo.objective.quadratic.to_dict())}")

Convertire il QUBO nel formato Iskay

Ora dobbiamo convertire l'oggetto QUBO nel formato dizionario richiesto dall'Iskay Optimizer di Kipu Quantum.

Gli argomenti problem e problem_type codificano un problema di ottimizzazione della forma

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

dove

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

• Scegliendo problem_type = "binary", specificate che la funzione di costo è in formato binary, il che significa che $D = \{0, 1\}^{n}$, cioè la funzione di costo è scritta nella formulazione QUBO/HUBO.
• D'altra parte, scegliendo problem_type = "spin", la funzione di costo è scritta nella formulazione di Ising, dove $D = \{-1, 1\}^{n}$.

I coefficienti del problema dovrebbero essere codificati in un dizionario come segue:

$$\begin{align} \nonumber &\texttt{\{} \\ \nonumber &\texttt{"()"}&: \quad &a, \\ \nonumber &\texttt{"(i,)"}&: \quad &b_i, \\ \nonumber &\texttt{"(i, j)"}&: \quad &c_{i, j}, \quad (i \neq j) \\ \nonumber &\quad \vdots \\ \nonumber &\texttt{"(} k_1, ..., k_m \texttt{)"}&: \quad &g_{k_1, ..., k_m}, \quad (k_1 \neq k_2 \neq \dots \neq k_m) \\ \nonumber &\texttt{\}} \end{align}$$

Nota che le chiavi del dizionario devono essere stringhe contenenti una tupla valida di interi non ripetuti. Per i problemi binari, sappiamo che:

$$x_i^2 = x_i$$

per $i=j$ (poiché $x_i \in \{0,1\}$ significa $x_i \cdot x_i = x_i$). Quindi, nella tua formulazione QUBO, se hai sia contributi lineari $b_i x_i$ che contributi quadratici diagonali $c_{i,i} x_i^2$, questi termini devono essere combinati in un singolo coefficiente lineare:

Coefficiente lineare totale per la variabile $x_i$: $b_i + c_{i,i}$

Questo significa:

• I termini lineari come "(i, )" contengono: coefficiente lineare originale + coefficiente quadratico diagonale
• I termini quadratici diagonali come "(i, i)" NON dovrebbero apparire nel dizionario finale
• Solo i termini quadratici fuori diagonale come "(i, j)" dove $i \neq j$ dovrebbero essere inclusi come voci separate

Esempio: Se il tuo QUBO ha $3x_1 + 2x_1^2 + 4x_1 x_2$, il dizionario Iskay dovrebbe contenere:

• "(0, )": 5.0 (combinando $3 + 2 = 5$)
• "(0, 1)": 4.0 (termine fuori diagonale)

NON voci separate per "(0, )": 3.0 e "(0, 0)": 2.0.

# Convert QUBO to Iskay dictionary format:

# Create empty Iskay input dictionary
iskay_input_problem = {}

# Convert QUBO to Iskay dictionary format
iskay_input_problem = {"()": qubo.objective.constant}

for i in range(qubo.get_num_vars()):
    for j in range(i, qubo.get_num_vars()):
        if i == j:
            # Add linear term (including diagonal quadratic contribution)
            iskay_input_problem[f"({i}, )"] = float(
                qubo.objective.linear.to_dict().get(i)
            ) + float(qubo.objective.quadratic.to_dict().get((i, i)))
        else:
            # Add off-diagonal quadratic term
            iskay_input_problem[f"({i}, {j})"] = float(
                qubo.objective.quadratic.to_dict().get((i, j))
            )

# Display Iskay dictionary summary
print("Iskay Dictionary Format:")
print("=" * 50)
print(f"Total coefficients: {len(iskay_input_problem)}")
print(f"  • Constant term: {iskay_input_problem['()']}")
print(
    f"  • Linear terms: {sum(1 for k in iskay_input_problem.keys() if k != '()' and ', )' in k)}"
)
print(
    f"  • Quadratic terms: {sum(1 for k in iskay_input_problem.keys() if k != '()' and ', )' not in k)}"
)
print("\nSample coefficients:")

# Get first 10 and last 5 items properly
items = list(iskay_input_problem.items())
first_10 = list(enumerate(items[:10]))
last_5 = list(enumerate(items[-5:], start=len(items) - 5))

for i, (key, value) in first_10 + last_5:
    coeff_type = (
        "constant"
        if key == "()"
        else "linear"
        if ", )" in key
        else "quadratic"
    )
    print(f"  {key}: {value} ({coeff_type})")
print("  ...")
print("\n✓ Problem ready for Iskay optimizer!")

Comprendere l'algoritmo bf-DCQO

Prima di eseguire l'ottimizzazione, comprendiamo l'algoritmo quantistico sofisticato che alimenta Iskay: bf-DCQO (bias-field digitized counterdiabatic quantum optimization) [1].

Cos'è il bf-DCQO?

Il bf-DCQO si basa sull'evoluzione temporale di un sistema quantistico in cui la soluzione del problema è codificata nello stato fondamentale (stato di energia più bassa) dell'Hamiltoniano quantistico finale [1]. L'algoritmo affronta una sfida fondamentale nell'ottimizzazione quantistica:

La sfida: Il calcolo quantistico adiabatico tradizionale richiede un'evoluzione molto lenta per mantenere le condizioni dello stato fondamentale secondo il teorema adiabatico. Questo richiede circuiti quantistici sempre più profondi man mano che la complessità del problema aumenta, portando a un maggior numero di operazioni di gate e ad errori accumulati.

La soluzione: Il bf-DCQO utilizza protocolli controdiabatici per consentire un'evoluzione rapida mantenendo la fedeltà dello stato fondamentale, riducendo drasticamente la profondità del circuito.

Quadro matematico

L'algoritmo minimizza una funzione di costo della forma:

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

dove $D = \{0,1\}^n$ per variabili binarie e:

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

Per il nostro problema Market Split, la funzione di costo è:

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

Il ruolo dei termini controdiabatici

I termini controdiabatici sono termini aggiuntivi introdotti nell'Hamiltoniano dipendente dal tempo che sopprimono le eccitazioni indesiderate durante l'evoluzione quantistica. Ecco perché sono cruciali:

Nell'ottimizzazione quantistica adiabatica, facciamo evolvere il sistema secondo un Hamiltoniano dipendente dal tempo:

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

dove $H_{\text{problem}}$ codifica il nostro problema di ottimizzazione. Per mantenere lo stato fondamentale durante un'evoluzione rapida, aggiungiamo termini controdiabatici:

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

Questi termini controdiabatici fanno quanto segue:

1. Sopprimono transizioni indesiderate: Impediscono allo stato quantistico di saltare agli stati eccitati durante l'evoluzione rapida
2. Consentono tempi di evoluzione più brevi: Ci permettono di raggiungere lo stato finale molto più velocemente senza violare l'adiabaticità
3. Riducono la profondità del circuito: Un'evoluzione più breve porta a un minor numero di gate e a meno errori

L'impatto pratico è drammatico: il bf-DCQO utilizza fino a 10 volte meno gate di entanglement rispetto al Digital Quantum Annealing [1], rendendolo praticabile per l'hardware quantistico rumoroso attuale.

Ottimizzazione iterativa del bias-field

A differenza degli algoritmi variazionali che ottimizzano i parametri del circuito attraverso molte iterazioni, il bf-DCQO utilizza un approccio guidato dal bias-field che converge in circa 10 iterazioni [1]:

Processo iterativo:

1. Evoluzione quantistica iniziale: Inizia con un circuito quantistico che implementa il protocollo di evoluzione controdiabatic

2. Misurazione: Misura lo stato quantistico per ottenere una distribuzione di probabilità sulle stringhe di bit

3. Calcolo del bias-field: Analizza le statistiche di misurazione e calcola un bias-field ottimale $h_i$ per ogni qubit: $h_i = \text{f}(\text{measurement statistics}, \text{previous solutions})$

4. Iterazione successiva: Il bias-field modifica l'Hamiltoniano per l'iterazione successiva: $H_{\text{next}} = H_{\text{problem}} + \sum_i h_i \sigma_i^z$

   Ciò consente di partire vicino alla buona soluzione trovata in precedenza, eseguendo effettivamente una forma di "ricerca locale quantistica"

5. Convergenza: Ripeti fino a quando la qualità della soluzione si stabilizza o viene raggiunto un numero massimo di iterazioni

Vantaggio chiave: Ogni iterazione fornisce un progresso significativo verso la soluzione ottimale incorporando informazioni dalle misurazioni precedenti, a differenza dei metodi variazionali che devono esplorare lo spazio dei parametri alla cieca.

Post-elaborazione classica integrata

Dopo che l'ottimizzazione quantistica converge, Iskay esegue un post-processing classico di ricerca locale:

• Esplorazione bit-flip: Capovolge sistematicamente o casualmente i bit nella migliore soluzione misurata
• Valutazione dell'energia: Calcola $C(x)$ per ogni soluzione modificata
• Selezione greedy: Accetta miglioramenti che abbassano la funzione di costo
• Passaggi multipli: Esegue diversi passaggi (controllati da postprocessing_level)

Questo approccio ibrido compensa gli errori di bit-flip derivanti dalle imperfezioni hardware e dagli errori di lettura, garantendo soluzioni di alta qualità anche su dispositivi quantistici rumorosi.

Perché il bf-DCQO eccelle sull'hardware attuale

L'algoritmo bf-DCQO è specificamente progettato per eccellere sui dispositivi quantistici a scala intermedia rumorosa (NISQ) odierni [1]:

1. Resilienza agli errori: Un minor numero di gate (riduzione di 10 volte) significa un accumulo di errori drasticamente inferiore
2. Nessuna mitigazione degli errori richiesta: L'efficienza intrinseca dell'algoritmo elimina la necessità di costose tecniche di mitigazione degli errori [1]
3. Scalabilità: Può gestire problemi con fino a 156 qubit (156 variabili binarie) con mappatura diretta qubit-qubit [1]
4. Prestazioni comprovate: Raggiunge rapporti di approssimazione del 100% su istanze benchmark MaxCut e HUBO [1]

Ora vediamo questo potente algoritmo in azione sul nostro problema Market Split!

Passo 2: Ottimizzare il problema per l'esecuzione su hardware quantistico

L'algoritmo bf-DCQO gestisce automaticamente l'ottimizzazione del circuito, creando circuiti quantistici poco profondi con termini controdiabatici specificamente progettati per il backend di destinazione.

Configurare l'ottimizzazione

L'Iskay Optimizer richiede diversi parametri chiave per risolvere efficacemente il tuo problema di ottimizzazione. Esaminiamo ciascun parametro e il suo ruolo nel processo di ottimizzazione quantistica:

Parametri richiesti

Parametro	Tipo	Descrizione	Esempio
problem	Dict[str, float]	Coefficienti QUBO in formato chiave-stringa	{"()": -21.0, "(0,4)": 0.5, "(0,1)": 0.5}
problem_type	str	Specifica del formato: "binary" per QUBO o "spin" per Ising	"binary"
backend_name	str	Dispositivo quantistico di destinazione	"ibm_fez"

Concetti essenziali

• Formato del problema: Usiamo "binary" poiché le nostre variabili sono binarie (0/1), rappresentando assegnazioni di mercato.
• Selezione del backend: Scegli tra le QPU disponibili (ad esempio, "ibm_fez") in base alle tue esigenze e all'istanza delle risorse di calcolo.
• Struttura QUBO: Il nostro dizionario del problema contiene i coefficienti esatti dalla trasformazione matematica.

Opzioni avanzate (opzionali)

Iskay fornisce capacità di ottimizzazione attraverso parametri opzionali. Sebbene i valori predefiniti funzionino bene per la maggior parte dei problemi, puoi personalizzare il comportamento per requisiti specifici:

Parametro	Tipo	Predefinito	Descrizione
shots	int	10000	Misurazioni quantistiche per iterazione (più alto = più accurato)
num_iterations	int	10	Iterazioni dell'algoritmo (più iterazioni possono migliorare la qualità della soluzione)
use_session	bool	True	Usa le sessioni IBM per ridurre i tempi di coda
seed_transpiler	int	None	Imposta per una compilazione del circuito quantistico riproducibile
direct_qubit_mapping	bool	False	Mappa i qubit virtuali direttamente ai qubit fisici
job_tags	List[str]	None	Tag personalizzati per il monitoraggio del lavoro
preprocessing_level	int	0	Intensità di pre-elaborazione del problema (0-3) - vedi dettagli sotto
postprocessing_level	int	2	Livello di raffinamento della soluzione (0-2) - vedi dettagli sotto
transpilation_level	int	0	Tentativi di ottimizzazione del transpiler (0-5) - vedi dettagli sotto
transpile_only	bool	False	Analizza l'ottimizzazione del circuito senza eseguire l'esecuzione completa

Livelli di pre-elaborazione (0-3): Particolarmente importanti per problemi più grandi che attualmente non possono rientrare nei tempi di coerenza dell'hardware. Livelli di pre-elaborazione più elevati ottengono profondità di circuito più superficiali attraverso approssimazioni nella traspirazione del problema:

• Livello 0: Esatto, circuiti più lunghi
• Livello 1: Buon equilibrio tra precisione e approssimazione, eliminando solo i gate con angoli nel 10° percentile più basso
• Livello 2: Approssimazione leggermente superiore, eliminando i gate con angoli nel 20° percentile più basso e utilizzando approximation_degree=0.95 nella traspirazione
• Livello 3: Livello di approssimazione massimo, eliminando i gate nel 30° percentile più basso e utilizzando approximation_degree=0.90 nella traspirazione

Livelli di traspirazione (0-5): Controllano i tentativi avanzati di ottimizzazione del transpiler per la compilazione del circuito quantistico. Questo può portare a un aumento dell'overhead classico e in alcuni casi potrebbe non modificare la profondità del circuito. Il valore predefinito 2 in generale porta al circuito più piccolo ed è relativamente veloce.

• Livello 0: Ottimizzazione del circuito DCQO decomposto (layout, routing, scheduling)
• Livello 1: Ottimizzazione di PauliEvolutionGate e poi del circuito DCQO decomposto (max_trials=10)
• Livello 2: Ottimizzazione di PauliEvolutionGate e poi del circuito DCQO decomposto (max_trials=15)
• Livello 3: Ottimizzazione di PauliEvolutionGate e poi del circuito DCQO decomposto (max_trials=20)
• Livello 4: Ottimizzazione di PauliEvolutionGate e poi del circuito DCQO decomposto (max_trials=25)
• Livello 5: Ottimizzazione di PauliEvolutionGate e poi del circuito DCQO decomposto (max_trials=50)

Livelli di post-elaborazione (0-2): Controllano quanta ottimizzazione classica, compensando gli errori di bit-flip con un numero diverso di passaggi greedy di una ricerca locale:

• Livello 0: 1 passaggio
• Livello 1: 2 passaggi
• Livello 2: 3 passaggi

Modalità solo traspirazione: Ora disponibile per gli utenti che desiderano analizzare l'ottimizzazione del circuito senza eseguire l'esecuzione completa dell'algoritmo quantistico.

Esempio di configurazione personalizzata

Ecco come potreste configurare Iskay con impostazioni diverse:

custom_options = {
    "shots": 15_000,                                        # Higher shot count for better statistics
    "num_iterations": 12,                                   # More iterations for solution refinement
    "preprocessing_level": 1,                               # Light preprocessing for problem simplification
    "postprocessing_level": 2,                              # Maximum postprocessing for solution quality
    "transpilation_level": 3,                               # Using higher transpilation level for circuit optimization
    "seed_transpiler": 42,                                  # Fixed seed for reproducible results
    "job_tags": ["market_split"]                            # Custom tracking tags
}

Per questo tutorial, manterremo la maggior parte dei parametri predefiniti e modificheremo solo il numero di iterazioni del bias-field:

# Specify the target backend
backend_name = "ibm_fez"

# Set the number of bias-field iterations and set a tag to identify the jobs
options = {
    "num_iterations": 3,  # Change number of bias-field iterations
    "job_tags": ["market_split_example"],  # Tag to identify jobs
}

# Configure Iskay optimizer
iskay_input = {
    "problem": iskay_input_problem,
    "problem_type": "binary",
    "backend_name": backend_name,
    "options": options,
}

print("Iskay Optimizer Configuration:")
print("=" * 40)
print(f"  Backend: {backend_name}")
print(f"  Problem: {len(iskay_input['problem'])} terms")
print("  Algorithm: bf-DCQO")

Passo 3: Eseguire utilizzando le primitive Qiskit

Ora sottomettiamo il nostro problema per l'esecuzione sull'hardware quantistico IBM. L'algoritmo bf-DCQO:

1. Costruirà circuiti quantistici poco profondi con termini controdiabatici
2. Eseguirà circa 10 iterazioni con ottimizzazione del bias-field
3. Eseguirà il post-processing classico con ricerca locale
4. Restituirà l'assegnazione di mercato ottimale

# Submit the optimization job
print("Submitting optimization job to Kipu Quantum...")
print(
    f"Problem size: {A.shape[1]} variables, {len(iskay_input['problem'])} terms"
)
print(
    "Algorithm: bf-DCQO (bias-field digitized counterdiabatic quantum optimization)"
)

job = iskay_solver.run(**iskay_input)

print("\nJob successfully submitted!")
print(f"Job ID: {job.job_id}")
print("Optimization in progress...")
print(
    f"The bf-DCQO algorithm will efficiently explore {2**A.shape[1]:,} possible assignments"
)

Monitorare lo stato del lavoro

Puoi controllare lo stato corrente del tuo lavoro di ottimizzazione. Gli stati possibili sono:

• QUEUED: Il lavoro è in attesa nella coda
• RUNNING: Il lavoro è attualmente in esecuzione sull'hardware quantistico
• DONE: Il lavoro è stato completato con successo
• CANCELED: Il lavoro è stato annullato
• ERROR: Il lavoro ha riscontrato un errore

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

Attendere il completamento

Questa cella si bloccherà fino al completamento del lavoro. Il processo di ottimizzazione include:

• Tempo di coda (attesa per l'accesso all'hardware quantistico)
• Tempo di esecuzione (esecuzione dell'algoritmo bf-DCQO con circa 10 iterazioni)
• Tempo di post-elaborazione (ricerca locale classica)

I tempi di completamento tipici variano da pochi minuti a decine di minuti a seconda delle condizioni della coda.

# Wait for job completion
while True:
    status = job.status()
    print(
        f"Waiting for job {job.job_id} to complete... (status: {status})",
        end="\r",
        flush=True,
    )
    if status in ["DONE", "CANCELED", "ERROR"]:
        print(
            f"\nJob {job.job_id} completed with status: {status}" + " " * 20
        )
        break
    time.sleep(30)

# Retrieve the optimization results
result = job.result()
print("\nOptimization complete!")

Passo 4: Post-elaborare e restituire il risultato nel formato classico desiderato

Ora post-elaboriamo i risultati dell'esecuzione quantistica. Questo include:

• Analizzare la struttura della soluzione
• Validare la soddisfazione dei vincoli
• Confrontare con approcci classici

Analizzare i risultati

Comprendere la struttura del risultato

Iskay restituisce un dizionario di risultati completo contenente:

• solution: Un dizionario che mappa gli indici delle variabili ai loro valori ottimali (0 o 1)
• solution_info: Informazioni dettagliate tra cui:
  • bitstring: L'assegnazione ottimale come stringa binaria
  • cost: Il valore della funzione obiettivo (dovrebbe essere 0 per la perfetta soddisfazione dei vincoli)
  • mapping: Come le posizioni delle stringhe di bit si mappano alle variabili del problema
  • seed_transpiler: Seed utilizzato per la riproducibilità
• prob_type: Se la soluzione è in formato binario o spin

Esaminiamo la soluzione restituita dall'ottimizzatore quantistico.

# Display the optimization results
print("Optimization Results")
print("=" * 50)
print(f"Problem Type: {result['prob_type']}")
print("\nSolution Info:")
print(f"  Bitstring: {result['solution_info']['bitstring']}")
print(f"  Cost: {result['solution_info']['cost']}")
print("\nSolution (first 10 variables):")
for i, (var, val) in enumerate(list(result["solution"].items())[:10]):
    print(f"  {var}: {val}")
print("  ...")

Validazione della soluzione

Ora valutiamo se la soluzione quantistica soddisfa i vincoli del Market Split. Il processo di validazione verifica:

Cos'è una violazione dei vincoli?

• Per ogni prodotto $i$, calcoliamo le vendite effettive nella Regione A: $(Ax)_i$
• Confrontiamo questo con le vendite target $b_i$
• La violazione è la differenza assoluta: $|(Ax)_i - b_i|$
• Una soluzione fattibile ha violazioni zero per tutti i prodotti

Cosa ci aspettiamo:

• Caso ideale: Violazione totale = 0 (tutti i vincoli perfettamente soddisfatti)
  • La Regione A ottiene esattamente 1002 unità del Prodotto 1, 879 unità del Prodotto 2 e 1040 unità del Prodotto 3
  • La Regione B ottiene le unità rimanenti (anche 1002, 879 e 1040 rispettivamente)
• Caso buono: La violazione totale è piccola (soluzione quasi ottimale)
• Caso scarso: Grandi violazioni indicano che la soluzione non soddisfa i requisiti aziendali

La funzione di validazione calcolerà:

1. Vendite effettive per prodotto in ciascuna regione
2. Violazioni dei vincoli per ciascun prodotto
3. Distribuzione del mercato tra le regioni

def validate_solution(A, b, solution):
    """Validate market split solution."""
    x = np.array(solution)
    region_a = A @ x
    region_b = A @ (1 - x)
    violations = np.abs(region_a - b)

    return {
        "target": b,
        "region_a": region_a,
        "region_b": region_b,
        "violations": violations,
        "total_violation": np.sum(violations),
        "is_feasible": np.sum(violations) == 0,
        "region_a_markets": int(np.sum(x)),
        "region_b_markets": len(x) - int(np.sum(x)),
    }

# Convert bitstring to list of integers and validate
optimal_assignment = [
    int(bit) for bit in result["solution_info"]["bitstring"]
]
validation = validate_solution(A, b, optimal_assignment)

Interpretare i risultati della validazione

I risultati della validazione mostrano se il Quantum Optimizer ha trovato una soluzione fattibile. Esaminiamo quanto segue:

Controllo di fattibilità:

• is_feasible = True significa che la soluzione soddisfa perfettamente tutti i vincoli (violazione totale = 0)
• is_feasible = False significa che alcuni vincoli sono violati

Analisi delle vendite:

• Confronta le vendite Target rispetto a quelle Effettive per ogni prodotto
• Per una soluzione perfetta: Effettive = Target per tutti i prodotti in entrambe le regioni
• La differenza indica quanto siamo vicini alla divisione di mercato desiderata

Distribuzione del mercato:

• Mostra quanti mercati sono assegnati a ciascuna regione
• Non c'è requisito per numeri uguali di mercati, solo che gli obiettivi di vendita siano raggiunti

print("Solution Validation")
print("=" * 50)
print(f"Feasible solution: {validation['is_feasible']}")
print(f"Total constraint violation: {validation['total_violation']}")

print("\nSales Analysis (Target vs Actual):")
for i, (target, actual_a, actual_b) in enumerate(
    zip(validation["target"], validation["region_a"], validation["region_b"])
):
    violation_a = abs(actual_a - target)
    violation_b = abs(actual_b - target)
    print(f"  Product {i+1}:")
    print(f"    Target: {target}")
    print(f"    Region A: {actual_a} (violation: {violation_a})")
    print(f"    Region B: {actual_b} (violation: {violation_b})")

print("\nMarket Distribution:")
print(f"  Region A: {validation['region_a_markets']} markets")
print(f"  Region B: {validation['region_b_markets']} markets")

Valutazione della qualità della soluzione

In base ai risultati della validazione sopra riportati, possiamo valutare la qualità della soluzione quantistica:

Se is_feasible = True (Violazione totale = 0):

• Il Quantum Optimizer ha trovato con successo una soluzione ottimale
• Tutti i vincoli aziendali sono perfettamente soddisfatti
• Questo dimostra il vantaggio quantistico su un problema in cui i risolutori classici hanno difficoltà [4]

Se is_feasible = False (Violazione totale > 0):

• La soluzione è quasi ottimale ma non perfetta
• Piccole violazioni possono essere accettabili nella pratica
• Considerate di regolare i parametri dell'ottimizzatore:
  • Aumentare num_iterations per più passaggi di ottimizzazione
  • Aumentare postprocessing_level per più raffinamento classico
  • Aumentare shots per migliori statistiche di misurazione

Interpretazione della funzione di costo:

• Il valore cost da solution_info è uguale a $||Ax - b||^2$
• Costo = 0 indica la perfetta soddisfazione dei vincoli
• Valori di costo più elevati indicano violazioni dei vincoli maggiori

Conclusione

Cosa abbiamo realizzato

In questo tutorial, abbiamo con successo:

1. Caricato un problema di ottimizzazione reale: Ottenuto un'istanza impegnativa del Market Split dalla libreria benchmark QOBLIB [2]
2. Trasformato in formato QUBO: Convertito il problema vincolato in una formulazione quadratica non vincolata [3]
3. Sfruttato algoritmi quantistici avanzati: Utilizzato l'algoritmo bf-DCQO di Kipu Quantum con termini controdiabatici [1]
4. Ottenuto soluzioni ottimali: Trovato soluzioni fattibili che soddisfano tutti i vincoli

Punti chiave

Innovazione algoritmica: L'algoritmo bf-DCQO rappresenta un avanzamento significativo [1]:

• 10 volte meno gate rispetto all'annealing quantistico digitale
• Circa 10 iterazioni invece di circa 100 per i metodi variazionali
• Resilienza agli errori integrata attraverso l'efficienza del circuito

Termini controdiabatici: Consentono un'evoluzione quantistica rapida mantenendo la fedeltà dello stato fondamentale, rendendo l'ottimizzazione quantistica praticabile sull'hardware rumoroso attuale [1].

Guida del bias-field: L'approccio iterativo del bias-field consente a ogni iterazione di iniziare vicino a buone soluzioni trovate in precedenza, fornendo una forma di ricerca locale potenziata quantisticamente [1].

Passi successivi

Per approfondire la tua comprensione ed esplorare ulteriormente:

1. Provare istanze diverse: Sperimentate con altre istanze QOBLIB di dimensioni variabili
2. Regolare i parametri: Regola num_iterations, preprocessing_level, postprocessing_level
3. Confrontare con il classico: Confronta con risolutori di ottimizzazione classici
4. Provare strategie diverse: Cerca di trovare una codifica migliore per il problema o formulalo come HUBO (se possibile)
5. Applicare al tuo dominio: Adatta le tecniche di formulazione QUBO/HUBO ai tuoi problemi di ottimizzazione

Riferimenti

[1] IBM Quantum. "Kipu Quantum Optimization." IBM Quantum Documentation.

[2] QOBLIB - Quantum Optimization Benchmarking Library. Zuse Institute Berlin (ZIB). https://git.zib.de/qopt/qoblib-quantum-optimization-benchmarking-library

[3] Glover, F., Kochenberger, G., & Du, Y. (2019). "Quantum bridge analytics I: a tutorial on formulating and using QUBO models." 4OR: A Quarterly Journal of Operations Research, 17(4), 335-371.