{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"id": "a005e247",
"metadata": {
"execution": {
"iopub.execute_input": "2026-08-05T16:35:50.284982Z",
"iopub.status.busy": "2026-08-05T16:35:50.284807Z",
"iopub.status.idle": "2026-08-05T16:35:50.733741Z",
"shell.execute_reply": "2026-08-05T16:35:50.733410Z"
}
},
"outputs": [
{
"data": {
"text/plain": [
"['Ket v0.10.1',\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": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from typing import Callable\n",
"from functools import partial\n",
"\n",
"from scipy.optimize import minimize, OptimizeResult\n",
"from IPython.display import display\n",
"\n",
"import plotly.io as pio\n",
"pio.renderers.default = \"notebook_connected\"\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": 2,
"id": "530bd12f",
"metadata": {
"execution": {
"iopub.execute_input": "2026-08-05T16:35:50.735220Z",
"iopub.status.busy": "2026-08-05T16:35:50.735097Z",
"iopub.status.idle": "2026-08-05T16:35:50.739132Z",
"shell.execute_reply": "2026-08-05T16:35:50.738790Z"
}
},
"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, simulator=\"dense\")\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",
" 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": 3,
"id": "maxcut_plotly_func",
"metadata": {
"execution": {
"iopub.execute_input": "2026-08-05T16:35:50.740088Z",
"iopub.status.busy": "2026-08-05T16:35:50.740018Z",
"iopub.status.idle": "2026-08-05T16:35:50.744165Z",
"shell.execute_reply": "2026-08-05T16:35:50.743836Z"
}
},
"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": 4,
"id": "ffb1cf5b",
"metadata": {
"execution": {
"iopub.execute_input": "2026-08-05T16:35:50.744913Z",
"iopub.status.busy": "2026-08-05T16:35:50.744850Z",
"iopub.status.idle": "2026-08-05T16:35:52.108820Z",
"shell.execute_reply": "2026-08-05T16:35:52.107722Z"
}
},
"outputs": [
{
"data": {
"text/html": [
" \n",
" \n",
" "
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
""
]
},
"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": [
"### Max-Cut 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": 5,
"id": "1cdf1dbf",
"metadata": {
"execution": {
"iopub.execute_input": "2026-08-05T16:35:52.112759Z",
"iopub.status.busy": "2026-08-05T16:35:52.111866Z",
"iopub.status.idle": "2026-08-05T16:35:52.118706Z",
"shell.execute_reply": "2026-08-05T16:35:52.117809Z"
}
},
"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": 6,
"id": "mixer_code",
"metadata": {
"execution": {
"iopub.execute_input": "2026-08-05T16:35:52.121597Z",
"iopub.status.busy": "2026-08-05T16:35:52.121361Z",
"iopub.status.idle": "2026-08-05T16:35:52.125951Z",
"shell.execute_reply": "2026-08-05T16:35:52.125094Z"
}
},
"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": 7,
"id": "exec_maxcut",
"metadata": {
"execution": {
"iopub.execute_input": "2026-08-05T16:35:52.128524Z",
"iopub.status.busy": "2026-08-05T16:35:52.128317Z",
"iopub.status.idle": "2026-08-05T16:35:54.722063Z",
"shell.execute_reply": "2026-08-05T16:35:54.720732Z"
}
},
"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": {
"text/html": [
""
]
},
"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": 8,
"id": "result_viz",
"metadata": {
"execution": {
"iopub.execute_input": "2026-08-05T16:35:54.725053Z",
"iopub.status.busy": "2026-08-05T16:35:54.724596Z",
"iopub.status.idle": "2026-08-05T16:35:56.023459Z",
"shell.execute_reply": "2026-08-05T16:35:56.022362Z"
}
},
"outputs": [
{
"data": {
"text/html": [
""
]
},
"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": [
"### Portfolio 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": 9,
"id": "portfolio_h",
"metadata": {
"execution": {
"iopub.execute_input": "2026-08-05T16:35:56.027732Z",
"iopub.status.busy": "2026-08-05T16:35:56.027431Z",
"iopub.status.idle": "2026-08-05T16:35:56.035250Z",
"shell.execute_reply": "2026-08-05T16:35:56.034338Z"
}
},
"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": 10,
"id": "portfolio_exec",
"metadata": {
"execution": {
"iopub.execute_input": "2026-08-05T16:35:56.038394Z",
"iopub.status.busy": "2026-08-05T16:35:56.038131Z",
"iopub.status.idle": "2026-08-05T16:36:07.166082Z",
"shell.execute_reply": "2026-08-05T16:36:07.164609Z"
}
},
"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": {
"text/html": [
""
]
},
"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",
""
]
},
{
"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": 11,
"id": "coloring_plotly_func",
"metadata": {
"execution": {
"iopub.execute_input": "2026-08-05T16:36:07.170424Z",
"iopub.status.busy": "2026-08-05T16:36:07.169702Z",
"iopub.status.idle": "2026-08-05T16:36:07.183567Z",
"shell.execute_reply": "2026-08-05T16:36:07.183118Z"
}
},
"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",
""
]
},
{
"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": 12,
"id": "k_color_h",
"metadata": {
"execution": {
"iopub.execute_input": "2026-08-05T16:36:07.185274Z",
"iopub.status.busy": "2026-08-05T16:36:07.185162Z",
"iopub.status.idle": "2026-08-05T16:36:07.188618Z",
"shell.execute_reply": "2026-08-05T16:36:07.187896Z"
}
},
"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": [
"### Graph Coloring 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": 13,
"id": "coloring_instance",
"metadata": {
"execution": {
"iopub.execute_input": "2026-08-05T16:36:07.190082Z",
"iopub.status.busy": "2026-08-05T16:36:07.189921Z",
"iopub.status.idle": "2026-08-05T16:36:08.462361Z",
"shell.execute_reply": "2026-08-05T16:36:08.460872Z"
}
},
"outputs": [
{
"data": {
"text/html": [
""
]
},
"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": 14,
"id": "standard_mixer_attempt",
"metadata": {
"execution": {
"iopub.execute_input": "2026-08-05T16:36:08.466118Z",
"iopub.status.busy": "2026-08-05T16:36:08.465900Z",
"iopub.status.idle": "2026-08-05T16:36:32.802082Z",
"shell.execute_reply": "2026-08-05T16:36:32.800841Z"
}
},
"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": {
"text/html": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
""
]
},
"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": 15,
"id": "xy_mixer_code",
"metadata": {
"execution": {
"iopub.execute_input": "2026-08-05T16:36:32.805911Z",
"iopub.status.busy": "2026-08-05T16:36:32.805608Z",
"iopub.status.idle": "2026-08-05T16:36:32.813211Z",
"shell.execute_reply": "2026-08-05T16:36:32.812297Z"
}
},
"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": 16,
"id": "coloring_initial_state",
"metadata": {
"execution": {
"iopub.execute_input": "2026-08-05T16:36:32.815587Z",
"iopub.status.busy": "2026-08-05T16:36:32.815374Z",
"iopub.status.idle": "2026-08-05T16:36:32.819998Z",
"shell.execute_reply": "2026-08-05T16:36:32.818878Z"
}
},
"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": 17,
"id": "xy_exec",
"metadata": {
"execution": {
"iopub.execute_input": "2026-08-05T16:36:32.823754Z",
"iopub.status.busy": "2026-08-05T16:36:32.823558Z",
"iopub.status.idle": "2026-08-05T16:37:19.583596Z",
"shell.execute_reply": "2026-08-05T16:37:19.582465Z"
}
},
"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.4703870242552477\n",
" x: [ 1.489e+00 1.730e+00 1.475e+00 3.027e-01 2.740e-01\n",
" 9.969e-01 4.157e-01 3.092e-01 2.825e-01 3.039e-01\n",
" 2.002e-01 -2.976e-01]\n",
" nfev: 1000\n",
" maxcv: 0.0\n"
]
},
{
"data": {
"text/html": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
""
]
},
"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.final.0)",
"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
}