{ "cells": [ { "cell_type": "markdown", "id": "2114652b-8f1f-4ba1-817b-48e98e3c6053", "metadata": {}, "source": [ "---\n", "title: \"최대 절단 요구 사항을 줄이기 위한 파울리 상관 인코딩\"\n", "description: \"양자 연산 효율을 높이기 위해 파울리 상관 인코딩을 사용하여 최적화 문제를 큐비트로 인코딩한다.\"\n", "---\n", "\n", "{/* cspell:ignore lbrack setminus coloneqq rbrack binom rhobeg nfev PCEFQ */}\n", "\n", "\n", "\n", "# 최대 절단 요구 사항을 줄이기 위한 파울리 상관 인코딩\n", "\n", "*예상 소요 시간: Eagle r3 프로세서 기준 35분 (참고: 이는 예상치에 불과합니다.) (실행 시간은 다를 수 있습니다.)*\n", "\n" ] }, { "cell_type": "markdown", "id": "7239458e-d833-490e-8462-eaf2b5a115d4", "metadata": {}, "source": [ "\n", "\n", "## 학습 성과\n", "\n", "* 다체 파울리 스트링이 어떻게 고전적 최적화 문제의 다항식 차수 압축을 가능하게 하는지 포함하여, 파울리 상관 인코딩(PCE)의 이론적 원리를 이해한다.\n", "* 실제 환경에서 PCE를 구현하여, 가까운 시일 내에 상용화될 양자 하드웨어에서 대규모 최적화 문제를 인코딩하고 해결한다.\n", "\n", "\n", "\n", "## 전제조건\n", "\n", "* [변분 양자 알고리즘](/learning/courses/variational-algorithm-design)\n", "* [QAOA와 최대 절단](/docs/tutorials/quantum-approximate-optimization-algorithm)\n", "\n" ] }, { "cell_type": "markdown", "id": "8a343d18-ab46-431f-899d-0664c2f99cc0", "metadata": {}, "source": [ "\n", "\n", "## 배경\n", "\n", "이 튜토리얼에서는 최적화 문제를 양자 연산에 더 효율적으로 큐비트로 인코딩하도록 설계된 접근 방식인 *폴리 상관관계 인코딩* (PCE) [\\[1\\]](#references) 을 소개합니다. PCE는 최적화 문제의 기존 변수를 다항식 폴리 행렬 상관관계에 매핑하여 문제의 공간 요구 사항을 다항식으로 압축합니다. PCE를 사용하면 인코딩에 필요한 큐비트 수가 줄어들어 큐비트 리소스가 제한된 단기 양자 장치에 특히 유리합니다. 또한, PCE는 본질적으로 불모지를 완화하여 이러한 현상에 대한 초다항식 복원력을 제공한다는 것이 분석적으로 입증되었습니다. 이 기본 제공 기능을 통해 양자 최적화 솔버에서 전례 없는 성능을 구현할 수 있습니다.\n", "\n" ] }, { "cell_type": "markdown", "id": "c133831c-1eff-4913-aff6-8c0d82df9d61", "metadata": {}, "source": [ "\n", "\n", "### 개요\n", "\n", "PCE 접근법은 아래 [\\[1\\]](#references) 의 그림 1에 나와 있는 바와 같이 세 가지 주요 단계로 구성됩니다:\n", "\n", "1. 최적화 문제를 폴리 상관 관계 공간으로 인코딩합니다.\n", "2. 양자 고전 최적화 솔버를 사용하여 문제를 해결합니다.\n", "3. 솔루션을 원래 최적화 공간으로 다시 디코딩합니다.\n", " PCE 접근 방식은 폴리 상관 행렬을 처리할 수 있는 모든 양자 최적화 솔버에 적용할 수 있습니다.\n", "\n" ] }, { "attachments": {}, "cell_type": "markdown", "id": "40a636a3-c0c0-42ba-a68a-2abcb8a7187b", "metadata": {}, "source": [ "![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": [ "[\\[1\\]](#references) 의 그림 1에서는 PCE 접근법을 설명하기 위해 [최대 절단](/docs/tutorials/quantum-approximate-optimization-algorithm) 문제를 예시로 사용하였다. $m=9$ 개의 노드를 가진 최대 절단 문제는 파울리 상관 공간으로 인코딩되며, 이는 최적화 문제를 상관 행렬로 표현합니다. 구체적으로, 이는 $n=3$ 큐비트 간 2체 파울리 행렬 상관관계입니다. $(Q_1, Q_2, Q_3)$. 노드의 색상은 각 인코딩된 노드에 사용된 파울리 문자열을 나타냅니다.\n", "예를 들어, 이진 변수 $x_1$ 에 해당하는 노드 1은 $Z_1 \\otimes Z_2 \\otimes I_3$ 의 기대값으로 인코딩되는 반면, $x_8$ 는 $I_1 \\otimes Y_2 \\otimes Y_3$ 로 인코딩됩니다.\n", "이는 문제의 $m$ 개 변수를 $ n = O(m^{1/2})$ 개의 큐비트로 압축하는 것과 같습니다. 더 넓게 보면, $k $ -체 상관관계는 $k>1$ 인 경우, $k$ 차원의 다항식 압축을 가능하게 한다. 선택된 파울리 집합은 서로 교환하는 파울리 문자열의 세 부분집합으로 구성되어 있어, 단 세 가지 측정 설정만으로 모든 $m$ 상관관계를 실험적으로 추정할 수 있다.\n", "\n", "원래의 최대 절단(max-cut) 목적 함수를 모방하는 파울리 기대값의 손실 함수 $\\mathcal{L}$ 가 구성된다. 그런 다음 손실 함수는 [변분 양자 고유값](/learning/courses/quantum-diagonalization-algorithms/vqe) 해법기(VQE)와 같은 양자-고전 최적화 솔버를 사용하여 최적화됩니다.\n", "\n", "최적화가 완료되면, 해는 원래의 최적화 공간으로 다시 디코딩되어 최적의 최대 절단 해를 산출합니다.\n", "\n", "\n", "\n", "## 요구사항\n", "\n", "이 튜토리얼을 시작하기 전에 다음이 설치되어 있는지 확인하세요:\n", "\n", "* Qiskit SDK v1.0 또는 이후 버전, [시각화](/docs/api/qiskit/visualization) 지원 기능 포함\n", "* Qiskit Runtime v0.22 또는 이후 (`pip install qiskit-ibm-runtime`)\n", "\n" ] }, { "cell_type": "markdown", "id": "adfa1c9b-0dd3-42d0-afd9-bce648cf668e", "metadata": {}, "source": [ "\n", "\n", "## 설정\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", "## 소규모 시뮬레이터 예시\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", "### 1단계: 고전적 입력을 양자 문제에 매핑하기\n", "\n", "\n", "\n", "#### 최대 절단 문제\n", "\n", "최대 절단 문제(max-cut problem)는 그래프 $G = (V, E)$ 위에서 정의되는 조합 최적화 문제로, 여기서 $V$ 는 정점의 집합이고 $E$ 는 변의 집합이다. 목표는 정점들을 두 집합, $S$ 와 $V \\setminus S$ 로 나누되, 두 집합 사이의 변의 개수가 최대가 되도록 하는 것이다.\n", "맥스컷(max-cut) 문제에 대한 자세한 설명은 [양자 근사 최적화 알고리즘](/docs/tutorials/quantum-approximate-optimization-algorithm) 튜토리얼을 참고하시기 바랍니다.\n", "최대 절단 문제(max-cut problem)는 [QAOA(Quantum Annealing)를 위한 고급 기법](/docs/tutorials/advanced-techniques-for-qaoa) 튜토리얼에서도 예시로 사용됩니다.\n", "해당 튜토리얼에서는 QAOA 알고리즘을 사용하여 최대 절단 문제를 해결합니다.\n", "\n", "-hamiltonian\" />\n", "\n", "#### 그래프 -> 해밀턴 그래프\n", "\n", "먼저 노드가 100개인 무작위 그래프를 생각해 보자.\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": [ "우리는 100개의 노드로 구성된 그래프를 9개의 큐비트에 걸친 2체 파울리 행렬 상관관계로 인코딩합니다(아래 설명 참조). 이 그래프는 상관 행렬로 표현되며, 각 노드는 파울리 문자열로 인코딩됩니다. 파울리 끈의 기대값의 부호는 노드의 분할을 나타낸다. 예를 들어, 노드 0은 파울리 문자열 $\\prod_0 = I_{8} \\otimes ... I_2 \\otimes X_1 \\otimes X_0$ 로 표현됩니다. 이 파울리 문자열의 기대값의 부호는 노드 0의 분할을 나타냅니다. 우리는 양자 얽힘( $\\prod$ )에 대한 *파울리 상관 인코딩* (PCE)을 다음과 같이 정의한다\n", "\n", "$x_i \\coloneqq \\textit{sgn}(\\langle\\prod_i \\rangle),$\n", "\n", "여기서 $x_i$ 는 노드 $i$ 의 파티션이고 $\\langle \\prod_i \\rangle \\coloneqq \\langle \\psi |\\prod_i| \\psi \\rangle $ 는 양자 상태 $|\\psi \\rangle$ 에 대한 폴리 문자열 인코딩 노드 $i$ 의 기대값입니다.\n", "\n" ] }, { "cell_type": "markdown", "id": "678e00fb-5bb9-450e-8229-0eab5676057a", "metadata": {}, "source": [ "이제 PCE를 사용하여 그래프를 해밀턴으로 인코딩해 보겠습니다.\n", "노드를 세 가지 세트로 나눕니다: $S_1$, $S_2$, $S_3$ 로 나눕니다. 그런 다음 각 세트의 노드를 각각 $X$, $Y$, $Z$ 로 폴리 문자열을 사용하여 인코딩합니다.\n", "\n" ] }, { "cell_type": "markdown", "id": "4d5d48e5-ebe8-4b36-9496-288f40174a7b", "metadata": {}, "source": [ "모든 노드를 인코딩하는 데 필요한 노드 수와 큐비트 수 간의 관계를 도출해야 합니다. 인코딩에 가능한 모든 순열을 적용하면 다음과 같은 결과가 나옵니다:\n", "\n", "$$\n", "m=3\\binom{n}{k}.\n", "$$\n", "\n", "이 예제에서는 $k=2$ 를 고려하므로,\n", "\n", "$$\n", "m = \\frac{3}{2} n(n-1).\n", "$$\n", "\n", "따라서, 특정 수의 노드 $m$ 를 표현하는 데 필요한 큐비트 수 $n$ 는 다음과 같이 계산됩니다:\n", "\n", "$$\n", "n = \\left\\lceil \\frac{1 + \\sqrt{1 + \\tfrac{8}{3}m}}{2} \\right\\rceil.\n", "$$\n", "\n", "*$\\lceil \\cdot \\rceil$ 기호는 천장 함수를 나타내며, 이는 모든 실수를 다음 정수로 올림합니다. 이를 통해 큐비트의 개수가 정수가 되도록 보장합니다.*\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", "### 2단계: 양자 하드웨어 실행을 위한 문제 최적화\n", "\n", "\n", "\n", "#### 양자 회로\n", "\n", "여기서 상태 $|\\psi \\rangle$ 는 $\\mathbf{\\theta}$ 로 매개변수화되고, 가변적 접근 방식을 사용하여 이러한 매개변수 $\\mathbf{\\theta}$ 를 최적화합니다.\n", "이 튜토리얼에서는 표현력과 구현의 용이성 때문에 변형 알고리즘에 `efficient_su2` ansatz를 사용합니다.\n", "또한 이 튜토리얼의 뒷부분에서 소개할 완화된 손실 기능도 사용합니다.\n", "그 결과, 더 적은 큐비트와 더 얕은 회로 깊이로 대규모 문제를 해결할 수 있습니다.\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", "#### 손실 함수\n", "\n", "손실 함수 $\\mathcal{L}$ 의 경우, [\\[1\\]](#references) 에 설명된 대로 최대 절단(max-cut) 목적 함수의 완화 형태를 사용하며, 이는 $\\mathcal{V}(\\mathbf{x}) \\coloneqq \\sum_{(i, j) \\in E} W_{i, j}(1-x_i x_j)$ 로 정의된다. 여기서 $W_{i, j}$ 는 변 $(i, j)$ 의 가중치를 나타내고, $x_i$ 는 노드 $i$ 의 분할을 나타낸다.\n", "손실 함수 $\\mathcal{L}$ 는 다음과 같이 주어진다:\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", "여기서 최대 절단(max-cut) 목적 함수는 노드를 인코딩하는 파울리 스트링의 기대값에 대한 부드러운 쌍곡 탄젠트 함수로 대체된다. 해법기의 성능을 향상시키기 위해 정규화 항 $\\mathcal{L}^{(\\text{reg})}$ 과 큐비트 수에 비례하는 재스케일링 계수 $\\alpha$ 를 도입한다.\n", "\n", "정규화 용어는 다음과 같이 정의됩니다:\n", "\n", "$\\mathcal{L}^{(\\text{reg})}$ 는 다음과 같이 정의됩니다 $\\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", "여기서 $\\beta=1/2$, $\\nu = |E|/2 + (m -1) /4$, $|E|$ 는 변의 개수이며, $m$ 는 그래프의 정점 개수이다.\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", "### 3단계: `Qiskit primitives` 명령어로 실행합니다\n", "\n" ] }, { "cell_type": "markdown", "id": "583ba786-e2e9-4593-bf75-00723b589d78", "metadata": {}, "source": [ "이 튜토리얼에서는 설명을 위해 최적화 루프에서 를 설정합니다 `max_iter=50` . 반복 횟수를 늘리면 더 나은 결과를 기대할 수 있습니다.\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", "### 4단계: 후처리 수행 및 원하는 클래식 형식으로 결과 반환\n", "\n", "노드의 파티션은 노드를 인코딩하는 폴리 문자열의 기대 값의 부호를 평가하여 결정됩니다.\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": [ "노드의 분할을 활용하여 최대 절단 문제의 절단 크기를 계산할 수 있습니다.\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": [ "훈련이 완료되면 고전적인 후처리 단계로 솔루션을 개선하기 위해 한 차례의 단일 비트 스왑 검색을 수행합니다.\n", "이 과정에서 두 노드의 파티션을 교체하고 잘라낸 크기를 평가합니다. 컷 크기가 개선되면 스왑을 유지합니다. 에지로 연결된 모든 가능한 노드 쌍에 대해 이 과정을 반복합니다.\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", "# 대규모 하드웨어 예시\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", "## 다음 단계\n", "\n", "\n", " 이 글이 흥미로웠다면, 다음 자료도 관심 있게 읽어보시기 바랍니다:\n", "\n", " * [QAOA용 고급 기술](/docs/tutorials/advanced-techniques-for-qaoa)\n", " * [오류 완화 옵션을 추정기 프리미티브와 결합하십시오.](/docs/tutorials/combine-error-mitigation-techniques)\n", "\n", "\n" ] }, { "cell_type": "markdown", "id": "99f8259d-fb92-4fae-ab68-96b1e50929a0", "metadata": {}, "source": [ "\n", "\n", "## 참조\n", "\n", "\\[1] Sciorilli, M., 보르헤스, L., 패티, T. L., 가르시아-마르틴, D., 카밀로, G., 아난드쿠마르, A., & 아올리타, L. (2024). 소수의 큐비트를 활용한 대규모 양자 최적화 솔버를 향하여. arXiv 사전 출판본 [arXiv:2401.09421](https://arxiv.org/abs/2401.09421).\n", "\n" ] }, { "cell_type": "markdown", "id": "a4d97730-3c7f-4ce9-8bb9-e4e1c3801c10", "metadata": {}, "source": [ "\n", "\n", "## 튜토리얼 설문조사\n", "\n", "이 튜토리얼에 대한 피드백을 제공하려면 간단한 설문조사에 참여해 주세요. 여러분의 인사이트는 콘텐츠 제공과 사용자 경험을 개선하는 데 도움이 됩니다.\n", "\n", "[설문조사 링크](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 }