Risolvi il problema della frammentazione del mercato con Iskay Quantum Optimizer di Kipu Quantum

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

Sfondo

Questa esercitazione mostra come risolvere il problema del Market Split utilizzando l'ottimizzatore quantistico Iskay di Kipu Quantum [1]. 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.

La sfida della divisione del mercato

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.

Formulazione matematica:

Cerchiamo un vettore di assegnazione binaria $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 il target di vendita (tipicamente la metà della domanda totale per prodotto)

Funzione di costo:

Per risolvere questo problema, minimizziamo la violazione del vincolo al quadrato:

$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 vendita per il prodotto $i$ in ogni regione
• Il costo è uguale a zero proprio quando tutti i vincoli sono soddisfatti

Ogni termine della somma rappresenta lo scarto quadratico rispetto alle vendite target per un determinato prodotto. Espandendo questa funzione di costo, si ottiene:

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

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

Complessità computazionale:

Nonostante la sua semplice interpretazione commerciale, questo problema presenta una notevole intrattabilità computazionale:

• 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]
• Crescita esponenziale : Lo spazio delle soluzioni cresce in modo esponenziale ( $2^n$ assegnazioni possibili), rendendo inapplicabili gli approcci di forza bruta

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

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 del circuito : L'algoritmo bf-DCQO ottiene una notevole riduzione dei gate [1] :

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

Progettazione non variazionale : A differenza degli algoritmi variazionali che richiedono circa 100 iterazioni, il bf-DCQO ne richiede in genere solo circa 10 [1]. Questo obiettivo viene raggiunto attraverso:

• Calcoli intelligenti del campo di polarizzazione a partire dalle distribuzioni di stato misurate
• Iniziare ogni iterazione da uno stato energetico prossimo alla soluzione precedente
• Postelaborazione classica integrata con la ricerca locale

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

Requisiti

Prima di iniziare questa esercitazione, assicuratevi di aver installato quanto segue:

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

È inoltre necessario ottenere l'accesso alla funzione Iskay Quantum Optimizer dal sito Qiskit Functions Catalog.

Configura

Per prima cosa, importare tutti i pacchetti necessari per questa esercitazione.

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

Configura le credenziali dell' IBM Quantum

Definite le vostre IBM Quantum® Platform credenziali. Saranno necessari:

• Token API : La chiave API di 44 caratteri da IBM Quantum Platform
• CRN dell'istanza : l'identificativo dell'istanza IBM Cloud®

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

Fase 1: mappare gli input classici su un problema quantistico

Cominciamo con la mappatura del nostro problema classico in una rappresentazione compatibile con quella quantistica. Questa fase prevede:

1. Collegamento all'ottimizzatore quantistico Iskay
2. Caricamento e formulazione del problema del Market Split
3. Capire l'algoritmo bf-DCQO che lo risolverà

Connettiti a Iskay Quantum Optimizer

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.

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 problematici

Le istanze dei problemi di QOBLIB (Quantum Optimization Benchmarking Library) [2] sono memorizzate in un semplice formato di testo. Esaminiamo il contenuto effettivo della nostra istanza di destinazione 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/riga della matrice $A$ )
  • 20 = numero di mercati (variabili/colonne della matrice $A$ )

• Le 3 righe successive: Matrice dei coefficienti $A$ e vettore target $b$

  • Ogni riga ha 21 numeri: i primi 20 sono i coefficienti di riga, l'ultimo è il target
  • Linea 2: 60 92 161 ... 51 | 1002
    • I primi 20 numeri: Quantità di prodotto 1 venduta da ognuno dei 20 mercati
    • Ultimo numero (1002): Vendite target per il prodotto 1 in una regione
  • Linea 3: 176 196 41 ... 46 | 879
    • Vendite del prodotto 2 per mercato e obiettivo (879)
  • Linea 4: 68 68 179 ... 95 | 1040
    • Vendite del prodotto 3 per mercato e target (1040)

Interpretazione commerciale:

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

La potenza dell'ottimizzazione quantistica sta nel trasformare i problemi vincolati in forme quadratiche non vincolate [4]. Per il problema della suddivisione del mercato, convertiamo i vincoli di uguaglianza in

$Ax = b$

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

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

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$

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$

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]. 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à.

Implementare le funzioni di caricamento dei dati e conversione QUBO

Definiamo ora 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 le istanze del problema 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

Carica l'istanza del problema

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

• 3 prodotti (vincoli)
• 20 mercati (variabili decisionali binarie)
• Oltre 1 milione di possibili incarichi 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: "
        f"2^{A.shape[1]} = {2**A.shape[1]:,} possible assignments"
    )

Converti in formato QUBO

Trasformiamo ora il problema di ottimizzazione vincolata 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())}")

Converti QUBO in formato Iskay

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

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

Dove

• 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.
• 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 devono essere codificati in un dizionario come segue:

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:

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:

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

Questo significa che:

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

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

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

NON sono 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: "
    f"{sum(1 for k in iskay_input_problem.keys() if k != '()' and ', )' in k)}"
)
print(
    f"  • Quadratic terms: "
    f"{sum(1 for k in iskay_input_problem.keys() if k != '()' and ', )' not in k)}"
)
print("\nSample coefficients:")

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

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

Comprendere l'algoritmo bf-DCQO

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

Che 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 a più bassa energia) dell'hamiltoniana quantistica finale [1]. L'algoritmo affronta una sfida fondamentale nell'ottimizzazione quantistica:

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.

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.

Struttura matematica

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 le 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 di 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 controdiabetici

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:

Nell'ottimizzazione quantistica adiabatica, il sistema evolve secondo un'hamiltoniana 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 l'evoluzione rapida, aggiungiamo termini controdiabatici:

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

Questi termini controdiabatici svolgono le seguenti funzioni:

1. Sopprimere le transizioni indesiderate : Impedire che lo stato quantico salti a stati eccitati durante l'evoluzione rapida
2. Consentono tempi di evoluzione più brevi : Permettono di raggiungere lo stato finale molto più velocemente senza violare l'adiabaticità
3. Riduzione della profondità del circuito : Un'evoluzione più breve porta a un minor numero di porte e a un minor numero di errori

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

Ottimizzazione iterativa del campo di distorsione

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 [:]

Processo di iterazione:

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

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

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

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$

   Questo permette di iniziare vicino alla soluzione buona trovata in precedenza, eseguendo di fatto una forma di "ricerca locale quantistica"

5. Convergenza : Ripetere 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 le informazioni delle misure precedenti, a differenza dei metodi variazionali che devono esplorare lo spazio dei parametri alla cieca.

Post-elaborazione classica integrata

Dopo la convergenza dell'ottimizzazione quantistica, Iskay esegue la classica post-elaborazione della ricerca locale :

• Esplorazione con salto mortale dei bit : Capovolgere sistematicamente o casualmente i bit nella migliore soluzione misurata
• Valutazione energetica : Calcolare $C(x)$ per ogni soluzione modificata
• Selezione avida : Accettare i miglioramenti che riducono la funzione di costo
• Passaggi multipli : Esegue più passate (controllate da postprocessing_level)

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.

Perché bf-DCQO eccelle sull'hardware attuale

L'algoritmo bf-DCQO è stato progettato specificamente per eccellere sugli attuali dispositivi quantistici rumorosi su scala intermedia (NISQ) [1] :

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

Vediamo ora questo potente algoritmo in azione sul nostro problema di Market Split!

Fase 2: Ottimizzazione del problema per l'esecuzione su hardware quantistico

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.

Configurare l'ottimizzazione

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:

Parametri obbligatori

Concetti essenziali

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

Opzioni avanzate (facoltative)

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:

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:

• Livello 0 : circuiti esatti e più lunghi
• Livello 1 : Buon equilibrio tra accuratezza e approssimazione, tagliando solo le porte con angoli nel 10 percentile più basso
• Livello 2 : approssimazione leggermente superiore, tagliando le porte con angoli nel 20 percentile più basso e utilizzando approximation_degree=0.95 nella trasposizione
• 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

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.

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

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:

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

Modalità Transpile-only : Ora disponibile per gli utenti che desiderano analizzare l'ottimizzazione dei circuiti senza eseguire l'intero algoritmo quantistico.

Esempio di configurazione personalizzata

Ecco come si potrebbe configurare Iskay con diverse impostazioni:

custom_options = {
    # Higher shot count for better statistics
    "shots": 15_000,

    # More iterations for solution refinement
    "num_iterations": 12,

    # Light preprocessing for problem simplification
    "preprocessing_level": 1,

    # Maximum postprocessing for solution quality
    "postprocessing_level": 2,

    # Using higher transpilation level for circuit optimization
    "transpilation_level": 3,

    # Fixed seed for reproducible results
    "seed_transpiler": 42,

    # Custom tracking tags
    "job_tags": ["market_split"]
}

Per questa esercitazione, manterremo la maggior parte dei parametri predefiniti e modificheremo solo il numero di iterazioni del campo di polarizzazione:

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

Passaggio 3: eseguire utilizzando Qiskit primitives

Ora sottoponiamo il nostro problema all'esecuzione su hardware IBM Quantum. L'algoritmo bf-DCQO:

1. Costruire circuiti quantistici poco profondi con termini controdiabatici
2. Eseguire circa 10 iterazioni con l'ottimizzazione del campo di polarizzazione
3. Eseguire una post-elaborazione classica con ricerca locale
4. Restituire l'assegnazione ottimale del mercato

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

job = iskay_solver.run(**iskay_input)

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

Monitorare lo stato del lavoro

È possibile controllare lo stato attuale del lavoro di ottimizzazione. Gli stati possibili sono:

• QUEUED: Il lavoro è in attesa nella coda
• RUNNING: Il lavoro è attualmente in esecuzione sull'hardware quantistico
• DONE: Lavoro 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 blocca fino al completamento del lavoro. Il processo di ottimizzazione comprende:

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

Fase 4: Post-elaborazione e restituzione del risultato nel formato classico desiderato

Ora elaboriamo i risultati dell'esecuzione quantistica. Ciò comprende:

• Analisi della struttura della soluzione
• Convalida della soddisfazione dei vincoli
• Benchmarking rispetto agli approcci classici

Analizza i risultati

Comprendere la struttura dei risultati

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 una perfetta soddisfazione dei vincoli)
  • mapping: Come le posizioni delle bitstringhe si adattano alle variabili del problema
  • seed_transpiler: Seme utilizzato per la riproducibilità
• prob_type: Se la soluzione è in formato binario o di 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("  ...")

Convalida della Soluzione

Ora verifichiamo se la soluzione quantistica soddisfa i vincoli del Market Split. Il processo di convalida controlla:

Che cos'è una violazione dei vincoli?

• Per ciascun prodotto $i$, calcoliamo le vendite effettive nella Regione A: $(Ax)_i$
• Confrontiamo questo dato con l'obiettivo di vendita $b_i$
• La violazione è la differenza assoluta: $|(Ax)_i - b_i|$
• Una soluzione fattibile ha violazioni pari a zero per tutti i prodotti

Cosa ci aspettiamo:

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

La funzione di convalida calcolerà:

1. Vendite effettive per prodotto in ogni regione
2. Violazioni dei vincoli per ogni 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 convalida

I risultati della convalida mostrano se l'ottimizzatore quantistico ha trovato una soluzione fattibile. Esaminiamo quanto segue:

Verifica della 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:

• Confrontare le vendite target con quelle effettive per ogni prodotto
• Per una soluzione perfetta: Effettivo = Obiettivo per tutti i prodotti in entrambe le regioni
• La differenza indica quanto siamo vicini alla suddivisione del mercato desiderata

Distribuzione sul mercato:

• Mostra il numero di mercati assegnati a ciascuna regione
• Non è richiesto un numero uguale di mercati, ma solo il raggiungimento degli obiettivi di vendita

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

Sulla base dei risultati della convalida di cui sopra, possiamo valutare la qualità della soluzione quantistica:

Se is_feasible = True (violazione totale = 0):

• L'ottimizzatore quantistico ha trovato con successo una soluzione ottimale
• Tutti i vincoli aziendali sono perfettamente soddisfatti
• Questo dimostra il vantaggio quantistico in 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
• Considerare la possibilità di regolare i parametri dell'ottimizzatore:
  • Aumentare num_iterations per un maggior numero di passaggi di ottimizzazione
  • Aumentare postprocessing_level per una raffinatezza più classica
  • Aumentare shots per migliorare le statistiche di misura

Interpretazione della funzione di costo:

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

Conclusione

Cosa abbiamo realizzato

In questa esercitazione, abbiamo avuto successo:

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

Punti chiave

Innovazione dell'algoritmo : L'algoritmo bf-DCQO rappresenta un progresso significativo [1] :

• 10 volte meno porte rispetto all'annealing quantistico digitale
• Circa 10 iterazioni invece di circa 100 per i metodi variazionali
• Resilienza agli errori incorporata grazie all'efficienza del circuito

Termini controdiabatici : Consentono una rapida evoluzione quantistica mantenendo la fedeltà allo stato fondamentale, rendendo l'ottimizzazione quantistica pratica sull'hardware rumoroso di oggi [1].

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

Passi successivi

Per approfondire la comprensione ed esplorare ulteriormente:

1. Provare diverse istanze : Sperimentare con altre istanze di QOBLIB di dimensioni diverse
2. Sintonizzare i parametri : Regolare num_iterations, preprocessing_level, postprocessing_level
3. Confronto con i classici : Benchmark rispetto ai solutori di ottimizzazione classici
4. Provare diverse strategie : Cercare di trovare una migliore codifica del problema o formularlo come HUBO (se possibile)
5. Applicare al proprio dominio : Adattare le tecniche di formulazione QUBO/HUBO ai vostri problemi di ottimizzazione

Riferimenti

[1] IBM Quantum. "Ottimizzazione quantistica di Kipu " IBM Quantum Documentazione.

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

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

[4] Lodi, A., Tramontani, A. e Weninger, K. (2023). "Il decathlon intrattabile: Benchmarking Hard Combinatorial Problems" INFORMS Journal on Computing.