{ "cells": [ { "cell_type": "markdown", "id": "1a869c2d-ae51-47d3-8a41-bfcf5e505f59", "metadata": {}, "source": [ "---\n", "title: \"QAOAの拡張機能テクニック\"\n", "description: \"このノートブックでは、多数の量子ビットを用いた量子近似最適化アルゴリズム（QAOA）の性能を向上させる高度な手法を紹介します。\"\n", "---\n", "\n", "{/* cspell:ignore pysat, lbrack, frameon, IEICE */}\n", "\n", "\n", "\n", "# QAOAの拡張機能テクニック\n", "\n", "*使用時間推定値: Heron r2 プロセッサ上で3分間（注: これはあくまで推定値です） 実行時間は異なる場合があります。*\n", "\n" ] }, { "cell_type": "markdown", "id": "1a6bbeef-966f-45e1-89aa-e964ef891eeb", "metadata": {}, "source": [ "\n", "\n", "## 前提条件\n", "\n", "ユーザーは、量子近似最適化アルゴリズム（QAOA）の基礎について理解している必要があります。 QAOAの概要については、以下のリソースをご覧ください：\n", "\n", "* 「 [Solve](/docs/tutorials/quantum-approximate-optimization-algorithm)」 によるユーティリティ規模の量子最適化問題に関するチュートリアル\n", "* IBM Quantum® Learning における「 [ユーティリティ規模のQAOA](/learning/courses/quantum-computing-in-practice/utility-scale-qaoa#utility-scale-qaoa) 」の講義（ [「実践的量子コンピューティング」](/learning/courses/quantum-computing-in-practice) コースの一部）\n", "\n", "\n", "\n", "## 学習成果\n", "\n", "このチュートリアルを学習した後、ユーザーは以下のことができるようになります：\n", "\n", "* QAOAのトランスパイルを改善し、QAOAのパフォーマンス向上を図るための高度な手法を活用する\n", "\n", "このチュートリアルの内容に関する詳しい解説については、 [こちらのQiskitの動画](https://youtu.be/rBfK-l-qSNk?si=PC28gFAdu4JYSYdk)をご覧ください。\n", "\n" ] }, { "cell_type": "markdown", "id": "ea97567d-810f-4cca-8edf-a47d70ea870a", "metadata": {}, "source": [ "\n", "\n", "## 背景\n", "\n", "このチュートリアルでは、多数の量子ビットにおいて**量子近似最適化アルゴリズム（QAOA）** の性能を向上させるための2つの高度な手法を紹介します。\n", "\n", "このノートには高度なテクニックが含まれている：\n", "\n", "* **SAT初期マッピングを用いたSWAP戦略** ：これは、SWAP戦略とSATソルバーを組み合わせて、QPU上で使用する物理量子ビットの選択精度を向上させるために、QAOA向けに特別に設計されたトランスパイラ・パスである。 SWAP戦略は、QAOA演算子の可換性を活用してゲートの順序を入れ替え、SWAPゲートの層を同時に実行できるようにすることで、回路の深さを低減するものである [\\[1\\]](#references)。 SATソルバーは、回路内の量子ビットをデバイス上の物理量子ビットにマッピングするために必要なSWAP演算の回数を最小化する初期マッピングを見つけるために使用される [\\[2\\]](#references)。\n", "* **CVaR 目的関数** ：通常、QAOAの目的関数としてはコストハミルトニアンの期待値が用いられるが、 [\\[3\\]](#references) で示されたように、期待値ではなく分布の尾部に焦点を当てることで、組み合わせ最適化問題におけるQAOAの性能を向上させることができる。 CVaR によってこれが実現されます。 検討中の最適化問題に対応する目的関数値を持つ一連のショットについて、信頼水準 $\\alpha \\in [0, 1]$ における条件付きバリュー・アット・リスク（ CVaR ）は、 $\\alpha$ のベストショットの平均として定義される [\\[3\\]](#references)。\n", " したがって、 $\\alpha = 1$ は標準的な期待値に対応し、 $\\alpha=0$ は与えられたショットの最小値に対応し、 $\\alpha \\in (0, 1)$ は、より良いショットに重点を置きつつも、最適化のランドスケープを滑らかにするためにある程度の平均化を行うというトレードオフを表しています。 さらに、 CVaR は、目的関数の推定精度を向上させるための誤差低減手法として利用することができる [\\[4\\]](#references)。\n", "\n", "このチュートリアルの最後には、これらの手法を活用して、最適化問題に対してQAOAを実行する際に最良の結果を得られるようになるはずです。\n", "\n" ] }, { "cell_type": "markdown", "id": "40fb546e-85e0-450b-a5ea-5d08950d129f", "metadata": {}, "source": [ "\n", "\n", "## 要件\n", "\n", "このチュートリアルを始める前に、以下のものがインストールされていることを確認してください：\n", "\n", "* Qiskit SDK v2.0 またはそれ以降、 [可視化](/docs/api/qiskit/visualization)サポート付き\n", "* v0.43Qiskit Runtime またはそれ以降 (`pip install qiskit-ibm-runtime`)\n", "* 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", "## セットアップ\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", "### 最大切断問題\n", "\n", "QAOAを用いて、100個のノードを持つグラフ上の**最大カット**問題を解いてみましょう。\n", "最大切断問題（max-cut problem）は、グラフ $G = (V, E)$ 上で定義される組み合わせ最適化問題である。ここで、 $V$ は頂点の集合であり、 $E$ は辺の集合である。 目的は、頂点を $S$ と $V \\setminus S$ の2つの集合に分割し、これら2つの集合間の辺の数を最大化することです。\n", "この例では、ハードウェア結合マップに基づいた100ノードのグラフを使用します。\n", "\n" ] }, { "cell_type": "markdown", "id": "663d13f5-a5f7-4b67-a89b-26deb41224ec", "metadata": {}, "source": [ "\n", "\n", "## 小規模シミュレータの例\n", "\n", "このチュートリアルの目的は、シミュレータでは処理しきれない規模においてQAOAがどのように動作するかを示すことであるため、この手順は省略します。\n", "\n", "シミュレータを用いたQAOAワークフローを試してみたい方は、 「[量子近似最適化アルゴリズム](/docs/tutorials/quantum-approximate-optimization-algorithm) 」のチュートリアルをご覧ください。\n", "\n" ] }, { "cell_type": "markdown", "id": "6ca05a7c-5fde-4485-a3ad-c0ba02844e50", "metadata": {}, "source": [ "\n", "\n", "## 大規模なハードウェアの例\n", "\n" ] }, { "cell_type": "markdown", "id": "b825afbf-10fd-4926-bd65-05272044f107", "metadata": {}, "source": [ "\n", "\n", "### ステップ1：古典的な入力を量子問題にマッピングする\n", "\n", "\n", "\n", "#### グラフ → ハミルトン\n", "\n", "まず、その問題をQAOAに適した量子回路にマッピングします。 このプロセスの詳細については[、QAOA入門チュートリアル](/docs/tutorials/quantum-approximate-optimization-algorithm)をご覧ください。\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", "### ステップ2：量子ハードウェア実行に向けた問題の最適化\n", "\n", "\n", "\n", "#### SAT初期マッピングを用いたSWAP戦略\n", "\n", "本講演では、 **SATイニシャル・マッピングを用いたSWAPストラテジーを**用いたQAOA回路の構築と最適化の方法を紹介する。SWAPストラテジーは、2次問題に適用されるQAOA用に特別に設計されたトランスパイラー・パスである。\n", "\n", "この例では、2量子ビットゲートが交互に配置されたブロックに対してSWAP挿入戦略を選択する。これは結合マップ上で同時に実行可能なSWAPゲートの層を適用するものである。 この戦略は [\\[1\\]](#references) で提示されており、標準化されたQiskitトランスパイラパスとして公開されている（参照 [`Commuting2qGateRouter`](/docs/api/qiskit/qiskit.transpiler.passes.Commuting2qGateRouter)`Commuting2qGateRouter`）に渡し込まれる。 この例ではラインスワップ戦略を使用します。\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", "#### SATマッパーを用いてグラフを再マッピングする\n", "\n", "回路がコミューティングゲートのみで構成されている場合でも（QAOA回路がこれに該当するが、アイジング・ハミルトニアンのトロッター化シミュレーションも同様である）、適切な初期マッピングを見つけることは困難な課題である。 [\\[2\\]](#references) で提案されたSATベースの手法を用いることで、ゲートが可換な回路に対して効果的な初期マッピングを見出すことができ、その結果、必要なSWAP層の数を大幅に削減できる。 論文で示されているように、この手法は最大 *500キュービット*まで拡張可能であることが実証されている。\n", "\n", "以下のコードは、Matsuoらの `SATMapper` 、グラフを再マッピングする方法を示している。 このプロセスにより、指定されたSWAP戦略に対してより最適な初期状態に問題をマッピングすることができ、その結果、回路の実行に必要なSWAPレイヤーの数を大幅に削減することができる。\n", "\n", "`SATMapper` では、良い初期マッピングを見つける問題はSAT問題として定式化される。 このようなQAOA回路の初期写像を求めるためにSATソルバーが用いられる。 `python-sat` (`pysat` ) はSATソルバー用の Python ライブラリで、この例ではSAT問題を解くのに使う。\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", "#### SWAP戦略とSATマッピングを用いてQAOA回路を構築する\n", "\n", "SWAPストラテジーをコスト・オペレーター層に適用したいだけなので、後で変換して最終的なQAOA回路に追加する分離ブロックを作ることから始める。\n", "\n", "これには、Qiskitのクラスを [`QAOAAnsatz`](/docs/api/qiskit/qiskit.circuit.library.QAOAAnsatz) 活用できます。 「」および `mixer_operator` 「」フィールド `initial_state` に空の回路を入力し、分離されたコスト演算子レイヤーを構築していることを確認します。\n", "また、RZZゲートがSWAPゲートの隣に配置されるように、この `edge_coloring` 写像を定義する。 この戦略的な配置により、CX便の欠航をうまく活用し、ルートの最適化を通じてパフォーマンスを向上させることができます。\n", "`create_qaoa_swap_circuit` この処理は、関数内で実行されます。\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", "## ステップ 3: `IBM Quantum` プリミティブを使用して実行する\n", "\n", "それでは、ハードウェア実行の準備を始めましょう。 まず最初に、変分量子最適化アルゴリズムの枠組み内で利用するために [\\[3\\]](#references) で導入された、条件付きバリュー・アット・リスク（ CVaR ）のコスト関数を定義する。\n", "\n", "信頼水準 $α ∈ (0, 1]$ についての確率変数 $X$ の CVaR は、次のように定義される。 $CVaR_{\\alpha}(X) = \\mathbb{E} \\lbrack X | X \\leq F_X^{-1}(\\alpha) \\rbrack$ ここで、 $F_X^{-1}(p)$ は、 $X$ の逆累積分布関数である。言い換えると、 CVaR は、 $X$ の分布の下側 $\\alpha$ -tailの期待値である。\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": [ "前述の通り [\\[4\\]](#references)、 CVaR はエラー軽減手法として利用することができる。 この例では、回路に関連する[層ごとのゲート誤差](/docs/guides/qpu-information#2q-error-layered) （EPLG）に基づいて、 $\\alpha$ およびショット数を決定します。\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", "## ステップ4：後処理を行い、結果を希望の古典形式で返す\n", "\n", "それでは、結果を可視化し、その後、後処理を行ってカットの値を求めましょう。\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": [ "以下は、サンプリングされたビット列から最適な解を取得するものです：\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": [ "**最大カット**問題に対するハミルトニアン $H_C$ について考える。 グラフの各頂点を、状態 $|0\\rangle$ または $|1\\rangle$ にある量子ビットに対応させるとする。ここで、値は、その頂点が属する集合を表す。 この問題の目的は、 $(v_1, v_2)$ において、 $v_1 = |0\\rangle$ かつ $v_2 = |1\\rangle$ となる辺の数、あるいはその逆となる辺の数を最大化することです。 各量子ビットに $Z$ 演算子を割り当てると、ここで\n", "\n", "$$\n", " Z|0\\rangle = |0\\rangle \\qquad Z|1\\rangle = -|1\\rangle,\n", "$$\n", "\n", "また、 $(v_1, v_2)$ という辺は、 $(Z_1|v_1\\rangle) \\cdot (Z_2|v_2\\rangle) = -1$ の固有値である場合にカットに属する。言い換えれば、 $v_1$ および $v_2$ に関連付けられた量子ビットが異なる場合である。 同様に、 $(Z_1|v_1\\rangle) \\cdot (Z_2|v_2\\rangle) = 1$ の固有値が 0 である場合、 $(v_1, v_2)$ は解の集合に含まれない。\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": [ "最後に、 CVaR の結果に基づいてグラフを描いてみよう。\n", "CVaR の結果に基づいて、グラフ・ノードを2つの集合に分割する。\n", "最初のセットのノードは灰色で、2番目のセットのノードは紫色で着色されている。\n", "2つのセット間のエッジは、パーティショニングによってカットされるエッジである。\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", "## 参照\n", "\n", "\\[1] ヴァイデンフェラー、J、 バロール、L． ガコン、J、 トルノー、C、 ベロ、L、 ヴォーナー、S.、エッガー、D. J. (2022). 量子近似最適化アルゴリズムの超伝導量子ビットベースのハードウェア上でのスケーリング。 Quantum, 6, 870.\n", "\n", "\\[2] 松尾、A、 山下、S, & Egger, D. J. (2023). SWAPゲート挿入における初期マッピング問題へのSATアプローチ。 電子情報通信学会論文誌, 106(11), 1424-1431.\n", "\n", "\\[3] Barkoutsos, P. K、 ナニチーニ、G、 ロバート、A、 Tavernelli, I., & Woerner, S. (2020). CVaR を用いた変分量子最適化の改善. Quantum, 4, 256.\n", "\n", "\\[4] バロン、S. V、 エッガー、D． ペロフスキー、E、 バーツキ、A、 アイデンベンツ、S、 Lehmkuehler, M., & Woerner, S. (2023). ノイズのあるサンプルから計算されたノイズのない期待値の証明可能な境界。 arXiv preprint arXiv:2312.00733.\n", "\n" ] }, { "cell_type": "markdown", "id": "a6a5bbfe-a159-4dc1-9333-488737aff503", "metadata": {}, "source": [ "\n", "\n", "## 次のステップ\n", "\n", "\n", " この作品が興味深かった方は、以下の資料もご参照ください：\n", "\n", " * [難解な十種競技](https://arxiv.org/pdf/2504.03832) ：従来の最適化アルゴリズムでは解決が困難な10の最適化問題のリストであり、本チュートリアルで紹介した手法を検証するための良いユースケースとなる可能性があります。\n", " * QAOAベースのワークフローの成果をさらに向上させるための、 [量子最適化に関するベストプラクティスをまとめたリポジトリです](https://github.com/qiskit-community/qopt-best-practices)。\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 }