{ "cells": [ { "cell_type": "code", "execution_count": 35, "id": "a005e247", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['Ket v0.10.0',\n", " 'libket v0.7.1 [rustc 1.97.0 (2d8144b78 2026-07-07) x86_64-unknown-linux-gnu]',\n", " 'kbw v0.5.1 [rustc 1.97.0 (2d8144b78 2026-07-07) x86_64-unknown-linux-gnu]']" ] }, "execution_count": 35, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from typing import Callable\n", "from functools import partial\n", "from functools import reduce\n", "from operator import add\n", "\n", "from scipy.optimize import minimize, OptimizeResult\n", "from IPython.display import display\n", "\n", "from ket import *\n", "from ket import ket_version\n", "\n", "ket_version()" ] }, { "cell_type": "markdown", "id": "7ce6969b", "metadata": {}, "source": [ "# Quantum Approximate Optimization Algorithm (QAOA)\n", "\n", "The **Quantum Approximate Optimization Algorithm (QAOA)** is a hybrid quantum-classical\n", "variational algorithm designed to find approximate solutions to combinatorial optimization problems.\n", "Tailored for near-term (NISQ) devices, QAOA functions as a discretized version of adiabatic quantum computing.\n", "\n", "At its core, the algorithm prepares a uniform initial quantum state $|+\\rangle^{\\otimes n}$, which then undergoes\n", "$p$ alternating layers of unitary evolution driven by two complementary Hamiltonians. Finally, the circuit is\n", "measured and the evolution parameters are fine-tuned by a classical optimizer.\n", "\n", "To understand how QAOA operates, let's explore its three main building blocks:" ] }, { "cell_type": "markdown", "id": "d281d2de", "metadata": {}, "source": [ "## 1. Problem Hamiltonian ($H_C$)\n", "\n", "This block encodes the classical objective (or cost) function of our optimization problem into a quantum format.\n", "\n", "- **Role:** The decision variables of the problem are mapped to Pauli-Z operators in the computational basis. The optimal solution corresponds to the lowest energy eigenstate (the ground state) of this Hamiltonian.\n", "\n", "- **Circuit Evolution:** The quantum state evolves under the problem Hamiltonian according to the operator: $\\hat U_C(\\gamma_k) = e^{-i\\gamma_k H_C}$" ] }, { "cell_type": "markdown", "id": "83b2cc21", "metadata": {}, "source": [ "## 2. Mixer Hamiltonian ($H_M$)\n", "\n", "To effectively explore the solution space and prevent the system from getting stuck, we introduce the mixer Hamiltonian.\n", "\n", "- **Role:** The fundamental requirement for $H_M$ is that it **must not commute** with the problem Hamiltonian $H_C$. The standard implementation uses a sum of Pauli-X operators acting on all qubits.\n", "\n", "- **Circuit Evolution:** The mixer creates transitions between different computational basis configurations, driven by the operator: $\\hat U_M(\\beta_k) = e^{-i\\beta_k H_M}$" ] }, { "cell_type": "markdown", "id": "16c57984", "metadata": {}, "source": [ "## 3. Classical Optimizer\n", "\n", "The iterative search for optimal parameters is handed over to a classical processor.\n", "\n", "- **Role:** By measuring the final state of the quantum circuit, we obtain the expected value of the cost function: $F(\\gamma, \\beta) = \\langle\\psi(\\gamma, \\beta)|H_C|\\psi(\\gamma, \\beta)\\rangle$. The classical optimizer evaluates this outcome and computes a new set of angles, $\\gamma$ and $\\beta$, aiming to minimize this expected value in the next iteration.\n", "\n", "- **Significance:** Once the optimizer converges on the ideal parameters $(\\gamma, \\beta)$, the quantum circuit will output the state encoding the approximate solution with high probability. Selecting a robust classical optimization routine is crucial to avoiding local minima and mitigating challenges like _barren plateaus_." ] }, { "cell_type": "markdown", "id": "4a682a55", "metadata": {}, "source": [ "## Implementation with Ket\n", "\n", "Let's implement the base QAOA structure using `ket`. We define functions to:\n", "\n", "1. Apply a single QAOA layer (`qaoa_layer`).\n", "2. Build the full $p$-layer ansatz (`ansatz`).\n", "3. Execute the complete hybrid optimization loop (`qaoa`).\n", "\n", "Ket's {func}`~ket.gates.evolve` function accepts a {class}`~ket.expv.Hamiltonian` object and automatically\n", "decomposes the time-evolution operator $e^{-i\\theta H}$ into native quantum gates, making the implementation\n", "concise and readable." ] }, { "cell_type": "code", "execution_count": 36, "id": "530bd12f", "metadata": {}, "outputs": [], "source": [ "def qaoa_layer(\n", " problem_h: Callable[[Quant], Hamiltonian],\n", " mixer_h: Callable[[Quant], Hamiltonian],\n", " qubits: Quant,\n", " gamma: float,\n", " beta: float,\n", "):\n", " \"\"\"\n", " Applies a single layer (p=1) of the QAOA Ansatz to the provided qubits.\n", "\n", " Args:\n", " problem_h: Function that takes the allocated qubits and returns the problem Hamiltonian (cost function).\n", " mixer_h: Function that takes the allocated qubits and returns the mixer Hamiltonian.\n", " qubits: Reference to the qubits allocated in the current process.\n", " gamma: Variational parameter associated with the evolution of the problem Hamiltonian.\n", " beta: Variational parameter associated with the evolution of the mixer Hamiltonian.\n", " \"\"\"\n", " evolve(problem_h(qubits) * gamma)\n", " evolve(mixer_h(qubits) * beta)\n", "\n", "\n", "def ansatz(\n", " problem_h: Callable[[Quant], Hamiltonian],\n", " mixer_h: Callable[[Quant], Hamiltonian],\n", " initial_state: Callable[[any], None],\n", " qubits: Quant,\n", " gamma: list[float],\n", " beta: list[float],\n", "):\n", " \"\"\"\n", " Constructs the complete QAOA quantum circuit, applying the initial state\n", " and the 'p' layers of alternating evolution.\n", "\n", " Args:\n", " problem_h: Problem Hamiltonian generator function.\n", " mixer_h: Mixer Hamiltonian generator function.\n", " initial_state: Function that prepares the appropriate initial state on the qubits\n", " (e.g., uniform superposition with H gates, or Dicke state for XY Mixer).\n", " qubits: Reference to the circuit qubits.\n", " gamma: List with the 'p' variational gamma parameters.\n", " beta: List with the 'p' variational beta parameters.\n", " \"\"\"\n", " initial_state(qubits)\n", " for g, b in zip(gamma, beta):\n", " qaoa_layer(problem_h, mixer_h, qubits, g, b)\n", "\n", "\n", "def qaoa(\n", " problem_h: Callable[[Quant], Hamiltonian],\n", " mixer_h: Callable[[Quant], Hamiltonian],\n", " initial_state: Callable[[any], None],\n", " num_qubits: int,\n", " p: int,\n", " dt: float = 0.5,\n", " method: str = \"COBYLA\",\n", ") -> tuple[OptimizeResult, Samples]:\n", " \"\"\"\n", " Executes the QAOA hybrid (classical-quantum) optimization loop.\n", "\n", " Initializes parameters inspired by a quantum annealing process\n", " (increasing gamma, decreasing beta) and uses a classical optimizer to\n", " find the configuration that minimizes the expected value of the problem Hamiltonian.\n", "\n", " Args:\n", " problem_h: Problem Hamiltonian generator function.\n", " mixer_h: Mixer Hamiltonian generator function.\n", " initial_state: Initial state preparation function.\n", " num_qubits: Total number of qubits required for the problem.\n", " p: Number of layers (depth) of the QAOA Ansatz.\n", " dt: Scale factor for the parameter initialization heuristic (default: 0.5).\n", " method: SciPy classical optimization algorithm to use (default: \"COBYLA\").\n", "\n", " Returns:\n", " A tuple containing:\n", " - The OptimizeResult object returned by SciPy with optimization details.\n", " - The final sampling of the optimized state (measurements and counts).\n", " \"\"\"\n", "\n", " def objective(parameters, final=False):\n", " gamma = parameters[:p]\n", " beta = parameters[p:]\n", "\n", " # Instantiates a new Ket Process\n", " process = Process(num_qubits=num_qubits)\n", " qubits = process.alloc(num_qubits)\n", " ansatz(problem_h, mixer_h, initial_state, qubits, gamma, beta)\n", "\n", " if final:\n", " # Samples the final state to retrieve likely solutions\n", " return sample(qubits, 100)\n", "\n", " # Returns the energy (expected value) to the classical optimizer\n", " result = exp_value(problem_h(qubits)).get()\n", " print(f\"{result=}\", end=\"\\r\")\n", " return result\n", "\n", " # Initialization heuristic based on annealing\n", " first_gamma = [i / p * dt for i in range(1, p + 1)] # Increasing\n", " first_beta = [(1 - i / p) * dt for i in range(0, p)] # Decreasing\n", "\n", " # Classical optimization loop\n", " res = minimize(\n", " objective,\n", " first_gamma + first_beta, # Gamma comes first, Beta second\n", " method=method,\n", " )\n", "\n", " # Execute the circuit one last time with optimal parameters to get the probability distribution\n", " final_sample = objective(res.x, final=True)\n", "\n", " return res, final_sample" ] }, { "cell_type": "markdown", "id": "7542e93e", "metadata": {}, "source": [ "## Example 1: Max-Cut\n", "\n", "The **Max-Cut** problem is one of the most widely used benchmarks for quantum optimization algorithms.\n", "It is an NP-Hard graph problem: finding an exact solution becomes classically intractable as the number\n", "of vertices grows.\n", "\n", "Given an undirected graph $G = (V, E)$, the objective is to partition the vertices into two disjoint\n", "sets $A$ and $B$ such that the number of edges crossing the partition is maximized.\n", "\n", "To model this on a quantum computer, we map each graph vertex to a qubit:\n", "\n", "- State $|0\\rangle \\rightarrow$ Vertex belongs to set $A$.\n", "- State $|1\\rangle \\rightarrow$ Vertex belongs to set $B$." ] }, { "cell_type": "markdown", "id": "7a904b24", "metadata": {}, "source": [ "### Max-Cut Hamiltonian Formulation\n", "\n", "For QAOA, we need to mathematically formulate a cost function that evaluates the quality of our cut using Pauli operators. The Pauli-Z operator is perfect for this:\n", "\n", "- $\\left<0|Z|0\\right> = +1$\n", "- $\\left<1|Z|1\\right> = -1$\n", "\n", "For any two vertices connected by an edge $(u, v)$, their interaction is measured by the product $Z_u Z_v$:\n", "\n", "- If both vertices are in the **same set** ($\\left|00\\right>$ or $\\left|11\\right>$), the product $Z_u Z_v$ is $+1$.\n", "- If they are in **different sets** ($\\left|01\\right>$ or $\\left|10\\right>$), the product $Z_u Z_v$ is $-1$.\n", "\n", "We can express the contribution of a single edge to our cut as $\\frac{1}{2}(1 - Z_u Z_v)$. This evaluates to $1$ if the edge is cut, and $0$ if it is not.\n", "\n", "The total Hamiltonian is the sum of these expressions across all edges in the graph. Since classical optimizers typically aim to **minimize** a function, we multiply the Hamiltonian by $-1$. This ensures that the state representing the maximum number of cuts corresponds to the lowest possible energy (the ground state):\n", "\n", "$$H_C = -\\frac{1}{2} \\sum_{(u,\\ v) \\in E} (1 - Z_u Z_v)$$" ] }, { "cell_type": "markdown", "id": "plot_intro", "metadata": {}, "source": [ "### Graph Visualization\n", "\n", "Before solving, let's visualize our problem graph using Plotly for an interactive view.\n", "We define a helper function that draws the graph and highlights cut edges based on a given\n", "partition of vertices." ] }, { "cell_type": "code", "execution_count": 37, "id": "maxcut_plotly_func", "metadata": {}, "outputs": [], "source": [ "def plot_maxcut_graph(\n", " graph_edges: list[tuple[int, int]],\n", " num_nodes: int,\n", " qubits_state: list[int] | int,\n", " title: str = \"Max-Cut Graph\",\n", "):\n", " \"\"\"\n", " Plots the Max-Cut problem graph using Plotly, coloring nodes according to their\n", " partition assignment and highlighting the cut edges.\n", "\n", " Args:\n", " graph_edges: List of tuples representing the graph edges.\n", " num_nodes: Total number of nodes/qubits.\n", " qubits_state: List where the index is the node and the value is the state (0 or 1).\n", " title: Plot title.\n", " \"\"\"\n", " import networkx as nx\n", " import plotly.graph_objects as go\n", "\n", " if isinstance(qubits_state, int):\n", " qubits_state = list(map(int, f\"{qubits_state:0{num_nodes}b}\"))\n", "\n", " G = nx.Graph()\n", " G.add_nodes_from(range(num_nodes))\n", " G.add_edges_from(graph_edges)\n", " pos = nx.spring_layout(G, seed=42)\n", "\n", " # --- Edge traces ---\n", " cut_edge_x, cut_edge_y = [], []\n", " non_cut_edge_x, non_cut_edge_y = [], []\n", " for u, v in graph_edges:\n", " x0, y0 = pos[u]\n", " x1, y1 = pos[v]\n", " if qubits_state[u] != qubits_state[v]:\n", " cut_edge_x += [x0, x1, None]\n", " cut_edge_y += [y0, y1, None]\n", " else:\n", " non_cut_edge_x += [x0, x1, None]\n", " non_cut_edge_y += [y0, y1, None]\n", "\n", " edge_traces = [\n", " go.Scatter(\n", " x=cut_edge_x,\n", " y=cut_edge_y,\n", " mode=\"lines\",\n", " line=dict(width=4, color=\"#e74c3c\"),\n", " name=\"Cut edge\",\n", " hoverinfo=\"none\",\n", " ),\n", " go.Scatter(\n", " x=non_cut_edge_x,\n", " y=non_cut_edge_y,\n", " mode=\"lines\",\n", " line=dict(width=2, color=\"#aaaaaa\", dash=\"dash\"),\n", " name=\"Non-cut edge\",\n", " hoverinfo=\"none\",\n", " ),\n", " ]\n", "\n", " # --- Node traces ---\n", " node_x = [pos[n][0] for n in G.nodes()]\n", " node_y = [pos[n][1] for n in G.nodes()]\n", " node_colors = [\"#e67e22\" if qubits_state[n] == 1 else \"#3498db\" for n in G.nodes()]\n", " node_text = [\n", " f\"Node {n}
Set {'B' if qubits_state[n] == 1 else 'A'} (|{qubits_state[n]}⟩)\"\n", " for n in G.nodes()\n", " ]\n", " node_labels = [str(n) for n in G.nodes()]\n", "\n", " node_trace = go.Scatter(\n", " x=node_x,\n", " y=node_y,\n", " mode=\"markers+text\",\n", " hoverinfo=\"text\",\n", " hovertext=node_text,\n", " text=node_labels,\n", " textposition=\"middle center\",\n", " textfont=dict(size=14, color=\"white\"),\n", " marker=dict(\n", " size=40,\n", " color=node_colors,\n", " line=dict(width=2, color=\"#333\"),\n", " ),\n", " name=\"Nodes\",\n", " showlegend=False,\n", " )\n", "\n", " num_cuts = sum(1 for u, v in graph_edges if qubits_state[u] != qubits_state[v])\n", "\n", " fig = go.Figure(\n", " data=edge_traces + [node_trace],\n", " layout=go.Layout(\n", " title=dict(\n", " text=f\"{title} — {num_cuts}/{len(graph_edges)} edges cut\", x=0.5\n", " ),\n", " showlegend=True,\n", " hovermode=\"closest\",\n", " margin=dict(b=20, l=5, r=5, t=50),\n", " xaxis=dict(showgrid=False, zeroline=False, showticklabels=False),\n", " yaxis=dict(showgrid=False, zeroline=False, showticklabels=False),\n", " legend=dict(x=0, y=1),\n", " ),\n", " )\n", " fig.show()" ] }, { "cell_type": "markdown", "id": "prob_instance", "metadata": {}, "source": [ "### Problem Instance\n", "\n", "Let's define our test graph: 5 nodes and 6 edges. The initial partition shown below\n", "is just a sample — the QAOA optimizer will find the best one." ] }, { "cell_type": "code", "execution_count": 38, "id": "ffb1cf5b", "metadata": {}, "outputs": [ { "data": { "application/vnd.plotly.v1+json": { "config": { "plotlyServerURL": "https://plot.ly" }, "data": [ { "hoverinfo": "none", "line": { "color": "#e74c3c", "width": 4 }, "mode": "lines", "name": "Cut edge", "type": "scatter", "x": [ 1, 0.24537112788370613, null, 0.21658684233928793, 0.24537112788370613, null, -0.7503722096196979, -0.7115857606032955, null ], "y": [ 0.03492797469890115, -0.3945287104413233, null, 0.4084010375951407, -0.3945287104413233, null, 0.4088120458522651, -0.45761234770498316, null ] }, { "hoverinfo": "none", "line": { "color": "#aaaaaa", "dash": "dash", "width": 2 }, "mode": "lines", "name": "Non-cut edge", "type": "scatter", "x": [ 1, 0.21658684233928793, null, 0.21658684233928793, -0.7503722096196979, null, 0.24537112788370613, -0.7115857606032955, null ], "y": [ 0.03492797469890115, 0.4084010375951407, null, 0.4084010375951407, 0.4088120458522651, null, -0.3945287104413233, -0.45761234770498316, null ] }, { "hoverinfo": "text", "hovertext": [ "Node 0
Set B (|1⟩)", "Node 1
Set B (|1⟩)", "Node 2
Set A (|0⟩)", "Node 3
Set B (|1⟩)", "Node 4
Set A (|0⟩)" ], "marker": { "color": [ "#e67e22", "#e67e22", "#3498db", "#e67e22", "#3498db" ], "line": { "color": "#333", "width": 2 }, "size": 40 }, "mode": "markers+text", "name": "Nodes", "showlegend": false, "text": [ "0", "1", "2", "3", "4" ], "textfont": { "color": "white", "size": 14 }, "textposition": "middle center", "type": "scatter", "x": [ 1, 0.21658684233928793, 0.24537112788370613, -0.7503722096196979, -0.7115857606032955 ], "y": [ 0.03492797469890115, 0.4084010375951407, -0.3945287104413233, 0.4088120458522651, -0.45761234770498316 ] } ], "layout": { "hovermode": "closest", "legend": { "x": 0, "y": 1 }, "margin": { "b": 20, "l": 5, "r": 5, "t": 50 }, "showlegend": true, "template": { "data": { "bar": [ { "error_x": { "color": "#2a3f5f" }, "error_y": { "color": "#2a3f5f" }, "marker": { "line": { "color": "#E5ECF6", "width": 0.5 }, "pattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 } }, "type": "bar" } ], "barpolar": [ { "marker": { "line": { "color": "#E5ECF6", "width": 0.5 }, "pattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 } }, "type": "barpolar" } ], "carpet": [ { "aaxis": { "endlinecolor": "#2a3f5f", "gridcolor": "white", "linecolor": "white", "minorgridcolor": "white", "startlinecolor": "#2a3f5f" }, "baxis": { "endlinecolor": "#2a3f5f", "gridcolor": "white", "linecolor": "white", "minorgridcolor": "white", "startlinecolor": "#2a3f5f" }, "type": "carpet" } ], "choropleth": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "type": "choropleth" } ], "contour": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "contour" } ], "contourcarpet": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "type": "contourcarpet" } ], "heatmap": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "heatmap" } ], "histogram": [ { "marker": { "pattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 } }, "type": "histogram" } ], "histogram2d": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "histogram2d" } ], "histogram2dcontour": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "histogram2dcontour" } ], "mesh3d": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "type": "mesh3d" } ], "parcoords": [ { "line": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "parcoords" } ], "pie": [ { "automargin": true, "type": "pie" } ], "scatter": [ { "fillpattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 }, "type": "scatter" } ], "scatter3d": [ { "line": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatter3d" } ], "scattercarpet": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattercarpet" } ], "scattergeo": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattergeo" } ], "scattergl": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattergl" } ], "scattermap": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattermap" } ], "scattermapbox": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattermapbox" } ], "scatterpolar": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatterpolar" } ], "scatterpolargl": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatterpolargl" } ], "scatterternary": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatterternary" } ], "surface": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "surface" } ], "table": [ { "cells": { "fill": { "color": "#EBF0F8" }, "line": { "color": "white" } }, "header": { "fill": { "color": "#C8D4E3" }, "line": { "color": "white" } }, "type": "table" } ] }, "layout": { "annotationdefaults": { "arrowcolor": "#2a3f5f", "arrowhead": 0, "arrowwidth": 1 }, "autotypenumbers": "strict", "coloraxis": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "colorscale": { "diverging": [ [ 0, "#8e0152" ], [ 0.1, "#c51b7d" ], [ 0.2, "#de77ae" ], [ 0.3, "#f1b6da" ], [ 0.4, "#fde0ef" ], [ 0.5, "#f7f7f7" ], [ 0.6, "#e6f5d0" ], [ 0.7, "#b8e186" ], [ 0.8, "#7fbc41" ], [ 0.9, "#4d9221" ], [ 1, "#276419" ] ], "sequential": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "sequentialminus": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ] }, "colorway": [ "#636efa", "#EF553B", "#00cc96", "#ab63fa", "#FFA15A", "#19d3f3", "#FF6692", "#B6E880", "#FF97FF", "#FECB52" ], "font": { "color": "#2a3f5f" }, "geo": { "bgcolor": "white", "lakecolor": "white", "landcolor": "#E5ECF6", "showlakes": true, "showland": true, "subunitcolor": "white" }, "hoverlabel": { "align": "left" }, "hovermode": "closest", "mapbox": { "style": "light" }, "paper_bgcolor": "white", "plot_bgcolor": "#E5ECF6", "polar": { "angularaxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" }, "bgcolor": "#E5ECF6", "radialaxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" } }, "scene": { "xaxis": { "backgroundcolor": "#E5ECF6", "gridcolor": "white", "gridwidth": 2, "linecolor": "white", "showbackground": true, "ticks": "", "zerolinecolor": "white" }, "yaxis": { "backgroundcolor": "#E5ECF6", "gridcolor": "white", "gridwidth": 2, "linecolor": "white", "showbackground": true, "ticks": "", "zerolinecolor": "white" }, "zaxis": { "backgroundcolor": "#E5ECF6", "gridcolor": "white", "gridwidth": 2, "linecolor": "white", "showbackground": true, "ticks": "", "zerolinecolor": "white" } }, "shapedefaults": { "line": { "color": "#2a3f5f" } }, "ternary": { "aaxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" }, "baxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" }, "bgcolor": "#E5ECF6", "caxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" } }, "title": { "x": 0.05 }, "xaxis": { "automargin": true, "gridcolor": "white", "linecolor": "white", "ticks": "", "title": { "standoff": 15 }, "zerolinecolor": "white", "zerolinewidth": 2 }, "yaxis": { "automargin": true, "gridcolor": "white", "linecolor": "white", "ticks": "", "title": { "standoff": 15 }, "zerolinecolor": "white", "zerolinewidth": 2 } } }, "title": { "text": "Sample Partition (not optimal) — 3/6 edges cut", "x": 0.5 }, "xaxis": { "showgrid": false, "showticklabels": false, "zeroline": false }, "yaxis": { "showgrid": false, "showticklabels": false, "zeroline": false } } }, "text/html": [ "
\n
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "edges = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 4), (3, 4)]\n", "num_nodes = 5\n", "\n", "# Show a sample partition (not optimal) to illustrate the problem\n", "plot_maxcut_graph(\n", " edges, num_nodes, [1, 1, 0, 1, 0], title=\"Sample Partition (not optimal)\"\n", ")" ] }, { "cell_type": "markdown", "id": "hamiltonian_section", "metadata": {}, "source": [ "### Hamiltonian Construction\n", "\n", "Ket's {func}`~ket.gates.obs` context manager creates an {class}`~ket.expv.Hamiltonian` object directly from\n", "Python expressions involving {func}`~ket.gates.Z` operators. The `sum` over all edges naturally\n", "yields the cost Hamiltonian:\n", "\n", "$$H_C = -\\frac{1}{2} \\sum_{(u,\\ v) \\in E} (1 - Z_u Z_v)$$" ] }, { "cell_type": "code", "execution_count": 39, "id": "1cdf1dbf", "metadata": {}, "outputs": [], "source": [ "def max_cut_problem_h(edges: list[tuple[int, int]], qubits: Quant) -> Hamiltonian:\n", " \"\"\"\n", " Returns the problem Hamiltonian attached to a specific graph.\n", " \"\"\"\n", "\n", " with obs():\n", " # Returns the negative cut energy (to minimize)\n", " return -sum(1 - Z(qubits[u]) * Z(qubits[v]) for u, v in edges) / 2" ] }, { "cell_type": "markdown", "id": "standard_mixer_md", "metadata": {}, "source": [ "### Standard Mixer Hamiltonian\n", "\n", "The mixer Hamiltonian allows the algorithm to transition between different graph partition configurations (different assignments of sets $A$ and $B$).\n", "\n", "The Pauli-X operator acts as a bit \"flip\" ($X|0\\rangle = |1\\rangle$ and $X|1\\rangle = |0\\rangle$). Applying the evolution of this Hamiltonian prevents the algorithm from getting trapped in local minima within the search space.\n", "\n", "The mixer Hamiltonian is simply the sum of the $X$ operator applied to each vertex/qubit individually:\n", "\n", "$$H_M = \\sum_{k \\in V} X_k$$" ] }, { "cell_type": "code", "execution_count": 40, "id": "mixer_code", "metadata": {}, "outputs": [], "source": [ "def default_mixer_h(qubits):\n", " \"\"\"\n", " Standard mixer Hamiltonian (Pauli-X on all qubits).\n", " \"\"\"\n", " with obs():\n", " return sum(X(q) for q in qubits)" ] }, { "cell_type": "markdown", "id": "exec_maxcut_md", "metadata": {}, "source": [ "### Executing the Max-Cut Optimization\n", "\n", "With both the problem and mixer Hamiltonians defined, we can now call our `qaoa` function to optimize the Max-Cut problem." ] }, { "cell_type": "code", "execution_count": 41, "id": "exec_maxcut", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " message: Return from COBYLA because the trust region radius reaches its lower bound.\n", " success: True\n", " status: 0\n", " fun: -4.495944781889398\n", " x: [ 1.033e+00 -4.299e-01 1.893e+00 -6.808e-01]\n", " nfev: 418\n", " maxcv: 0.0\n" ] }, { "data": { "application/vnd.plotly.v1+json": { "config": { "plotlyServerURL": "https://plot.ly" }, "data": [ { "hovertemplate": "State=%{x}
Count=%{y}
Energy=%{marker.color}", "legendgroup": "", "marker": { "color": { "bdata": "AAAAAAAACMAAAAAAAAAQwAAAAAAAABTAAAAAAAAAEMAAAAAAAAAUwAAAAAAAAAjAAAAAAAAAEMAAAAAAAAAQwAAAAAAAAAAAAAAAAAAACMAAAAAAAAAAwAAAAAAAABDAAAAAAAAAFMAAAAAAAAAAwAAAAAAAABTAAAAAAAAACMAAAAAAAAAAwAAAAAAAAAjAAAAAAAAAEMA=", "dtype": "f8" }, "coloraxis": "coloraxis", "pattern": { "shape": "" } }, "name": "", "orientation": "v", "showlegend": false, "textposition": "auto", "type": "bar", "x": { "bdata": "GBEZDgkaDRMfCwMSBhwWBR0KDA==", "dtype": "i1" }, "xaxis": "x", "y": { "bdata": "AQYOAw4CBgUBAgEHEQEMAQEBBQ==", "dtype": "i1" }, "yaxis": "y" } ], "layout": { "bargap": 0.75, "barmode": "relative", "coloraxis": { "colorbar": { "title": { "text": "Energy" } }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ] }, "legend": { "tracegroupgap": 0 }, "margin": { "t": 60 }, "template": { "data": { "bar": [ { "error_x": { "color": "#2a3f5f" }, "error_y": { "color": "#2a3f5f" }, "marker": { "line": { "color": "#E5ECF6", "width": 0.5 }, "pattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 } }, "type": "bar" } ], "barpolar": [ { "marker": { "line": { "color": "#E5ECF6", "width": 0.5 }, "pattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 } }, "type": "barpolar" } ], "carpet": [ { "aaxis": { "endlinecolor": "#2a3f5f", "gridcolor": "white", "linecolor": "white", "minorgridcolor": "white", "startlinecolor": "#2a3f5f" }, "baxis": { "endlinecolor": "#2a3f5f", "gridcolor": "white", "linecolor": "white", "minorgridcolor": "white", "startlinecolor": "#2a3f5f" }, "type": "carpet" } ], "choropleth": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "type": "choropleth" } ], "contour": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "contour" } ], "contourcarpet": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "type": "contourcarpet" } ], "heatmap": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "heatmap" } ], "histogram": [ { "marker": { "pattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 } }, "type": "histogram" } ], "histogram2d": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "histogram2d" } ], "histogram2dcontour": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "histogram2dcontour" } ], "mesh3d": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "type": "mesh3d" } ], "parcoords": [ { "line": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "parcoords" } ], "pie": [ { "automargin": true, "type": "pie" } ], "scatter": [ { "fillpattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 }, "type": "scatter" } ], "scatter3d": [ { "line": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatter3d" } ], "scattercarpet": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattercarpet" } ], "scattergeo": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattergeo" } ], "scattergl": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattergl" } ], "scattermap": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattermap" } ], "scattermapbox": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattermapbox" } ], "scatterpolar": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatterpolar" } ], "scatterpolargl": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatterpolargl" } ], "scatterternary": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatterternary" } ], "surface": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "surface" } ], "table": [ { "cells": { "fill": { "color": "#EBF0F8" }, "line": { "color": "white" } }, "header": { "fill": { "color": "#C8D4E3" }, "line": { "color": "white" } }, "type": "table" } ] }, "layout": { "annotationdefaults": { "arrowcolor": "#2a3f5f", "arrowhead": 0, "arrowwidth": 1 }, "autotypenumbers": "strict", "coloraxis": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "colorscale": { "diverging": [ [ 0, "#8e0152" ], [ 0.1, "#c51b7d" ], [ 0.2, "#de77ae" ], [ 0.3, "#f1b6da" ], [ 0.4, "#fde0ef" ], [ 0.5, "#f7f7f7" ], [ 0.6, "#e6f5d0" ], [ 0.7, "#b8e186" ], [ 0.8, "#7fbc41" ], [ 0.9, "#4d9221" ], [ 1, "#276419" ] ], "sequential": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "sequentialminus": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ] }, "colorway": [ "#636efa", "#EF553B", "#00cc96", "#ab63fa", "#FFA15A", "#19d3f3", "#FF6692", "#B6E880", "#FF97FF", "#FECB52" ], "font": { "color": "#2a3f5f" }, "geo": { "bgcolor": "white", "lakecolor": "white", "landcolor": "#E5ECF6", "showlakes": true, "showland": true, "subunitcolor": "white" }, "hoverlabel": { "align": "left" }, "hovermode": "closest", "mapbox": { "style": "light" }, "paper_bgcolor": "white", "plot_bgcolor": "#E5ECF6", "polar": { "angularaxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" }, "bgcolor": "#E5ECF6", "radialaxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" } }, "scene": { "xaxis": { "backgroundcolor": "#E5ECF6", "gridcolor": "white", "gridwidth": 2, "linecolor": "white", "showbackground": true, "ticks": "", "zerolinecolor": "white" }, "yaxis": { "backgroundcolor": "#E5ECF6", "gridcolor": "white", "gridwidth": 2, "linecolor": "white", "showbackground": true, "ticks": "", "zerolinecolor": "white" }, "zaxis": { "backgroundcolor": "#E5ECF6", "gridcolor": "white", "gridwidth": 2, "linecolor": "white", "showbackground": true, "ticks": "", "zerolinecolor": "white" } }, "shapedefaults": { "line": { "color": "#2a3f5f" } }, "ternary": { "aaxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" }, "baxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" }, "bgcolor": "#E5ECF6", "caxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" } }, "title": { "x": 0.05 }, "xaxis": { "automargin": true, "gridcolor": "white", "linecolor": "white", "ticks": "", "title": { "standoff": 15 }, "zerolinecolor": "white", "zerolinewidth": 2 }, "yaxis": { "automargin": true, "gridcolor": "white", "linecolor": "white", "ticks": "", "title": { "standoff": 15 }, "zerolinecolor": "white", "zerolinewidth": 2 } } }, "xaxis": { "anchor": "y", "domain": [ 0, 1 ], "tickangle": -90, "tickmode": "array", "ticktext": [ "|11000⟩", "|10001⟩", "|11001⟩", "|01110⟩", "|01001⟩", "|11010⟩", "|01101⟩", "|10011⟩", "|11111⟩", "|01011⟩", "|00011⟩", "|10010⟩", "|00110⟩", "|11100⟩", "|10110⟩", "|00101⟩", "|11101⟩", "|01010⟩", "|01100⟩" ], "tickvals": [ 24, 17, 25, 14, 9, 26, 13, 19, 31, 11, 3, 18, 6, 28, 22, 5, 29, 10, 12 ], "title": { "text": "State" }, "type": "linear" }, "yaxis": { "anchor": "x", "domain": [ 0, 1 ], "title": { "text": "Count" } } } }, "text/html": [ "
\n
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "max_cut = partial(max_cut_problem_h, edges)\n", "\n", "res, result = qaoa(\n", " problem_h=max_cut,\n", " mixer_h=default_mixer_h,\n", " initial_state=H,\n", " num_qubits=num_nodes,\n", " p=2,\n", ")\n", "\n", "print(res)\n", "result.histogram(\"bin\", hamiltonian=max_cut)" ] }, { "cell_type": "markdown", "id": "result_viz_md", "metadata": {}, "source": [ "### Visualizing the Result\n", "\n", "Let's visualize the most frequent measurement outcome as the proposed Max-Cut partition:" ] }, { "cell_type": "code", "execution_count": 42, "id": "result_viz", "metadata": {}, "outputs": [ { "data": { "application/vnd.plotly.v1+json": { "config": { "plotlyServerURL": "https://plot.ly" }, "data": [ { "hoverinfo": "none", "line": { "color": "#e74c3c", "width": 4 }, "mode": "lines", "name": "Cut edge", "type": "scatter", "x": [ 1, 0.24537112788370613, null, 0.21658684233928793, 0.24537112788370613, null, 0.21658684233928793, -0.7503722096196979, null, 0.24537112788370613, -0.7115857606032955, null, -0.7503722096196979, -0.7115857606032955, null ], "y": [ 0.03492797469890115, -0.3945287104413233, null, 0.4084010375951407, -0.3945287104413233, null, 0.4084010375951407, 0.4088120458522651, null, -0.3945287104413233, -0.45761234770498316, null, 0.4088120458522651, -0.45761234770498316, null ] }, { "hoverinfo": "none", "line": { "color": "#aaaaaa", "dash": "dash", "width": 2 }, "mode": "lines", "name": "Non-cut edge", "type": "scatter", "x": [ 1, 0.21658684233928793, null ], "y": [ 0.03492797469890115, 0.4084010375951407, null ] }, { "hoverinfo": "text", "hovertext": [ "Node 0
Set A (|0⟩)", "Node 1
Set A (|0⟩)", "Node 2
Set B (|1⟩)", "Node 3
Set B (|1⟩)", "Node 4
Set A (|0⟩)" ], "marker": { "color": [ "#3498db", "#3498db", "#e67e22", "#e67e22", "#3498db" ], "line": { "color": "#333", "width": 2 }, "size": 40 }, "mode": "markers+text", "name": "Nodes", "showlegend": false, "text": [ "0", "1", "2", "3", "4" ], "textfont": { "color": "white", "size": 14 }, "textposition": "middle center", "type": "scatter", "x": [ 1, 0.21658684233928793, 0.24537112788370613, -0.7503722096196979, -0.7115857606032955 ], "y": [ 0.03492797469890115, 0.4084010375951407, -0.3945287104413233, 0.4088120458522651, -0.45761234770498316 ] } ], "layout": { "hovermode": "closest", "legend": { "x": 0, "y": 1 }, "margin": { "b": 20, "l": 5, "r": 5, "t": 50 }, "showlegend": true, "template": { "data": { "bar": [ { "error_x": { "color": "#2a3f5f" }, "error_y": { "color": "#2a3f5f" }, "marker": { "line": { "color": "#E5ECF6", "width": 0.5 }, "pattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 } }, "type": "bar" } ], "barpolar": [ { "marker": { "line": { "color": "#E5ECF6", "width": 0.5 }, "pattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 } }, "type": "barpolar" } ], "carpet": [ { "aaxis": { "endlinecolor": "#2a3f5f", "gridcolor": "white", "linecolor": "white", "minorgridcolor": "white", "startlinecolor": "#2a3f5f" }, "baxis": { "endlinecolor": "#2a3f5f", "gridcolor": "white", "linecolor": "white", "minorgridcolor": "white", "startlinecolor": "#2a3f5f" }, "type": "carpet" } ], "choropleth": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "type": "choropleth" } ], "contour": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "contour" } ], "contourcarpet": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "type": "contourcarpet" } ], "heatmap": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "heatmap" } ], "histogram": [ { "marker": { "pattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 } }, "type": "histogram" } ], "histogram2d": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "histogram2d" } ], "histogram2dcontour": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "histogram2dcontour" } ], "mesh3d": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "type": "mesh3d" } ], "parcoords": [ { "line": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "parcoords" } ], "pie": [ { "automargin": true, "type": "pie" } ], "scatter": [ { "fillpattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 }, "type": "scatter" } ], "scatter3d": [ { "line": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatter3d" } ], "scattercarpet": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattercarpet" } ], "scattergeo": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattergeo" } ], "scattergl": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattergl" } ], "scattermap": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattermap" } ], "scattermapbox": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattermapbox" } ], "scatterpolar": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatterpolar" } ], "scatterpolargl": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatterpolargl" } ], "scatterternary": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatterternary" } ], "surface": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "surface" } ], "table": [ { "cells": { "fill": { "color": "#EBF0F8" }, "line": { "color": "white" } }, "header": { "fill": { "color": "#C8D4E3" }, "line": { "color": "white" } }, "type": "table" } ] }, "layout": { "annotationdefaults": { "arrowcolor": "#2a3f5f", "arrowhead": 0, "arrowwidth": 1 }, "autotypenumbers": "strict", "coloraxis": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "colorscale": { "diverging": [ [ 0, "#8e0152" ], [ 0.1, "#c51b7d" ], [ 0.2, "#de77ae" ], [ 0.3, "#f1b6da" ], [ 0.4, "#fde0ef" ], [ 0.5, "#f7f7f7" ], [ 0.6, "#e6f5d0" ], [ 0.7, "#b8e186" ], [ 0.8, "#7fbc41" ], [ 0.9, "#4d9221" ], [ 1, "#276419" ] ], "sequential": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "sequentialminus": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ] }, "colorway": [ "#636efa", "#EF553B", "#00cc96", "#ab63fa", "#FFA15A", "#19d3f3", "#FF6692", "#B6E880", "#FF97FF", "#FECB52" ], "font": { "color": "#2a3f5f" }, "geo": { "bgcolor": "white", "lakecolor": "white", "landcolor": "#E5ECF6", "showlakes": true, "showland": true, "subunitcolor": "white" }, "hoverlabel": { "align": "left" }, "hovermode": "closest", "mapbox": { "style": "light" }, "paper_bgcolor": "white", "plot_bgcolor": "#E5ECF6", "polar": { "angularaxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" }, "bgcolor": "#E5ECF6", "radialaxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" } }, "scene": { "xaxis": { "backgroundcolor": "#E5ECF6", "gridcolor": "white", "gridwidth": 2, "linecolor": "white", "showbackground": true, "ticks": "", "zerolinecolor": "white" }, "yaxis": { "backgroundcolor": "#E5ECF6", "gridcolor": "white", "gridwidth": 2, "linecolor": "white", "showbackground": true, "ticks": "", "zerolinecolor": "white" }, "zaxis": { "backgroundcolor": "#E5ECF6", "gridcolor": "white", "gridwidth": 2, "linecolor": "white", "showbackground": true, "ticks": "", "zerolinecolor": "white" } }, "shapedefaults": { "line": { "color": "#2a3f5f" } }, "ternary": { "aaxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" }, "baxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" }, "bgcolor": "#E5ECF6", "caxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" } }, "title": { "x": 0.05 }, "xaxis": { "automargin": true, "gridcolor": "white", "linecolor": "white", "ticks": "", "title": { "standoff": 15 }, "zerolinecolor": "white", "zerolinewidth": 2 }, "yaxis": { "automargin": true, "gridcolor": "white", "linecolor": "white", "ticks": "", "title": { "standoff": 15 }, "zerolinecolor": "white", "zerolinewidth": 2 } } }, "title": { "text": "QAOA Max-Cut Result — 5/6 edges cut", "x": 0.5 }, "xaxis": { "showgrid": false, "showticklabels": false, "zeroline": false }, "yaxis": { "showgrid": false, "showticklabels": false, "zeroline": false } } }, "text/html": [ "
\n
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "plot_maxcut_graph(\n", " edges, num_nodes, result.most_frequent_state(), title=\"QAOA Max-Cut Result\"\n", ")" ] }, { "cell_type": "markdown", "id": "portfolio_intro", "metadata": {}, "source": [ "## Example 2: Portfolio Optimization\n", "\n", "In portfolio optimization, an investment manager aims to select a portfolio of financial assets that maximizes the expected return while simultaneously minimizing market risk (measured by the covariance between assets) and adhering to a strict budget constraint." ] }, { "cell_type": "markdown", "id": "qubo_intro", "metadata": {}, "source": [ "### The QUBO Formalism\n", "\n", "QUBO (Quadratic Unconstrained Binary Optimization) is a mathematical formulation where the goal is to minimize a quadratic function of classical binary variables, $x_i \\in \\{0, 1\\}$. The general QUBO cost function looks like this:\n", "\n", "$$E(x) = \\sum_{i} Q_{ii} x_i + \\sum_{i < j} Q_{ij} x_i x_j$$\n", "\n", "Here, the $Q_{ii}$ terms represent the linear costs of selecting an individual variable, while the $Q_{ij}$ terms capture the quadratic costs associated with the interactions or dependencies between pairs of decisions.\n", "\n", "To map this classical problem onto a quantum circuit, we convert the binary variables $\\{0, 1\\}$ into quantum operators whose eigenvalues correspond to the computational basis. We achieve this using the Pauli-Z operator, which has eigenvalues of $+1$ (for the $|0\\rangle$ state) and $-1$ (for the $|1\\rangle$ state).\n", "\n", "The mathematical transformation for each variable is:\n", "\n", "$$x_i = \\frac{I - Z_i}{2}$$\n", "\n", "By substituting this relation into the QUBO equation, we seamlessly transform the problem into the **Ising Model**, allowing us to work with quantum spins. A key advantage of `ket` is that it allows us to perform this operator algebra directly within the code, sparing us the manual expansion and calculation of new linear and quadratic coefficients." ] }, { "cell_type": "markdown", "id": "portfolio_formulation", "metadata": {}, "source": [ "### Formulating the Portfolio Optimization Problem\n", "\n", "Let's model this problem using binary variables $x_i$, where $x_i = 1$ indicates that asset $i$ is included in the portfolio, and $x_i = 0$ means it is excluded. Our classical cost function combines three core objectives:\n", "\n", "$$H(x) = \\underbrace{- \\sum_{i=1}^n \\mu_i x_i}_{\\text{Maximize Return}} + \\underbrace{q \\sum_{i,j} \\sigma_{ij} x_i x_j}_{\\text{Minimize Risk}} + \\underbrace{\\lambda \\left( \\sum_{i=1}^n x_i - B \\right)^2}_{\\text{Constraint (Budget)}}$$\n", "\n", "- **Return:** $\\mu_i$ represents the expected return of asset $i$. The negative sign reflects our desire to maximize return (by minimizing the overall cost function).\n", "- **Risk:** $\\sigma_{ij}$ represents the covariance between the variations of assets $i$ and $j$, and $q$ acts as the investor's **risk aversion factor**.\n", "- **Budget Constraint:** This ensures exactly $B$ assets are selected. Any deviation from $B$ incurs a heavy penalty, scaled by the penalty weight $\\lambda$." ] }, { "cell_type": "markdown", "id": "portfolio_ham_md", "metadata": {}, "source": [ "### Hamiltonian Construction\n", "\n", "Ket provides a {func}`~ket.gates.B` (binary) operator that directly implements the mapping $x_i = \\frac{I - Z_i}{2}$,\n", "allowing us to write the QUBO objective function in native Python arithmetic and let Ket handle the\n", "operator algebra automatically:" ] }, { "cell_type": "code", "execution_count": 43, "id": "portfolio_h", "metadata": {}, "outputs": [], "source": [ "def portfolio_optimization_h(\n", " mu: list[float],\n", " sigma: list[list[float]],\n", " budget: int,\n", " risk_aversion: float,\n", " penalty: float,\n", " qubits: Quant,\n", ") -> Hamiltonian:\n", " \"\"\"\n", " Generates the problem Hamiltonian for Financial Portfolio Optimization.\n", " Maps the classical QUBO formulation to the quantum space automatically via Ket.\n", "\n", " Args:\n", " mu: List with the expected return of each asset.\n", " sigma: Square covariance matrix between assets.\n", " budget: Exact quantity (B) of assets that must be purchased.\n", " risk_aversion: Weight factor 'q' that quantifies the investor's risk aversion.\n", " penalty: Scale factor 'lambda' to punish budget violations.\n", " \"\"\"\n", " n = len(mu)\n", "\n", " # 1. Maximize Expected Return\n", " expected_return = sum(mu[i] * B(qubits[i]) for i in range(n))\n", "\n", " # 2. Minimize Risk Covariance\n", " portfolio_risk = sum(\n", " sigma[i][j] * B(qubits[i]) * B(qubits[j])\n", " for i in range(n)\n", " for j in range(i + 1, n)\n", " )\n", "\n", " # 3. Apply Strict Budget Constraint (Penalty Term)\n", " budget_constraint = (sum(B(q) for q in qubits) - budget) ** 2\n", "\n", " # Final assembly of the QUBO cost function directly combined in the quantum space\n", " h_total = (\n", " -expected_return + risk_aversion * portfolio_risk + penalty * budget_constraint\n", " )\n", "\n", " return h_total" ] }, { "cell_type": "markdown", "id": "portfolio_exec_md", "metadata": {}, "source": [ "### Executing the Portfolio Optimization\n", "\n", "Now, let's run the QAOA algorithm to find the optimal asset allocation." ] }, { "cell_type": "code", "execution_count": 44, "id": "portfolio_exec", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " message: Return from COBYLA because the objective function has been evaluated MAXFUN times.\n", " success: False\n", " status: 3\n", " fun: -0.4478631603358989\n", " x: [ 1.455e+00 1.811e-01 1.633e+00 4.320e-01 1.566e+00\n", " 8.524e-01 5.007e-01 4.077e-01 4.225e-01 2.178e-01\n", " 1.702e-01 2.177e-01]\n", " nfev: 1000\n", " maxcv: 0.0\n" ] }, { "data": { "application/vnd.plotly.v1+json": { "config": { "plotlyServerURL": "https://plot.ly" }, "data": [ { "hovertemplate": "State=%{x}
Count=%{y}
Energy=%{marker.color}", "legendgroup": "", "marker": { "color": { "bdata": "+OXcJK6U2r/0bVsCUuvWvxwDxW5N8MW/vEh8cMrV178wDYhnKrnjv0wg3RwQf9u/", "dtype": "f8" }, "coloraxis": "coloraxis", "pattern": { "shape": "" } }, "name": "", "orientation": "v", "showlegend": false, "textposition": "auto", "type": "bar", "x": { "bdata": "AwUGDAkK", "dtype": "i1" }, "xaxis": "x", "y": { "bdata": "DhIDDSIS", "dtype": "i1" }, "yaxis": "y" } ], "layout": { "bargap": 0.75, "barmode": "relative", "coloraxis": { "colorbar": { "title": { "text": "Energy" } }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ] }, "legend": { "tracegroupgap": 0 }, "margin": { "t": 60 }, "template": { "data": { "bar": [ { "error_x": { "color": "#2a3f5f" }, "error_y": { "color": "#2a3f5f" }, "marker": { "line": { "color": "#E5ECF6", "width": 0.5 }, "pattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 } }, "type": "bar" } ], "barpolar": [ { "marker": { "line": { "color": "#E5ECF6", "width": 0.5 }, "pattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 } }, "type": "barpolar" } ], "carpet": [ { "aaxis": { "endlinecolor": "#2a3f5f", "gridcolor": "white", "linecolor": "white", "minorgridcolor": "white", "startlinecolor": "#2a3f5f" }, "baxis": { "endlinecolor": "#2a3f5f", "gridcolor": "white", "linecolor": "white", "minorgridcolor": "white", "startlinecolor": "#2a3f5f" }, "type": "carpet" } ], "choropleth": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "type": "choropleth" } ], "contour": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "contour" } ], "contourcarpet": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "type": "contourcarpet" } ], "heatmap": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "heatmap" } ], "histogram": [ { "marker": { "pattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 } }, "type": "histogram" } ], "histogram2d": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "histogram2d" } ], "histogram2dcontour": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "histogram2dcontour" } ], "mesh3d": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "type": "mesh3d" } ], "parcoords": [ { "line": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "parcoords" } ], "pie": [ { "automargin": true, "type": "pie" } ], "scatter": [ { "fillpattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 }, "type": "scatter" } ], "scatter3d": [ { "line": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatter3d" } ], "scattercarpet": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattercarpet" } ], "scattergeo": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattergeo" } ], "scattergl": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattergl" } ], "scattermap": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattermap" } ], "scattermapbox": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattermapbox" } ], "scatterpolar": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatterpolar" } ], "scatterpolargl": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatterpolargl" } ], "scatterternary": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatterternary" } ], "surface": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "surface" } ], "table": [ { "cells": { "fill": { "color": "#EBF0F8" }, "line": { "color": "white" } }, "header": { "fill": { "color": "#C8D4E3" }, "line": { "color": "white" } }, "type": "table" } ] }, "layout": { "annotationdefaults": { "arrowcolor": "#2a3f5f", "arrowhead": 0, "arrowwidth": 1 }, "autotypenumbers": "strict", "coloraxis": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "colorscale": { "diverging": [ [ 0, "#8e0152" ], [ 0.1, "#c51b7d" ], [ 0.2, "#de77ae" ], [ 0.3, "#f1b6da" ], [ 0.4, "#fde0ef" ], [ 0.5, "#f7f7f7" ], [ 0.6, "#e6f5d0" ], [ 0.7, "#b8e186" ], [ 0.8, "#7fbc41" ], [ 0.9, "#4d9221" ], [ 1, "#276419" ] ], "sequential": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "sequentialminus": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ] }, "colorway": [ "#636efa", "#EF553B", "#00cc96", "#ab63fa", "#FFA15A", "#19d3f3", "#FF6692", "#B6E880", "#FF97FF", "#FECB52" ], "font": { "color": "#2a3f5f" }, "geo": { "bgcolor": "white", "lakecolor": "white", "landcolor": "#E5ECF6", "showlakes": true, "showland": true, "subunitcolor": "white" }, "hoverlabel": { "align": "left" }, "hovermode": "closest", "mapbox": { "style": "light" }, "paper_bgcolor": "white", "plot_bgcolor": "#E5ECF6", "polar": { "angularaxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" }, "bgcolor": "#E5ECF6", "radialaxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" } }, "scene": { "xaxis": { "backgroundcolor": "#E5ECF6", "gridcolor": "white", "gridwidth": 2, "linecolor": "white", "showbackground": true, "ticks": "", "zerolinecolor": "white" }, "yaxis": { "backgroundcolor": "#E5ECF6", "gridcolor": "white", "gridwidth": 2, "linecolor": "white", "showbackground": true, "ticks": "", "zerolinecolor": "white" }, "zaxis": { "backgroundcolor": "#E5ECF6", "gridcolor": "white", "gridwidth": 2, "linecolor": "white", "showbackground": true, "ticks": "", "zerolinecolor": "white" } }, "shapedefaults": { "line": { "color": "#2a3f5f" } }, "ternary": { "aaxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" }, "baxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" }, "bgcolor": "#E5ECF6", "caxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" } }, "title": { "x": 0.05 }, "xaxis": { "automargin": true, "gridcolor": "white", "linecolor": "white", "ticks": "", "title": { "standoff": 15 }, "zerolinecolor": "white", "zerolinewidth": 2 }, "yaxis": { "automargin": true, "gridcolor": "white", "linecolor": "white", "ticks": "", "title": { "standoff": 15 }, "zerolinecolor": "white", "zerolinewidth": 2 } } }, "xaxis": { "anchor": "y", "domain": [ 0, 1 ], "tickangle": -90, "tickmode": "array", "ticktext": [ "|0011⟩", "|0101⟩", "|0110⟩", "|1100⟩", "|1001⟩", "|1010⟩" ], "tickvals": [ 3, 5, 6, 12, 9, 10 ], "title": { "text": "State" }, "type": "linear" }, "yaxis": { "anchor": "x", "domain": [ 0, 1 ], "title": { "text": "Count" } } } }, "text/html": [ "
\n
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "mu = [0.31542042, 0.0571331, 0.11430001, 0.30109367]\n", "\n", "sigma = [\n", " [1.08774352e-03, 2.59532811e-04, 1.80247155e-04, 3.21724369e-04],\n", " [2.59532811e-04, 4.43192629e-04, 7.43211072e-05, 2.27911525e-04],\n", " [1.80247155e-04, 7.43211072e-05, 3.89444953e-04, 1.37915422e-04],\n", " [3.21724369e-04, 2.27911525e-04, 1.37915422e-04, 8.75437564e-04],\n", "]\n", "\n", "budget = 2\n", "risk_aversion = 0.5\n", "\n", "penalty = 1\n", "\n", "portfolio = partial(\n", " portfolio_optimization_h,\n", " mu,\n", " sigma,\n", " budget,\n", " risk_aversion,\n", " penalty,\n", ")\n", "\n", "res, result = qaoa(\n", " problem_h=portfolio,\n", " mixer_h=default_mixer_h,\n", " initial_state=H,\n", " num_qubits=len(mu),\n", " p=6,\n", ")\n", "\n", "print(res)\n", "result.histogram(\"bin\", hamiltonian=portfolio)" ] }, { "cell_type": "markdown", "id": "coloring_intro", "metadata": {}, "source": [ "## Example 3: Graph Coloring\n", "\n", "The **Graph Coloring** problem asks us to assign a color to each vertex of a graph such that no two adjacent vertices share the same color. We must accomplish this using a maximum of _k_ available colors.\n", "\n", "![](https://upload.wikimedia.org/wikipedia/commons/9/90/Petersen_graph_3-coloring.svg)" ] }, { "cell_type": "markdown", "id": "coloring_viz_md", "metadata": {}, "source": [ "### Graph Visualization Helper\n", "\n", "The coloring visualization function uses Plotly for interactive exploration of the\n", "coloring assignment, highlighting any color conflicts in red." ] }, { "cell_type": "code", "execution_count": 45, "id": "coloring_plotly_func", "metadata": {}, "outputs": [], "source": [ "def plot_k_coloring_graph(\n", " graph_edges: list[tuple[int, int]],\n", " num_nodes: int,\n", " num_colors: int,\n", " qubits_state: list[int] | int,\n", " title: str = \"k-Coloring Graph\",\n", "):\n", " \"\"\"\n", " Plots the Graph Coloring problem using Plotly, coloring nodes according to their\n", " one-hot encoded quantum states and highlighting conflicting edges.\n", "\n", " Args:\n", " graph_edges: List of tuples representing the graph edges.\n", " num_nodes: Total number of graph vertices.\n", " num_colors: Number of available colors (k).\n", " qubits_state: Flat list of (num_nodes * num_colors) qubit states or an integer.\n", " title: Plot title.\n", " \"\"\"\n", " import networkx as nx\n", " import plotly.graph_objects as go\n", "\n", " total_qubits = num_nodes * num_colors\n", " if isinstance(qubits_state, int):\n", " qubits_state = list(map(int, f\"{qubits_state:0{total_qubits}b}\"))\n", "\n", " # A palette of distinct colors for each color index\n", " PALETTE = [\"#e74c3c\", \"#2ecc71\", \"#3498db\", \"#f39c12\", \"#9b59b6\", \"#1abc9c\"]\n", "\n", " G = nx.Graph()\n", " G.add_nodes_from(range(num_nodes))\n", " G.add_edges_from(graph_edges)\n", " pos = nx.spring_layout(G, seed=42)\n", "\n", " node_color_index = {}\n", " for v in range(num_nodes):\n", " bits = qubits_state[v * num_colors : (v + 1) * num_colors]\n", " ones = [c for c, b in enumerate(bits) if b == 1]\n", " node_color_index[v] = ones[0] if len(ones) == 1 else -1\n", "\n", " conflict_edges, ok_edges = [], []\n", " for u, v in graph_edges:\n", " cu, cv = node_color_index.get(u, -1), node_color_index.get(v, -1)\n", " if cu == cv and cu != -1:\n", " conflict_edges.append((u, v))\n", " else:\n", " ok_edges.append((u, v))\n", "\n", " def edge_trace(edge_list, color, dash, name):\n", " ex, ey = [], []\n", " for u, v in edge_list:\n", " x0, y0 = pos[u]\n", " x1, y1 = pos[v]\n", " ex += [x0, x1, None]\n", " ey += [y0, y1, None]\n", " return go.Scatter(\n", " x=ex,\n", " y=ey,\n", " mode=\"lines\",\n", " line=dict(width=3, color=color, dash=dash),\n", " name=name,\n", " hoverinfo=\"none\",\n", " )\n", "\n", " traces = [\n", " edge_trace(conflict_edges, \"#e74c3c\", \"solid\", \"Conflict\"),\n", " edge_trace(ok_edges, \"#aaaaaa\", \"dash\", \"OK\"),\n", " ]\n", "\n", " color_names = [f\"Color {c}\" for c in range(num_colors)]\n", " for ci in range(num_colors):\n", " nodes_ci = [n for n in G.nodes() if node_color_index[n] == ci]\n", " if not nodes_ci:\n", " continue\n", " traces.append(\n", " go.Scatter(\n", " x=[pos[n][0] for n in nodes_ci],\n", " y=[pos[n][1] for n in nodes_ci],\n", " mode=\"markers+text\",\n", " text=[str(n) for n in nodes_ci],\n", " textposition=\"middle center\",\n", " textfont=dict(size=14, color=\"white\"),\n", " hovertext=[f\"Node {n} → {color_names[ci]}\" for n in nodes_ci],\n", " hoverinfo=\"text\",\n", " marker=dict(\n", " size=40,\n", " color=PALETTE[ci % len(PALETTE)],\n", " line=dict(width=2, color=\"#333\"),\n", " ),\n", " name=color_names[ci],\n", " )\n", " )\n", "\n", " invalid_nodes = [n for n in G.nodes() if node_color_index[n] == -1]\n", " if invalid_nodes:\n", " traces.append(\n", " go.Scatter(\n", " x=[pos[n][0] for n in invalid_nodes],\n", " y=[pos[n][1] for n in invalid_nodes],\n", " mode=\"markers+text\",\n", " text=[str(n) for n in invalid_nodes],\n", " textposition=\"middle center\",\n", " textfont=dict(size=14, color=\"white\"),\n", " marker=dict(size=40, color=\"#555\", line=dict(width=2, color=\"#333\")),\n", " name=\"Invalid\",\n", " )\n", " )\n", "\n", " num_conflicts = len(conflict_edges)\n", " fig = go.Figure(\n", " data=traces,\n", " layout=go.Layout(\n", " title=dict(text=f\"{title} — {num_conflicts} conflict(s)\", x=0.5),\n", " showlegend=True,\n", " hovermode=\"closest\",\n", " margin=dict(b=20, l=5, r=5, t=50),\n", " xaxis=dict(showgrid=False, zeroline=False, showticklabels=False),\n", " yaxis=dict(showgrid=False, zeroline=False, showticklabels=False),\n", " legend=dict(x=0, y=1),\n", " ),\n", " )\n", " fig.show()" ] }, { "cell_type": "markdown", "id": "one_hot_md", "metadata": {}, "source": [ "### One-Hot Encoding for Colors\n", "\n", "Unlike Max-Cut, where our decision was simply binary (set A or set B), here each vertex must choose one out of _k_ possible colors. To represent this using qubits, we employ **One-Hot Encoding**.\n", "\n", "For a graph with $n$ vertices and $k$ colors, we need $n \\times k$ qubits in total. The qubits corresponding to a single vertex are grouped together. The critical rule is: exactly one qubit in this group can be in the $|1\\rangle$ state, while the rest must remain in $|0\\rangle$.\n", "\n", "**Example for _k=3_ (Red, Green, Blue):**\n", "\n", "- $|100\\rangle$ 🔴\n", "- $|010\\rangle$ 🟢\n", "- $|001\\rangle$ 🔵\n", "\n", "![](https://ar5iv.labs.arxiv.org/html/1709.03489/assets/figs/n4graphMap.png)" ] }, { "cell_type": "markdown", "id": "k_color_ham_md", "metadata": {}, "source": [ "### The $k$-Coloring Hamiltonian\n", "\n", "We model the graph coloring problem using binary variables $x_{u,c} \\in \\{0, 1\\}$, where $x_{u,c} = 1$ if vertex $u$ is assigned color $c$. The classical QUBO cost function enforces the problem's rules through two main components:\n", "\n", "$$H_C = \\overbrace{\\sum_{(u,\\ v) \\in E} \\sum_{c} x_{u,c} x_{v,c}}^{\\text{Conflicts (Minimize)}} + A \\underbrace{\\sum_{v}\\left(\\sum_{c} x_{v,c} -1\\right)^2}_\\text{Single Color Constraint}$$\n", "\n", "### 1. Conflict Term (Edge Penalty)\n", "\n", "This term evaluates the graph's topology. For every edge connecting vertices $u$ and $v$, and for every possible color $c$, we check if both vertices share the same color. If $x_{u,c} = 1$ and $x_{v,c} = 1$, the product is $1$, which adds a penalty to the total energy. The optimizer seeks to minimize this sum, striving for a configuration with zero adjacent color conflicts.\n", "\n", "### 2. Single Color Constraint (Vertex Penalty)\n", "\n", "This term enforces our one-hot encoding logic. For every vertex $v$, the total number of colors assigned to it ($\\sum_{c} x_{v,c}$) must be exactly $1$.\n", "\n", "- If a vertex receives zero colors, or multiple colors, the term inside the parentheses will be non-zero.\n", "- By squaring this deviation and multiplying it by a massive penalty constant ($A$), we construct an energy barrier that heavily discourages the optimizer from violating the \"one color per vertex\" rule." ] }, { "cell_type": "code", "execution_count": 46, "id": "k_color_h", "metadata": {}, "outputs": [], "source": [ "def graph_coloring_h(\n", " edges: list[tuple[int, int]],\n", " num_nodes: int,\n", " num_colors: int,\n", " penalty: int,\n", " qubits: Quant,\n", ") -> Hamiltonian:\n", "\n", " qubits = [qubits[i * num_colors : (i + 1) * num_colors] for i in range(num_nodes)]\n", "\n", " conflict = sum(\n", " sum(B(qubits[u][c]) * B(qubits[v][c]) for c in range(num_colors))\n", " for u, v in edges\n", " )\n", "\n", " one_hot_restriction = sum(\n", " (sum(B(qubits[v][c]) for c in range(num_colors)) - 1) ** 2\n", " for v in range(num_nodes)\n", " )\n", "\n", " return conflict + penalty * one_hot_restriction" ] }, { "cell_type": "markdown", "id": "coloring_instance_md", "metadata": {}, "source": [ "### Problem Instance\n", "\n", "Let's define our test graph (4 nodes, 5 edges) and display it with a valid 3-coloring:" ] }, { "cell_type": "code", "execution_count": 47, "id": "coloring_instance", "metadata": {}, "outputs": [ { "data": { "application/vnd.plotly.v1+json": { "config": { "plotlyServerURL": "https://plot.ly" }, "data": [ { "hoverinfo": "none", "line": { "color": "#e74c3c", "dash": "solid", "width": 3 }, "mode": "lines", "name": "Conflict", "type": "scatter", "x": [ 0.9948268418817919, -0.3012183995495115, null ], "y": [ 0.647963182490978, 0.46812332412713853, null ] }, { "hoverinfo": "none", "line": { "color": "#aaaaaa", "dash": "dash", "width": 3 }, "mode": "lines", "name": "OK", "type": "scatter", "x": [ 0.9948268418817919, 0.30639155766771947, null, 0.30639155766771947, -0.3012183995495115, null, 0.30639155766771947, -1, null, -0.3012183995495115, -1, null ], "y": [ 0.647963182490978, -0.4647540139421561, null, -0.4647540139421561, 0.46812332412713853, null, -0.4647540139421561, -0.6513324926759609, null, 0.46812332412713853, -0.6513324926759609, null ] }, { "hoverinfo": "text", "hovertext": [ "Node 3 → Color 0" ], "marker": { "color": "#e74c3c", "line": { "color": "#333", "width": 2 }, "size": 40 }, "mode": "markers+text", "name": "Color 0", "text": [ "3" ], "textfont": { "color": "white", "size": 14 }, "textposition": "middle center", "type": "scatter", "x": [ -1 ], "y": [ -0.6513324926759609 ] }, { "hoverinfo": "text", "hovertext": [ "Node 1 → Color 1" ], "marker": { "color": "#2ecc71", "line": { "color": "#333", "width": 2 }, "size": 40 }, "mode": "markers+text", "name": "Color 1", "text": [ "1" ], "textfont": { "color": "white", "size": 14 }, "textposition": "middle center", "type": "scatter", "x": [ 0.30639155766771947 ], "y": [ -0.4647540139421561 ] }, { "hoverinfo": "text", "hovertext": [ "Node 0 → Color 2", "Node 2 → Color 2" ], "marker": { "color": "#3498db", "line": { "color": "#333", "width": 2 }, "size": 40 }, "mode": "markers+text", "name": "Color 2", "text": [ "0", "2" ], "textfont": { "color": "white", "size": 14 }, "textposition": "middle center", "type": "scatter", "x": [ 0.9948268418817919, -0.3012183995495115 ], "y": [ 0.647963182490978, 0.46812332412713853 ] } ], "layout": { "hovermode": "closest", "legend": { "x": 0, "y": 1 }, "margin": { "b": 20, "l": 5, "r": 5, "t": 50 }, "showlegend": true, "template": { "data": { "bar": [ { "error_x": { "color": "#2a3f5f" }, "error_y": { "color": "#2a3f5f" }, "marker": { "line": { "color": "#E5ECF6", "width": 0.5 }, "pattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 } }, "type": "bar" } ], "barpolar": [ { "marker": { "line": { "color": "#E5ECF6", "width": 0.5 }, "pattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 } }, "type": "barpolar" } ], "carpet": [ { "aaxis": { "endlinecolor": "#2a3f5f", "gridcolor": "white", "linecolor": "white", "minorgridcolor": "white", "startlinecolor": "#2a3f5f" }, "baxis": { "endlinecolor": "#2a3f5f", "gridcolor": "white", "linecolor": "white", "minorgridcolor": "white", "startlinecolor": "#2a3f5f" }, "type": "carpet" } ], "choropleth": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "type": "choropleth" } ], "contour": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "contour" } ], "contourcarpet": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "type": "contourcarpet" } ], "heatmap": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "heatmap" } ], "histogram": [ { "marker": { "pattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 } }, "type": "histogram" } ], "histogram2d": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "histogram2d" } ], "histogram2dcontour": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "histogram2dcontour" } ], "mesh3d": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "type": "mesh3d" } ], "parcoords": [ { "line": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "parcoords" } ], "pie": [ { "automargin": true, "type": "pie" } ], "scatter": [ { "fillpattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 }, "type": "scatter" } ], "scatter3d": [ { "line": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatter3d" } ], "scattercarpet": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattercarpet" } ], "scattergeo": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattergeo" } ], "scattergl": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattergl" } ], "scattermap": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattermap" } ], "scattermapbox": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattermapbox" } ], "scatterpolar": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatterpolar" } ], "scatterpolargl": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatterpolargl" } ], "scatterternary": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatterternary" } ], "surface": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "surface" } ], "table": [ { "cells": { "fill": { "color": "#EBF0F8" }, "line": { "color": "white" } }, "header": { "fill": { "color": "#C8D4E3" }, "line": { "color": "white" } }, "type": "table" } ] }, "layout": { "annotationdefaults": { "arrowcolor": "#2a3f5f", "arrowhead": 0, "arrowwidth": 1 }, "autotypenumbers": "strict", "coloraxis": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "colorscale": { "diverging": [ [ 0, "#8e0152" ], [ 0.1, "#c51b7d" ], [ 0.2, "#de77ae" ], [ 0.3, "#f1b6da" ], [ 0.4, "#fde0ef" ], [ 0.5, "#f7f7f7" ], [ 0.6, "#e6f5d0" ], [ 0.7, "#b8e186" ], [ 0.8, "#7fbc41" ], [ 0.9, "#4d9221" ], [ 1, "#276419" ] ], "sequential": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "sequentialminus": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ] }, "colorway": [ "#636efa", "#EF553B", "#00cc96", "#ab63fa", "#FFA15A", "#19d3f3", "#FF6692", "#B6E880", "#FF97FF", "#FECB52" ], "font": { "color": "#2a3f5f" }, "geo": { "bgcolor": "white", "lakecolor": "white", "landcolor": "#E5ECF6", "showlakes": true, "showland": true, "subunitcolor": "white" }, "hoverlabel": { "align": "left" }, "hovermode": "closest", "mapbox": { "style": "light" }, "paper_bgcolor": "white", "plot_bgcolor": "#E5ECF6", "polar": { "angularaxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" }, "bgcolor": "#E5ECF6", "radialaxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" } }, "scene": { "xaxis": { "backgroundcolor": "#E5ECF6", "gridcolor": "white", "gridwidth": 2, "linecolor": "white", "showbackground": true, "ticks": "", "zerolinecolor": "white" }, "yaxis": { "backgroundcolor": "#E5ECF6", "gridcolor": "white", "gridwidth": 2, "linecolor": "white", "showbackground": true, "ticks": "", "zerolinecolor": "white" }, "zaxis": { "backgroundcolor": "#E5ECF6", "gridcolor": "white", "gridwidth": 2, "linecolor": "white", "showbackground": true, "ticks": "", "zerolinecolor": "white" } }, "shapedefaults": { "line": { "color": "#2a3f5f" } }, "ternary": { "aaxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" }, "baxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" }, "bgcolor": "#E5ECF6", "caxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" } }, "title": { "x": 0.05 }, "xaxis": { "automargin": true, "gridcolor": "white", "linecolor": "white", "ticks": "", "title": { "standoff": 15 }, "zerolinecolor": "white", "zerolinewidth": 2 }, "yaxis": { "automargin": true, "gridcolor": "white", "linecolor": "white", "ticks": "", "title": { "standoff": 15 }, "zerolinecolor": "white", "zerolinewidth": 2 } } }, "title": { "text": "Example Valid 3-Coloring — 1 conflict(s)", "x": 0.5 }, "xaxis": { "showgrid": false, "showticklabels": false, "zeroline": false }, "yaxis": { "showgrid": false, "showticklabels": false, "zeroline": false } } }, "text/html": [ "
\n
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "edges = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)]\n", "num_nodes = 4\n", "num_colors = 3\n", "\n", "# Show an example valid coloring\n", "plot_k_coloring_graph(\n", " edges,\n", " num_nodes,\n", " num_colors,\n", " [0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0],\n", " title=\"Example Valid 3-Coloring\",\n", ")" ] }, { "cell_type": "markdown", "id": "standard_mixer_attempt_md", "metadata": {}, "source": [ "### First Attempt: Standard Mixer\n", "\n", "We first try QAOA with the standard Pauli-X mixer and Hadamard initial state.\n", "This explores the full $2^{nk}$ Hilbert space rather than just the valid one-hot subspace.\n", "The penalty term enforces the one-hot constraint." ] }, { "cell_type": "code", "execution_count": 48, "id": "standard_mixer_attempt", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " message: Return from COBYLA because the trust region radius reaches its lower bound.\n", " success: True\n", " status: 0\n", " fun: 5.544658237597814\n", " x: [ 1.559e+00 -9.054e-02 3.891e-01 1.440e+00 4.284e-01\n", " 5.227e-01 4.239e-01 5.970e-01 3.112e-02 1.996e-01\n", " 1.114e-01 1.572e-01]\n", " nfev: 234\n", " maxcv: 0.0\n" ] }, { "data": { "application/vnd.plotly.v1+json": { "config": { "plotlyServerURL": "https://plot.ly" }, "data": [ { "hovertemplate": "State=%{x}
Count=%{y}
Energy=%{marker.color}", "legendgroup": "", "marker": { "color": { "bdata": "AAAAAAAAHEAAAAAAAAAIQAAAAAAAABhAAAAAAAAAAEAAAAAAAAAsQAAAAAAAABxAAAAAAAAAEEAAAAAAAAAcQAAAAAAAABxAAAAAAAAAAEAAAAAAAAAcQAAAAAAAAAhAAAAAAAAACEAAAAAAAAAIQAAAAAAAABRAAAAAAAAAFEAAAAAAAAAIQAAAAAAAABRAAAAAAAAALkAAAAAAAAAQQAAAAAAAAC5AAAAAAAAAAEAAAAAAAADwPwAAAAAAACJAAAAAAAAAFEAAAAAAAAAQQAAAAAAAAPA/AAAAAAAAEEAAAAAAAAAiQAAAAAAAAAhAAAAAAAAAGEAAAAAAAAAQQAAAAAAAAABAAAAAAAAAHEAAAAAAAAAcQAAAAAAAAPA/AAAAAAAAEEAAAAAAAAAIQAAAAAAAAAhAAAAAAAAAHEAAAAAAAAAIQAAAAAAAABhAAAAAAAAACEAAAAAAAAAAQAAAAAAAAPA/AAAAAAAAKEAAAAAAAAA0QAAAAAAAABRAAAAAAAAA8D8AAAAAAAAmQAAAAAAAABBAAAAAAAAACEAAAAAAAAAqQAAAAAAAABRAAAAAAAAAFEAAAAAAAAAgQAAAAAAAABxAAAAAAAAAIEAAAAAAAAAAQAAAAAAAABBAAAAAAAAACEAAAAAAAAAcQAAAAAAAABRAAAAAAAAAFEAAAAAAAAAAQAAAAAAAABxAAAAAAAAA8D8AAAAAAAAUQAAAAAAAABRAAAAAAAAAIEAAAAAAAAAYQAAAAAAAABhAAAAAAAAAIkAAAAAAAAAcQAAAAAAAACRAAAAAAAAAIEAAAAAAAAAcQAAAAAAAAABAAAAAAAAACEAAAAAAAAAAQAAAAAAAABxAAAAAAAAAFEAAAAAAAAAkQAAAAAAAACBAAAAAAAAAHEAAAAAAAAAAQAAAAAAAABBAAAAAAAAAGEA=", "dtype": "f8" }, "coloraxis": "coloraxis", "pattern": { "shape": "" } }, "name": "", "orientation": "v", "showlegend": false, "textposition": "auto", "type": "bar", "x": { "bdata": "YwoJATQIUgSyDTQJiABICiUBEglACZIITgSJAEkCSAKVApQJPgKgAMENEQhKBMsEIAmJDAoJUQlNCZQECACJCkIIWQKEAUwIYACIAkkIBQFSACAAIQlRBJQIwwanDlYAIgPTCggBYQCbBqgEFgVTBkgGAACJAgECIwWOBZAAIgwMCaQJUghJACQJmAMEALIIpAtyDFULiwaKDaIESgJCBEMAkATZAsIK0gRhCIoKAAE=", "dtype": "i2" }, "xaxis": "x", "y": { "bdata": "AQIBAQEBAQEBAQEBAQECAwEBAQIBAQEBAQEBAQECAwEBAQEBAgEBAQEBAQEBAQEBAQEDAQEBAQEBAQIBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQ==", "dtype": "i1" }, "yaxis": "y" } ], "layout": { "bargap": 0.2, "barmode": "relative", "coloraxis": { "colorbar": { "title": { "text": "Energy" } }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ] }, "legend": { "tracegroupgap": 0 }, "margin": { "t": 60 }, "template": { "data": { "bar": [ { "error_x": { "color": "#2a3f5f" }, "error_y": { "color": "#2a3f5f" }, "marker": { "line": { "color": "#E5ECF6", "width": 0.5 }, "pattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 } }, "type": "bar" } ], "barpolar": [ { "marker": { "line": { "color": "#E5ECF6", "width": 0.5 }, "pattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 } }, "type": "barpolar" } ], "carpet": [ { "aaxis": { "endlinecolor": "#2a3f5f", "gridcolor": "white", "linecolor": "white", "minorgridcolor": "white", "startlinecolor": "#2a3f5f" }, "baxis": { "endlinecolor": "#2a3f5f", "gridcolor": "white", "linecolor": "white", "minorgridcolor": "white", "startlinecolor": "#2a3f5f" }, "type": "carpet" } ], "choropleth": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "type": "choropleth" } ], "contour": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "contour" } ], "contourcarpet": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "type": "contourcarpet" } ], "heatmap": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "heatmap" } ], "histogram": [ { "marker": { "pattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 } }, "type": "histogram" } ], "histogram2d": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "histogram2d" } ], "histogram2dcontour": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "histogram2dcontour" } ], "mesh3d": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "type": "mesh3d" } ], "parcoords": [ { "line": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "parcoords" } ], "pie": [ { "automargin": true, "type": "pie" } ], "scatter": [ { "fillpattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 }, "type": "scatter" } ], "scatter3d": [ { "line": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatter3d" } ], "scattercarpet": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattercarpet" } ], "scattergeo": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattergeo" } ], "scattergl": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattergl" } ], "scattermap": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattermap" } ], "scattermapbox": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattermapbox" } ], "scatterpolar": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatterpolar" } ], "scatterpolargl": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatterpolargl" } ], "scatterternary": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatterternary" } ], "surface": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "surface" } ], "table": [ { "cells": { "fill": { "color": "#EBF0F8" }, "line": { "color": "white" } }, "header": { "fill": { "color": "#C8D4E3" }, "line": { "color": "white" } }, "type": "table" } ] }, "layout": { "annotationdefaults": { "arrowcolor": "#2a3f5f", "arrowhead": 0, "arrowwidth": 1 }, "autotypenumbers": "strict", "coloraxis": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "colorscale": { "diverging": [ [ 0, "#8e0152" ], [ 0.1, "#c51b7d" ], [ 0.2, "#de77ae" ], [ 0.3, "#f1b6da" ], [ 0.4, "#fde0ef" ], [ 0.5, "#f7f7f7" ], [ 0.6, "#e6f5d0" ], [ 0.7, "#b8e186" ], [ 0.8, "#7fbc41" ], [ 0.9, "#4d9221" ], [ 1, "#276419" ] ], "sequential": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "sequentialminus": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ] }, "colorway": [ "#636efa", "#EF553B", "#00cc96", "#ab63fa", "#FFA15A", "#19d3f3", "#FF6692", "#B6E880", "#FF97FF", "#FECB52" ], "font": { "color": "#2a3f5f" }, "geo": { "bgcolor": "white", "lakecolor": "white", "landcolor": "#E5ECF6", "showlakes": true, "showland": true, "subunitcolor": "white" }, "hoverlabel": { "align": "left" }, "hovermode": "closest", "mapbox": { "style": "light" }, "paper_bgcolor": "white", "plot_bgcolor": "#E5ECF6", "polar": { "angularaxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" }, "bgcolor": "#E5ECF6", "radialaxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" } }, "scene": { "xaxis": { "backgroundcolor": "#E5ECF6", "gridcolor": "white", "gridwidth": 2, "linecolor": "white", "showbackground": true, "ticks": "", "zerolinecolor": "white" }, "yaxis": { "backgroundcolor": "#E5ECF6", "gridcolor": "white", "gridwidth": 2, "linecolor": "white", "showbackground": true, "ticks": "", "zerolinecolor": "white" }, "zaxis": { "backgroundcolor": "#E5ECF6", "gridcolor": "white", "gridwidth": 2, "linecolor": "white", "showbackground": true, "ticks": "", "zerolinecolor": "white" } }, "shapedefaults": { "line": { "color": "#2a3f5f" } }, "ternary": { "aaxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" }, "baxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" }, "bgcolor": "#E5ECF6", "caxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" } }, "title": { "x": 0.05 }, "xaxis": { "automargin": true, "gridcolor": "white", "linecolor": "white", "ticks": "", "title": { "standoff": 15 }, "zerolinecolor": "white", "zerolinewidth": 2 }, "yaxis": { "automargin": true, "gridcolor": "white", "linecolor": "white", "ticks": "", "title": { "standoff": 15 }, "zerolinecolor": "white", "zerolinewidth": 2 } } }, "xaxis": { "anchor": "y", "domain": [ 0, 1 ], "tickangle": -90, "tickmode": "array", "ticktext": [ "|101001100011⟩", "|000100001001⟩", "|100000110100⟩", "|010001010010⟩", "|110110110010⟩", "|100100110100⟩", "|000010001000⟩", "|101001001000⟩", "|000100100101⟩", "|100100010010⟩", "|100101000000⟩", "|100010010010⟩", "|010001001110⟩", "|000010001001⟩", "|001001001001⟩", "|001001001000⟩", "|001010010101⟩", "|100110010100⟩", "|001000111110⟩", "|000010100000⟩", "|110111000001⟩", "|100000010001⟩", "|010001001010⟩", "|010011001011⟩", "|100100100000⟩", "|110010001001⟩", "|100100001010⟩", "|100101010001⟩", "|100101001101⟩", "|010010010100⟩", "|000000001000⟩", "|101010001001⟩", "|100001000010⟩", "|001001011001⟩", "|000110000100⟩", "|100001001100⟩", "|000001100000⟩", "|001010001000⟩", "|100001001001⟩", "|000100000101⟩", "|000001010010⟩", "|000000100000⟩", "|100100100001⟩", "|010001010001⟩", "|100010010100⟩", "|011011000011⟩", "|111010100111⟩", "|000001010110⟩", "|001100100010⟩", "|101011010011⟩", "|000100001000⟩", "|000001100001⟩", "|011010011011⟩", "|010010101000⟩", "|010100010110⟩", "|011001010011⟩", "|011001001000⟩", "|000000000000⟩", "|001010001001⟩", "|001000000001⟩", "|010100100011⟩", "|010110001110⟩", "|000010010000⟩", "|110000100010⟩", "|100100001100⟩", "|100110100100⟩", "|100001010010⟩", "|000001001001⟩", "|100100100100⟩", "|001110011000⟩", "|000000000100⟩", "|100010110010⟩", "|101110100100⟩", "|110001110010⟩", "|101101010101⟩", "|011010001011⟩", "|110110001010⟩", "|010010100010⟩", "|001001001010⟩", "|010001000010⟩", "|000001000011⟩", "|010010010000⟩", "|001011011001⟩", "|101011000010⟩", "|010011010010⟩", "|100001100001⟩", "|101010001010⟩", "|000100000000⟩" ], "tickvals": [ 2659, 265, 2100, 1106, 3506, 2356, 136, 2632, 293, 2322, 2368, 2194, 1102, 137, 585, 584, 661, 2452, 574, 160, 3521, 2065, 1098, 1227, 2336, 3209, 2314, 2385, 2381, 1172, 8, 2697, 2114, 601, 388, 2124, 96, 648, 2121, 261, 82, 32, 2337, 1105, 2196, 1731, 3751, 86, 802, 2771, 264, 97, 1691, 1192, 1302, 1619, 1608, 0, 649, 513, 1315, 1422, 144, 3106, 2316, 2468, 2130, 73, 2340, 920, 4, 2226, 2980, 3186, 2901, 1675, 3466, 1186, 586, 1090, 67, 1168, 729, 2754, 1234, 2145, 2698, 256 ], "title": { "text": "State" }, "type": "category" }, "yaxis": { "anchor": "x", "domain": [ 0, 1 ], "title": { "text": "Count" } } } }, "text/html": [ "
\n
" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "application/vnd.plotly.v1+json": { "config": { "plotlyServerURL": "https://plot.ly" }, "data": [ { "hoverinfo": "none", "line": { "color": "#e74c3c", "dash": "solid", "width": 3 }, "mode": "lines", "name": "Conflict", "type": "scatter", "x": [ 0.9948268418817919, 0.30639155766771947, null, 0.9948268418817919, -0.3012183995495115, null, 0.30639155766771947, -0.3012183995495115, null ], "y": [ 0.647963182490978, -0.4647540139421561, null, 0.647963182490978, 0.46812332412713853, null, -0.4647540139421561, 0.46812332412713853, null ] }, { "hoverinfo": "none", "line": { "color": "#aaaaaa", "dash": "dash", "width": 3 }, "mode": "lines", "name": "OK", "type": "scatter", "x": [ 0.30639155766771947, -1, null, -0.3012183995495115, -1, null ], "y": [ -0.4647540139421561, -0.6513324926759609, null, 0.46812332412713853, -0.6513324926759609, null ] }, { "hoverinfo": "text", "hovertext": [ "Node 0 → Color 2", "Node 1 → Color 2", "Node 2 → Color 2" ], "marker": { "color": "#3498db", "line": { "color": "#333", "width": 2 }, "size": 40 }, "mode": "markers+text", "name": "Color 2", "text": [ "0", "1", "2" ], "textfont": { "color": "white", "size": 14 }, "textposition": "middle center", "type": "scatter", "x": [ 0.9948268418817919, 0.30639155766771947, -0.3012183995495115 ], "y": [ 0.647963182490978, -0.4647540139421561, 0.46812332412713853 ] }, { "marker": { "color": "#555", "line": { "color": "#333", "width": 2 }, "size": 40 }, "mode": "markers+text", "name": "Invalid", "text": [ "3" ], "textfont": { "color": "white", "size": 14 }, "textposition": "middle center", "type": "scatter", "x": [ -1 ], "y": [ -0.6513324926759609 ] } ], "layout": { "hovermode": "closest", "legend": { "x": 0, "y": 1 }, "margin": { "b": 20, "l": 5, "r": 5, "t": 50 }, "showlegend": true, "template": { "data": { "bar": [ { "error_x": { "color": "#2a3f5f" }, "error_y": { "color": "#2a3f5f" }, "marker": { "line": { "color": "#E5ECF6", "width": 0.5 }, "pattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 } }, "type": "bar" } ], "barpolar": [ { "marker": { "line": { "color": "#E5ECF6", "width": 0.5 }, "pattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 } }, "type": "barpolar" } ], "carpet": [ { "aaxis": { "endlinecolor": "#2a3f5f", "gridcolor": "white", "linecolor": "white", "minorgridcolor": "white", "startlinecolor": "#2a3f5f" }, "baxis": { "endlinecolor": "#2a3f5f", "gridcolor": "white", "linecolor": "white", "minorgridcolor": "white", "startlinecolor": "#2a3f5f" }, "type": "carpet" } ], "choropleth": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "type": "choropleth" } ], "contour": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "contour" } ], "contourcarpet": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "type": "contourcarpet" } ], "heatmap": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "heatmap" } ], "histogram": [ { "marker": { "pattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 } }, "type": "histogram" } ], "histogram2d": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "histogram2d" } ], "histogram2dcontour": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "histogram2dcontour" } ], "mesh3d": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "type": "mesh3d" } ], "parcoords": [ { "line": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "parcoords" } ], "pie": [ { "automargin": true, "type": "pie" } ], "scatter": [ { "fillpattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 }, "type": "scatter" } ], "scatter3d": [ { "line": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatter3d" } ], "scattercarpet": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattercarpet" } ], "scattergeo": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattergeo" } ], "scattergl": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattergl" } ], "scattermap": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattermap" } ], "scattermapbox": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattermapbox" } ], "scatterpolar": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatterpolar" } ], "scatterpolargl": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatterpolargl" } ], "scatterternary": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatterternary" } ], "surface": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "surface" } ], "table": [ { "cells": { "fill": { "color": "#EBF0F8" }, "line": { "color": "white" } }, "header": { "fill": { "color": "#C8D4E3" }, "line": { "color": "white" } }, "type": "table" } ] }, "layout": { "annotationdefaults": { "arrowcolor": "#2a3f5f", "arrowhead": 0, "arrowwidth": 1 }, "autotypenumbers": "strict", "coloraxis": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "colorscale": { "diverging": [ [ 0, "#8e0152" ], [ 0.1, "#c51b7d" ], [ 0.2, "#de77ae" ], [ 0.3, "#f1b6da" ], [ 0.4, "#fde0ef" ], [ 0.5, "#f7f7f7" ], [ 0.6, "#e6f5d0" ], [ 0.7, "#b8e186" ], [ 0.8, "#7fbc41" ], [ 0.9, "#4d9221" ], [ 1, "#276419" ] ], "sequential": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "sequentialminus": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ] }, "colorway": [ "#636efa", "#EF553B", "#00cc96", "#ab63fa", "#FFA15A", "#19d3f3", "#FF6692", "#B6E880", "#FF97FF", "#FECB52" ], "font": { "color": "#2a3f5f" }, "geo": { "bgcolor": "white", "lakecolor": "white", "landcolor": "#E5ECF6", "showlakes": true, "showland": true, "subunitcolor": "white" }, "hoverlabel": { "align": "left" }, "hovermode": "closest", "mapbox": { "style": "light" }, "paper_bgcolor": "white", "plot_bgcolor": "#E5ECF6", "polar": { "angularaxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" }, "bgcolor": "#E5ECF6", "radialaxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" } }, "scene": { "xaxis": { "backgroundcolor": "#E5ECF6", "gridcolor": "white", "gridwidth": 2, "linecolor": "white", "showbackground": true, "ticks": "", "zerolinecolor": "white" }, "yaxis": { "backgroundcolor": "#E5ECF6", "gridcolor": "white", "gridwidth": 2, "linecolor": "white", "showbackground": true, "ticks": "", "zerolinecolor": "white" }, "zaxis": { "backgroundcolor": "#E5ECF6", "gridcolor": "white", "gridwidth": 2, "linecolor": "white", "showbackground": true, "ticks": "", "zerolinecolor": "white" } }, "shapedefaults": { "line": { "color": "#2a3f5f" } }, "ternary": { "aaxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" }, "baxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" }, "bgcolor": "#E5ECF6", "caxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" } }, "title": { "x": 0.05 }, "xaxis": { "automargin": true, "gridcolor": "white", "linecolor": "white", "ticks": "", "title": { "standoff": 15 }, "zerolinecolor": "white", "zerolinewidth": 2 }, "yaxis": { "automargin": true, "gridcolor": "white", "linecolor": "white", "ticks": "", "title": { "standoff": 15 }, "zerolinecolor": "white", "zerolinewidth": 2 } } }, "title": { "text": "k-Coloring Graph — 3 conflict(s)", "x": 0.5 }, "xaxis": { "showgrid": false, "showticklabels": false, "zeroline": false }, "yaxis": { "showgrid": false, "showticklabels": false, "zeroline": false } } }, "text/html": [ "
\n
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "penalty = 2\n", "k_coloring = partial(graph_coloring_h, edges, num_nodes, num_colors, penalty)\n", "\n", "res, result = qaoa(\n", " problem_h=k_coloring,\n", " mixer_h=default_mixer_h,\n", " initial_state=H,\n", " num_qubits=num_nodes * num_colors,\n", " p=6,\n", ")\n", "\n", "print(res)\n", "display(result.histogram(\"bin\", hamiltonian=k_coloring))\n", "\n", "plot_k_coloring_graph(\n", " edges,\n", " num_nodes,\n", " num_colors,\n", " result.most_frequent_state(),\n", ")" ] }, { "cell_type": "markdown", "id": "xy_mixer_md", "metadata": {}, "source": [ "### XY Mixer in the One-Hot Subspace\n", "\n", "Using the standard mixer Hamiltonian ($\\sum X_i$) for this problem introduces a significant challenge. The Pauli-X operator flips qubits individually.\n", "\n", "Applying $e^{-i\\beta X}$ to a valid state like $|100\\rangle$ generates superpositions involving invalid states, such as $|110\\rangle$ (a vertex with two colors) or $|000\\rangle$ (a vertex with no colors). This inadvertently expands our search space from $k^n$ (valid configurations) to $2^{nk}$ (the entire Hilbert space). This drastically reduces optimization efficiency and necessitates a huge number of layers ($p$) to guide the system back to valid states.\n", "\n", "To restrict the algorithm to only explore valid configurations, we use the **XY Mixer** (often called the _Ring Mixer_).\n", "\n", "The XY Mixer evolution operator acts on pairs of qubits, swapping the states $|01\\rangle \\leftrightarrow |10\\rangle$ while leaving $|00\\rangle$ and $|11\\rangle$ unchanged:\n", "\n", "$$H_{XY} = \\frac{1}{2} (X_i X_j + Y_i Y_j)$$\n", "\n", "**Implementation in QAOA:**\n", "\n", "We connect the $k$ qubits of a single vertex in a ring topology (qubit 1 connects to 2, 2 connects to 3, ... and the last connects back to 1). Applying the XY Mixer across this ring ensures the single $|1\\rangle$ state (the vertex's current color) can only \"jump\" to an adjacent color slot. This creates a superposition of valid color assignments without ever introducing a second color or eliminating the existing one." ] }, { "cell_type": "code", "execution_count": 49, "id": "xy_mixer_code", "metadata": {}, "outputs": [], "source": [ "def xy_mixer_h(qubits: Quant) -> Hamiltonian:\n", " \"\"\"XY-Mixer Hamiltonian\"\"\"\n", "\n", " n = len(qubits)\n", " ring = [(i, (i + 1) % n) for i in range(n)]\n", "\n", " with obs():\n", " return sum(X(i) * X(j) + Y(i) * Y(j) for i, j in map(qubits.at, ring)) / 2\n", "\n", "\n", "def graph_coloring_mixer_h(\n", " num_nodes: int,\n", " num_colors: int,\n", " qubits: Quant,\n", ") -> Hamiltonian:\n", "\n", " qubits = [qubits[i * num_colors : (i + 1) * num_colors] for i in range(num_nodes)]\n", "\n", " return sum(xy_mixer_h(node) for node in qubits)" ] }, { "cell_type": "markdown", "id": "coloring_xy_exec_md", "metadata": {}, "source": [ "### Executing the Graph Coloring Optimization\n", "\n", "When running this subspace-restricted version of QAOA, we can no longer use a simple layer of Hadamard ($H$) gates for our `initial_state`. We must prepare an initial state that starts as a valid One-Hot configuration for every vertex. \n", "\n", "For example, we can initialize the first color qubit of each vertex with an $X$ gate, or use `ket.qulib.prepare.w` to create an equal superposition of all valid one-hot states." ] }, { "cell_type": "code", "execution_count": 50, "id": "coloring_initial_state", "metadata": {}, "outputs": [], "source": [ "def graph_coloring_initial_state(\n", " num_nodes: int,\n", " num_colors: int,\n", " qubits: Quant,\n", "):\n", " qubits = [qubits[i * num_colors : (i + 1) * num_colors] for i in range(num_nodes)]\n", " for node in qubits:\n", " qulib.prepare.w(node)" ] }, { "cell_type": "markdown", "id": "xy_exec_md", "metadata": {}, "source": [ "### Executing with XY Mixer\n", "\n", "With the XY mixer and one-hot initial state, QAOA stays entirely within the valid\n", "coloring subspace. This removes the need for a penalty term ($A=0$) and dramatically\n", "improves convergence:" ] }, { "cell_type": "code", "execution_count": 51, "id": "xy_exec", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " message: Return from COBYLA because the objective function has been evaluated MAXFUN times.\n", " success: False\n", " status: 3\n", " fun: 0.5113087189152257\n", " x: [ 1.439e+00 1.750e+00 1.569e+00 2.988e-01 4.746e-01\n", " 7.441e-01 4.208e-01 3.129e-01 3.237e-01 3.592e-01\n", " 9.900e-02 -2.918e-01]\n", " nfev: 1000\n", " maxcv: 0.0\n" ] }, { "data": { "application/vnd.plotly.v1+json": { "config": { "plotlyServerURL": "https://plot.ly" }, "data": [ { "hovertemplate": "State=%{x}
Count=%{y}
Energy=%{marker.color}", "legendgroup": "", "marker": { "color": { "bdata": "AAAAAAAA8D8AAAAAAAAAAAAAAAAAAAAAAAAAAAAACEAAAAAAAAAAAAAAAAAAAABAAAAAAAAACEAAAAAAAADwPwAAAAAAAPA/AAAAAAAA8D8AAAAAAAAAQAAAAAAAAAAAAAAAAAAA8D8AAAAAAAAAAAAAAAAAAABAAAAAAAAA8D8AAAAAAAAAQAAAAAAAAPA/AAAAAAAAAAAAAAAAAADwPwAAAAAAAPA/AAAAAAAA8D8AAAAAAAAAQAAAAAAAAABAAAAAAAAAAEAAAAAAAADwPw==", "dtype": "f8" }, "coloraxis": "coloraxis", "pattern": { "shape": "" } }, "name": "", "orientation": "v", "showlegend": false, "textposition": "auto", "type": "bar", "x": { "bdata": "IQOhAowISQhiBFIElAQRCQoDogJkAhEDlAgKBRIFTAhRAmIIVAgUA6EIpAJhAgkDYQhRCA==", "dtype": "i2" }, "xaxis": "x", "y": { "bdata": "AQ8LAQgEAQEBAQELAgsCAQEBEgEBAgEBAQE=", "dtype": "i1" }, "yaxis": "y" } ], "layout": { "bargap": 0.2, "barmode": "relative", "coloraxis": { "colorbar": { "title": { "text": "Energy" } }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ] }, "legend": { "tracegroupgap": 0 }, "margin": { "t": 60 }, "template": { "data": { "bar": [ { "error_x": { "color": "#2a3f5f" }, "error_y": { "color": "#2a3f5f" }, "marker": { "line": { "color": "#E5ECF6", "width": 0.5 }, "pattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 } }, "type": "bar" } ], "barpolar": [ { "marker": { "line": { "color": "#E5ECF6", "width": 0.5 }, "pattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 } }, "type": "barpolar" } ], "carpet": [ { "aaxis": { "endlinecolor": "#2a3f5f", "gridcolor": "white", "linecolor": "white", "minorgridcolor": "white", "startlinecolor": "#2a3f5f" }, "baxis": { "endlinecolor": "#2a3f5f", "gridcolor": "white", "linecolor": "white", "minorgridcolor": "white", "startlinecolor": "#2a3f5f" }, "type": "carpet" } ], "choropleth": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "type": "choropleth" } ], "contour": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "contour" } ], "contourcarpet": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "type": "contourcarpet" } ], "heatmap": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "heatmap" } ], "histogram": [ { "marker": { "pattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 } }, "type": "histogram" } ], "histogram2d": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "histogram2d" } ], "histogram2dcontour": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "histogram2dcontour" } ], "mesh3d": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "type": "mesh3d" } ], "parcoords": [ { "line": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "parcoords" } ], "pie": [ { "automargin": true, "type": "pie" } ], "scatter": [ { "fillpattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 }, "type": "scatter" } ], "scatter3d": [ { "line": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatter3d" } ], "scattercarpet": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattercarpet" } ], "scattergeo": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattergeo" } ], "scattergl": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattergl" } ], "scattermap": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattermap" } ], "scattermapbox": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattermapbox" } ], "scatterpolar": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatterpolar" } ], "scatterpolargl": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatterpolargl" } ], "scatterternary": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatterternary" } ], "surface": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "surface" } ], "table": [ { "cells": { "fill": { "color": "#EBF0F8" }, "line": { "color": "white" } }, "header": { "fill": { "color": "#C8D4E3" }, "line": { "color": "white" } }, "type": "table" } ] }, "layout": { "annotationdefaults": { "arrowcolor": "#2a3f5f", "arrowhead": 0, "arrowwidth": 1 }, "autotypenumbers": "strict", "coloraxis": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "colorscale": { "diverging": [ [ 0, "#8e0152" ], [ 0.1, "#c51b7d" ], [ 0.2, "#de77ae" ], [ 0.3, "#f1b6da" ], [ 0.4, "#fde0ef" ], [ 0.5, "#f7f7f7" ], [ 0.6, "#e6f5d0" ], [ 0.7, "#b8e186" ], [ 0.8, "#7fbc41" ], [ 0.9, "#4d9221" ], [ 1, "#276419" ] ], "sequential": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "sequentialminus": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ] }, "colorway": [ "#636efa", "#EF553B", "#00cc96", "#ab63fa", "#FFA15A", "#19d3f3", "#FF6692", "#B6E880", "#FF97FF", "#FECB52" ], "font": { "color": "#2a3f5f" }, "geo": { "bgcolor": "white", "lakecolor": "white", "landcolor": "#E5ECF6", "showlakes": true, "showland": true, "subunitcolor": "white" }, "hoverlabel": { "align": "left" }, "hovermode": "closest", "mapbox": { "style": "light" }, "paper_bgcolor": "white", "plot_bgcolor": "#E5ECF6", "polar": { "angularaxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" }, "bgcolor": "#E5ECF6", "radialaxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" } }, "scene": { "xaxis": { "backgroundcolor": "#E5ECF6", "gridcolor": "white", "gridwidth": 2, "linecolor": "white", "showbackground": true, "ticks": "", "zerolinecolor": "white" }, "yaxis": { "backgroundcolor": "#E5ECF6", "gridcolor": "white", "gridwidth": 2, "linecolor": "white", "showbackground": true, "ticks": "", "zerolinecolor": "white" }, "zaxis": { "backgroundcolor": "#E5ECF6", "gridcolor": "white", "gridwidth": 2, "linecolor": "white", "showbackground": true, "ticks": "", "zerolinecolor": "white" } }, "shapedefaults": { "line": { "color": "#2a3f5f" } }, "ternary": { "aaxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" }, "baxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" }, "bgcolor": "#E5ECF6", "caxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" } }, "title": { "x": 0.05 }, "xaxis": { "automargin": true, "gridcolor": "white", "linecolor": "white", "ticks": "", "title": { "standoff": 15 }, "zerolinecolor": "white", "zerolinewidth": 2 }, "yaxis": { "automargin": true, "gridcolor": "white", "linecolor": "white", "ticks": "", "title": { "standoff": 15 }, "zerolinecolor": "white", "zerolinewidth": 2 } } }, "xaxis": { "anchor": "y", "domain": [ 0, 1 ], "tickangle": -90, "tickmode": "array", "ticktext": [ "|001100100001⟩", "|001010100001⟩", "|100010001100⟩", "|100001001001⟩", "|010001100010⟩", "|010001010010⟩", "|010010010100⟩", "|100100010001⟩", "|001100001010⟩", "|001010100010⟩", "|001001100100⟩", "|001100010001⟩", "|100010010100⟩", "|010100001010⟩", "|010100010010⟩", "|100001001100⟩", "|001001010001⟩", "|100001100010⟩", "|100001010100⟩", "|001100010100⟩", "|100010100001⟩", "|001010100100⟩", "|001001100001⟩", "|001100001001⟩", "|100001100001⟩", "|100001010001⟩" ], "tickvals": [ 801, 673, 2188, 2121, 1122, 1106, 1172, 2321, 778, 674, 612, 785, 2196, 1290, 1298, 2124, 593, 2146, 2132, 788, 2209, 676, 609, 777, 2145, 2129 ], "title": { "text": "State" }, "type": "category" }, "yaxis": { "anchor": "x", "domain": [ 0, 1 ], "title": { "text": "Count" } } } }, "text/html": [ "
\n
" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "application/vnd.plotly.v1+json": { "config": { "plotlyServerURL": "https://plot.ly" }, "data": [ { "hoverinfo": "none", "line": { "color": "#e74c3c", "dash": "solid", "width": 3 }, "mode": "lines", "name": "Conflict", "type": "scatter", "x": [], "y": [] }, { "hoverinfo": "none", "line": { "color": "#aaaaaa", "dash": "dash", "width": 3 }, "mode": "lines", "name": "OK", "type": "scatter", "x": [ 0.9948268418817919, 0.30639155766771947, null, 0.9948268418817919, -0.3012183995495115, null, 0.30639155766771947, -0.3012183995495115, null, 0.30639155766771947, -1, null, -0.3012183995495115, -1, null ], "y": [ 0.647963182490978, -0.4647540139421561, null, 0.647963182490978, 0.46812332412713853, null, -0.4647540139421561, 0.46812332412713853, null, -0.4647540139421561, -0.6513324926759609, null, 0.46812332412713853, -0.6513324926759609, null ] }, { "hoverinfo": "text", "hovertext": [ "Node 0 → Color 0", "Node 3 → Color 0" ], "marker": { "color": "#e74c3c", "line": { "color": "#333", "width": 2 }, "size": 40 }, "mode": "markers+text", "name": "Color 0", "text": [ "0", "3" ], "textfont": { "color": "white", "size": 14 }, "textposition": "middle center", "type": "scatter", "x": [ 0.9948268418817919, -1 ], "y": [ 0.647963182490978, -0.6513324926759609 ] }, { "hoverinfo": "text", "hovertext": [ "Node 2 → Color 1" ], "marker": { "color": "#2ecc71", "line": { "color": "#333", "width": 2 }, "size": 40 }, "mode": "markers+text", "name": "Color 1", "text": [ "2" ], "textfont": { "color": "white", "size": 14 }, "textposition": "middle center", "type": "scatter", "x": [ -0.3012183995495115 ], "y": [ 0.46812332412713853 ] }, { "hoverinfo": "text", "hovertext": [ "Node 1 → Color 2" ], "marker": { "color": "#3498db", "line": { "color": "#333", "width": 2 }, "size": 40 }, "mode": "markers+text", "name": "Color 2", "text": [ "1" ], "textfont": { "color": "white", "size": 14 }, "textposition": "middle center", "type": "scatter", "x": [ 0.30639155766771947 ], "y": [ -0.4647540139421561 ] } ], "layout": { "hovermode": "closest", "legend": { "x": 0, "y": 1 }, "margin": { "b": 20, "l": 5, "r": 5, "t": 50 }, "showlegend": true, "template": { "data": { "bar": [ { "error_x": { "color": "#2a3f5f" }, "error_y": { "color": "#2a3f5f" }, "marker": { "line": { "color": "#E5ECF6", "width": 0.5 }, "pattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 } }, "type": "bar" } ], "barpolar": [ { "marker": { "line": { "color": "#E5ECF6", "width": 0.5 }, "pattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 } }, "type": "barpolar" } ], "carpet": [ { "aaxis": { "endlinecolor": "#2a3f5f", "gridcolor": "white", "linecolor": "white", "minorgridcolor": "white", "startlinecolor": "#2a3f5f" }, "baxis": { "endlinecolor": "#2a3f5f", "gridcolor": "white", "linecolor": "white", "minorgridcolor": "white", "startlinecolor": "#2a3f5f" }, "type": "carpet" } ], "choropleth": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "type": "choropleth" } ], "contour": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "contour" } ], "contourcarpet": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "type": "contourcarpet" } ], "heatmap": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "heatmap" } ], "histogram": [ { "marker": { "pattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 } }, "type": "histogram" } ], "histogram2d": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "histogram2d" } ], "histogram2dcontour": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "histogram2dcontour" } ], "mesh3d": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "type": "mesh3d" } ], "parcoords": [ { "line": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "parcoords" } ], "pie": [ { "automargin": true, "type": "pie" } ], "scatter": [ { "fillpattern": { "fillmode": "overlay", "size": 10, "solidity": 0.2 }, "type": "scatter" } ], "scatter3d": [ { "line": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatter3d" } ], "scattercarpet": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattercarpet" } ], "scattergeo": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattergeo" } ], "scattergl": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattergl" } ], "scattermap": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattermap" } ], "scattermapbox": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scattermapbox" } ], "scatterpolar": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatterpolar" } ], "scatterpolargl": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatterpolargl" } ], "scatterternary": [ { "marker": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "type": "scatterternary" } ], "surface": [ { "colorbar": { "outlinewidth": 0, "ticks": "" }, "colorscale": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "type": "surface" } ], "table": [ { "cells": { "fill": { "color": "#EBF0F8" }, "line": { "color": "white" } }, "header": { "fill": { "color": "#C8D4E3" }, "line": { "color": "white" } }, "type": "table" } ] }, "layout": { "annotationdefaults": { "arrowcolor": "#2a3f5f", "arrowhead": 0, "arrowwidth": 1 }, "autotypenumbers": "strict", "coloraxis": { "colorbar": { "outlinewidth": 0, "ticks": "" } }, "colorscale": { "diverging": [ [ 0, "#8e0152" ], [ 0.1, "#c51b7d" ], [ 0.2, "#de77ae" ], [ 0.3, "#f1b6da" ], [ 0.4, "#fde0ef" ], [ 0.5, "#f7f7f7" ], [ 0.6, "#e6f5d0" ], [ 0.7, "#b8e186" ], [ 0.8, "#7fbc41" ], [ 0.9, "#4d9221" ], [ 1, "#276419" ] ], "sequential": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ], "sequentialminus": [ [ 0, "#0d0887" ], [ 0.1111111111111111, "#46039f" ], [ 0.2222222222222222, "#7201a8" ], [ 0.3333333333333333, "#9c179e" ], [ 0.4444444444444444, "#bd3786" ], [ 0.5555555555555556, "#d8576b" ], [ 0.6666666666666666, "#ed7953" ], [ 0.7777777777777778, "#fb9f3a" ], [ 0.8888888888888888, "#fdca26" ], [ 1, "#f0f921" ] ] }, "colorway": [ "#636efa", "#EF553B", "#00cc96", "#ab63fa", "#FFA15A", "#19d3f3", "#FF6692", "#B6E880", "#FF97FF", "#FECB52" ], "font": { "color": "#2a3f5f" }, "geo": { "bgcolor": "white", "lakecolor": "white", "landcolor": "#E5ECF6", "showlakes": true, "showland": true, "subunitcolor": "white" }, "hoverlabel": { "align": "left" }, "hovermode": "closest", "mapbox": { "style": "light" }, "paper_bgcolor": "white", "plot_bgcolor": "#E5ECF6", "polar": { "angularaxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" }, "bgcolor": "#E5ECF6", "radialaxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" } }, "scene": { "xaxis": { "backgroundcolor": "#E5ECF6", "gridcolor": "white", "gridwidth": 2, "linecolor": "white", "showbackground": true, "ticks": "", "zerolinecolor": "white" }, "yaxis": { "backgroundcolor": "#E5ECF6", "gridcolor": "white", "gridwidth": 2, "linecolor": "white", "showbackground": true, "ticks": "", "zerolinecolor": "white" }, "zaxis": { "backgroundcolor": "#E5ECF6", "gridcolor": "white", "gridwidth": 2, "linecolor": "white", "showbackground": true, "ticks": "", "zerolinecolor": "white" } }, "shapedefaults": { "line": { "color": "#2a3f5f" } }, "ternary": { "aaxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" }, "baxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" }, "bgcolor": "#E5ECF6", "caxis": { "gridcolor": "white", "linecolor": "white", "ticks": "" } }, "title": { "x": 0.05 }, "xaxis": { "automargin": true, "gridcolor": "white", "linecolor": "white", "ticks": "", "title": { "standoff": 15 }, "zerolinecolor": "white", "zerolinewidth": 2 }, "yaxis": { "automargin": true, "gridcolor": "white", "linecolor": "white", "ticks": "", "title": { "standoff": 15 }, "zerolinecolor": "white", "zerolinewidth": 2 } } }, "title": { "text": "k-Coloring Graph — 0 conflict(s)", "x": 0.5 }, "xaxis": { "showgrid": false, "showticklabels": false, "zeroline": false }, "yaxis": { "showgrid": false, "showticklabels": false, "zeroline": false } } }, "text/html": [ "
\n
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "penalty = 0\n", "k_coloring = partial(graph_coloring_h, edges, num_nodes, num_colors, penalty)\n", "\n", "res, result = qaoa(\n", " problem_h=k_coloring,\n", " mixer_h=partial(graph_coloring_mixer_h, num_nodes, num_colors),\n", " initial_state=partial(graph_coloring_initial_state, num_nodes, num_colors),\n", " num_qubits=num_nodes * num_colors,\n", " p=6,\n", ")\n", "\n", "print(res)\n", "display(result.histogram(\"bin\", hamiltonian=k_coloring))\n", "\n", "plot_k_coloring_graph(\n", " edges,\n", " num_nodes,\n", " num_colors,\n", " result.most_frequent_state(),\n", ")" ] } ], "metadata": { "kernelspec": { "display_name": "quantum-ket.gitlab.io (3.14.6)", "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.14.6" } }, "nbformat": 4, "nbformat_minor": 5 }