{ "cells": [ { "cell_type": "markdown", "id": "1a869c2d-ae51-47d3-8a41-bfcf5e505f59", "metadata": {}, "source": [ "---\n", "title: \"Técnicas avançadas para QAOA\"\n", "description: \"Este caderno apresenta técnicas avançadas para melhorar o desempenho do Algoritmo de Otimização Aproximada Quântica (QAOA) com um grande número de qubits.\"\n", "---\n", "\n", "{/* cspell:ignore pysat, lbrack, frameon, IEICE */}\n", "\n", "\n", "\n", "# Técnicas avançadas para QAOA\n", "\n", "*Estimativa de uso: 3 minutos em um processador r2 Heron (NOTA: Esta é apenas uma estimativa. O tempo de execução pode variar.)*\n", "\n" ] }, { "cell_type": "markdown", "id": "1a6bbeef-966f-45e1-89aa-e964ef891eeb", "metadata": {}, "source": [ "\n", "\n", "## Pré-requisitos\n", "\n", "Os usuários devem estar familiarizados com os conceitos básicos do Algoritmo de Otimização Aproximada Quântica (QAOA). Consulte os recursos a seguir para obter uma introdução ao QAOA:\n", "\n", "* Tutorial sobre [a resolução de problemas de otimização quântica em escala industrial](/docs/tutorials/quantum-approximate-optimization-algorithm)\n", "* A aula [sobre QAOA em escala de utilidade](/learning/courses/quantum-computing-in-practice/utility-scale-qaoa#utility-scale-qaoa) (parte do curso “[Computação quântica na prática](/learning/courses/quantum-computing-in-practice) ”) em IBM Quantum® Learning\n", "\n", "\n", "\n", "## Resultados do aprendizado\n", "\n", "Após concluir este tutorial, os usuários deverão ser capazes de fazer o seguinte:\n", "\n", "* Utilizar técnicas avançadas que ajudem a melhorar a transpilagem do QAOA e ofereçam meios para melhorar o desempenho do QAOA\n", "\n", "Para um passo a passo detalhado do conteúdo deste tutorial, assista a este [vídeo do Qiskit](https://youtu.be/rBfK-l-qSNk?si=PC28gFAdu4JYSYdk).\n", "\n" ] }, { "cell_type": "markdown", "id": "ea97567d-810f-4cca-8edf-a47d70ea870a", "metadata": {}, "source": [ "\n", "\n", "## Segundo plano\n", "\n", "Este tutorial apresenta duas técnicas avançadas para melhorar o desempenho do **Algoritmo de Otimização Aproximada Quântica (QAOA)** com um grande número de qubits.\n", "\n", "As técnicas avançadas desse notebook incluem:\n", "\n", "* **Estratégia SWAP com mapeamento inicial SAT** : Trata-se de uma etapa de transpilador projetada especificamente para o QAOA que utiliza uma estratégia SWAP e um solucionador SAT em conjunto para otimizar a seleção dos qubits físicos a serem utilizados na QPU. A estratégia SWAP aproveita a comutatividade dos operadores QAOA para reordenar as portas, de modo que as camadas de portas SWAP possam ser executadas simultaneamente, reduzindo assim a profundidade do circuito [\\[1\\]](#references). O solucionador SAT é utilizado para encontrar um mapeamento inicial que minimize o número de operações SWAP necessárias para mapear os qubits do circuito para os qubits físicos no dispositivo [\\[2\\]](#references).\n", "* **CVaR função de custo** : Normalmente, o valor esperado do hamiltoniano de custo é utilizado como função de custo para o QAOA; no entanto, conforme demonstrado em [\\[3\\]](#references), concentrar-se na cauda da distribuição, em vez do valor esperado, pode melhorar o desempenho do QAOA em problemas de otimização combinatória. O `CVaR` faz exatamente isso. Para um determinado conjunto de soluções com valores-alvo correspondentes do problema de otimização em questão, o Valor em Risco Condicional ( CVaR ) com nível de confiança $\\alpha \\in [0, 1]$ é definido como a média das melhores soluções $\\alpha$ [\\[3\\]](#references).\n", " Assim, $\\alpha = 1$ corresponde ao valor esperado padrão, enquanto $\\alpha=0$ corresponde ao mínimo entre as imagens fornecidas, e $\\alpha \\in (0, 1)$ representa um equilíbrio entre priorizar as melhores imagens e, ao mesmo tempo, aplicar alguma média para suavizar o espaço de otimização. Além disso, o método de estimativa de média ponderada ( CVaR ) pode ser utilizado como técnica de mitigação de erros para melhorar a qualidade da estimativa do valor objetivo [\\[4\\]](#references).\n", "\n", "Ao final deste tutorial, você deverá ser capaz de utilizar essas técnicas para obter os melhores resultados ao executar o QAOA em seus problemas de otimização.\n", "\n" ] }, { "cell_type": "markdown", "id": "40fb546e-85e0-450b-a5ea-5d08950d129f", "metadata": {}, "source": [ "\n", "\n", "## Requisitos\n", "\n", "Antes de iniciar este tutorial, verifique se você tem os seguintes itens instalados:\n", "\n", "* Qiskit SDK v2.0 ou posterior, com suporte [para visualização](/docs/api/qiskit/visualization)\n", "* v0.43Qiskit Runtime ou mais tarde (`pip install qiskit-ibm-runtime`)\n", "* Biblioteca de gráficos 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", "## Instalação\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 do corte máximo\n", "\n", "Vamos considerar a resolução do problema **do corte máximo** em um grafo com 100 nós usando o algoritmo QAOA.\n", "O problema do corte máximo é um problema de otimização combinatória definido em um grafo $G = (V, E)$, onde $V$ é o conjunto de vértices e $E$ é o conjunto de arestas. O objetivo é dividir os vértices em dois conjuntos, $S$ e $V \\setminus S$, de modo a maximizar o número de arestas entre os dois conjuntos.\n", "Neste exemplo, utilizamos um gráfico com 100 nós baseado em um mapa de acoplamento de hardware.\n", "\n" ] }, { "cell_type": "markdown", "id": "663d13f5-a5f7-4b67-a89b-26deb41224ec", "metadata": {}, "source": [ "\n", "\n", "## Exemplo de simulador em pequena escala\n", "\n", "Como o objetivo deste tutorial é mostrar o desempenho do QAOA em escalas que vão além da capacidade de um simulador, vamos pular esta etapa.\n", "\n", "Se você quiser experimentar um fluxo de trabalho QAOA baseado em simulador, experimente o tutorial sobre [o algoritmo de otimização aproximada quântica](/docs/tutorials/quantum-approximate-optimization-algorithm).\n", "\n" ] }, { "cell_type": "markdown", "id": "6ca05a7c-5fde-4485-a3ad-c0ba02844e50", "metadata": {}, "source": [ "\n", "\n", "## Exemplo de hardware em grande escala\n", "\n" ] }, { "cell_type": "markdown", "id": "b825afbf-10fd-4926-bd65-05272044f107", "metadata": {}, "source": [ "\n", "\n", "### Passo 1: Mapear entradas clássicas para um problema quântico\n", "\n", "\n", "\n", "#### Gráfico → Hamiltoniano\n", "\n", "Primeiro, represente o problema em um circuito quântico adequado para o QAOA. Mais detalhes sobre esse processo podem ser encontrados no [tutorial](/docs/tutorials/quantum-approximate-optimization-algorithm) introdutório do 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", "### Etapa 2: Otimizar o problema para execução em hardware quântico\n", "\n", "\n", "\n", "#### Estratégia SWAP com o mapeamento inicial SAT\n", "\n", "Demonstraremos como criar e otimizar circuitos QAOA usando a **estratégia SWAP com mapeamento inicial SAT**, uma passagem de transpilador especificamente projetada para QAOA aplicada a problemas quadráticos.\n", "\n", "Neste exemplo, escolhemos uma estratégia de inserção SWAP para blocos de portas de dois qubits comutáveis, que aplica camadas de portas SWAP que são executáveis simultaneamente no mapa de acoplamento. Essa estratégia é apresentada em [\\[1\\]](#references) e é passada para `Commuting2qGateRouter`, que é exposta como uma passagem transpiler Qiskit padronizada (consulte [`Commuting2qGateRouter`](/docs/api/qiskit/qiskit.transpiler.passes.Commuting2qGateRouter)). Usamos uma estratégia de troca de linha neste exemplo.\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", "#### Remapeie o gráfico usando um mapeador SAT\n", "\n", "Mesmo quando um circuito é composto por portas comutadoras (como é o caso do circuito QAOA, mas também das simulações de Hamiltonianos de Ising com o método de Trotter), encontrar um bom mapeamento inicial é uma tarefa desafiadora. Ao utilizarmos a abordagem baseada em SAT apresentada em [\\[2\\]](#references), podemos identificar mapeamentos iniciais eficazes para circuitos com portas comutativas, o que resulta em uma redução significativa no número de camadas SWAP necessárias. Foi demonstrado que essa abordagem pode ser escalonada até *500 qubits*, conforme ilustrado no artigo.\n", "\n", "O código a seguir demonstra como usar o site `SATMapper` de Matsuo et al. para remapear o gráfico. Esse processo permite que o problema seja mapeado para um estado inicial mais ideal para uma estratégia SWAP especificada, resultando em uma redução significativa no número de camadas SWAP necessárias para executar o circuito.\n", "\n", "Em `SATMapper`, o problema de encontrar um bom mapeamento inicial é formulado como um problema SAT. Um solucionador SAT é usado para encontrar esse mapeamento inicial para o circuito QAOA. `python-sat` (`pysat` para abreviar) é uma biblioteca Python para um solucionador SAT, e nós a usaremos para resolver o problema SAT neste exemplo.\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", "#### Construa um circuito QAOA com a estratégia SWAP e o mapeamento SAT\n", "\n", "Queremos aplicar as estratégias SWAP somente à camada do operador de custo, portanto, começamos criando o bloco isolado que, posteriormente, transformaremos e anexaremos ao circuito QAOA final.\n", "\n", "Para isso, podemos usar a [`QAOAAnsatz`](/docs/api/qiskit/qiskit.circuit.library.QAOAAnsatz) classe do Qiskit. Inserimos um circuito vazio nos campos `initial_state` e `mixer_operator` para garantir que estamos criando uma camada de operadores de custo isolada.\n", "Também definimos o `edge_coloring` mapa de forma que as portas RZZ fiquem posicionadas ao lado das portas SWAP. Essa localização estratégica nos permite aproveitar os cancelamentos da CX, otimizando o circuito para obter um melhor desempenho.\n", "Esse processo é executado dentro da `create_qaoa_swap_circuit` função.\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", "## Etapa 3: Executar usando primitivas d Qiskit Runtime\n", "\n", "Vamos agora nos preparar para a execução em hardware. Nosso primeiro passo será definir uma função de custo do Valor em Risco Condicional ( CVaR ), que foi introduzida em [\\[3\\]](#references) para uso no âmbito do paradigma dos algoritmos de otimização quântica variacional.\n", "\n", "O CVaR de uma variável aleatória $X$ para um nível de confiança $α ∈ (0, 1]$ é definido como $CVaR_{\\alpha}(X) = \\mathbb{E} \\lbrack X | X \\leq F_X^{-1}(\\alpha) \\rbrack$ em que $F_X^{-1}(p)$ é a função de distribuição cumulativa inversa de $X$. Em outras palavras, CVaR é o valor esperado da cauda inferior $\\alpha$ da distribuição de $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": [ "O mecanismo de compensação de erros ( CVaR ) pode ser utilizado como técnica de mitigação de erros, conforme discutido anteriormente [\\[4\\]](#references). Neste exemplo, determinamos o parâmetro de compensação de tensão ( $\\alpha$ ) e o número de disparos com base no [erro por porta em camada](/docs/guides/qpu-information#2q-error-layered) (EPLG) associado ao 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", "## Etapa 4: Pós-processamento e retorno do resultado no formato clássico desejado\n", "\n", "Vamos agora visualizar nossos resultados e, em seguida, processá-los para determinar o valor do corte.\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": [ "O código a seguir recupera a melhor solução a partir das sequências de bits amostradas:\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": [ "Considere o hamiltoniano $H_C$ para o problema **do corte máximo**. Seja cada vértice do grafo associado a um qubit no estado $|0\\rangle$ ou $|1\\rangle$, onde o valor indica o conjunto ao qual o vértice pertence. O objetivo do problema é maximizar o número de arestas $(v_1, v_2)$ para as quais $v_1 = |0\\rangle$ e $v_2 = |1\\rangle$, ou vice-versa. Se associarmos o operador $Z$ a a cada qubit, onde\n", "\n", "$$\n", " Z|0\\rangle = |0\\rangle \\qquad Z|1\\rangle = -|1\\rangle,\n", "$$\n", "\n", "então, uma aresta $(v_1, v_2)$ pertence ao corte se o valor próprio de $(Z_1|v_1\\rangle) \\cdot (Z_2|v_2\\rangle) = -1$; em outras palavras, os qubits associados a $v_1$ e $v_2$ são diferentes. Da mesma forma, $(v_1, v_2)$ não pertence ao conjunto de corte se o autovalor de $(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": [ "Por fim, vamos desenhar um gráfico com base no resultado do CVaR.\n", "Dividimos os nós do gráfico em dois conjuntos com base no resultado do CVaR.\n", "Os nós do primeiro conjunto são coloridos em cinza, e os nós do segundo conjunto são coloridos em roxo.\n", "As bordas entre os dois conjuntos são as bordas que são cortadas pelo particionamento.\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", "## Referências\n", "\n", "\\[1] Weidenfeller, J., Valor, L. C., Gacon, J., Tornow, C., Bello, L., Woerner, S., & Egger, D. J. (2022). Dimensionamento do algoritmo de otimização quântica aproximada em hardware baseado em qubit supercondutor. Quantum, 6, 870.\n", "\n", "\\[2] Matsuo, A., Yamashita, S., & Egger, D. J. (2023). Uma abordagem SAT para o problema de mapeamento inicial na inserção de portas SWAP para portas comutáveis. 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., & Woerner, S. (2020). Aprimoramento da otimização quântica variacional usando CVaR. Quantum, 4, 256.\n", "\n", "\\[4] Barron, S. V., Egger, D. J., Pelofske, E., Bärtschi, A., Eidenbenz, S., Lehmkuehler, M., & Woerner, S. (2023). Limites prováveis para valores de expectativa sem ruído calculados a partir de amostras com ruído. arXiv pré-impressão arXiv:2312.00733.\n", "\n" ] }, { "cell_type": "markdown", "id": "a6a5bbfe-a159-4dc1-9333-488737aff503", "metadata": {}, "source": [ "\n", "\n", "## Próximas etapas\n", "\n", "\n", " Se você achou este trabalho interessante, talvez se interesse pelo seguinte material:\n", "\n", " * [O decatlo intratável](https://arxiv.org/pdf/2504.03832) : uma lista de 10 problemas de otimização que representam um desafio para os algoritmos clássicos de otimização e que podem servir como bons casos de uso para testar as técnicas apresentadas neste tutorial.\n", " * [Um repositório de melhores práticas para otimização quântica,](https://github.com/qiskit-community/qopt-best-practices) com o objetivo de melhorar ainda mais os resultados do seu fluxo de trabalho baseado em 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 }