{ "cells": [ { "cell_type": "markdown", "id": "dde95705", "metadata": {}, "source": [ "---\n", "title: \"Ottimizzatore quantistico vincolato - Una funzione Qiskit realizzata da Aqarios\"\n", "description: \"Risolvi problemi di ottimizzazione binaria con vincoli su hardware \\\" IBM Quantum \\\" utilizzando l'algoritmo iterativo QAOA con warm-start e XY-mixer di Aqarios.\"\n", "---\n", "\n", "{/* cspell:ignore Aqarios QOBLIB Bucher docplex forall Zachary quicksum */}\n", "\n", "\n", "\n", "# Ottimizzatore quantistico vincolato - Una funzione Qiskit realizzata da Aqarios\n", "\n", "*Consulta la [guida di riferimento all'API](/docs/api/functions/aqarios-constrained-quantum-optimizer)*\n", "\n", "\n", " Qiskit Functions sono una funzionalità sperimentale disponibile solo per gli utenti dei piani \" IBM Quantum® Premium Plan \", \"Flex Plan\" e \" On-Prem \" (tramite l'API di IBM Quantum Platform ). Sono in fase di anteprima e soggette a modifiche.\n", "\n", "\n", "\n", "\n", "## Panoramica\n", "\n", "Con il Constrained Quantum Optimizer di Aqarios è possibile risolvere problemi di ottimizzazione binaria con vincoli su hardware quant IBM® e senza dover ricorrere alla riformulazione manuale e alla mappatura dei circuiti. È sufficiente fornire il problema sotto forma di file LP, file MPS o [modello Luna](https://docs.aqarios.com/luna-model). La funzione gestisce automaticamente la riformulazione, la sintesi dei circuiti, la transpilazione e l'esecuzione hardware. Il risolutore utilizza il warm-starting iterativo [\\[1\\]](#references) dell'algoritmo [FlexQAOA](https://docs.aqarios.com/luna-solve/algorithms/quantum-gate/flexqaoa/), un'estensione nativa per i vincoli dell'algoritmo di ottimizzazione approssimativa quantistica (QAOA).\n", "\n", "L'ottimizzatore è progettato per risolvere problemi binari con vincoli. In particolare, i vincoli “one-hot” e quelli di “set-packing” possono essere applicati in modo nativo utilizzando i mixer XY. Altri tipi di vincoli vengono automaticamente riformulati come termini di penalità.\n", "\n", "\n", " La funzione risolve solo problemi discreti. Ogni variabile decisionale deve essere binaria oppure un numero intero con un limite inferiore e uno superiore espliciti, in modo da poter essere codificata in qubit. Le variabili continue (a valori reali) non sono supportate: un modello che le contenga viene rifiutato con il codice di errore `4710`.\n", "\n", "\n" ] }, { "cell_type": "markdown", "id": "e9f4110b", "metadata": { "tags": [ "version-info" ] }, "source": [ "\n" ] }, { "cell_type": "markdown", "id": "8bcd63ea", "metadata": {}, "source": [ "\n", "\n", "## Descrizione\n", "\n", "\n", " Le prestazioni possono dipendere sia dall'istanza del problema che dalle fasi di elaborazione successive. In alcuni casi, i campioni classici e quelli generati quantisticamente potrebbero raggiungere una qualità finale simile della soluzione dopo una post-elaborazione equivalente. La valutazione dovrebbe quindi prendere in considerazione l'intero flusso di lavoro di ottimizzazione.\n", "\n", "\n", "Il Constrained Quantum Optimizer implementa l'algoritmo QAOA iterativo con warm-start e XY-mixer (IWS-QAOA) [\\[1\\]](#references). L'algoritmo esegue circuiti QAOA ad angolo fisso su hardware quantistico e aggiorna le probabilità iniziali di \"warm-start\" di ciascun circuito utilizzando i risultati delle misurazioni dell'iterazione precedente. Non è necessario alcun addestramento dei parametri variazionali; si opta invece per una parametrizzazione a rampa lineare fissa.\n", "\n", "Utilizzando i mixer XY per applicare vincoli “one-hot”, è possibile migliorare notevolmente la qualità della soluzione per i problemi con vincoli, poiché lo spazio di ricerca viene praticamente ridotto a un sottospazio fattibile più piccolo — senza che venga introdotta alcuna complessità aggiuntiva, dovuta a termini di penalità, nel panorama di ottimizzazione.\n", "\n", "\n", "\n", "### Flusso di lavoro\n", "\n", "Di seguito viene descritto il flusso di lavoro della funzione:\n", "\n", "1. **Pre-elaborazione** : prima della sintesi del circuito, l'ottimizzatore analizza la struttura dei vincoli del problema in ingresso:\n", " * *Pre-elaborazione dei grafi:* quando il problema lo consente, viene analizzato come un grafo, in cui gli archi determinano la relazione tra le variabili. L'analisi di questo grafico consente di apportare due miglioramenti al problema della pre-elaborazione. In primo luogo, i singoli vincoli possono essere aggregati in un unico grande vincolo mediante la fusione dei clique, in modo da essere rappresentati da un unico XY-mixer. In secondo luogo, le variabili con un solo vicino possono essere fissate in modo deterministico, riducendo così la dimensione e la complessità del problema.\n", " * *Risoluzione dei vincoli:* il preprocessore gestisce ogni vincolo separatamente: se il vincolo è di tipo “one-hot”, può essere applicato tramite XY-mixer. Se si tratta di un vincolo di inserto di insiemi, verrà prima trasformato in un vincolo \"one-hot\". I vincoli di uguaglianza vengono gestiti tramite penalità quadratiche, mentre i vincoli di disuguaglianza tramite [penalizzazione sbilanciata](https://doi.org/10.1088/2058-9565/ad35e4).\n", " * *Derivazione della penalità:* i vincoli che non possono essere espressi come vincoli di uguaglianza one-hot vengono convertiti in termini di penalità. L'ottimizzatore ricava automaticamente l'intensità della penalità dalla struttura del problema.\n", "2. **Avvio a caldo iterativo** : l'ottimizzatore esegue più *catene di avvio a caldo in parallelo*. Ogni catena contiene una distribuzione di probabilità sulle assegnazioni delle variabili, che viene utilizzata come probabilità iniziale del circuito QAOA (stato di avvio a caldo). Ad ogni iterazione, una catena preleva campioni dal circuito quantistico, applica una post-elaborazione classica e aggiorna la propria distribuzione in base alla frequenza di occorrenza dei campioni. Nel corso delle iterazioni, questo approccio concentra la ricerca su soluzioni di alta qualità senza ricorrere a un ciclo di ottimizzazione variazionale.\n", "\n", "Il numero di catene (`num_parallel`), il budget totale di shot per catena (`total_shots`) e il numero di ripetizioni QAOA (`reps`) sono i parametri principali che consentono di bilanciare la qualità della soluzione e il tempo di esecuzione.\n", "\n", "![Diagramma del flusso di lavoro dell'ottimizzatore quantistico vincolato](https://quantum.cloud.ibm.com/docs/images/guides/aqarios-constrained-quantum-optimizer/cqo-diagram.svg)\n", "\n", "\n", "\n", "## Benchmark\n", "\n", "I benchmark riportati di seguito dimostrano che la funzione Qiskit \"Constrained Quantum Optimizer\" è in grado di trovare soluzioni fattibili e di alta qualità a problemi di ottimizzazione vincolata con ben oltre 100 variabili binarie. L'accuratezza è il rapporto tra il valore oggettivo rilevato e il valore ottimale noto. Il tempo di esecuzione corrisponde al tempo effettivo trascorso dall'invocazione della funzione alla restituzione del risultato. L'utilizzo della QPU corrisponde al tempo di calcolo quantistico fatturabile.\n", "\n", "Sono stati esaminati due problemi: il problema [dell’insieme indipendente massimo](/docs/tutorials/find-the-maximum-independent-set-with-aqarios-constrained-quantum-optimizer) (MIS) e il problema del taglio “Max- $k$ ”, che rappresenta un’estensione del ben noto problema del taglio “ MaxCut ” a più di due categorie. Il problema \"Max- $k$ -Cut\" è anche l'equivalente, in termini di ottimizzazione, del problema di colorazione dei grafi (quando tutti gli archi vengono tagliati, il grafo è \" $k$ -colorable\").\n", "\n", "| Problema | Variabili | Vincoli | Qubit | Accuratezza | Fattibilità | Durata totale (s) | Utilizzo della QPU (s) | Tiri totali |\n", "| ------------------------ | --------- | ------- | ----- | ----------- | ----------- | ----------------- | ---------------------- | ----------- |\n", "| MIS es60fst02 | 186 | 280 | 124 | 100.0% | Vero | 940.2 | 147.0 | 25.0k |\n", "| MIS sloane\\_2dc\\_128 | 128 | 5173 | 74 | 100.0% | Vero | 347.6 | 106.0 | 12.5k |\n", "| Max-3-Cut Club di karate | 99 | 33 | 99 | 98.7% | Vero | 279.5 | 166.0 | 25.0k |\n", "| Max-4-Cut Club di karate | 132 | 33 | 132 | 100.0% | Vero | 258.3 | 200.0 | 25.0k |\n", "\n" ] }, { "cell_type": "markdown", "id": "5f761442", "metadata": {}, "source": [ "\n", "\n", "### Note sul benchmark\n", "\n", "* I risultati sopra riportati sono stati ottenuti sul processore `ibm_marrakesh` Heron r2 con le opzioni predefinite e la funzione abilitata `use_session` . Ad esempio `sloane_2dc_128` , `total_shots=12500` è stato utilizzato.\n", "* Il numero ridotto di qubit nelle istanze MIS (74 e 124 rispetto a 128 e 186 variabili) riflette la fissazione delle variabili in fase di pre-elaborazione.\n", "* Le istanze di problema per il MIS sono tratte dalla [Quantum Optimization Benchmarking Library](https://doi.org/10.1038/s43588-026-00991-1). - L'istanza per il problema del taglio Max- $k$ -Cut è il [grafo dello](https://en.wikipedia.org/wiki/Zachary%27s_karate_club) Zachary Karate Club, che ha un numero cromatico pari a 5.\n", "\n" ] }, { "cell_type": "markdown", "id": "73390a19", "metadata": {}, "source": [ "\n", "\n", "## Introduzione\n", "\n", "Questa guida illustra le nozioni di base sull'utilizzo del Constrained Quantum Optimizer, spiegando come caricare la funzione ed eseguire semplici problemi. Per un tutorial più approfondito, consulta \" [Come trovare l'insieme indipendente massimo con l'ottimizzatore quantistico con vincoli di Aqarios](/docs/tutorials/find-the-maximum-independent-set-with-aqarios-constrained-quantum-optimizer) \".\n", "\n", "Effettua l'autenticazione utilizzando la tua chiave API di IBM Quantum e l'istanza CRN, quindi carica la funzione dal catalogo.\n", "\n", "\n", " Il codice riportato di seguito presuppone che tu abbia salvato le tue credenziali. Per configurarle, segui le istruzioni riportate nella sezione “[Salva le credenziali del tuo account IBM Cloud](/docs/guides/functions-get-started#install-qiskit-functions-catalog-client) ”.\n", "\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "95a715d2", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[QiskitFunction(aqarios/constrained-quantum-optimizer)]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from qiskit_ibm_catalog import QiskitFunctionsCatalog\n", "\n", "catalog = QiskitFunctionsCatalog(channel=\"ibm_quantum_platform\")\n", "\n", "# Verify that you have access to the function\n", "catalog.list()" ] }, { "cell_type": "code", "execution_count": null, "id": "fe865158", "metadata": {}, "outputs": [], "source": [ "# Load the function\n", "optimizer = catalog.load(\"aqarios/constrained-quantum-optimizer\")" ] }, { "cell_type": "code", "execution_count": 3, "id": "d976e101", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[,\n", " ,\n", " ,\n", " ,\n", " ,\n", " ,\n", " ]" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Check the list of backends you have access to\n", "catalog.backends()" ] }, { "cell_type": "code", "execution_count": 4, "id": "6b0f5c79", "metadata": {}, "outputs": [], "source": [ "# Select the backend you want to use\n", "backend = catalog.backend(\"ibm_phoenix\")" ] }, { "cell_type": "markdown", "id": "e4445979", "metadata": {}, "source": [ "\n", "\n", "## Esempio 1: Un semplice problema con vincoli\n", "\n", "Il primo esempio illustra come utilizzare la funzione con [i file LP](https://www.ibm.com/docs/icos/22.1.1?topic=cplex-lp-file-format-algebraic-representation), una specifica comune per i problemi di ottimizzazione utilizzata nella ricerca operativa. Dovrete formulare il seguente problema di ottimizzazione arbitrario con cinque variabili binarie $x_i \\in \\{0,1\\}$, soggetto a due vincoli:\n", "\n", "$$\n", " \\min x_1 x_2 + 2 x_2 x_3 - x_3 x_4 - 2 x_4 x_5 - 2 x_1 x_3 - 4 x_2 x_5 \\\\\n", " \\text{s.t.}\\quad x_1 + x_2 + x_3 \\leq 1 \\\\\n", " \\quad x_3 - x_4 + x_5 = 0\n", "$$\n", "\n", "\n", "\n", "### 1. Formulare il problema\n", "\n", "Esprimere direttamente l'espressione matematica nel seguente formato LP-string:\n", "\n" ] }, { "cell_type": "code", "execution_count": 5, "id": "7c3af25d", "metadata": { "lines_to_next_cell": 0 }, "outputs": [], "source": [ "lp_str = \"\"\"\\\\Problem name: Example\n", "Minimize\n", " obj: [ 2 x_1 x_2 + 4 x_2 x_3 - 2 x_3 x_4 - 4 x_4 x_5 - 4 x_1 x_3 - 8 x_2 x_5 ] / 2\n", "Subject To\n", " c1: x_1 + x_2 + x_3 <= 1\n", " c2: x_3 - x_4 + x_5 = 0\n", "Binaries\n", " x_1 x_2 x_3 x_4 x_5\n", "End\n", "\"\"\"" ] }, { "cell_type": "markdown", "id": "f6c75f9d", "metadata": {}, "source": [ "Si noti che `[...] / 2` è una notazione obbligatoria per gli obiettivi quadratici secondo lo standard LP.\n", "\n" ] }, { "cell_type": "markdown", "id": "003a933c", "metadata": {}, "source": [ "\n", "\n", "### 2. Eseguire l'ottimizzatore\n", "\n", "Risolvi il problema con l’ottimizzatore.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "242f1f89", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Job ID: 2e06a3a8-7c29-4c76-94d7-194293363f4a\n" ] } ], "source": [ "# Set up low-resource options for the simple problem\n", "options = {\"total_shots\": 2000, \"num_parallel\": 5, \"use_session\": True}\n", "\n", "# Dispatch the job\n", "job_1 = optimizer.run(\n", " problem=lp_str, backend_name=backend.name, options=options\n", ")\n", "\n", "print(f\"Job ID: {job_1.job_id}\")" ] }, { "cell_type": "code", "execution_count": 7, "id": "4bd4790a", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'RUNNING: WAITING_FOR_QPU'" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Monitor the job status\n", "job_1.status()" ] }, { "cell_type": "markdown", "id": "acff0671", "metadata": { "lines_to_next_cell": 0 }, "source": [ "\n", "\n", "### 3. Recuperare il risultato\n", "\n", "La soluzione, che mette in corrispondenza i nomi delle variabili con le assegnazioni associate, è fornita dal risultato.\n", "\n" ] }, { "cell_type": "code", "execution_count": 8, "id": "6a121188", "metadata": { "lines_to_next_cell": 0 }, "outputs": [ { "data": { "text/plain": [ "{'solutions': [{'x_1': 0, 'x_2': 1, 'x_3': 0, 'x_4': 1, 'x_5': 1}],\n", " 'solution_bitstrings': ['01011'],\n", " 'raw_energy': -6.0,\n", " 'objective_value': -6.0,\n", " 'feasible': True,\n", " 'metadata': {'resource_usage': {'RUNNING: MAPPING': {'CPU': 5.405},\n", " 'RUNNING: OPTIMIZING_FOR_HARDWARE': {'CPU': 9.902},\n", " 'RUNNING: WAITING_FOR_QPU': {'CPU': 25.456},\n", " 'RUNNING: EXECUTING_QPU': {'CPU': 25.202},\n", " 'RUNNING: POST_PROCESSING': {'CPU': 6.481}},\n", " 'circuit_metrics': {'before_transpilation': {'num_qubits': 6,\n", " 'gate_count': 42,\n", " 'depth': 15,\n", " 'two_qubit_gate_count': 12,\n", " 'two_qubit_gate_depth': 7,\n", " 'operations': {'rz': 12,\n", " 'p': 8,\n", " 'ry': 7,\n", " 'rzz': 4,\n", " 'cx': 3,\n", " 'xx_plus_yy': 3,\n", " 'global_phase': 2,\n", " 'cry': 2,\n", " 'x': 1}},\n", " 'after_transpilation': {'num_qubits': 6,\n", " 'gate_count': 254,\n", " 'depth': 100,\n", " 'two_qubit_gate_count': 48,\n", " 'two_qubit_gate_depth': 33,\n", " 'operations': {'rz': 78, 'sx': 122, 'cz': 48, 'measure': 6, 'x': 0}}},\n", " 'solver_info': {'variable_mapping': {'x_1': 0,\n", " 'x_2': 1,\n", " 'x_3': 2,\n", " 'x_4': 3,\n", " 'x_5': 4}}}}" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "result = job_1.result()\n", "\n", "result" ] }, { "cell_type": "markdown", "id": "e8837f5f", "metadata": {}, "source": [ "Il `solutions` campo nel dizionario di ritorno contiene tutte le soluzioni ottimali degenerate individuate, sotto forma di dizionari che associano ciascun nome di variabile al suo valore. Le stesse soluzioni vengono restituite anche come stringhe di bit in `solution_bitstrings`; `metadata.solver_info.variable_mapping` indica a quale posizione di carattere di una stringa di bit corrisponde ciascuna variabile. Oltre ai dati relativi alla soluzione, `metadata` vengono forniti il `objective_value`, un flag `feasible` e ulteriori.\n", "\n", "\n", "\n", "## Esempio 2: Insieme indipendente massimo\n", "\n", "Il problema dell'insieme indipendente massimo (MIS) consiste nell'individuare il più grande sottoinsieme di vertici in un grafo tale che nessun paio di vertici all'interno del sottoinsieme sia collegato da un arco. Questo esempio risolve il problema MIS su un grafo regolare a 12 nodi. Per ulteriori informazioni sul problema e per un esempio più dettagliato, consulta il [tutorial](/docs/tutorials/find-the-maximum-independent-set-with-aqarios-constrained-quantum-optimizer).\n", "\n", "Il problema è stato creato con [qiskit-addon-opt-mapper](https://github.com/qiskit/qiskit-addon-opt-mapper).\n", "Se necessario, installa i pacchetti richiesti:\n", "\n" ] }, { "cell_type": "code", "execution_count": 5, "id": "a1e2f301", "metadata": {}, "outputs": [], "source": [ "# %pip install networkx qiskit-addon-opt-mapper" ] }, { "cell_type": "markdown", "id": "d56e1440", "metadata": {}, "source": [ "\n", "\n", "### Fase 1: Definire il problema\n", "\n", "Costruire un grafo regolare a 3 spigoli scelto a caso e definire il problema di ottimizzazione MIS. Ogni nodo del grafo diventa una variabile binaria e ogni arco introduce un vincolo che garantisce che venga selezionato al massimo un estremo.\n", "\n" ] }, { "cell_type": "code", "execution_count": 9, "id": "03998691", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\\ This file has been generated by DOcplex\n", "\\ ENCODING=ISO-8859-1\n", "\\Problem name: Independent set\n", "\n", "Maximize\n", " obj: x_0 + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 + x_10 + x_11\n", "Subject To\n", " c0: x_0 + x_4 <= 1\n", " c1: x_0 + x_9 <= 1\n", " c2: x_0 + x_8 <= 1\n", " c3: x_1 + x_2 <= 1\n", " c4: x_1 + x_7 <= 1\n", " c5: x_1 + x_3 <= 1\n", " c6: x_2 + x_4 <= 1\n", " c7: x_2 + x_11 <= 1\n", " c8: x_3 + x_10 <= 1\n", " c9: x_3 + x_11 <= 1\n", " c10: x_4 + x_5 <= 1\n", " c11: x_5 + x_10 <= 1\n", " c12: x_5 + x_6 <= 1\n", " c13: x_6 + x_8 <= 1\n", " c14: x_6 + x_7 <= 1\n", " c15: x_7 + x_9 <= 1\n", " c16: x_8 + x_11 <= 1\n", " c17: x_9 + x_10 <= 1\n", "\n", "Bounds\n", " 0 <= x_0 <= 1\n", " 0 <= x_1 <= 1\n", " 0 <= x_2 <= 1\n", " 0 <= x_3 <= 1\n", " 0 <= x_4 <= 1\n", " 0 <= x_5 <= 1\n", " 0 <= x_6 <= 1\n", " 0 <= x_7 <= 1\n", " 0 <= x_8 <= 1\n", " 0 <= x_9 <= 1\n", " 0 <= x_10 <= 1\n", " 0 <= x_11 <= 1\n", "\n", "Binaries\n", " x_0 x_1 x_2 x_3 x_4 x_5 x_6 x_7 x_8 x_9 x_10 x_11\n", "End\n", "\n" ] } ], "source": [ "import networkx as nx\n", "from qiskit_addon_opt_mapper.applications import IndependentSet\n", "from qiskit_addon_opt_mapper.translators import to_docplex_mp\n", "\n", "# 12-node random 3-regular graph\n", "G = nx.random_regular_graph(3, 12, seed=7)\n", "\n", "# Build MIS problem and export as LP string\n", "mis = IndependentSet(G)\n", "mis_problem = mis.to_optimization_problem()\n", "lp_str = to_docplex_mp(mis_problem).export_as_lp_string()\n", "\n", "print(lp_str)" ] }, { "cell_type": "markdown", "id": "e6f7a8b9", "metadata": { "lines_to_next_cell": 0 }, "source": [ "\n", "\n", "### Fase 2: Eseguire l'ottimizzatore\n", "\n", "Risolvi il problema con l’ottimizzatore.\n", "\n" ] }, { "cell_type": "code", "execution_count": 10, "id": "04236c83", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Job ID: f041431c-b42e-4627-afe5-522fea61faf6\n" ] } ], "source": [ "options = {\"total_shots\": 2000, \"use_session\": True}\n", "\n", "# Dispatch the job\n", "job_2 = optimizer.run(\n", " problem=lp_str, backend_name=backend.name, options=options\n", ")\n", "\n", "print(f\"Job ID: {job_2.job_id}\")" ] }, { "cell_type": "code", "execution_count": 11, "id": "079ebc2f", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'QUEUED'" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Monitor the job status\n", "job_2.status()" ] }, { "cell_type": "markdown", "id": "90c6de7c", "metadata": {}, "source": [ "\n", "\n", "### Fase 3: Acquisizione e interpretazione dei risultati\n", "\n", "Infine, recuperiamo la soluzione e ne verifichiamo la correttezza.\n", "\n" ] }, { "cell_type": "code", "execution_count": 12, "id": "f1a2b3c4", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Feasible: True\n", "Independent set size: 5\n", "Selected nodes: [1, 4, 6, 9, 11]\n", "Edge conflicts: []\n" ] } ], "source": [ "result = job_2.result()\n", "\n", "print(f\"Feasible: {result['feasible']}\")\n", "print(f\"Independent set size: {int(result['objective_value'])}\")\n", "\n", "# Extract the selected nodes\n", "solution = result[\"solutions\"][0]\n", "independent_set = [\n", " int(k.split(\"_\")[1]) for k, v in solution.items() if v == 1\n", "]\n", "print(f\"Selected nodes: {sorted(independent_set)}\")\n", "\n", "# Verify no two selected nodes share an edge\n", "conflicts = [\n", " (u, v)\n", " for u, v in G.edges()\n", " if u in independent_set and v in independent_set\n", "]\n", "print(f\"Edge conflicts: {conflicts}\")" ] }, { "cell_type": "markdown", "id": "a2b3c4d5", "metadata": {}, "source": [ "\n", "\n", "## Esempio 3: Colorazione di grafi a 3 colori ( Max-3-Cut )\n", "\n", "Il problema “Max- $k$ -Cut” suddivide i vertici di un grafo in gruppi “ $k$ ” in modo da massimizzare il numero di archi i cui estremi appartengono a gruppi diversi. Per $k = 3$ ciò equivale a trovare una colorazione a 3 colori che massimizzi il numero di spigoli di colore incrociato.\n", "\n", "Formalmente, si assegna a ciascun nodo $i \\in V$ uno dei gruppi $k$ con variabili binarie $x_{i,c}$ per il colore $c \\in \\{1, \\ldots, k\\}$. Il vincolo \"one-hot\" $\\sum_c x_{i,c} = 1$ per ciascun nodo garantisce un’assegnazione univoca. L'obiettivo massimizza i bordi tra i gruppi:\n", "\n", "$$\n", "\\min \\sum_{(u,v) \\in E} \\sum_c x_{u,c} \\, x_{v,c}\\\\\n", "\\text{s.t.} \\sum_{c} x_{i,c} = 1 \\quad \\forall i \\in V\n", "$$\n", "\n", "I vincoli \"one-hot\" sono ideali per i mixer XY, che l'ottimizzatore gestisce in modo nativo.\n", "\n", "In questo esempio viene utilizzato il [grafico dello](https://en.wikipedia.org/wiki/Zachary%27s_karate_club) Zachary Karate Club (34 nodi, 78 archi) e il modello viene costruito con [Luna Model](https://docs.aqarios.com/luna-model/).\n", "Se necessario, installa i pacchetti richiesti:\n", "\n" ] }, { "cell_type": "code", "execution_count": 9, "id": "b3c4d5e6", "metadata": {}, "outputs": [], "source": [ "# %pip install networkx matplotlib luna-model" ] }, { "cell_type": "markdown", "id": "c4d5e6f7", "metadata": {}, "source": [ "\n", "\n", "### Fase 1: Definire il problema\n", "\n", "Per prima cosa, generare le variabili binarie con il pacchetto `luna-model` . Quindi, definire l'obiettivo e aggiungere i vincoli al modello.\n", "\n" ] }, { "cell_type": "code", "execution_count": 13, "id": "d5e6f7a8", "metadata": {}, "outputs": [], "source": [ "import networkx as nx\n", "from luna_model import Model, quicksum\n", "\n", "k = 3\n", "G = nx.karate_club_graph()\n", "\n", "# Instantiate the Model object\n", "model = Model(name=\"Max-3-Cut\")\n", "\n", "# Add binary variables\n", "x = model.add_variables(\"x\", shape=(G.number_of_nodes(), k))\n", "\n", "# Add the objective by using the numpy dot abstraction\n", "model.objective = quicksum(x[i].dot(x[j]) for i, j in G.edges)\n", "\n", "# Bulk-add the one-hot constraints\n", "model.add_constraints(x.sum(axis=1) == 1)\n", "\n", "# Encode the model to send via API\n", "model_enc = model.encode_b64()" ] }, { "cell_type": "markdown", "id": "263ccb5d", "metadata": { "lines_to_next_cell": 0 }, "source": [ "\n", "\n", "### Fase 2: Eseguire l'ottimizzatore\n", "\n", "Risolvi il problema con l’ottimizzatore.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "f7a8b9c0", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Job ID: df911d83-9df7-44a1-bfad-5d66e08676c3\n" ] } ], "source": [ "options = {\"use_session\": True}\n", "\n", "# Dispatch the job\n", "job_3 = optimizer.run(\n", " problem=model_enc, backend_name=backend.name, options=options\n", ")\n", "\n", "print(f\"Job ID: {job_3.job_id}\")" ] }, { "cell_type": "code", "execution_count": 15, "id": "e2ff9b51", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'RUNNING: WAITING_FOR_QPU'" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Monitor the job status\n", "job_3.status()" ] }, { "cell_type": "markdown", "id": "a8b9c0d1", "metadata": {}, "source": [ "\n", "\n", "### Fase 3: Recupero e visualizzazione dei risultati\n", "\n", "Recuperare e visualizzare i risultati.\n", "\n" ] }, { "cell_type": "code", "execution_count": 16, "id": "b9c0d1e2", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Feasible: True\n", "Violations: 4\n" ] }, { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "result = job_3.result()\n", "solution = result[\"solutions\"][0]\n", "\n", "# Map each node to its assigned color group\n", "node_group = {}\n", "for i in G.nodes:\n", " for c in range(k):\n", " if solution[f\"x{i},{c}\"] == 1:\n", " node_group[i] = c\n", "\n", "print(f\"Feasible: {result['feasible']}\")\n", "print(f\"Violations: {int(result['objective_value'])}\")\n", "\n", "# Visualize the partition\n", "colors = [\"tab:blue\", \"tab:orange\", \"tab:green\"]\n", "node_colors = [colors[node_group[i]] for i in G.nodes()]\n", "nx.draw(G, nx.kamada_kawai_layout(G), node_color=node_colors, node_size=200)" ] }, { "cell_type": "markdown", "id": "3f1a7c02", "metadata": {}, "source": [ "\n", "\n", "## Changelog\n", "\n", "\n", "\n", "### \\[0.4.0] - 22 settembre 2026\n", "\n", "**Modifiche sostanziali**\n", "\n", "* Il parametro di input è stato rinominato `model` in `problem`.\n", "* Ho rinominato il campo di output `obj_value` in `objective_value`.\n", "* L'opzione `postprocessing` è stata sostituita con `postprocessing_level`, che accetta un numero intero compreso nell'intervallo `[0, 3]` anziché una stringa. I valori precedenti corrispondono a `\"off\"` -> `0`, `\"weak\"` -> `1`, `\"medium\"` -> e `\"strong\"` -> `2``3`, mentre il valore predefinito rimane invariato a `3`.\n", "* Ristrutturato `metadata.circuit_metrics`. Ora riporta `num_qubits`, `gate_count`, `depth`, `two_qubit_gate_count`, `two_qubit_gate_depth`, e `operations` separatamente per `before_transpilation` e `after_transpilation`, invece di un unico dizionario piatto contenente i conteggi medi dei gate. Il campo viene compilato quando `None` il problema è stato risolto durante la pre-elaborazione e non è stato eseguito alcun circuito (codice di errore `4712`).\n", "\n", "**Funzioni**\n", "\n", "* È stata aggiunta l'opzione `seed_transpiler` per rendere la sintesi e il routing dei circuiti riproducibili tra un'esecuzione e l'altra.\n", "* È stata aggiunta l'opzione `job_tags` che consente di associare tag personalizzati a ogni processo Qiskit Runtime inviato dalla funzione.\n", "* È stato aggiunto il campo di output `solution_bitstrings`, che restituisce le stesse soluzioni in `solutions` formato stringa di bit.\n", "* Aggiunto `metadata.solver_info.variable_mapping`, che associa ogni nome di variabile alla sua posizione in termini di caratteri nelle voci di `solution_bitstrings`.\n", "\n", "**Documentazione**\n", "\n", "* È stato documentato che le variabili continue (a valori reali) non sono supportate e che le variabili intere richiedono limiti espliciti. Tali modelli generano un errore con il codice `4710`.\n", "\n" ] }, { "cell_type": "markdown", "id": "e9ec2e67", "metadata": {}, "source": [ "\n", "\n", "## Ottenere supporto\n", "\n", "Per domande o problemi, contatta [support@aqarios.com](mailto:support@aqarios.com) indicando il numero di riferimento del lavoro.\n", "\n" ] }, { "cell_type": "markdown", "id": "5a6a25c8", "metadata": { "jp-MarkdownHeadingCollapsed": true }, "source": [ "\n", "\n", "## Passi successivi\n", "\n", "\n", " * [Richiedi l'accesso al Constrained Quantum Optimizer di Aqarios](https://aqarios.com/qiskit-function-access/).\n", " * Consulta la [guida di riferimento dell'API](/docs/api/functions/aqarios-constrained-quantum-optimizer) per la documentazione completa sui parametri e sui risultati.\n", " * Prova il tutorial \" [Trova l'insieme indipendente massimo con l'ottimizzatore quantistico con vincoli Aqarios](/docs/tutorials/find-the-maximum-independent-set-with-aqarios-constrained-quantum-optimizer)\" per approfondire un'istanza reale del benchmark QOBLIB.\n", " * Si veda la pubblicazione “[Ottimizzazione quantistica vincolata tramite XY-Mixer iterativi con Warm-Start](https://doi.org/10.1088/1367-2630/ae8ea2) ”.\n", "\n", "\n" ] }, { "cell_type": "markdown", "id": "6c0a20cb", "metadata": {}, "source": [ "\n", "\n", "## Riferimenti\n", "\n", "1. Bucher et al. (2026), \\*Ottimizzazione quantistica vincolata tramite XY-Mixer iterativi con Warm-Start \\*[10.1088/1367-2630/ae8ea2](https://doi.org/10.1088/1367-2630/ae8ea2)\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 }