{
"cells": [
{
"cell_type": "markdown",
"id": "b6d1e3ec",
"metadata": {},
"source": [
"---\n",
"title: \"Risolvi il problema della frammentazione del mercato con l’ottimizzatore Parity Twine di ParityQC\"\n",
"description: \"Scopri come risolvere il problema della frammentazione del mercato utilizzando il Parity Twine Optimizer.\"\n",
"---\n",
"\n",
"{/* cspell:ignore parityqc QOBLIB marketsplit independentset */}\n",
"\n",
"\n",
"\n",
"# Risolvi il problema della frammentazione del mercato con l’ottimizzatore Parity Twine di ParityQC\n",
"\n"
]
},
{
"attachments": {},
"cell_type": "markdown",
"id": "a6f69b77",
"metadata": {},
"source": [
"Stima del tempo di *esecuzione: 10 secondi su un processore Nighthawk r2. (NOTA: Si tratta solo di una stima. (La durata potrebbe variare.)*\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "21156b6f",
"metadata": {},
"source": [
"\n",
"\n",
"## Risultati di apprendimento\n",
"\n",
"* Recuperare e formattare il problema di suddivisione del mercato dalla libreria [QOBLIB (Quantum Optimization Benchmarking Library)](https://github.com/ZIB-AOPT/QOBLIB).\n",
"* Configurare e utilizzare Parity Twine Optimizer per risolvere un caso di split di mercato.\n",
"* Scopri come scegliere le opzioni per il Parity Twine Optimizer e quali risultati vengono generati.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "d185259f257c1618",
"metadata": {},
"source": [
"\n",
"\n",
"## Sfondo\n",
"\n",
"Questo tutorial illustra come risolvere il problema della suddivisione del mercato utilizzando l’ottimizzatore Parity Twine di ParityQC.\n",
"\n",
"L'esempio del problema è tratto dalla [QOBLIB (Quantum Optimization Benchmarking Library)](https://github.com/ZIB-AOPT/QOBLIB).\n",
"\n",
"\n",
"\n",
"### Problema di frammentazione del mercato\n",
"\n",
"Il problema della suddivisione del mercato è un problema reale di allocazione delle risorse di complessità NP-difficile ed è diventato un punto di riferimento per gli algoritmi di ottimizzazione quantistica.\n",
"Si tratta di una sfida logistica di grande importanza: come suddividere un panorama complesso di clienti e prodotti in territori gestibili e di dimensioni equivalenti.\n",
"\n",
"L'obiettivo è quello di suddividere i mercati di $n$ in due regioni di vendita equilibrate, in modo tale che ciascuna regione riceva esattamente la metà della domanda totale dei prodotti di $m$.\n",
"La soluzione consiste nella configurazione specifica che garantisce la distribuzione più uniforme possibile della domanda di prodotti, consentendo all’azienda di attuare una strategia logistica e di gestione del personale che garantisca l’equilibrio tra le due regioni,\n",
"riducendo al minimo i rischi quali carenze localizzate di prodotti o sovraffollamento dei magazzini.\n",
"\n",
"Con l'aumentare del numero di mercati e prodotti, il numero di possibili combinazioni cresce in modo esponenziale, rendendo difficile individuare la suddivisione ottimale ricorrendo alle tradizionali ricerche esaustive.\n",
"\n",
"\n",
"\n",
"### Formulazione matematica\n",
"\n",
"Sia $A$ una matrice di tipo $m \\times n$ che rappresenta la domanda dei prodotti nei vari mercati, dove $A_{ij}$ è la domanda del prodotto $i$ nel mercato $j$.\n",
"\n",
"Si definisce un vettore di assegnazione binario, $x = [x_1, x_2, \\dots, x_n]^T \\in \\{0, 1\\}^n$, per cui:\n",
"\n",
"* $x_j = 1$ assegna l' $j$ e di mercato alla Regione A.\n",
"* $x_j = 0$ assegna l’ $j$ e di mercato alla Regione B.\n",
"\n",
"Sia $d = [d_1, d_2, \\dots, d_m]^T$ il vettore della domanda totale per ciascun prodotto, calcolato come $d = A \\cdot \\mathbf{1}$. Il volume di vendite target per regione del prodotto $i$ è esattamente $\\frac{d_i}{2}$.\n",
"\n",
"Il vincolo di ottimizzazione o di fattibilità richiede che il totale delle vendite assegnate alla Regione A corrisponda esattamente alla metà della domanda totale per ciascun prodotto:\n",
"\n",
"$A x = \\frac{1}{2} A \\mathbf{1} = b.$\n",
"\n",
"In pratica, poiché raramente è possibile effettuare una divisione esatta, il problema viene formulato in modo da minimizzare il quadrato della violazione dei vincoli (la funzione di costo):\n",
"\n",
"$\\min_{x} \\left\\Vert{} A x - b \\right\\Vert{}^2 = \\sum_{i=1}^{m} \\left( \\sum_{j=1}^{n} A_{ij} x_j - b\\right)^2.$\n",
"\n",
"Espandendo questa espressione si ottiene una forma equivalente a un problema di ottimizzazione binaria quadratica senza vincoli (QUBO).\n",
"\n",
"Una volta risolto il problema, il vettore di soluzione $x$ determina a quale regione viene assegnato il mercato. Questa è la configurazione che consente di ottenere la distribuzione più equilibrata possibile della domanda di prodotto.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "55b94021",
"metadata": {},
"source": [
"\n",
"\n",
"## Requisiti\n",
"\n",
"Prima di iniziare questo tutorial, assicurati che siano installati i seguenti componenti:\n",
"\n",
"* Qiskit Functions Catalog IBM Cliente (`pip install qiskit-ibm-catalog`)\n",
"* Componente aggiuntivo di Qiskit: Optimization Mapper (`pip install qiskit_addon_opt_mapper`)\n",
"* NumPy (`pip install numpy`)\n",
"\n",
"È inoltre necessario disporre dell'autorizzazione per accedere alla funzione \"Twine Optimizer\" di ParityQC. Per richiedere l'accesso, compila questo [modulo](https://parityqc.com/products/parity-twine-optimizer/free-trial).\n",
"\n"
]
},
{
"attachments": {},
"cell_type": "markdown",
"id": "7db2e559",
"metadata": {},
"source": [
"\n",
"\n",
"## Configura\n",
"\n",
"(Questo codice presuppone che tu abbia già [salvato il tuo account](/docs/guides/functions-get-started#install-qiskit-functions-catalog-client) nell'ambiente locale.)\n",
"\n",
"Per prima cosa, importa tutti i pacchetti necessari per questo tutorial.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "bc380c46",
"metadata": {},
"outputs": [],
"source": [
"import tempfile\n",
"\n",
"from collections.abc import Callable\n",
"from pathlib import Path\n",
"\n",
"import numpy as np\n",
"import requests\n",
"\n",
"from qiskit_addon_opt_mapper import OptimizationProblem\n",
"from qiskit_addon_opt_mapper.converters import OptimizationProblemToQubo\n",
"from qiskit_ibm_catalog import QiskitFunctionsCatalog"
]
},
{
"cell_type": "markdown",
"id": "d59c6bf33095b413",
"metadata": {},
"source": [
"Carica il “Parity Twine Optimizer” dal catalogo “ Qiskit Functions ”:\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "805c80a1180e79fe",
"metadata": {},
"outputs": [],
"source": [
"catalog = QiskitFunctionsCatalog(channel=\"ibm_quantum_platform\")\n",
"function = catalog.load(\"parityqc/parity-twine-optimizer\")"
]
},
{
"attachments": {},
"cell_type": "markdown",
"id": "988ee237",
"metadata": {},
"source": [
"\n",
"\n",
"### Fase 1: Definire il problema come funzione obiettivo\n",
"\n",
"È possibile ottenere un esempio di problema di suddivisione del mercato dalla libreria [QOBLIB (Quantum Optimization Benchmarking Library)](https://github.com/ZIB-AOPT/QOBLIB) come indicato di seguito.\n",
"\n",
"La funzione `load_market_split_problem` recupera un problema specificato da QOBLIB e lo converte in un problema QUBO.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "2a90bce6-1925-436f-a167-4fab3255f4a0",
"metadata": {},
"outputs": [],
"source": [
"def load_market_split_problem(instance_name: str) -> OptimizationProblem:\n",
" \"\"\"Load and formulate a market split optimization problem from an QOBLIB instance.\n",
"\n",
" The QOBLIB library can be found here:\n",
" https://github.com/ZIB-AOPT/QOBLIB.\n",
"\n",
" Args:\n",
" instance_name: Name of the market split instance to load as specified by the .dat file\n",
" in the QOBLIB repo.\n",
"\n",
" Returns:\n",
" The output OptimizationProblem containing the loaded market split problem.\n",
" \"\"\"\n",
"\n",
" problem_matrix, problem_vector = fetch_and_parse(\n",
" instance_name, \"01-marketsplit\", parse_marketsplit_dat\n",
" )\n",
"\n",
" # Create optimization problem\n",
" optimization_problem = OptimizationProblem(instance_name)\n",
"\n",
" # Add binary variables (one for each market)\n",
" optimization_problem.binary_var_list(problem_matrix.shape[1])\n",
"\n",
" # Add equality constraints (one for each product)\n",
" for idx, rhs in enumerate(problem_vector):\n",
" optimization_problem.linear_constraint(\n",
" problem_matrix[idx, :], sense=\"==\", rhs=rhs\n",
" )\n",
"\n",
" # Convert to QUBO with penalty parameter\n",
" return OptimizationProblemToQubo(penalty=1).convert(optimization_problem)"
]
},
{
"cell_type": "markdown",
"id": "becd6460-8eb9-4796-8a21-60d6edc56cd1",
"metadata": {},
"source": [
"La funzione `load_market_split_problem` richiede le seguenti funzioni di analisi sintattica per recuperare ed elaborare i dati relativi al problema della suddivisione del mercato da QOBLIB.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c07d1d1b-3dc1-4fd8-b7cd-b7898e974eee",
"metadata": {},
"outputs": [],
"source": [
"def fetch_and_parse(instance_name: str, problem: str, parse_func: Callable):\n",
" \"\"\"Generic function to fetch and parse data from QOBLIB repository.\n",
"\n",
" Args:\n",
" instance_name: Name of the instance to fetch.\n",
" problem: Category of the problem (e.g., '01-marketsplit', '07-independentset').\n",
" parse_func: Function used to parse the downloaded file\n",
" (e.g., parse_marketsplit_dat, parse_gph_file).\n",
"\n",
" Returns:\n",
" Result of `parse_func` - either (np.ndarray, np.ndarray) for marketsplit\n",
" or nx.Graph for MIS.\n",
" \"\"\"\n",
" base_url = (\n",
" \"https://raw.githubusercontent.com/ZIB-AOPT/QOBLIB/refs/heads/main/\"\n",
" )\n",
" url = (\n",
" base_url\n",
" + problem\n",
" + \"/instances/\"\n",
" + instance_name\n",
" + (\".dat\" if problem == \"01-marketsplit\" else \".gph\")\n",
" )\n",
"\n",
" try:\n",
" response = requests.get(url, timeout=30)\n",
" response.raise_for_status()\n",
"\n",
" with tempfile.NamedTemporaryFile(\n",
" mode=\"w\",\n",
" suffix=\".dat\" if problem == \"01-marketsplit\" else \".gph\",\n",
" delete=False,\n",
" encoding=\"utf-8\",\n",
" ) as temp_file:\n",
" temp_file.write(response.text)\n",
" temp_file_path = temp_file.name\n",
"\n",
" try:\n",
" return parse_func(temp_file_path)\n",
" finally:\n",
" Path(temp_file_path).unlink(missing_ok=True)\n",
"\n",
" except requests.RequestException as e:\n",
" print(f\"Error fetching data from repository: {e}\")\n",
" except (ValueError, OSError) as e:\n",
" print(f\"Error processing data: {e}\")\n",
" return None\n",
"\n",
"\n",
"def parse_marketsplit_dat(filename: str) -> tuple[np.ndarray, np.ndarray]:\n",
" \"\"\"Parse a market split problem from a .dat file format.\n",
"\n",
" Args:\n",
" filename: Path to the .dat file.\n",
"\n",
" Returns:\n",
" Tuple of (A, b) where:\n",
" - A: (m, n) array of coefficients.\n",
" - b: (m,) array of target values.\n",
"\n",
" Raises:\n",
" ValueError: If file format is invalid or file is empty.\n",
" \"\"\"\n",
" with Path(filename).open(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",
" try:\n",
" m, n = map(int, lines[0].split())\n",
" except (ValueError, IndexError) as e:\n",
" raise ValueError(\n",
" \"Invalid file format: first line must contain 'm n' integers\"\n",
" ) from e\n",
"\n",
" if len(lines) < m + 1:\n",
" raise ValueError(\n",
" f\"File contains {len(lines)} lines but expected {m + 1} lines\"\n",
" )\n",
"\n",
" # Next m lines: each row of A followed by corresponding element of b\n",
" mat_a = []\n",
" vec_b = []\n",
"\n",
" for i in range(1, m + 1):\n",
" try:\n",
" values = list(map(int, lines[i].split()))\n",
" except ValueError as e:\n",
" raise ValueError(f\"Invalid integer values in line {i + 1}\") from e\n",
"\n",
" if len(values) != n + 1:\n",
" raise ValueError(\n",
" f\"Line {i + 1} contains {len(values)} values but expected {n + 1}\"\n",
" )\n",
"\n",
" mat_a.append(values[:-1]) # First n values: product sales per market\n",
" vec_b.append(values[-1]) # Last value: target sales for this product\n",
"\n",
" return np.array(mat_a), np.array(vec_b)"
]
},
{
"cell_type": "markdown",
"id": "9811ef6c-717e-4033-963d-3fd85790be23",
"metadata": {},
"source": [
"Una volta definito, `load_marketsplit_problem` può essere utilizzato per caricare un'istanza specifica del problema dalla libreria:\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "287f6c52-9b2a-46b7-994d-7005bd4ab1c6",
"metadata": {},
"outputs": [],
"source": [
"ms_instance = \"ms_04_050_001\"\n",
"\n",
"ms_problem = load_market_split_problem(ms_instance)"
]
},
{
"cell_type": "markdown",
"id": "ac6f36e3",
"metadata": {},
"source": [
"\n",
"\n",
"### Fase 2: Conversione in formato JSON\n",
"\n",
"Nella prima fase, hai ottenuto la rappresentazione QUBO del problema. Ora, convertilo in formato JSON per la funzione di ottimizzazione:\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "fe1169b1-50a0-4edb-9db5-7c0d99ce9a68",
"metadata": {},
"outputs": [],
"source": [
"def optimization_problem_to_json(\n",
" problem: OptimizationProblem,\n",
") -> dict[str, float]:\n",
" \"\"\"\n",
" Converts an unconstrained quadratic OptimizationProblem in terms of binary or spin variables\n",
" to the JSON input format of the Parity Twine Qiskit Function.\n",
"\n",
" Args:\n",
" problem: The optimization problem to convert to JSON.\n",
"\n",
" Returns:\n",
" The JSON input format of the given problem.\n",
" \"\"\"\n",
" ising, constant = problem.to_ising()\n",
" output = {\"()\": float(constant)}\n",
" for op, coefficient in zip(ising.paulis, ising.coeffs, strict=True):\n",
" # Invert the label strings because Qiskit has opposite convention\n",
" qubits = tuple(\n",
" num\n",
" for num, pauli in enumerate(op.to_label()[::-1])\n",
" if pauli == \"Z\"\n",
" )\n",
" output[str(qubits)] = float(coefficient)\n",
" return output"
]
},
{
"cell_type": "markdown",
"id": "9e374de6-384a-497e-bcf1-c8617c1945ec",
"metadata": {},
"source": [
"L'istanza QUBO del problema della suddivisione del mercato è ora convertita in formato JSON come segue:\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "4885df90-4d15-4bc7-8130-ec1d9ece7670",
"metadata": {},
"outputs": [],
"source": [
"json_ms_problem = optimization_problem_to_json(ms_problem)"
]
},
{
"attachments": {},
"cell_type": "markdown",
"id": "b4d480b3",
"metadata": {},
"source": [
"\n",
"\n",
"### Fase 3: Risolvi il problema utilizzando il Parity Twine Optimizer\n",
"\n",
"Ora che hai ottenuto il problema della suddivisione del mercato e lo hai convertito nella forma corretta, puoi trovare una soluzione utilizzando Twine Optimizer e un backend IBM® a tua scelta.\n",
"\n",
"Per eseguire la funzione, selezionare un dispositivo backend adeguato; ad esempio, `ibm_phoenix`.\n",
"\n",
"È possibile utilizzare `options` per un ulteriore controllo (facoltativo) sull'invio:\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "a3eaff0a-9c54-4ffc-b6b2-5d43c49e6a07",
"metadata": {},
"outputs": [],
"source": [
"options = {\n",
" \"shots\": 100000,\n",
" \"postprocessing_level\": 1,\n",
" \"transpile_only\": False,\n",
" \"job_tags\": [\"market_split\"],\n",
"}"
]
},
{
"cell_type": "markdown",
"id": "864629a2-34fe-473b-b9f1-277e0a99752d",
"metadata": {},
"source": [
"dove `shots` è un numero intero che specifica il numero di esecuzioni del circuito, `postprocessing_level` determina se al risultato viene applicata una post-elaborazione,\n",
"`transpile_only`specifica se il problema viene solo transpilato in un circuito (e non risolto), e `job_tags` è l'etichetta utilizzata per identificare il job su IBM Quantum® Platform.\n",
"\n",
"Esegui l'ottimizzatore:\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "2c4a5ce3de728746",
"metadata": {},
"outputs": [],
"source": [
"function_job = function.run(\n",
" problem=json_ms_problem,\n",
" variable_type=\"spin\",\n",
" backend_name=\"ibm_phoenix\",\n",
" options=options,\n",
")\n",
"print(f\"Job ID: {function_job.job_id}\")"
]
},
{
"cell_type": "markdown",
"id": "e8e66a1efeef3757",
"metadata": {},
"source": [
"Verifica lo stato dell'attività:\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "be7bbe053da38198",
"metadata": {},
"outputs": [],
"source": [
"# Monitor the job status\n",
"function_job.status()"
]
},
{
"cell_type": "markdown",
"id": "fe4ea9784df0bcbb",
"metadata": {},
"source": [
"Recupera i risultati:\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "9af5dddb30694451",
"metadata": {},
"outputs": [],
"source": [
"# Retrieve the job result if the status is DONE\n",
"result = function_job.result()\n",
"\n",
"result"
]
},
{
"cell_type": "markdown",
"id": "8b888ac0-c0eb-4849-be0d-4bf331707df5",
"metadata": {},
"source": [
"Il risultato ha la forma seguente:\n",
"\n",
"```\n",
"{\n",
" 'solution': {'0': 1, '1': -1, '10': 1, ... },\n",
" 'objective_value': 1.0,\n",
" 'solution_bitstring': '010000011101111011001001110010',\n",
" 'metadata': {\n",
" 'circuit_metrics': {\n",
" 'depth': 309,\n",
" 'gate_count': 3880,\n",
" 'two_qubit_gate_depth': 116,\n",
" 'two_qubit_gate_count': 899,\n",
" 'num_qubits': 30,\n",
" 'operations': {'sx': 1244, 'rz': 1227, 'cz': 899, 'delay': 473, 'measure': 30, 'x': 7},\n",
" },\n",
" 'solver_info': {\n",
" 'variable_mapping': {'0': 0, '1': 1, '10': 2, ... },\n",
" 'bitstring_distributions': {\n",
" 'before_postprocessing': {'011101110010110111001110011000': 1, ...},\n",
" 'after_postprocessing': {'011011110000110101001111011000': 1, ...}\n",
" },\n",
" 'best_parameters': {\n",
" 'beta': [-0.18054534155552715],\n",
" 'gamma': [1.4141236348317905]\n",
" }\n",
" },\n",
" 'resource_usage': {\n",
" 'RUNNING: MAPPING': {'CPU_TIME': 172.936},\n",
" 'RUNNING: OPTIMIZING_FOR_HARDWARE': {'CPU_TIME': 0.272},\n",
" 'RUNNING: WAITING_FOR_QPU': {'CPU_TIME': 7.798},\n",
" 'RUNNING: EXECUTING_QPU': {'QPU_TIME': 30.0},\n",
" 'RUNNING: POST_PROCESSING': {'CPU_TIME': 31.613},\n",
" },\n",
" }\n",
"}\n",
"```\n",
"\n",
"dove il dizionario `solution` corrisponde ai qubit definiti nel problema e fornisce i loro valori di spin ottimizzati.\n",
"`metadata` fornisce informazioni sulla transpilazione (numero di porte a due qubit/profondità, porte utilizzate, qubit attivi) e sui vari tempi di esecuzione.\n",
"\n",
"Nel contesto del problema della suddivisione dei mercati, la stringa di bit della soluzione rappresenta un vettore di assegnazione binario utilizzato per suddividere i mercati in due regioni distinte. Un valore pari a 1 assegna quel\n",
"specifico mercato alla Regione A, mentre un valore pari a 0 lo assegna alla Regione B. Nella soluzione ottimale, la combinazione bilancia la ripartizione, il che significa che entrambe le regioni ricevono esattamente la metà della domanda totale dell’azienda\n",
"per ogni prodotto.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "2cb5785c",
"metadata": {},
"source": [
"\n",
"\n",
"## Passi successivi\n",
"\n",
"\n",
" * Richiedi l'accesso alla funzione compilando questo [modulo](https://parityqc.com/products/parity-twine-optimizer/free-trial).\n",
" * Consulta la documentazione [di riferimento dell'API](/docs/api/functions/parity-twine-optimizer) relativa a questa funzione di Qiskit.\n",
" * Leggi la [guida](/docs/guides/parity-twine-optimizer).\n",
" * Prova il [tutorial](/docs/tutorials/parity-twine-optimizer-sk) sull'applicazione del Parity Twine Optimizer al modello di Sherrington-Kirkpatrick.\n",
" * Si veda il preprint [“Connectivity-aware Synthesis of Quantum Algorithms”, Drier et al. (2025)](https://arxiv.org/abs/2501.14020) ArXiv.\n",
"\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"
}
},
"nbformat": 4,
"nbformat_minor": 5
}