{ "cells": [ { "cell_type": "markdown", "id": "1a869c2d-ae51-47d3-8a41-bfcf5e505f59", "metadata": {}, "source": [ "---\n", "title: \"Tecniche avanzate per QAOA\"\n", "description: \"Questo notebook introduce tecniche avanzate per migliorare le prestazioni dell'algoritmo di ottimizzazione approssimativa quantistica (QAOA) con un numero elevato di qubit.\"\n", "---\n", "\n", "{/* cspell:ignore pysat, lbrack, frameon, IEICE */}\n", "\n", "\n", "\n", "# Tecniche avanzate per QAOA\n", "\n", "*Stima di utilizzo: 3 minuti su un processore r2 Heron (NOTA: si tratta solo di una stima. Il tempo di esecuzione può variare.)*\n", "\n" ] }, { "cell_type": "markdown", "id": "1a6bbeef-966f-45e1-89aa-e964ef891eeb", "metadata": {}, "source": [ "\n", "\n", "## Prerequisiti\n", "\n", "Gli utenti dovrebbero avere familiarità con i fondamenti dell'algoritmo di ottimizzazione approssimativa quantistica (QAOA). Per un'introduzione al QAOA, consulta le seguenti risorse:\n", "\n", "* Tutorial su come [risolvere problemi di ottimizzazione quantistica su scala industriale](/docs/tutorials/quantum-approximate-optimization-algorithm)\n", "* La lezione [sul QAOA su](/learning/courses/quantum-computing-in-practice/utility-scale-qaoa#utility-scale-qaoa) scala industriale (parte del corso \"[Il calcolo](/learning/courses/quantum-computing-in-practice) quantistico nella pratica\") su IBM Quantum® Learning\n", "\n", "\n", "\n", "## Risultati di apprendimento\n", "\n", "Dopo aver seguito questo tutorial, gli utenti dovrebbero essere in grado di:\n", "\n", "* Utilizzare tecniche avanzate che contribuiscano a migliorare la traslazione QAOA e forniscano strumenti per ottimizzarne le prestazioni\n", "\n", "Per una guida dettagliata ai contenuti di questo tutorial, guarda questo [video su Qiskit](https://youtu.be/rBfK-l-qSNk?si=PC28gFAdu4JYSYdk).\n", "\n" ] }, { "cell_type": "markdown", "id": "ea97567d-810f-4cca-8edf-a47d70ea870a", "metadata": {}, "source": [ "\n", "\n", "## Sfondo\n", "\n", "Questo tutorial presenta due tecniche avanzate per migliorare le prestazioni **dell** 'algoritmo di ottimizzazione approssimativa quantistica (QAOA) in presenza di un numero elevato di qubit.\n", "\n", "Le tecniche avanzate contenute in questo quaderno comprendono:\n", "\n", "* **Strategia SWAP con mappatura iniziale SAT** : si tratta di un passaggio del transpiler progettato specificamente per il QAOA che utilizza congiuntamente una strategia SWAP e un risolutore SAT per migliorare la selezione dei qubit fisici da impiegare sulla QPU. La strategia SWAP sfrutta la commutatività degli operatori QAOA per riorganizzare i gate in modo che gli strati di gate SWAP possano essere eseguiti simultaneamente, riducendo così la profondità del circuito [\\[1\\]](#references). Il risolutore SAT viene utilizzato per individuare una mappatura iniziale che riduca al minimo il numero di operazioni SWAP necessarie per mappare i qubit del circuito sui qubit fisici presenti sul dispositivo [\\[2\\]](#references).\n", "* **CVaR funzione di costo** : in genere, come funzione di costo per il QAOA viene utilizzato il valore atteso dell'Hamiltoniano di costo; tuttavia, come dimostrato in [\\[3\\]](#references), concentrarsi sulla coda della distribuzione, anziché sul valore atteso, può migliorare le prestazioni del QAOA nei problemi di ottimizzazione combinatoria. L' CVaR e permette di ottenere questo risultato. Per un dato insieme di soluzioni con i corrispondenti valori oggettivi del problema di ottimizzazione in esame, il valore a rischio condizionato ( CVaR ) con un livello di confidenza dell' $\\alpha \\in [0, 1]$ e è definito come la media delle soluzioni migliori dell' $\\alpha$ [\\[3\\]](#references).\n", " Pertanto, $\\alpha = 1$ corrisponde al valore atteso standard, mentre $\\alpha=0$ corrisponde al minimo tra gli scatti disponibili, e $\\alpha \\in (0, 1)$ rappresenta un compromesso tra la ricerca degli scatti migliori e l'applicazione di una media per uniformare il panorama di ottimizzazione. Inoltre, l' CVaR e può essere utilizzato come tecnica di mitigazione degli errori per migliorare la qualità della stima del valore oggettivo [\\[4\\]](#references).\n", "\n", "Al termine di questo tutorial, dovresti essere in grado di utilizzare queste tecniche per ottenere i migliori risultati dall'esecuzione di QAOA per i tuoi problemi di ottimizzazione.\n", "\n" ] }, { "cell_type": "markdown", "id": "40fb546e-85e0-450b-a5ea-5d08950d129f", "metadata": {}, "source": [ "\n", "\n", "## Requisiti\n", "\n", "Prima di iniziare questa esercitazione, assicuratevi di aver installato quanto segue:\n", "\n", "* Qiskit SDK v2.0 o versioni successive, con supporto [alla visualizzazione](/docs/api/qiskit/visualization)\n", "* v0.43Qiskit Runtime o successivamente (`pip install qiskit-ibm-runtime`)\n", "* Libreria grafica Rustworkx (`pip install rustworkx`)\n", "* Python SAT (`pip install python-sat`)\n", "\n" ] }, { "cell_type": "markdown", "id": "50285e5f-1a7b-471c-a223-1ae0af19d9ed", "metadata": {}, "source": [ "\n", "\n", "## Configura\n", "\n" ] }, { "cell_type": "code", "execution_count": 91, "id": "d019ea68-61e0-4341-84c7-e612ca10dde7", "metadata": {}, "outputs": [], "source": [ "from __future__ import annotations\n", "\n", "import numpy as np\n", "import rustworkx as rx\n", "from dataclasses import dataclass\n", "from itertools import combinations\n", "from threading import Timer\n", "from collections.abc import Callable, Iterable\n", "from pysat.formula import CNF, IDPool\n", "from pysat.solvers import Solver\n", "from scipy.optimize import minimize\n", "from rustworkx.visualization import mpl_draw as draw_graph\n", "\n", "from qiskit.quantum_info import SparsePauliOp\n", "from qiskit.circuit.library import QAOAAnsatz\n", "from qiskit.circuit import QuantumCircuit, ParameterVector\n", "from qiskit.transpiler import CouplingMap, PassManager\n", "from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager\n", "from qiskit.transpiler.passes.routing.commuting_2q_gate_routing import (\n", " SwapStrategy,\n", " FindCommutingPauliEvolutions,\n", " Commuting2qGateRouter,\n", ")\n", "\n", "from qiskit_ibm_runtime import QiskitRuntimeService, Session\n", "from qiskit_ibm_runtime import SamplerV2 as Sampler" ] }, { "cell_type": "markdown", "id": "8b77b0c9-f5a6-476e-86b8-069ba14f9ab3", "metadata": {}, "source": [ "\n", "\n", "### Problema del taglio massimo\n", "\n", "Proviamo a risolvere il problema **del taglio massimo** su un grafo con 100 nodi utilizzando il metodo QAOA.\n", "Il problema del taglio massimo è un problema di ottimizzazione combinatoria definito su un grafo $G = (V, E)$, dove $V$ è l'insieme dei vertici e $E$ è l'insieme dei bordi. L'obiettivo è quello di suddividere i vertici in due insiemi, $S$ e $V \\setminus S$, in modo tale da massimizzare il numero di spigoli tra i due insiemi.\n", "In questo esempio utilizziamo un grafico con 100 nodi basato su una mappa di accoppiamento hardware.\n", "\n" ] }, { "cell_type": "markdown", "id": "663d13f5-a5f7-4b67-a89b-26deb41224ec", "metadata": {}, "source": [ "\n", "\n", "## Esempio di simulatore su piccola scala\n", "\n", "Poiché l'obiettivo di questo tutorial è mostrare le prestazioni di QAOA su scale che vanno oltre quelle gestibili da un simulatore, salteremo questo passaggio.\n", "\n", "Se desideri provare un flusso di lavoro QAOA basato su un simulatore, dai un'occhiata al tutorial [sull'algoritmo di ottimizzazione approssimativa quantistica](/docs/tutorials/quantum-approximate-optimization-algorithm).\n", "\n" ] }, { "cell_type": "markdown", "id": "6ca05a7c-5fde-4485-a3ad-c0ba02844e50", "metadata": {}, "source": [ "\n", "\n", "## Esempio di hardware su larga scala\n", "\n" ] }, { "cell_type": "markdown", "id": "b825afbf-10fd-4926-bd65-05272044f107", "metadata": {}, "source": [ "\n", "\n", "### Fase 1: mappare gli input classici su un problema quantistico\n", "\n", "\n", "\n", "#### Grafico → Hamiltoniano\n", "\n", "Per prima cosa, trasponi il problema in un circuito quantistico adatto al QAOA. Maggiori dettagli su questa procedura sono disponibili nel [tutorial](/docs/tutorials/quantum-approximate-optimization-algorithm) introduttivo al QAOA.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "8c25db38-5f36-4a39-bdde-4f83616a6dde", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n" ] } ], "source": [ "# Instantiate runtime to access backend\n", "service = QiskitRuntimeService()\n", "backend = service.least_busy(\n", " min_num_qubits=100, operational=True, simulator=False\n", ")\n", "print(backend)" ] }, { "cell_type": "code", "execution_count": null, "id": "e04ce982-8294-4ebe-8dcc-f74205938800", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 96, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Check if the coupling map is symmetric. We will add a conditional below\n", "# to avoid over-counting edges for symmetric/bi-directional coupling maps.\n", "\n", "backend.coupling_map.is_symmetric" ] }, { "cell_type": "code", "execution_count": null, "id": "8b864d32-9483-45ea-831f-60488e330adb", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "n = 100\n", "graph_100 = rx.PyGraph()\n", "graph_100.add_nodes_from((np.arange(0, n, 1)))\n", "w = 1.0\n", "elist = []\n", "\n", "for edge in backend.coupling_map:\n", " if (edge[0] < n) and (edge[1] < n):\n", " # Conditional to avoid over-counting edges\n", " if (\n", " edge[1],\n", " edge[0],\n", " w,\n", " ) not in elist:\n", " elist.append((edge[0], edge[1], w))\n", "\n", "graph_100.add_edges_from(elist)\n", "draw_graph(graph_100, with_labels=True)" ] }, { "cell_type": "code", "execution_count": 98, "id": "e39c4e42-ce97-4a04-8879-da4d33a684bc", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Cost Function Hamiltonian: SparsePauliOp(['IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZ', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZI', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIZIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIZIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIZIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIZIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIZIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIZIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIZIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIZIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIZIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIZIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIZIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIZIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIZIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIZIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIZIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IZIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'ZIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII'],\n", " coeffs=[1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n", " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n", " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n", " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n", " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n", " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n", " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n", " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n", " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n", " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n", " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n", " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n", " 1.+0.j, 1.+0.j, 1.+0.j])\n" ] } ], "source": [ "# Construct cost hamiltonian\n", "\n", "\n", "def build_max_cut_paulis(graph: rx.PyGraph) -> list[tuple[str, float]]:\n", " \"\"\"Convert the graph to Pauli list.\n", "\n", " This function does the inverse of `build_max_cut_graph`\n", " \"\"\"\n", " pauli_list = []\n", " for edge in list(graph.edge_list()):\n", " paulis = [\"I\"] * len(graph)\n", " paulis[edge[0]], paulis[edge[1]] = \"Z\", \"Z\"\n", "\n", " weight = graph.get_edge_data(edge[0], edge[1])\n", "\n", " pauli_list.append((\"\".join(paulis)[::-1], weight))\n", "\n", " return pauli_list\n", "\n", "\n", "max_cut_paulis = build_max_cut_paulis(graph_100)\n", "\n", "cost_hamiltonian = SparsePauliOp.from_list(max_cut_paulis)\n", "print(\"Cost Function Hamiltonian:\", cost_hamiltonian)" ] }, { "cell_type": "markdown", "id": "4e576068-53e7-4a06-a83b-87e95de141e9", "metadata": {}, "source": [ "\n", "\n", "### Fase 2: Ottimizzazione del problema per l'esecuzione su hardware quantistico\n", "\n", "\n", "\n", "#### Strategia SWAP con mappatura iniziale SAT\n", "\n", "Dimostreremo come costruire e ottimizzare i circuiti QAOA utilizzando la **strategia SWAP con mappatura iniziale SAT**, un passaggio di transpiler specificamente progettato per QAOA applicato a problemi quadratici.\n", "\n", "In questo esempio, scegliamo una strategia di inserimento SWAP per blocchi di porte a due qubit commutanti, che applica livelli di porte SWAP eseguibili simultaneamente sulla mappa di accoppiamento. Questa strategia è presentata in [\\[1\\]](#references) e viene passata a `Commuting2qGateRouter`, che è esposto come un passaggio transpiler Qiskit standardizzato (vedi [`Commuting2qGateRouter`](/docs/api/qiskit/qiskit.transpiler.passes.Commuting2qGateRouter)). In questo esempio utilizziamo una strategia di scambio di linee.\n", "\n" ] }, { "cell_type": "code", "execution_count": 99, "id": "7c54402a-7696-4b0e-826a-6e0ac4c54395", "metadata": {}, "outputs": [], "source": [ "# Extract longest path with no repeated nodes\n", "nodes = rx.longest_simple_path(graph_100)\n", "\n", "# Collect even edges and odd edges\n", "even_edges = [\n", " (nodes[i], nodes[i + 1])\n", " if nodes[i] < nodes[i + 1]\n", " else (nodes[i + 1], nodes[i])\n", " for i in range(0, len(nodes) - 1, 2)\n", "]\n", "odd_edges = [\n", " (nodes[i], nodes[i + 1])\n", " if nodes[i] < nodes[i + 1]\n", " else (nodes[i + 1], nodes[i])\n", " for i in range(1, len(nodes) - 1, 2)\n", "]\n", "edge_list = [\n", " (edge[0], edge[1]) if edge[0] < edge[1] else (edge[1], edge[0])\n", " for edge in graph_100.edge_list()\n", "]\n", "\n", "swap_strategy = SwapStrategy(CouplingMap(edge_list), (even_edges, odd_edges))" ] }, { "cell_type": "markdown", "id": "ba53fd1d-0d68-43e3-9102-4c6e64f04de7", "metadata": {}, "source": [ "\n", "\n", "#### Rimappare il grafico utilizzando un mappatore SAT\n", "\n", "Anche quando un circuito è costituito da porte a commutazione (come nel caso del circuito QAOA, ma anche nelle simulazioni di tipo Trotter degli hamiltoniani di Ising), trovare una buona mappatura iniziale è un compito arduo. Quando utilizziamo l'approccio basato sul SAT presentato in [\\[2\\]](#references), riusciamo a individuare mappature iniziali efficaci per i circuiti con porte commutanti, ottenendo così una significativa riduzione del numero di livelli SWAP necessari. Come illustrato nell'articolo, è stato dimostrato che questo approccio è scalabile fino a *500 qubit*.\n", "\n", "Il codice seguente dimostra come utilizzare il sito `SATMapper` di Matsuo et al. per rimappare il grafico. Questo processo consente di mappare il problema su uno stato iniziale più ottimale per una determinata strategia SWAP, con conseguente riduzione significativa del numero di strati SWAP necessari per l'esecuzione del circuito.\n", "\n", "In `SATMapper`, il problema di trovare una buona mappatura iniziale è formulato come un problema SAT. Per trovare una mappatura iniziale per il circuito QAOA si utilizza un risolutore SAT. `python-sat` (`pysat` in breve) è una libreria Python per un risolutore SAT e la utilizzeremo per risolvere il problema SAT in questo esempio.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "df9d861a-64e8-49ee-aed1-c41f437fa743", "metadata": {}, "outputs": [], "source": [ "\"\"\"A class to solve the SWAP gate insertion initial mapping problem\n", "using the SAT approach from https://arxiv.org/abs/2212.05666.\n", "\"\"\"\n", "\n", "\n", "@dataclass\n", "class SATResult:\n", " \"\"\"A data class to hold the result of a SAT solver.\"\"\"\n", "\n", " satisfiable: bool # Satisfiable is True if the SAT model could be solved\n", " # in a given time.\n", " solution: dict # The solution to the SAT problem if it is satisfiable.\n", " mapping: list # The mapping of nodes in the pattern graph to nodes in the\n", " # target graph.\n", " elapsed_time: float # The time it took to solve the SAT model.\n", "\n", "\n", "class SATMapper:\n", " r\"\"\"A class to introduce a SAT-approach to solve\n", " the initial mapping problem in SWAP gate insertion for commuting gates.\n", "\n", " When this pass is run on a DAG it will look for the first instance of\n", " :class:`.Commuting2qBlock` and use the program graph :math:`P` of this block\n", " of gates to find a layout for a given swap strategy. This layout is found\n", " with a binary search over the layers :math:`l` of the swap strategy. At each\n", " considered layer a subgraph isomorphism problem formulated as a SAT is solved\n", " by a SAT solver. Each instance is whether it is possible to embed the program\n", " graph :math:`P` into the effective connectivity graph :math:`C_l` that is\n", " achieved by applying :math:`l` layers of the swap strategy to the coupling map\n", " :math:`C_0` of the backend. Since solving SAT problems can be hard, a\n", " ``time_out`` fixes the maximum time allotted to the SAT solver for each\n", " instance. If this time is exceeded the considered problem is deemed\n", " unsatisfiable and the binary search proceeds to the next number of swap\n", " layers :math:``l``.\n", " \"\"\"\n", "\n", " def __init__(self, timeout: int = 60):\n", " \"\"\"Initialize the SATMapping.\n", "\n", " Args:\n", " timeout: The allowed time in seconds for each iteration of the SAT\n", " solver. This variable defaults to 60 seconds.\n", " \"\"\"\n", " self.timeout = timeout\n", "\n", " def find_initial_mappings(\n", " self,\n", " program_graph: rx.Graph,\n", " swap_strategy: SwapStrategy,\n", " min_layers: int | None = None,\n", " max_layers: int | None = None,\n", " ) -> dict[int, SATResult]:\n", " r\"\"\"Find an initial mapping for a given swap strategy. Perform a\n", " binary search over the number of swap layers, and for each number\n", " of swap layers solve a subgraph isomorphism problem formulated as\n", " a SAT problem.\n", "\n", " Args:\n", " program_graph (rx.Graph): The program graph with commuting gates, where\n", " each edge represents a two-qubit gate.\n", " swap_strategy (SwapStrategy): The swap strategy to use to find the\n", " initial mapping.\n", " min_layers (int): The minimum number of swap layers to consider.\n", " Defaults to the maximum degree of the\n", " program graph - 2.\n", " max_layers (int): The maximum number of swap layers to consider.\n", " Defaults to the number of qubits in the\n", " swap strategy - 2.\n", "\n", " Returns:\n", " dict[int, SATResult]: A dictionary containing the results of the SAT\n", " solver for each number of swap layers.\n", " \"\"\"\n", " num_nodes_g1 = len(program_graph.nodes())\n", " num_nodes_g2 = swap_strategy.distance_matrix.shape[0]\n", " if num_nodes_g1 > num_nodes_g2:\n", " return SATResult(False, [], [], 0)\n", " if min_layers is None:\n", " # use the maximum degree of the program graph - 2\n", " # as the lower bound.\n", " min_layers = max((d for _, d in program_graph.degree)) - 2\n", " if max_layers is None:\n", " max_layers = num_nodes_g2 - 1\n", "\n", " variable_pool = IDPool(start_from=1)\n", " variables = np.array(\n", " [\n", " [variable_pool.id(f\"v_{i}_{j}\") for j in range(num_nodes_g2)]\n", " for i in range(num_nodes_g1)\n", " ],\n", " dtype=int,\n", " )\n", " vid2mapping = {v: idx for idx, v in np.ndenumerate(variables)}\n", " binary_search_results = {}\n", "\n", " def interrupt(solver):\n", " # This function is called to interrupt the solver when the\n", " # timeout is reached.\n", " solver.interrupt()\n", "\n", " # Make a cnf (conjunctive normal form) for the one-to-one\n", " # mapping constraint\n", " cnf1 = []\n", " for i in range(num_nodes_g1):\n", " clause = variables[i, :].tolist()\n", " cnf1.append(clause)\n", " for k, m in combinations(clause, 2):\n", " cnf1.append([-1 * k, -1 * m])\n", " for j in range(num_nodes_g2):\n", " clause = variables[:, j].tolist()\n", " for k, m in combinations(clause, 2):\n", " cnf1.append([-1 * k, -1 * m])\n", "\n", " # Perform a binary search over the number of swap layers to find the\n", " # minimum number of swap layers that satisfies the subgraph isomorphism\n", " # problem.\n", " while min_layers < max_layers:\n", " num_layers = (min_layers + max_layers) // 2\n", "\n", " # Create the connectivity matrix. Note that if the swap strategy\n", " # cannot reach full connectivity then its distance matrix will have\n", " # entries with -1. These entries must be treated as False.\n", " d_matrix = swap_strategy.distance_matrix\n", " connectivity_matrix = (\n", " (-1 < d_matrix) & (d_matrix <= num_layers)\n", " ).astype(int)\n", " # Make a cnf for the adjacency constraint\n", " cnf2 = []\n", " for e_0, e_1 in list(program_graph.edge_list()):\n", " clause_matrix = np.multiply(\n", " connectivity_matrix, variables[e_1, :]\n", " )\n", " clause = np.concatenate(\n", " (\n", " [[-variables[e_0, i]] for i in range(num_nodes_g2)],\n", " clause_matrix,\n", " ),\n", " axis=1,\n", " )\n", " # Remove 0s from each clause\n", " cnf2.extend([c[c != 0].tolist() for c in clause])\n", "\n", " cnf = CNF(from_clauses=cnf1 + cnf2)\n", "\n", " with Solver(bootstrap_with=cnf, use_timer=True) as solver:\n", " # Solve the SAT problem with a timeout.\n", " # Timer is used to interrupt the solver when the\n", " # timeout is reached.\n", " timer = Timer(self.timeout, interrupt, [solver])\n", " timer.start()\n", " status = solver.solve_limited(expect_interrupt=True)\n", " timer.cancel()\n", " # Get the solution and the elapsed time.\n", " sol = solver.get_model()\n", " e_time = solver.time()\n", "\n", " print(\n", " f\"Layers: {num_layers}, Status: {status}, Time: {e_time}\"\n", " )\n", " if status:\n", " # If the SAT problem is satisfiable, convert the solution\n", " # to a mapping.\n", " mapping = [vid2mapping[idx] for idx in sol if idx > 0]\n", " binary_search_results[num_layers] = SATResult(\n", " status, sol, mapping, e_time\n", " )\n", " max_layers = num_layers\n", " else:\n", " # If the SAT problem is unsatisfiable, return the last\n", " # satisfiable solution.\n", " binary_search_results[num_layers] = SATResult(\n", " status, sol, [], e_time\n", " )\n", " min_layers = num_layers + 1\n", "\n", " return binary_search_results\n", "\n", " def remap_graph_with_sat(\n", " self, graph: rx.Graph, swap_strategy, max_layers\n", " ):\n", " \"\"\"Applies the SAT mapping.\n", "\n", " Args:\n", " graph (nx.Graph): The graph to remap.\n", " swap_strategy (SwapStrategy): The swap strategy to use\n", " to find the initial mapping.\n", "\n", " Returns:\n", " tuple: A tuple containing the remapped graph, the edge map, and the\n", " number of layers of the swap strategy that was used to find the\n", " initial mapping. If no solution is found then the tuple contains\n", " None for each element. Note the returned edge map `{k: v}` means that\n", " node `k` in the original graph gets mapped to node `v` in the\n", " Pauli strings.\n", " \"\"\"\n", " num_nodes = len(graph.nodes())\n", " results = self.find_initial_mappings(\n", " graph, swap_strategy, 0, max_layers\n", " )\n", " solutions = [k for k, v in results.items() if v.satisfiable]\n", "\n", " if len(solutions):\n", " min_k = min(solutions)\n", " edge_map = dict(results[min_k].mapping)\n", " # Create the remapped graph\n", " remapped_graph = rx.PyGraph()\n", " remapped_graph.add_nodes_from(range(num_nodes))\n", " mapping = dict(results[min_k].mapping)\n", " for i, graph_edge in enumerate(list(graph.edge_list())):\n", " remapped_edge = tuple(mapping[node] for node in graph_edge)\n", " remapped_graph.add_edge(*remapped_edge, graph.edges()[i])\n", " return remapped_graph, edge_map, min_k\n", " else:\n", " return None, None, None" ] }, { "cell_type": "code", "execution_count": 101, "id": "e689e09e-6ca7-4154-8602-d1d954ebe80b", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Layers: 0, Status: True, Time: 0.022812999999999306\n", "Map from old to new nodes: {0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9, 10: 10, 11: 11, 12: 12, 13: 13, 14: 14, 15: 15, 16: 16, 17: 17, 18: 18, 19: 19, 20: 20, 21: 21, 22: 22, 23: 23, 24: 24, 25: 25, 26: 26, 27: 27, 28: 28, 29: 29, 30: 30, 31: 31, 32: 32, 33: 33, 34: 34, 35: 35, 36: 36, 37: 37, 38: 38, 39: 39, 40: 40, 41: 41, 42: 42, 43: 43, 44: 44, 45: 45, 46: 46, 47: 47, 48: 48, 49: 49, 50: 50, 51: 51, 52: 52, 53: 53, 54: 54, 55: 55, 56: 56, 57: 57, 58: 58, 59: 59, 60: 60, 61: 61, 62: 62, 63: 63, 64: 64, 65: 65, 66: 66, 67: 67, 68: 68, 69: 69, 70: 70, 71: 71, 72: 72, 73: 73, 74: 74, 75: 75, 76: 76, 77: 77, 78: 78, 79: 79, 80: 80, 81: 81, 82: 82, 83: 83, 84: 84, 85: 85, 86: 86, 87: 87, 88: 88, 89: 89, 90: 90, 91: 91, 92: 92, 93: 93, 94: 94, 95: 95, 96: 96, 97: 97, 98: 98, 99: 99}\n", "Min SWAP layers: 0\n" ] }, { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "sm = SATMapper(timeout=10)\n", "remapped_graph, edge_map, min_swap_layers = sm.remap_graph_with_sat(\n", " graph=graph_100, swap_strategy=swap_strategy, max_layers=1\n", ")\n", "print(\"Map from old to new nodes: \", edge_map)\n", "print(\"Min SWAP layers:\", min_swap_layers)\n", "draw_graph(remapped_graph, node_size=200, with_labels=True, width=1)" ] }, { "cell_type": "code", "execution_count": 102, "id": "ecf6e8c3-65c2-4430-8dd3-d67b8842045d", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "SparsePauliOp(['IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZ', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZI', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIZIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIZIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIZIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIZIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIZIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIZIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIZIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIZIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIZIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIZIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIZIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIZIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIZIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIZIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIZIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IZIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'ZIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII'],\n", " coeffs=[1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n", " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n", " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n", " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n", " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n", " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n", " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n", " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n", " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n", " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n", " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n", " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n", " 1.+0.j, 1.+0.j, 1.+0.j])\n" ] } ], "source": [ "remapped_max_cut_paulis = build_max_cut_paulis(remapped_graph)\n", "# define a qiskit SparsePauliOp from the list of paulis\n", "remapped_cost_operator = SparsePauliOp.from_list(remapped_max_cut_paulis)\n", "print(remapped_cost_operator)" ] }, { "cell_type": "markdown", "id": "5ae531be-80eb-4acd-b84a-7d466fd872e7", "metadata": {}, "source": [ "\n", "\n", "#### Costruisci un circuito QAOA con la strategia SWAP e la mappatura SAT\n", "\n", "Vogliamo applicare le strategie SWAP solo al livello dell'operatore di costo, quindi iniziamo creando il blocco isolato che poi trasformeremo e aggiungeremo al circuito QAOA finale.\n", "\n", "A tal fine, possiamo utilizzare la [`QAOAAnsatz`](/docs/api/qiskit/qiskit.circuit.library.QAOAAnsatz) classe di Qiskit. Inseriamo un circuito vuoto nei campi `initial_state` e `mixer_operator` per assicurarci di creare un livello di operatori di costo isolato.\n", "Definiamo inoltre la `edge_coloring` mappa in modo che i gate RZZ siano posizionati accanto ai gate SWAP. Questa posizione strategica ci permette di sfruttare le cancellazioni dei voli CX, ottimizzando il circuito per ottenere prestazioni migliori.\n", "Questo processo viene eseguito all'interno della `create_qaoa_swap_circuit` funzione.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "57d5eb53-9cda-4c38-a00b-26ed4b533bcd", "metadata": {}, "outputs": [], "source": [ "def make_meas_map(circuit: QuantumCircuit) -> dict:\n", " \"\"\"Return a mapping from qubit index (the key) to classical bit (the value).\n", "\n", " This allows us to account for the swapping order introduced by the\n", " SWAP strategy.\n", " \"\"\"\n", " creg = circuit.cregs[0]\n", " qreg = circuit.qregs[0]\n", "\n", " meas_map = {}\n", " for inst in circuit.data:\n", " if inst.operation.name == \"measure\":\n", " meas_map[qreg.index(inst.qubits[0])] = creg.index(inst.clbits[0])\n", "\n", " return meas_map\n", "\n", "\n", "def apply_swap_strategy(\n", " circuit: QuantumCircuit,\n", " swap_strategy: SwapStrategy,\n", " edge_coloring: dict[tuple[int, int], int] | None = None,\n", ") -> QuantumCircuit:\n", " \"\"\"Transpile with a SWAP strategy.\n", "\n", " Returns:\n", " A quantum circuit transpiled with the given swap strategy.\n", " \"\"\"\n", "\n", " pm_pre = PassManager(\n", " [\n", " FindCommutingPauliEvolutions(),\n", " Commuting2qGateRouter(\n", " swap_strategy,\n", " edge_coloring,\n", " ),\n", " ]\n", " )\n", " return pm_pre.run(circuit)\n", "\n", "\n", "def apply_qaoa_layers(\n", " cost_layer: QuantumCircuit,\n", " meas_map: dict,\n", " num_layers: int,\n", " gamma: list[float] | ParameterVector = None,\n", " beta: list[float] | ParameterVector = None,\n", " initial_state: QuantumCircuit = None,\n", " mixer: QuantumCircuit = None,\n", "):\n", " \"\"\"Applies QAOA layers to construct circuit.\n", "\n", " First, the initial state is applied. If `initial_state` is None, we begin in\n", " the initial superposition state. Next, we alternate between layers of the\n", " cost operator and the mixer. The cost operator is alternatively applied in\n", " order and in reverse instruction order. This allows us to apply the swap\n", " strategy on odd `p` layers and undo the swap strategy on even `p` layers.\n", " \"\"\"\n", "\n", " num_qubits = cost_layer.num_qubits\n", " new_circuit = QuantumCircuit(num_qubits, num_qubits)\n", "\n", " if initial_state is not None:\n", " new_circuit.append(initial_state, range(num_qubits))\n", " else:\n", " # all h state by default\n", " new_circuit.h(range(num_qubits))\n", "\n", " if gamma is None or beta is None:\n", " gamma = ParameterVector(\"γ'\", num_layers)\n", " if mixer is None or mixer.num_parameters == 0:\n", " beta = ParameterVector(\"β'\", num_layers)\n", " else:\n", " beta = ParameterVector(\"β'\", num_layers * mixer.num_parameters)\n", "\n", " if mixer is not None:\n", " mixer_layer = mixer\n", " else:\n", " mixer_layer = QuantumCircuit(num_qubits)\n", " mixer_layer.rx(-2 * beta[0], range(num_qubits))\n", "\n", " for layer in range(num_layers):\n", " bind_dict = {cost_layer.parameters[0]: gamma[layer]}\n", " cost_layer_ = cost_layer.assign_parameters(bind_dict)\n", " bind_dict = {\n", " mixer_layer.parameters[i]: beta[layer + i]\n", " for i in range(mixer_layer.num_parameters)\n", " }\n", " layer_mixer = mixer_layer.assign_parameters(bind_dict)\n", "\n", " if layer % 2 == 0:\n", " new_circuit.append(cost_layer_, range(num_qubits))\n", " else:\n", " new_circuit.append(cost_layer_.reverse_ops(), range(num_qubits))\n", "\n", " new_circuit.append(layer_mixer, range(num_qubits))\n", "\n", " for qidx, cidx in meas_map.items():\n", " new_circuit.measure(qidx, cidx)\n", "\n", " return new_circuit\n", "\n", "\n", "def create_qaoa_swap_circuit(\n", " cost_operator: SparsePauliOp,\n", " swap_strategy: SwapStrategy,\n", " edge_coloring: dict = None,\n", " theta: list[float] = None,\n", " qaoa_layers: int = 1,\n", " initial_state: QuantumCircuit = None,\n", " mixer: QuantumCircuit = None,\n", "):\n", " \"\"\"Create the circuit for QAOA.\n", "\n", " Notes: This circuit construction for QAOA works for quadratic terms in `Z`\n", " and will be extended to first-order terms in `Z`.\n", " Higher-orders are not supported.\n", "\n", " Args:\n", " cost_operator: the cost operator.\n", " swap_strategy: selected swap strategy\n", " edge_coloring: A coloring of edges that should correspond to the\n", " coupling map of the hardware. It defines the order in which\n", " we apply the Rzz gates. This allows us to choose an ordering\n", " such that `Rzz` gates will immediately precede SWAP gates\n", " to leverage CNOT cancellation.\n", " theta: The QAOA angles.\n", " qaoa_layers: The number of layers of the cost operator and the\n", " mixer operator.\n", " initial_state: The initial state on which we apply layers of\n", " cost operator and mixer.\n", " mixer: The QAOA mixer. It will be applied as is onto the QAOA\n", " circuit. Therefore, its output must have the same ordering\n", " of qubits as its input.\n", " \"\"\"\n", "\n", " num_qubits = cost_operator.num_qubits\n", "\n", " if theta is not None:\n", " gamma = theta[: len(theta) // 2]\n", " beta = theta[len(theta) // 2 :]\n", " qaoa_layers = len(theta) // 2\n", " else:\n", " gamma = beta = None\n", "\n", " # First, create the ansatz of one layer of QAOA without mixer\n", " cost_layer = QAOAAnsatz(\n", " cost_operator,\n", " reps=1,\n", " initial_state=QuantumCircuit(num_qubits),\n", " mixer_operator=QuantumCircuit(num_qubits),\n", " ).decompose()\n", "\n", " # This will allow us to recover the permutation of the measurements\n", " # that the swaps introduce.\n", " cost_layer.measure_all()\n", "\n", " # Now, apply the swap strategy for commuting gates\n", " cost_layer = apply_swap_strategy(cost_layer, swap_strategy, edge_coloring)\n", "\n", " # Compute the measurement map (qubit to classical bit).\n", " # We will apply this for odd layers where the swaps were inserted.\n", " if qaoa_layers % 2 == 1:\n", " meas_map = make_meas_map(cost_layer)\n", " else:\n", " meas_map = {idx: idx for idx in range(num_qubits)}\n", "\n", " cost_layer.remove_final_measurements()\n", "\n", " # Finally, introduce the mixer circuit and add measurements\n", " # following measurement map\n", " circuit = apply_qaoa_layers(\n", " cost_layer, meas_map, qaoa_layers, gamma, beta, initial_state, mixer\n", " )\n", "\n", " return circuit" ] }, { "cell_type": "code", "execution_count": null, "id": "7793ef92-ce59-4fd7-b43f-48d4e3427e3a", "metadata": {}, "outputs": [], "source": [ "# We can define the edge_coloring map so that RZZ gates are positioned\n", "# right before SWAP gates to exploit CX cancellations\n", "# We use greedy edge coloring from rustworkx to color the edges of\n", "# the graph. This coloring is used to order the RZZ gates\n", "# in the circuit.\n", "\n", "edge_coloring_idx = rx.graph_greedy_edge_color(graph_100)\n", "edge_coloring = {\n", " edge: edge_coloring_idx[idx]\n", " for idx, edge in enumerate(list(graph_100.edge_list()))\n", "}\n", "edge_coloring = {tuple(sorted(k)): v for k, v in edge_coloring.items()}" ] }, { "cell_type": "code", "execution_count": 105, "id": "82ae28b3-85eb-4487-8100-1e622e93cccf", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 105, "metadata": {}, "output_type": "execute_result" } ], "source": [ "qaoa_circ = create_qaoa_swap_circuit(\n", " remapped_cost_operator,\n", " swap_strategy,\n", " edge_coloring=edge_coloring,\n", " qaoa_layers=1,\n", ")\n", "qaoa_circ.draw(output=\"mpl\", fold=False)" ] }, { "cell_type": "markdown", "id": "e2afd1a7-0980-433b-a3a8-303d7e7718b1", "metadata": {}, "source": [ "\n", "\n", "## Fase 3: Esecuzione tramite le primitive \" IBM Quantum \"\n", "\n", "Passiamo ora alla preparazione per l'esecuzione hardware. Il nostro primo passo sarà quello di definire una funzione di costo del valore a rischio condizionale ( CVaR ), introdotta in [\\[3\\]](#references) per essere utilizzata nell'ambito del paradigma degli algoritmi di ottimizzazione quantistica variazionale.\n", "\n", "La CVaR di una variabile casuale $X$ per un livello di confidenza $α ∈ (0, 1]$ è definita come $CVaR_{\\alpha}(X) = \\mathbb{E} \\lbrack X | X \\leq F_X^{-1}(\\alpha) \\rbrack$ dove $F_X^{-1}(p)$ è la funzione di distribuzione cumulativa inversa di $X$. In altre parole, CVaR è il valore atteso della $\\alpha$ coda inferiore della distribuzione di $X$.\n", "\n" ] }, { "cell_type": "code", "execution_count": 106, "id": "172023f9-164e-43bd-bbc8-39d87628287e", "metadata": {}, "outputs": [], "source": [ "pass_manager = generate_preset_pass_manager(\n", " backend=backend,\n", " optimization_level=3,\n", ")\n", "\n", "transpiled_qaoa_circ = pass_manager.run(qaoa_circ)" ] }, { "cell_type": "code", "execution_count": null, "id": "e6794cf3-7fbe-46a5-bdc0-5faad1235365", "metadata": {}, "outputs": [], "source": [ "# Utility functions for the evaluation of the expectation value of a measured state\n", "# In this code, for optimization, the measured state is converted into a bit string,\n", "# and the sign of the value is determined by taking the exclusive OR of the bits\n", "# corresponding to Pauli Z.\n", "\n", "_PARITY = np.array(\n", " [-1 if bin(i).count(\"1\") % 2 else 1 for i in range(256)],\n", " dtype=np.complex128,\n", ")\n", "\n", "\n", "def evaluate_sparse_pauli(state: int, observable: SparsePauliOp) -> complex:\n", " \"\"\"Utility for the evaluation of the expectation value\n", " of a measured state.\n", "\n", " Args:\n", " state (int): The measured state.\n", " observable (SparsePauliOp): The observable to evaluate the\n", " expectation value for.\n", "\n", " Returns:\n", " complex: The expectation value of the measured state.\n", " \"\"\"\n", " packed_uint8 = np.packbits(\n", " observable.paulis.z, axis=1, bitorder=\"little\"\n", " ) # convert observable to array with 8 bit integer\n", " state_bytes = np.frombuffer(\n", " state.to_bytes(packed_uint8.shape[1], \"little\"),\n", " dtype=np.uint8, # convert bitstring to array with 8 bit integer\n", " )\n", " reduced = np.bitwise_xor.reduce(packed_uint8 & state_bytes, axis=1)\n", " # take bitwise xor of the result of 'and' conditional on the\n", " # above two, return 0 or 1\n", " return np.sum(observable.coeffs * _PARITY[reduced])" ] }, { "cell_type": "code", "execution_count": null, "id": "c5e5f7a4-01f6-4a02-9114-3bb0e24be1a2", "metadata": {}, "outputs": [], "source": [ "def qaoa_sampler_cost_fun(\n", " params, ansatz, hamiltonian, sampler, aggregation=None\n", "):\n", " \"\"\"Standard sampler-based QAOA cost function to be plugged into\n", " optimizer routines.\n", "\n", " Args:\n", " params (np.ndarray): Parameters for the ansatz.\n", " ansatz (QuantumCircuit): Ansatz circuit.\n", " hamiltonian (SparsePauliOp): Hamiltonian to be minimized.\n", " sampler (QAOASampler): Sampler to be used.\n", " aggregation (Callable | float | None): Aggregation function\n", " to be applied to the sampled results. If None, the sum\n", " of the expectation values is returned.\n", " If float, the CVaR with the given alpha is used.\n", " \"\"\"\n", " # Run the circuit\n", " job = sampler.run([(ansatz, params)])\n", " sampler_result = job.result()\n", " sampled_int_counts = sampler_result[\n", " 0\n", " ].data.c.get_int_counts() # bitstrings are stored as integers\n", " shots = sum(sampled_int_counts.values())\n", " int_count_distribution = {\n", " key: val / shots for key, val in sampled_int_counts.items()\n", " }\n", "\n", " # a dictionary containing: {state: (measurement probability, value)}\n", " evaluated = {\n", " state: (\n", " probability,\n", " np.real(evaluate_sparse_pauli(state, hamiltonian)),\n", " )\n", " for state, probability in int_count_distribution.items()\n", " }\n", "\n", " # If aggregation is None, return the sum of the expectation values.\n", " # If aggregation is a float, return the CVaR with the given alpha.\n", " # Otherwise, use the aggregation function.\n", " if aggregation is None:\n", " result = sum(\n", " probability * value for probability, value in evaluated.values()\n", " )\n", " elif isinstance(aggregation, float):\n", " cvar_aggregation = _get_cvar_aggregation(aggregation)\n", " result = cvar_aggregation(evaluated.values())\n", " else:\n", " result = aggregation(evaluated.values())\n", "\n", " global iter_counts, result_dict\n", " iter_counts += 1\n", " temp_dict = {}\n", " temp_dict[\"params\"] = params.tolist()\n", " temp_dict[\"cvar_fval\"] = result\n", " temp_dict[\"fval\"] = sum(\n", " probability * value for probability, value in evaluated.values()\n", " )\n", " temp_dict[\"distribution\"] = sampled_int_counts\n", " temp_dict[\"evaluated\"] = evaluated\n", " result_dict[iter_counts] = temp_dict\n", " print(f\"Iteration {iter_counts}: {result}\")\n", "\n", " return result\n", "\n", "\n", "def _get_cvar_aggregation(alpha: float | None) -> Callable:\n", " \"\"\"Return the CVaR aggregation function with the given alpha.\n", "\n", " Args:\n", " alpha (float | None): Alpha value for the CVaR aggregation.\n", " If None, 1 is used by default.\n", " Raises:\n", " ValueError: If alpha is not in [0, 1].\n", " \"\"\"\n", " if alpha is None:\n", " alpha = 1\n", " elif not 0 <= alpha <= 1:\n", " raise ValueError(f\"alpha must be in [0, 1], but {alpha} was given.\")\n", "\n", " def cvar_aggregation(\n", " objective_dict: Iterable[tuple[float, float]],\n", " ) -> float:\n", " \"\"\"Return the CVaR of the given measurements.\n", " Args:\n", " objective_dict (Iterable[tuple[float, float]]): An iterable\n", " of tuples containing the measured bit string and the\n", " objective value based on the bit string.\n", "\n", " \"\"\"\n", " sorted_measurements = sorted(objective_dict, key=lambda x: x[1])\n", " # accumulate the probabilities until alpha is reached\n", " accumulated_percent = 0.0\n", " cvar = 0.0\n", " for probability, value in sorted_measurements:\n", " cvar += value * min(probability, alpha - accumulated_percent)\n", " accumulated_percent += probability\n", " if accumulated_percent >= alpha:\n", " break\n", " return cvar / alpha\n", "\n", " return cvar_aggregation" ] }, { "cell_type": "markdown", "id": "63fa2ab4-5354-4022-ab46-e9bbf73870de", "metadata": {}, "source": [ "L' CVaR e può essere utilizzato come tecnica di mitigazione degli errori, come già illustrato in precedenza [\\[4\\]](#references). In questo esempio, determiniamo l' $\\alpha$ e e il numero di shot in base [all](/docs/guides/qpu-information#2q-error-layered) 'errore per gate a strati (EPLG) associato al circuito.\n", "\n" ] }, { "cell_type": "code", "execution_count": 109, "id": "032bf312-4bf4-40f4-81f0-2ae8a719b98b", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "layer fidelity 0.5454643821399414\n", "\n", "The corresponding CVaR aggregation value is: 0.2568730767702702\n", "To mitigate the twirled noise, increase shots by a factor of 3.8929731857197782\n" ] } ], "source": [ "num_2q_ops = transpiled_qaoa_circ.count_ops()[\n", " \"cz\"\n", "] # the two qubit gates on our backend are cz's.\n", "\n", "for el in backend.properties().general:\n", " if el.name[:2] == \"lf\" and el.name[3:] == str(\n", " n\n", " ): # pick out lf_100, lf of the best 100q chain\n", " lf = el.value # layer fidelity\n", " print(\"layer fidelity\", lf)\n", " eplg = 1 - lf ** (1 / (n - 1)) # error per layered gate (EPLG)\n", " fid_cz = 1 - eplg\n", " gamma_cz = 1 / fid_cz**2\n", " gamma_circ = gamma_cz**num_2q_ops\n", "\n", "cvar_aggregation = 1 / np.sqrt(gamma_circ)\n", "print(\"\")\n", "print(\"The corresponding CVaR aggregation value is: \", cvar_aggregation)\n", "print(\n", " \"To mitigate the twirled noise, increase shots by a factor of\",\n", " np.sqrt(gamma_circ),\n", ")" ] }, { "cell_type": "code", "execution_count": null, "id": "382e8acd-d0d0-4302-99aa-b64e5dd31e17", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Iteration 1: -13.227556797094595\n", "Iteration 2: -13.181545294899571\n", "Iteration 3: -13.149537293372594\n", "Iteration 4: -3.305576300816324\n", "Iteration 5: -12.647411769418035\n", "Iteration 6: -13.443610807401718\n", "Iteration 7: -12.475368761210511\n", "Iteration 8: -15.905726329447413\n", "Iteration 9: -18.011752834505565\n", "Iteration 10: -14.125781339945583\n", "Iteration 11: -19.693673319331744\n", "Iteration 12: -21.175543794613695\n", "Iteration 13: -21.805701324676196\n", "Iteration 14: -22.121280244318488\n", "Iteration 15: -20.02575633517435\n", "Iteration 16: -22.399349757584158\n", "Iteration 17: -22.569392265696226\n", "Iteration 18: -21.877719328111898\n", "Iteration 19: -22.79144777628963\n", "Iteration 20: -22.437359259397432\n", "Iteration 21: -23.021505287264777\n", "Iteration 22: -22.69742427180412\n", "Iteration 23: -23.12553129222746\n", "Iteration 24: -22.893473281156922\n", " message: Return from COBYLA because the trust region radius reaches its lower bound.\n", " success: True\n", " status: 0\n", " fun: -23.12553129222746\n", " x: [ 2.766e+00 1.080e+00]\n", " nfev: 24\n", " maxcv: 0.0\n" ] } ], "source": [ "iter_counts = 0\n", "result_dict = {}\n", "init_params = [np.pi, np.pi / 2]\n", "\n", "with Session(backend=backend) as session:\n", " sampler = Sampler(mode=session)\n", " sampler.options.default_shots = int(1000 / cvar_aggregation)\n", " sampler.options.dynamical_decoupling.enable = True\n", " sampler.options.dynamical_decoupling.sequence_type = \"XY4\"\n", " sampler.options.twirling.enable_gates = True\n", " sampler.options.twirling.enable_measure = True\n", " sampler.options.environment.job_tags = [\n", " \"TUT_AQAOA\"\n", " ] # add tag for your job execution\n", "\n", " result = minimize(\n", " qaoa_sampler_cost_fun,\n", " init_params,\n", " args=(\n", " transpiled_qaoa_circ,\n", " remapped_cost_operator,\n", " sampler,\n", " cvar_aggregation,\n", " ),\n", " method=\"COBYLA\",\n", " tol=1e-2,\n", " )\n", "print(result)" ] }, { "cell_type": "markdown", "id": "1d190fa4-3bbe-412a-b296-6dddd3ad2b12", "metadata": {}, "source": [ "\n", "\n", "## Fase 4: Post-elaborazione e restituzione del risultato nel formato classico desiderato\n", "\n", "Visualizziamo ora i nostri risultati e poi elaboriamoli per determinare il valore del taglio.\n", "\n" ] }, { "cell_type": "code", "execution_count": 111, "id": "761821cb-9a0c-4efb-806b-75513302d34a", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "from matplotlib import pyplot as plt\n", "\n", "plt.figure(figsize=(12, 6))\n", "plt.plot(\n", " [result_dict[i][\"cvar_fval\"] for i in range(1, iter_counts + 1)],\n", " label=\"CVaR\",\n", ")\n", "plt.plot(\n", " [result_dict[i][\"fval\"] for i in range(1, iter_counts + 1)],\n", " label=\"Standard\",\n", ")\n", "plt.legend()\n", "plt.xlabel(\"Iteration\")\n", "plt.ylabel(\"Cost\")\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "38aadfcb-aec9-4dbb-a9d3-319239eae196", "metadata": {}, "source": [ "Il codice seguente recupera la soluzione ottimale dalle stringhe di bit campionate:\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "7e8af29e-c99b-41f2-b6dd-2be471e1af21", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "bitstring (int): 283561207335785714592526814041, probability: 0.00025693730729701953, objective value: -43.0\n" ] } ], "source": [ "# Sort the result_dict[iter_counts]['evaluated'] by the CVaR value\n", "sorted_result_dict = [\n", " (k, v)\n", " for k, v in sorted(\n", " result_dict[iter_counts][\"evaluated\"].items(),\n", " key=lambda item: item[1][1],\n", " )\n", "]\n", "print(\n", " f\"bitstring (int): {sorted_result_dict[0][0]}, \"\n", " f\"probability: {sorted_result_dict[0][1][0]}, \"\n", " f\"objective value: {sorted_result_dict[0][1][1]}\"\n", ")" ] }, { "cell_type": "markdown", "id": "9cbeacc1-ff99-4b3d-b38d-b293a19642e2", "metadata": {}, "source": [ "Si consideri l' $H_C$ e hamiltoniano per il problema **del taglio massimo**. Si associ a ciascun vertice del grafo un qubit nello stato $|0\\rangle$ o $|1\\rangle$, dove il valore indica l'insieme a cui appartiene il vertice. Lo scopo del problema è massimizzare il numero di spigoli $(v_1, v_2)$ per i quali $v_1 = |0\\rangle$ e $v_2 = |1\\rangle$, o viceversa. Se associamo l'operatore \" $Z$ \" a ciascun qubit, dove\n", "\n", "$$\n", " Z|0\\rangle = |0\\rangle \\qquad Z|1\\rangle = -|1\\rangle,\n", "$$\n", "\n", "Allora un bordo $(v_1, v_2)$ appartiene al taglio se l'autovalore di $(Z_1|v_1\\rangle) \\cdot (Z_2|v_2\\rangle) = -1$; in altre parole, i qubit associati a $v_1$ e $v_2$ sono diversi. Analogamente, $(v_1, v_2)$ non fa parte dell'insieme di taglio se l'autovalore di $(Z_1|v_1\\rangle) \\cdot (Z_2|v_2\\rangle) = 1$.\n", "\n" ] }, { "cell_type": "code", "execution_count": 113, "id": "5ea9e6aa-4297-4687-b484-1695d415bad5", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Result bitstring (binary) : [1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0]\n", "The value of the cut is: 77\n" ] } ], "source": [ "from typing import Sequence\n", "\n", "\n", "def to_bitstring(integer, num_bits):\n", " result = np.binary_repr(integer, width=num_bits)\n", " return [int(digit) for digit in result]\n", "\n", "\n", "def evaluate_sample(x: Sequence[int], graph: rx.PyGraph) -> float:\n", " assert len(x) == len(\n", " list(graph.nodes())\n", " ), \"The length of x must coincide with the number of nodes in the graph.\"\n", " return sum(\n", " x[u] * (1 - x[v])\n", " + x[v]\n", " * (\n", " 1 - x[u]\n", " ) # x[u] = x[v] if same cut, x[u] \\neq x[v] if different cuts\n", " for u, v in list(graph.edge_list())\n", " )\n", "\n", "\n", "bitstring = to_bitstring(\n", " sorted_result_dict[0][0], len(list(remapped_graph.nodes()))\n", ")\n", "bitstring = bitstring[::-1]\n", "print(f\"Result bitstring (binary) : {bitstring}\")\n", "\n", "cut_value = evaluate_sample(bitstring, remapped_graph)\n", "print(f\"The value of the cut is: {cut_value}\")" ] }, { "cell_type": "markdown", "id": "c5879546-35ab-4876-bed9-262b85f130cc", "metadata": {}, "source": [ "Infine, tracciamo un grafico basato sul risultato di CVaR.\n", "Abbiamo diviso i nodi del grafo in due insiemi in base al risultato di CVaR.\n", "I nodi del primo gruppo sono colorati in grigio, mentre quelli del secondo gruppo sono colorati in viola.\n", "I bordi tra i due insiemi sono i bordi tagliati dal partizionamento.\n", "\n" ] }, { "cell_type": "code", "execution_count": 124, "id": "852dfeed-2871-4ca1-9754-15c95293198e", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "def plot_result(G, x):\n", " colors = [\"tab:grey\" if i == 0 else \"tab:purple\" for i in x]\n", " pos, _default_axes = rx.spring_layout(G), plt.axes(frameon=True)\n", " rx.visualization.mpl_draw(\n", " G,\n", " node_color=colors,\n", " node_size=150,\n", " alpha=0.8,\n", " pos=pos,\n", " with_labels=True,\n", " width=1,\n", " )\n", "\n", "\n", "plot_result(graph_100, to_bitstring(sorted_result_dict[0][0], 100)[::-1])" ] }, { "cell_type": "markdown", "id": "82f5c13b-a141-4657-adfd-bb18e88ad9f2", "metadata": {}, "source": [ "\n", "\n", "## Riferimenti\n", "\n", "\\[1] Weidenfeller, J., Valor, L. C., Gacon, J., Tornow, C., Bello, L., Woerner, S., & Egger, D. J. (2022). Scalabilità dell'algoritmo di ottimizzazione approssimativa quantistica su hardware basato su qubit superconduttori. Quantum, 6, 870.\n", "\n", "\\[2] Matsuo, A., Yamashita, S., & Egger, D. J. (2023). Un approccio SAT al problema della mappatura iniziale nell'inserimento di porte SWAP per porte pendolari. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 106(11), 1424-1431.\n", "\n", "\\[3] Barkoutsos, P. K., Nannicini, G., Robert, A., Tavernelli, I. e Woerner, S. (2020). Migliorare l'ottimizzazione quantistica variazionale utilizzando CVaR. Quantum, 4, 256.\n", "\n", "\\[4] Barron, S. V., Egger, D. J., Pelofske, E., Bärtschi, A., Eidenbenz, S., Lehmkuehler, M. e Woerner, S. (2023). Limiti dimostrabili per i valori di aspettativa senza rumore calcolati da campioni rumorosi. arXiv preprint arXiv:2312.00733.\n", "\n" ] }, { "cell_type": "markdown", "id": "a6a5bbfe-a159-4dc1-9333-488737aff503", "metadata": {}, "source": [ "\n", "\n", "## Passi successivi\n", "\n", "\n", " Se questo lavoro ti è sembrato interessante, potrebbero interessarti anche i seguenti contenuti:\n", "\n", " * [Il decathlon irrisolvibile](https://arxiv.org/pdf/2504.03832) : un elenco di 10 problemi di ottimizzazione che risultano difficili per gli algoritmi di ottimizzazione classici e che potrebbero costituire ottimi casi d'uso per testare le tecniche illustrate in questo tutorial.\n", " * [Un repository di best practice per l'ottimizzazione quantistica,](https://github.com/qiskit-community/qopt-best-practices) pensato per migliorare ulteriormente i risultati del tuo flusso di lavoro basato su QAOA.\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" }, "hours": 1.5, "qpuSeconds": 180 }, "nbformat": 4, "nbformat_minor": 4 }