{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "f637e1e7",
   "metadata": {},
   "source": [
    "# 11 - Simon's Algorithm\n",
    "\n",
    "Find a hidden period with exponential quantum speedup.\n",
    "\n",
    "**Concepts:** Period finding, 2-to-1 function, linear system"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "043ea373",
   "metadata": {},
   "outputs": [],
   "source": [
    "import quantsdk as qs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "55912382",
   "metadata": {},
   "outputs": [],
   "source": [
    "def simons_circuit(n: int = 2) -> qs.Circuit:\n",
    "    \"\"\"Simon's algorithm for s='11' (n=2).\"\"\"\n",
    "    circuit = qs.Circuit(2 * n, name=\"simons\")\n",
    "    \n",
    "    # Hadamard on input register\n",
    "    for i in range(n):\n",
    "        circuit.h(i)\n",
    "    \n",
    "    # Oracle for s = '11'\n",
    "    circuit.barrier()\n",
    "    circuit.cx(0, 2)\n",
    "    circuit.cx(1, 3)\n",
    "    circuit.cx(0, 3)\n",
    "    circuit.cx(1, 2)\n",
    "    circuit.barrier()\n",
    "    \n",
    "    # Hadamard on input register\n",
    "    for i in range(n):\n",
    "        circuit.h(i)\n",
    "    \n",
    "    # Measure input register\n",
    "    for i in range(n):\n",
    "        circuit.measure(i)\n",
    "    \n",
    "    return circuit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "17724dbe",
   "metadata": {},
   "outputs": [],
   "source": [
    "circuit = simons_circuit()\n",
    "result = qs.run(circuit, shots=1000, seed=42)\n",
    "\n",
    "print(\"Simon's algorithm results (s='11'):\")\n",
    "print(f\"Counts: {result.counts}\")\n",
    "print()\n",
    "print(\"Valid outputs y must satisfy s.y = 0 (mod 2):\")\n",
    "print(\"  y=00: 11.00 = 0 mod 2 = 0  (valid)\")\n",
    "print(\"  y=11: 11.11 = 1+1 = 0 mod 2 = 0  (valid)\")\n",
    "print(\"\\nFrom y=11: s.y=0, plus s != 00 -> s = 11\")"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}