{ "cells": [ { "cell_type": "markdown", "id": "2114652b-8f1f-4ba1-817b-48e98e3c6053", "metadata": {}, "source": [ "---\n", "title: \"Codificação de correlação de Pauli para reduzir os requisitos de corte máximo\"\n", "description: \"Utilizar a codificação por correlação de Pauli para codificar problemas de otimização em qubits com maior eficiência para a computação quântica.\"\n", "---\n", "\n", "{/* cspell:ignore lbrack setminus coloneqq rbrack binom rhobeg nfev PCEFQ */}\n", "\n", "\n", "\n", "# Codificação de correlação de Pauli para reduzir os requisitos de corte máximo\n", "\n", "*Estimativa de tempo de execução: 35 minutos em um processador Eagle r3 (NOTA: Trata-se apenas de uma estimativa. (O tempo de execução pode variar.)*\n", "\n" ] }, { "cell_type": "markdown", "id": "7239458e-d833-490e-8462-eaf2b5a115d4", "metadata": {}, "source": [ "\n", "\n", "## Resultados do aprendizado\n", "\n", "Após concluir este tutorial, os usuários devem esperar os seguintes resultados:\n", "\n", "* Compreender os princípios teóricos subjacentes à Codificação por Correlação de Pauli (PCE), incluindo como as cadeias de Pauli de múltiplos corpos permitem a compressão polinomial de problemas de otimização clássicos.\n", "* Implementar o PCE na prática para codificar e resolver tarefas de otimização em grande escala em hardware quântico de curto prazo.\n", "\n", "\n", "\n", "## Pré-requisitos\n", "\n", "Recomendamos que você esteja familiarizado com os seguintes tópicos antes de seguir com este tutorial:\n", "\n", "* [Algoritmos quânticos variacionais](/learning/courses/variational-algorithm-design)\n", "* [QAOA e max-cut](/docs/tutorials/quantum-approximate-optimization-algorithm)\n", "\n" ] }, { "cell_type": "markdown", "id": "8a343d18-ab46-431f-899d-0664c2f99cc0", "metadata": {}, "source": [ "\n", "\n", "## Segundo plano\n", "\n", "Este tutorial apresenta a *codificação de correlação de Pauli* (PCE) [\\[1\\]](#references), uma abordagem projetada para codificar problemas de otimização em qubits com maior eficiência para a computação quântica. O PCE mapeia variáveis clássicas em problemas de otimização para correlações de matriz Pauli de múltiplos corpos, resultando em uma compressão polinomial dos requisitos de espaço do problema. Ao empregar o PCE, o número de qubits necessários para a codificação é reduzido, o que o torna particularmente vantajoso para dispositivos quânticos de curto prazo com recursos limitados de qubits. Além disso, é demonstrado analiticamente que o PCE atenua inerentemente os platôs estéreis, oferecendo uma resistência superpolinomial contra esse fenômeno. Esse recurso integrado permite um desempenho sem precedentes em solucionadores de otimização quântica.\n", "\n" ] }, { "cell_type": "markdown", "id": "c133831c-1eff-4913-aff6-8c0d82df9d61", "metadata": {}, "source": [ "\n", "\n", "### Visão geral\n", "\n", "A abordagem PCE consiste em três etapas principais, conforme ilustrado na Figura 1 de [\\[1\\]](#references) abaixo:\n", "\n", "1. Codificação do problema de otimização em um espaço de correlação de Pauli.\n", "2. Resolver o problema usando um solucionador de otimização quântico-clássico.\n", "3. Decodificação da solução de volta ao espaço de otimização original.\n", " A abordagem PCE é adaptável a qualquer solucionador de otimização quântica capaz de processar matrizes de correlação de Pauli.\n", "\n" ] }, { "attachments": {}, "cell_type": "markdown", "id": "40a636a3-c0c0-42ba-a68a-2abcb8a7187b", "metadata": {}, "source": [ "![Visão geral do PCE.](https://quantum.cloud.ibm.com/docs/images/tutorials/solving-maxcut-with-reduced-qubit-requirements-using-pauli-correlation-encoding/af2cb835-88db-4a3d-9c86-51424b1a4bd3.avif)\n", "\n" ] }, { "cell_type": "markdown", "id": "1f28c0b3-b6dd-4627-90e6-db70b9114cd0", "metadata": {}, "source": [ "Na Figura 1 de [\\[1\\]](#references), o problema [do corte máximo](/docs/tutorials/quantum-approximate-optimization-algorithm) é utilizado como exemplo para ilustrar a abordagem PCE. O problema de corte máximo com $m=9$ nós é codificado em um espaço de correlação de Pauli, representando o problema de otimização como uma matriz de correlação — especificamente, correlações da matriz de Pauli de dois corpos entre $n=3$ qubits $(Q_1, Q_2, Q_3)$. As cores dos nós indicam a sequência de Pauli utilizada para cada nó codificado.\n", "Por exemplo, o nó 1, que corresponde à variável binária $x_1$, é codificado pelo valor esperado de $Z_1 \\otimes Z_2 \\otimes I_3$, enquanto $x_8$ é codificado por $I_1 \\otimes Y_2 \\otimes Y_3$.\n", "Isso corresponde à compressão das $m$ variáveis do problema em $ n = O(m^{1/2})$ qubits. De forma mais ampla, as correlações de três corpos do tipo “ $k $ ” permitem compressões polinomiais da ordem de $k$, com $k>1$. O conjunto de Pauli escolhido compreende três subconjuntos de cadeias de Pauli mutuamente comutativas, permitindo que todas as correlações do tipo “ $m$ ” sejam estimadas experimentalmente com apenas três configurações de medição.\n", "\n", "É construída uma função de perda $\\mathcal{L}$ de valores esperados de Pauli que imita a função objetivo original do corte máximo. A função de perda é então otimizada utilizando um solucionador de otimização quântico-clássico, como o [Variational Quantum Eigensolver (VQE)](/learning/courses/quantum-diagonalization-algorithms/vqe).\n", "\n", "Assim que a otimização for concluída, a solução é decodificada de volta para o espaço de otimização original, resultando na solução ótima do problema do corte máximo.\n", "\n", "\n", "\n", "## Requisitos\n", "\n", "Antes de iniciar este tutorial, verifique se você tem os seguintes itens instalados:\n", "\n", "* Qiskit SDK v1.0 ou posterior, com suporte [para visualização](/docs/api/qiskit/visualization)\n", "* Qiskit Runtime v0.22 ou mais tarde (`pip install qiskit-ibm-runtime`)\n", "\n" ] }, { "cell_type": "markdown", "id": "adfa1c9b-0dd3-42d0-afd9-bce648cf668e", "metadata": {}, "source": [ "\n", "\n", "## Instalação\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "5abb33b8-080d-4375-ac16-7788f2f1516a", "metadata": {}, "outputs": [], "source": [ "from itertools import combinations\n", "\n", "import numpy as np\n", "import rustworkx as rx\n", "import networkx as nx\n", "\n", "from scipy.optimize import minimize, OptimizeResult\n", "\n", "from qiskit.circuit.library import efficient_su2\n", "from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager\n", "from qiskit.quantum_info import SparsePauliOp\n", "from qiskit_ibm_runtime import EstimatorV2 as Estimator\n", "from qiskit_ibm_runtime import QiskitRuntimeService\n", "from qiskit_ibm_runtime import Session\n", "from rustworkx.visualization import mpl_draw\n", "from qiskit_aer import AerSimulator" ] }, { "cell_type": "code", "execution_count": 2, "id": "89c2999b-d309-4cf4-820e-9ef8a5cd5807", "metadata": {}, "outputs": [], "source": [ "def calc_cut_size(graph, partition0, partition1):\n", " \"\"\"Calculate the cut size of the given partitions of the graph.\"\"\"\n", "\n", " cut_size = 0\n", " for edge0, edge1 in graph.edge_list():\n", " if edge0 in partition0 and edge1 in partition1:\n", " cut_size += 1\n", " elif edge0 in partition1 and edge1 in partition0:\n", " cut_size += 1\n", " return cut_size" ] }, { "cell_type": "markdown", "id": "19cc2e86-204f-4ebf-b1a3-942025cc7015", "metadata": {}, "source": [ "\n", "\n", "## Exemplo de simulador em pequena escala\n", "\n" ] }, { "cell_type": "code", "execution_count": 3, "id": "af0c1db0-3b69-459c-8013-5149ede620c2", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "We are using the aer_simulator_from(ibm_pittsburgh)\n" ] } ], "source": [ "service = QiskitRuntimeService()\n", "real_backend = service.least_busy(\n", " operational=True, simulator=False, min_num_qubits=156\n", ")\n", "backend = AerSimulator.from_backend(real_backend)\n", "print(f\"We are using the {backend.name}\")" ] }, { "cell_type": "markdown", "id": "c8084430-5386-4788-97c3-c6e4fb7cb191", "metadata": {}, "source": [ "\n", "\n", "### Passo 1: Mapear entradas clássicas para um problema quântico\n", "\n", "\n", "\n", "#### O problema do corte máximo\n", "\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", "Para uma descrição detalhada do problema max-cut, consulte o tutorial sobre [o algoritmo de otimização aproximada de](/docs/tutorials/quantum-approximate-optimization-algorithm) Quantum.\n", "O problema do corte máximo também é utilizado como exemplo no tutorial “[Técnicas avançadas para QAOA](/docs/tutorials/advanced-techniques-for-qaoa) ”.\n", "Nesses tutoriais, o algoritmo QAOA é utilizado para resolver o problema do corte máximo.\n", "\n", "-hamiltonian\" />\n", "\n", "#### Gráfico -> Hamiltoniano\n", "\n", "Vamos considerar, em primeiro lugar, um grafo aleatório com 100 nós.\n", "\n" ] }, { "cell_type": "code", "execution_count": 4, "id": "37edb718-2bab-49d7-ad66-5f2f67d2aeff", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " $\"Output$ " ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "num_nodes = 100 # Number of nodes in graph\n", "seed = 42\n", "graph = rx.undirected_gnp_random_graph(num_nodes, 0.1, seed=seed)\n", "mpl_draw(graph)" ] }, { "cell_type": "code", "execution_count": null, "id": "eb7a80dc-74ea-472b-a13f-11cb8d4c0ca9", "metadata": {}, "outputs": [], "source": [ "nx_graph = nx.Graph()\n", "nx_graph.add_nodes_from(range(num_nodes))" ] }, { "cell_type": "code", "execution_count": 6, "id": "63451877-908a-4e80-9e11-23eb0d288bfc", "metadata": {}, "outputs": [], "source": [ "for edge in graph.edge_list():\n", " nx_graph.add_edge(edge[0], edge[1])" ] }, { "cell_type": "code", "execution_count": 7, "id": "515e7220-586f-4e2a-82b6-3885e3e38566", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Initial cut size: 345\n" ] } ], "source": [ "curr_cut_size, partition = nx.approximation.one_exchange(nx_graph, seed=1)\n", "print(f\"Initial cut size: {curr_cut_size}\")" ] }, { "cell_type": "markdown", "id": "57e3804e-61ae-45c5-9d94-3665cf01784b", "metadata": {}, "source": [ "Codificamos o grafo com 100 nós em correlações da matriz de Pauli de dois corpos entre nove qubits (veja a explicação abaixo). O gráfico é representado como uma matriz de correlação, na qual cada nó é codificado por uma sequência de Pauli. O sinal do valor esperado da corda de Pauli indica a partição do nó. Por exemplo, o nó 0 é codificado por uma cadeia de Pauli, $\\prod_0 = I_{8} \\otimes ... I_2 \\otimes X_1 \\otimes X_0$. O sinal do valor esperado dessa cadeia de Pauli indica a partição do nó 0. Definimos uma *codificação por correlação de Pauli* (PCE) em relação a um $\\prod$ e como\n", "\n", "$x_i \\coloneqq \\textit{sgn}(\\langle\\prod_i \\rangle),$\n", "\n", "em que $x_i$ é a partição do nó $i$ e $\\langle \\prod_i \\rangle \\coloneqq \\langle \\psi |\\prod_i| \\psi \\rangle $ é o valor de expectativa do nó de codificação da cadeia de Pauli $i$ em um estado quântico $|\\psi \\rangle$.\n", "\n" ] }, { "cell_type": "markdown", "id": "678e00fb-5bb9-450e-8229-0eab5676057a", "metadata": {}, "source": [ "Agora, vamos codificar o gráfico em um Hamiltoniano usando o PCE.\n", "Dividimos os nós em três conjuntos: $S_1$, $S_2$, e $S_3$. Em seguida, codificamos os nós em cada conjunto usando as cadeias de Pauli com $X$, $Y$ e $Z$, respectivamente.\n", "\n" ] }, { "cell_type": "markdown", "id": "4d5d48e5-ebe8-4b36-9496-288f40174a7b", "metadata": {}, "source": [ "Precisamos estabelecer uma relação entre o número de nós e os qubits necessários para codificar todos os nós. Ao utilizar todas as permutações possíveis para a codificação, obtém-se:\n", "\n", "$$\n", "m=3\\binom{n}{k}.\n", "$$\n", "\n", "Neste exemplo, consideramos que $k=2$; portanto,\n", "\n", "$$\n", "m = \\frac{3}{2} n(n-1).\n", "$$\n", "\n", "Portanto, o número de qubits $n$ necessário para representar um determinado número de nós $m$ é dado pela seguinte fórmula:\n", "\n", "$$\n", "n = \\left\\lceil \\frac{1 + \\sqrt{1 + \\tfrac{8}{3}m}}{2} \\right\\rceil.\n", "$$\n", "\n", "*Observe que o símbolo $\\lceil \\cdot \\rceil$ representa a função teto, que arredonda qualquer número real para o inteiro imediatamente superior. Isso garante que o número de qubits seja um número inteiro.*\n", "\n" ] }, { "cell_type": "code", "execution_count": 13, "id": "8ea1f545-3e9f-4620-bde8-755178ad3ec9", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Number of qubits: 9\n", "List 1: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]\n", "List 2: [33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65]\n", "List 3: [66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]\n" ] } ], "source": [ "num_qubits = int(np.ceil((1 + np.sqrt(1 + (8 / 3) * num_nodes)) / 2))\n", "\n", "list_size = num_nodes // 3\n", "node_x = [i for i in range(list_size)]\n", "node_y = [i for i in range(list_size, 2 * list_size)]\n", "node_z = [i for i in range(2 * list_size, num_nodes)]\n", "\n", "print(f\"Number of qubits: {num_qubits}\")\n", "print(\"List 1:\", node_x)\n", "print(\"List 2:\", node_y)\n", "print(\"List 3:\", node_z)" ] }, { "cell_type": "code", "execution_count": 14, "id": "d2649acb-7857-4cf4-88dc-4ef381a8552f", "metadata": {}, "outputs": [], "source": [ "def build_pauli_correlation_encoding(pauli, node_list, n, k=2):\n", " pauli_correlation_encoding = []\n", " for idx, c in enumerate(combinations(range(n), k)):\n", " if idx >= len(node_list):\n", " break\n", " paulis = [\"I\"] * n\n", " paulis[c[0]], paulis[c[1]] = pauli, pauli\n", " pauli_correlation_encoding.append((\"\".join(paulis)[::-1], 1))\n", "\n", " hamiltonian = []\n", " for pauli, weight in pauli_correlation_encoding:\n", " hamiltonian.append(SparsePauliOp.from_list([(pauli, weight)]))\n", "\n", " return hamiltonian\n", "\n", "\n", "pauli_correlation_encoding_x = build_pauli_correlation_encoding(\n", " \"X\", node_x, num_qubits\n", ")\n", "pauli_correlation_encoding_y = build_pauli_correlation_encoding(\n", " \"Y\", node_y, num_qubits\n", ")\n", "pauli_correlation_encoding_z = build_pauli_correlation_encoding(\n", " \"Z\", node_z, num_qubits\n", ")" ] }, { "cell_type": "markdown", "id": "4ce84c90-8b64-4959-a315-2380482801ad", "metadata": {}, "source": [ "\n", "\n", "### Etapa 2: Otimizar o problema para execução em hardware quântico\n", "\n", "\n", "\n", "#### Circuito quântico\n", "\n", "Aqui, o estado $|\\psi \\rangle$ é parametrizado com $\\mathbf{\\theta}$, e otimizamos esses parâmetros $\\mathbf{\\theta}$ usando uma abordagem variacional.\n", "Este tutorial utiliza o `efficient_su2` ansatz para nosso algoritmo variacional devido a seus recursos expressivos e facilidade de implementação.\n", "Também usamos a função de perda relaxada, que será apresentada mais adiante neste tutorial.\n", "Como resultado, podemos resolver problemas de grande escala com menos qubits e circuitos mais profundos.\n", "\n" ] }, { "cell_type": "code", "execution_count": 15, "id": "035f6b4a-4de0-452a-b60f-7260f9e3103a", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " $\"Output$ " ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Build the quantum circuit\n", "qc = efficient_su2(num_qubits, su2_gates=[\"ry\", \"rz\"], reps=2)\n", "qc.draw(\"mpl\")" ] }, { "cell_type": "code", "execution_count": 16, "id": "162f1384-98f5-406e-b5ae-0e12d0ad4b59", "metadata": {}, "outputs": [], "source": [ "# Optimize the circuit\n", "\n", "pm = generate_preset_pass_manager(optimization_level=3, backend=backend)\n", "qc = pm.run(qc)" ] }, { "cell_type": "markdown", "id": "644c9317-7988-427e-979a-975c0a616f52", "metadata": {}, "source": [ "\n", "\n", "#### Função de perda\n", "\n", "Para a função de perda $\\mathcal{L}$, utilizamos um relaxamento da função objetivo do corte máximo, conforme descrito em [\\[1\\]](#references), que é definida como $\\mathcal{V}(\\mathbf{x}) \\coloneqq \\sum_{(i, j) \\in E} W_{i, j}(1-x_i x_j)$. Aqui, $W_{i, j}$ denota o peso da aresta $(i, j)$, e $x_i$ representa a partição do nó $i$.\n", "A função de perda $\\mathcal{L}$ é dada por:\n", "\n", "$\\mathcal{L}\\coloneqq \\sum_{(i, j) \\in E} W_{i, j} \\text{tanh} (\\alpha \\langle\\prod_i \\rangle) \\text{tanh} (\\alpha \\langle\\prod_j \\rangle) + \\mathcal{L}^{(\\text{reg})},$\n", "\n", "onde a função objetivo max-cut é substituída pelas tangentes hiperbólicas suaves dos valores esperados das cadeias de Pauli que codificam os nós. O termo de regularização $\\mathcal{L}^{(\\text{reg})}$ e o fator de redimensionamento $\\alpha$, proporcional ao número de qubits, são introduzidos para melhorar o desempenho do solucionador.\n", "\n", "O termo de regularização é definido como:\n", "\n", "$\\mathcal{L}^{(\\text{reg})}$ é definido como $\\mathcal{L}^{(\\text{reg})} \\coloneqq \\beta \\nu \\lbrack \\frac{1}{m} \\sum_{i \\in V} \\text{tanh} (\\alpha \\langle\\prod_i \\rangle)^2 \\rbrack ^2$\n", "\n", "onde $\\beta=1/2$, $\\nu = |E|/2 + (m -1) /4$, $|E|$ é o número de arestas, e $m$ é o número de vértices no grafo.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "fe608e6a-08ce-493d-9b0a-eb9d6e0028ff", "metadata": {}, "outputs": [], "source": [ "def loss_func_estimator(x, ansatz, hamiltonian, estimator, graph):\n", " \"\"\"\n", " Calculates the specified loss function for the given ansatz, Hamiltonian,\n", " and graph.\n", "\n", " The expectation values of each Pauli string in the Hamiltonian are first\n", " obtained by running the ansatz on the quantum backend. These\n", " expectation values are then passed through the nonlinear function\n", " tanh(alpha * prod_i). The loss function is\n", " subsequently computed from these transformed values.\n", " \"\"\"\n", " job = estimator.run(\n", " [\n", " (ansatz, hamiltonian[0], x),\n", " (ansatz, hamiltonian[1], x),\n", " (ansatz, hamiltonian[2], x),\n", " ]\n", " )\n", " result = job.result()\n", "\n", " # calculate the loss function\n", " node_exp_map = {}\n", " idx = 0\n", " for r in result:\n", " for ev in r.data.evs:\n", " node_exp_map[idx] = ev\n", " idx += 1\n", "\n", " loss = 0\n", " alpha = num_qubits\n", " for edge0, edge1 in graph.edge_list():\n", " loss += np.tanh(alpha * node_exp_map[edge0]) * np.tanh(\n", " alpha * node_exp_map[edge1]\n", " )\n", "\n", " regulation_term = 0\n", " for i in range(len(graph.nodes())):\n", " regulation_term += np.tanh(alpha * node_exp_map[i]) ** 2\n", " regulation_term = regulation_term / len(graph.nodes())\n", " regulation_term = regulation_term**2\n", " beta = 1 / 2\n", " v = len(graph.edges()) / 2 + (len(graph.nodes()) - 1) / 4\n", " regulation_term = beta * v * regulation_term\n", "\n", " loss = loss + regulation_term\n", "\n", " global experiment_result\n", " print(f\"Iter {len(experiment_result)}: {loss}\")\n", " experiment_result.append({\"loss\": loss, \"exp_map\": node_exp_map})\n", " return loss" ] }, { "cell_type": "markdown", "id": "49943596-7f90-4226-a900-d5890deefbd9", "metadata": {}, "source": [ "\n", "\n", "### Passo 3: Execute usando Qiskit primitives\n", "\n" ] }, { "cell_type": "markdown", "id": "583ba786-e2e9-4593-bf75-00723b589d78", "metadata": {}, "source": [ "Neste tutorial, definimos `max_iter=50` no ciclo de otimização para fins de demonstração. Se aumentarmos o número de iterações, podemos esperar melhores resultados.\n", "\n" ] }, { "cell_type": "code", "execution_count": 18, "id": "8d203dd5-8b72-4b78-a36e-c10fdef3ebc3", "metadata": {}, "outputs": [], "source": [ "pce = []\n", "pce.append(\n", " [op.apply_layout(qc.layout) for op in pauli_correlation_encoding_x]\n", ")\n", "pce.append(\n", " [op.apply_layout(qc.layout) for op in pauli_correlation_encoding_y]\n", ")\n", "pce.append(\n", " [op.apply_layout(qc.layout) for op in pauli_correlation_encoding_z]\n", ")" ] }, { "cell_type": "code", "execution_count": null, "id": "8d9d6313-9bcd-4ffb-b40c-361d18c68afe", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Iter 0: 159.88755362682548\n", "Iter 1: 113.46202580636677\n", "Iter 2: 56.76494226400048\n", "Iter 3: 32.63357946896002\n", "Iter 4: 21.517837239610117\n", "Iter 5: 30.96034960483569\n", "Iter 6: 20.780475923938027\n", "Iter 7: 24.54251816279811\n", "Iter 8: 27.834486461763042\n", "Iter 9: 16.705460776812693\n", "Iter 10: 18.020587887236864\n", "Iter 11: 12.252379762741352\n", "Iter 12: 5.253885750886939\n", "Iter 13: 6.985984759592262\n", "Iter 14: 6.908717244584757\n", "Iter 15: 12.915466016863858\n", "Iter 16: 4.105776920457279\n", "Iter 17: 11.707504530740305\n", "Iter 18: 7.154360511076546\n", "Iter 19: 10.3890865704735\n", "Iter 20: 10.376147647857252\n", "Iter 21: 2.533430195296697\n", "Iter 22: 3.8612421907795462\n", "Iter 23: 6.103735057461906\n", "Iter 24: -1.1190368234312347\n", "Iter 25: 6.125915279494738\n", "Iter 26: 11.086280445482455\n", "Iter 27: 10.102569882302827\n", "Iter 28: -0.02664415648133822\n", "Iter 29: 7.621887727398785\n", "Iter 30: 5.967346615554497\n", "Iter 31: 3.85345716014828\n", "Iter 32: 4.5494846149011\n", "Iter 33: 10.006668112637232\n", "Iter 34: -3.1927138938527877\n", "Iter 35: 2.8829882366285116\n", "Iter 36: 3.3130087521654144\n", "Iter 37: -4.907566569808272\n", "Iter 38: -4.980134722109894\n", "Iter 39: -2.990457463896541\n", "Iter 40: -5.938401817344579\n", "Iter 41: -2.1807712386469724\n", "Iter 42: -1.0945774380342126\n", "Iter 43: -4.7548102593556685\n", "Iter 44: -3.8762362299208144\n", "Iter 45: -4.9348321021624\n", "Iter 46: -6.487722842864011\n", "Iter 47: 0.7064210113389331\n", "Iter 48: -2.3428323031772216\n", "Iter 49: -2.626032270380895\n", " message: Return from COBYLA because the objective function has been evaluated 50 times.\n", " success: False\n", " status: 3\n", " fun: -2.626032270380895\n", " x: [ 1.375e+00 1.951e+00 ... 9.395e-01 8.948e-01]\n", " nfev: 50\n" ] } ], "source": [ "max_iter = 50\n", "counter = {\"i\": 0}\n", "last_x = {\"value\": None}\n", "last_fun = {\"value\": None}\n", "\n", "with Session(backend=backend) as session:\n", " estimator = Estimator(mode=session)\n", "\n", " experiment_result = []\n", "\n", " def loss_func(x):\n", " last_x[\"value\"] = x.copy()\n", " if counter[\"i\"] + 1 > max_iter:\n", " return last_fun[\"value\"]\n", " counter[\"i\"] += 1\n", " val = loss_func_estimator(\n", " x, qc, [pce[0], pce[1], pce[2]], estimator, graph\n", " )\n", " last_fun[\"value\"] = val\n", " return val\n", "\n", " np.random.seed(seed)\n", " initial_params = np.random.rand(qc.num_parameters)\n", "\n", " result = minimize(\n", " loss_func, initial_params, method=\"COBYLA\", options={\"rhobeg\": 1.0}\n", " )\n", "\n", " if counter[\"i\"] >= max_iter:\n", " result = OptimizeResult(\n", " message=f\"Return from COBYLA because the objective function \"\n", " f\"has been evaluated {max_iter} times.\",\n", " success=False,\n", " status=3,\n", " fun=last_fun[\"value\"],\n", " x=last_x[\"value\"],\n", " nfev=counter[\"i\"],\n", " )\n", "\n", "print(result)" ] }, { "cell_type": "markdown", "id": "5c9dd9f8-ed15-4008-8841-e44caf11cf99", "metadata": {}, "source": [ "\n", "\n", "### Etapa 4: Pós-processamento e retorno do resultado no formato clássico desejado\n", "\n", "As partições dos nós são determinadas pela avaliação do sinal dos valores de expectativa das cadeias de Pauli que codificam os nós.\n", "\n" ] }, { "cell_type": "code", "execution_count": 20, "id": "fa2db108-754b-4036-af98-87f5390a9c11", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{0, 2, 3, 8, 9, 11, 12, 13, 17, 18, 20, 22, 23, 24, 25, 26, 27, 30, 35, 37, 38, 40, 43, 46, 48, 49, 50, 51, 53, 57, 61, 62, 63, 66, 67, 68, 70, 71, 74, 77, 81, 82, 83, 84, 87, 88, 94, 96, 99} {1, 4, 5, 6, 7, 10, 14, 15, 16, 19, 21, 28, 29, 31, 32, 33, 34, 36, 39, 41, 42, 44, 45, 47, 52, 54, 55, 56, 58, 59, 60, 64, 65, 69, 72, 73, 75, 76, 78, 79, 80, 85, 86, 89, 90, 91, 92, 93, 95, 97, 98}\n" ] } ], "source": [ "# Calculate the partitions based on the final expectation values\n", "# If the expectation value is positive, the node belongs to partition 0 (par0)\n", "# Otherwise, the node belongs to partition 1 (par1)\n", "def get_partitions(experiment_result):\n", " par0, par1 = set(), set()\n", " best_index = min(\n", " range(len(experiment_result)),\n", " key=lambda i: experiment_result[i][\"loss\"],\n", " )\n", " for i in experiment_result[best_index][\"exp_map\"]:\n", " if experiment_result[best_index][\"exp_map\"][i] >= 0:\n", " par0.add(i)\n", " else:\n", " par1.add(i)\n", " return par0, par1, best_index\n", "\n", "\n", "par0, par1, best_index = get_partitions(experiment_result)\n", "print(par0, par1)" ] }, { "cell_type": "markdown", "id": "6f82e256-36f1-4ac1-badb-abdc98a26b23", "metadata": {}, "source": [ "Podemos calcular o tamanho do corte no problema do corte máximo utilizando as partições do nó.\n", "\n" ] }, { "cell_type": "code", "execution_count": 21, "id": "bd85ceae-ef8b-4e21-b447-e92ca92e06eb", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Cut size: 268\n" ] } ], "source": [ "cut_size = calc_cut_size(graph, par0, par1)\n", "print(f\"Cut size: {cut_size}\")" ] }, { "cell_type": "markdown", "id": "ef94b209-ea19-4292-aedc-f77edf77a2eb", "metadata": {}, "source": [ "Após a conclusão do treinamento, realizamos uma rodada de pesquisa de troca de bit único para melhorar a solução como uma etapa clássica de pós-processamento.\n", "Nesse processo, trocamos as partições de dois nós e avaliamos o tamanho do corte. Se o tamanho do corte for melhorado, manteremos a troca. Repetimos esse processo para todos os pares possíveis de nós conectados por uma borda.\n", "\n" ] }, { "cell_type": "code", "execution_count": 22, "id": "b0df38ef-98d0-4d8c-bbdf-75d14e4680f7", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1]\n" ] } ], "source": [ "cur_bits = []\n", "\n", "for i in experiment_result[best_index][\"exp_map\"]:\n", " if experiment_result[best_index][\"exp_map\"][i] >= 0:\n", " cur_bits.append(1)\n", " else:\n", " cur_bits.append(0)\n", "print(cur_bits)" ] }, { "cell_type": "code", "execution_count": 23, "id": "232658b0-a86b-4cb5-aff8-c8f2423491b6", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "279 [1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1]\n" ] } ], "source": [ "# Swap the partitions and calculate the cut size\n", "\n", "\n", "def swap_partitions(graph, cur_bits):\n", " best_cut = 0\n", " best_bits = []\n", " for edge0, edge1 in graph.edge_list():\n", " swapped_bits = cur_bits.copy()\n", " swapped_bits[edge0], swapped_bits[edge1] = (\n", " swapped_bits[edge1],\n", " swapped_bits[edge0],\n", " )\n", "\n", " cur_partition = [set(), set()]\n", " for i, bit in enumerate(swapped_bits):\n", " if bit > 0:\n", " cur_partition[0].add(i)\n", " else:\n", " cur_partition[1].add(i)\n", " cut_size = calc_cut_size(graph, cur_partition[0], cur_partition[1])\n", " if best_cut < cut_size:\n", " best_cut = cut_size\n", " best_bits = swapped_bits\n", " return best_cut, best_bits\n", "\n", "\n", "best_cut, best_bits = swap_partitions(graph, cur_bits)\n", "print(best_cut, best_bits)" ] }, { "cell_type": "markdown", "id": "5142e8d0-ef6f-4abb-974e-ed25e5bfe692", "metadata": {}, "source": [ "\n", "\n", "# Exemplo de hardware em grande escala\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "d91c4ac2-3c5b-4afb-aa2c-42d1b50fa674", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "We are using 33 qubits\n", "We are using the ibm_pittsburgh\n", "Iter 0: 57399.57543902076\n", "Iter 1: 56458.787143794\n", "Iter 2: 40778.45608998947\n", "Iter 3: 35571.58511146131\n", "Iter 4: 33861.6835761173\n", "Iter 5: 39697.22637736274\n", "Iter 6: 34984.77893767163\n", "Iter 7: 32051.882157096858\n", "Iter 8: 26134.153216063707\n", "Iter 9: 24914.322627065787\n", "Iter 10: 24030.21227315425\n", "Iter 11: 23047.463945514\n", "Iter 12: 22629.42866110748\n", "Iter 13: 17374.859132614685\n", "Iter 14: 18020.11637762458\n", "Iter 15: 17924.7066364044\n", "Iter 16: 15825.1992250984\n", "Iter 17: 16553.346711978447\n", "Iter 18: 12393.565736512377\n", "Iter 19: 11994.021456089155\n", "Iter 20: 11199.994322735669\n", "Iter 21: 9624.895532927634\n", "Iter 22: 9073.811130188606\n", "Iter 23: 9836.721241931278\n", "Iter 24: 10555.925186133794\n", "Iter 25: 9179.1179493286\n", "Iter 26: 8495.394826965305\n", "Iter 27: 8913.688189840399\n", "Iter 28: 7830.448471810181\n", "Iter 29: 7757.430542422075\n", "Iter 30: 6796.187594518731\n", "Iter 31: 7307.985913766867\n", "Iter 32: 7340.225833330675\n", "Iter 33: 7064.731899380469\n", "Iter 34: 7632.270657372515\n", "Iter 35: 7049.154710767935\n", "Iter 36: 7486.118442084411\n", "Iter 37: 6302.12602219333\n", "Iter 38: 6244.934230209166\n", "Iter 39: 7154.9748739261395\n", "Iter 40: 6482.109600054041\n", "Iter 41: 5718.475169152395\n", "Iter 42: 5693.008457857462\n", "Iter 43: 4869.782667921923\n", "Iter 44: 4957.625304450959\n", "Iter 45: 5582.240637063214\n", "Iter 46: 4983.90082772116\n", "Iter 47: 5416.268575648202\n", "Iter 48: 4809.98398457807\n", "Iter 49: 5092.527306646118\n", " message: Return from COBYLA because the objective function has been evaluated 50 times.\n", " success: False\n", " status: 3\n", " fun: 5092.527306646118\n", " x: [ 1.375e+00 1.951e+00 ... 7.259e-01 8.971e-01]\n", " nfev: 50\n", "Cut size: 56152\n", "The best max-cut value achieved for a graph with 1500 nodes on 33 qubits is 56219\n", "and the specific partition we obtained is [1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n" ] } ], "source": [ "# -------------------------Step 1-------------------------\n", "\n", "num_nodes = 1500 # Number of nodes in graph\n", "graph = rx.undirected_gnp_random_graph(num_nodes, 0.1, seed=seed)\n", "nx_graph = nx.Graph()\n", "nx_graph.add_nodes_from(range(num_nodes))\n", "for edge in graph.edge_list():\n", " nx_graph.add_edge(edge[0], edge[1])\n", "\n", "num_qubits = int(np.ceil((1 + np.sqrt(1 + (8 / 3) * num_nodes)) / 2))\n", "\n", "list_size = num_nodes // 3\n", "node_x = [i for i in range(list_size)]\n", "node_y = [i for i in range(list_size, 2 * list_size)]\n", "node_z = [i for i in range(2 * list_size, num_nodes)]\n", "\n", "pauli_correlation_encoding_x = build_pauli_correlation_encoding(\n", " \"X\", node_x, num_qubits\n", ")\n", "pauli_correlation_encoding_y = build_pauli_correlation_encoding(\n", " \"Y\", node_y, num_qubits\n", ")\n", "pauli_correlation_encoding_z = build_pauli_correlation_encoding(\n", " \"Z\", node_z, num_qubits\n", ")\n", "print(f\"We are using {num_qubits} qubits\")\n", "\n", "# -------------------------Step 2-------------------------\n", "backend = real_backend\n", "print(f\"We are using the {backend.name}\")\n", "qc = efficient_su2(num_qubits, [\"ry\", \"rz\"], reps=2)\n", "pm = generate_preset_pass_manager(optimization_level=3, backend=backend)\n", "qc = pm.run(qc)\n", "# -------------------------Step 3-------------------------\n", "pce = []\n", "pce.append(\n", " [op.apply_layout(qc.layout) for op in pauli_correlation_encoding_x]\n", ")\n", "pce.append(\n", " [op.apply_layout(qc.layout) for op in pauli_correlation_encoding_y]\n", ")\n", "pce.append(\n", " [op.apply_layout(qc.layout) for op in pauli_correlation_encoding_z]\n", ")\n", "\n", "# Run the optimization using a session.\n", "max_iter = 50\n", "counter = {\"i\": 0}\n", "with Session(backend=backend) as session:\n", " estimator = Estimator(mode=session)\n", " estimator.options.environment.job_tags = [\"TUT_PCEFQ\"]\n", " experiment_result = []\n", "\n", " def loss_func(x):\n", " last_x[\"value\"] = x.copy()\n", " if counter[\"i\"] + 1 > max_iter:\n", " return last_fun[\"value\"]\n", " counter[\"i\"] += 1\n", " val = loss_func_estimator(\n", " x, qc, [pce[0], pce[1], pce[2]], estimator, graph\n", " )\n", " last_fun[\"value\"] = val\n", " return val\n", "\n", " np.random.seed(seed)\n", " initial_params = np.random.rand(qc.num_parameters)\n", " result = minimize(\n", " loss_func, initial_params, method=\"COBYLA\", options={\"rhobeg\": 1.0}\n", " )\n", " if counter[\"i\"] >= max_iter:\n", " result = OptimizeResult(\n", " message=\"Return from COBYLA because the objective function \"\n", " \"has been evaluated {max_iter} times.\",\n", " success=False,\n", " status=3,\n", " fun=last_fun[\"value\"],\n", " x=last_x[\"value\"],\n", " nfev=counter[\"i\"],\n", " )\n", "print(result)\n", "\n", "# -------------------------Step 4-------------------------\n", "\n", "par0, par1, best_index = get_partitions(experiment_result)\n", "cut_size = calc_cut_size(graph, par0, par1)\n", "print(f\"Cut size: {cut_size}\")\n", "\n", "best_bits = []\n", "cur_bits = []\n", "for i in experiment_result[best_index][\"exp_map\"]:\n", " if experiment_result[best_index][\"exp_map\"][i] >= 0:\n", " cur_bits.append(1)\n", " else:\n", " cur_bits.append(0)\n", "best_cut, best_bits = swap_partitions(graph, cur_bits)\n", "# Print final solution\n", "\n", "print(\n", " f\"The best max-cut value achieved for a graph with {num_nodes} nodes \"\n", " f\"on {num_qubits} qubits is {best_cut}\"\n", ")\n", "print(f\"and the specific partition we obtained is {best_bits}\")" ] }, { "cell_type": "markdown", "id": "9d68b120-bf43-4070-b897-013652c824d7", "metadata": {}, "source": [ "\n", "\n", "## Próximas etapas\n", "\n", "\n", " Se você achou este trabalho interessante, talvez se interesse pelo seguinte material:\n", "\n", " * [Técnicas avançadas para QAOA](/docs/tutorials/advanced-techniques-for-qaoa)\n", " * [Combinar opções de mitigação de erro com o primitivo Estimator](/docs/tutorials/combine-error-mitigation-techniques)\n", "\n", "\n" ] }, { "cell_type": "markdown", "id": "99f8259d-fb92-4fae-ab68-96b1e50929a0", "metadata": {}, "source": [ "\n", "\n", "## Referências\n", "\n", "\\[1] Sciorilli, M., Borges, L., Patti, T. L., García-Martín, D., Camilo, G., Anandkumar, A., & Aolita, L. (2024). Rumo a solucionadores de otimização quântica em grande escala com poucos qubits. arXiv Pré-impressão [arXiv:2401.09421](https://arxiv.org/abs/2401.09421).\n", "\n" ] }, { "cell_type": "markdown", "id": "a4d97730-3c7f-4ce9-8bb9-e4e1c3801c10", "metadata": {}, "source": [ "\n", "\n", "## Pesquisa tutorial\n", "\n", "Responda a esta breve pesquisa para fornecer feedback sobre este tutorial. Suas percepções nos ajudarão a melhorar nossas ofertas de conteúdo e a experiência do usuário.\n", "\n", "[Link para a pesquisa](https://your.feedback.ibm.com/jfe/form/SV_8ANZAlsKSFf6DA2)\n", "\n" ] }, { "cell_type": "markdown", "id": "0c934e9b-2864-4292-94c9-7fa9b5bce007", "metadata": {}, "source": [ "© IBM Corp. 2024-2026\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": 2100 }, "nbformat": 4, "nbformat_minor": 4 }