{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "094d99e8",
   "metadata": {},
   "source": [
    "# 16 - QAOA for MaxCut\n",
    "\n",
    "Solve MaxCut on a small graph using the Quantum Approximate Optimization Algorithm.\n",
    "\n",
    "**Concepts:** Combinatorial optimization, cost/mixer layers, variational circuit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a834fa62",
   "metadata": {},
   "outputs": [],
   "source": [
    "import quantsdk as qs\n",
    "import math\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c41a2010",
   "metadata": {},
   "source": [
    "## Triangle Graph\n",
    "\n",
    "Edges: (0,1), (1,2), (0,2). MaxCut = 2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "28de2b85",
   "metadata": {},
   "outputs": [],
   "source": [
    "edges = [(0, 1), (1, 2), (0, 2)]\n",
    "n = 3\n",
    "\n",
    "def qaoa_circuit(gamma: float, beta: float) -> qs.Circuit:\n",
    "    \"\"\"QAOA p=1 circuit for MaxCut on a triangle.\"\"\"\n",
    "    circuit = qs.Circuit(n, name=\"QAOA\")\n",
    "    \n",
    "    # Initial superposition\n",
    "    for i in range(n):\n",
    "        circuit.h(i)\n",
    "    \n",
    "    # Cost layer: e^(-i*gamma*C)\n",
    "    for i, j in edges:\n",
    "        circuit.cx(i, j)\n",
    "        circuit.rz(j, 2 * gamma)\n",
    "        circuit.cx(i, j)\n",
    "    \n",
    "    # Mixer layer: e^(-i*beta*B)\n",
    "    for i in range(n):\n",
    "        circuit.rx(i, 2 * beta)\n",
    "    \n",
    "    circuit.measure_all()\n",
    "    return circuit\n",
    "\n",
    "def maxcut_value(bitstring: str) -> int:\n",
    "    \"\"\"Count edges crossing the cut.\"\"\"\n",
    "    return sum(1 for i, j in edges if bitstring[i] != bitstring[j])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "47aac81a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def expected_cut(gamma: float, beta: float, shots: int = 4000) -> float:\n",
    "    \"\"\"Compute expected MaxCut value.\"\"\"\n",
    "    circuit = qaoa_circuit(gamma, beta)\n",
    "    result = qs.run(circuit, shots=shots, seed=42)\n",
    "    total = sum(maxcut_value(bs) * count for bs, count in result.counts.items())\n",
    "    return total / shots\n",
    "\n",
    "# Grid search\n",
    "best_cut = 0\n",
    "best_params = (0, 0)\n",
    "gammas = np.linspace(0, math.pi, 15)\n",
    "betas = np.linspace(0, math.pi / 2, 15)\n",
    "\n",
    "for g in gammas:\n",
    "    for b in betas:\n",
    "        cut = expected_cut(g, b)\n",
    "        if cut > best_cut:\n",
    "            best_cut = cut\n",
    "            best_params = (g, b)\n",
    "\n",
    "print(f\"Best gamma={best_params[0]:.3f}, beta={best_params[1]:.3f}\")\n",
    "print(f\"Expected cut: {best_cut:.3f} (optimal=2)\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "36705406",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Run with best parameters\n",
    "circuit = qaoa_circuit(*best_params)\n",
    "result = qs.run(circuit, shots=2000, seed=42)\n",
    "\n",
    "print(\"QAOA results:\")\n",
    "for bs, count in sorted(result.counts.items(), key=lambda x: -x[1]):\n",
    "    cut = maxcut_value(bs)\n",
    "    print(f\"  |{bs}>: count={count}, cut={cut} {'<-- optimal' if cut == 2 else ''}\")"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}