{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "f7c5ce7e",
   "metadata": {},
   "source": [
    "# 12 - Grover's Search\n",
    "\n",
    "Quadratic speedup for unstructured search using amplitude amplification.\n",
    "\n",
    "**Concepts:** Oracle, diffusion operator, amplitude amplification"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "72b9db97",
   "metadata": {},
   "outputs": [],
   "source": [
    "import quantsdk as qs\n",
    "import math"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "809867ed",
   "metadata": {},
   "source": [
    "## 2-Qubit Grover (Search 4 items)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b5f16ed6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def grover_2qubit(target: str = \"11\") -> qs.Circuit:\n",
    "    \"\"\"Grover's search for a 2-bit target.\"\"\"\n",
    "    circuit = qs.Circuit(2, name=f\"grover-{target}\")\n",
    "    \n",
    "    # Superposition\n",
    "    circuit.h(0).h(1)\n",
    "    \n",
    "    # Oracle: flip phase of target\n",
    "    if target[0] == '0': circuit.x(0)\n",
    "    if target[1] == '0': circuit.x(1)\n",
    "    circuit.cz(0, 1)\n",
    "    if target[0] == '0': circuit.x(0)\n",
    "    if target[1] == '0': circuit.x(1)\n",
    "    \n",
    "    # Diffusion\n",
    "    circuit.h(0).h(1)\n",
    "    circuit.x(0).x(1)\n",
    "    circuit.cz(0, 1)\n",
    "    circuit.x(0).x(1)\n",
    "    circuit.h(0).h(1)\n",
    "    \n",
    "    circuit.measure_all()\n",
    "    return circuit\n",
    "\n",
    "# Search for each possible target\n",
    "for target in ['00', '01', '10', '11']:\n",
    "    circuit = grover_2qubit(target)\n",
    "    result = qs.run(circuit, shots=1000, seed=42)\n",
    "    print(f\"Target={target}: found={result.most_likely} (P={result.probabilities.get(target, 0):.3f})\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06ae5ba2",
   "metadata": {},
   "source": [
    "## 3-Qubit Grover (Search 8 items)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aef7ed0e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def grover_3qubit(target: str = \"101\") -> qs.Circuit:\n",
    "    \"\"\"Grover's search for a 3-bit target.\"\"\"\n",
    "    n = 3\n",
    "    num_iterations = int(math.pi / 4 * math.sqrt(2**n))\n",
    "    circuit = qs.Circuit(n, name=f\"grover-{target}\")\n",
    "    \n",
    "    # Superposition\n",
    "    for i in range(n):\n",
    "        circuit.h(i)\n",
    "    \n",
    "    for _ in range(num_iterations):\n",
    "        # Oracle\n",
    "        for i in range(n):\n",
    "            if target[i] == '0':\n",
    "                circuit.x(i)\n",
    "        circuit.ccz(0, 1, 2)\n",
    "        for i in range(n):\n",
    "            if target[i] == '0':\n",
    "                circuit.x(i)\n",
    "        \n",
    "        # Diffusion\n",
    "        for i in range(n): circuit.h(i)\n",
    "        for i in range(n): circuit.x(i)\n",
    "        circuit.ccz(0, 1, 2)\n",
    "        for i in range(n): circuit.x(i)\n",
    "        for i in range(n): circuit.h(i)\n",
    "    \n",
    "    circuit.measure_all()\n",
    "    return circuit\n",
    "\n",
    "target = \"101\"\n",
    "circuit = grover_3qubit(target)\n",
    "result = qs.run(circuit, shots=1000, seed=42)\n",
    "\n",
    "print(f\"Searching for: {target}\")\n",
    "print(f\"Found: {result.most_likely}\")\n",
    "print(f\"Probability: {result.probabilities.get(target, 0):.3f}\")\n",
    "print(f\"Iterations: {int(math.pi/4 * math.sqrt(8))}\")\n",
    "print(f\"\\nFull distribution:\")\n",
    "for bs, count in sorted(result.counts.items(), key=lambda x: -x[1]):\n",
    "    print(f\"  |{bs}>: {count/1000:.3f}\")"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}