{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "ea394d19",
   "metadata": {},
   "source": [
    "# 13 - Quantum Fourier Transform\n",
    "\n",
    "Implement the QFT — the foundation of Shor's algorithm and phase estimation.\n",
    "\n",
    "**Concepts:** QFT, controlled phase rotations, bit reversal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c0952c5b",
   "metadata": {},
   "outputs": [],
   "source": [
    "import quantsdk as qs\n",
    "import math"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1672666a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def qft(n: int) -> qs.Circuit:\n",
    "    \"\"\"Build an n-qubit QFT circuit.\"\"\"\n",
    "    circuit = qs.Circuit(n, name=f\"QFT-{n}\")\n",
    "    \n",
    "    for i in range(n):\n",
    "        circuit.h(i)\n",
    "        for j in range(i + 1, n):\n",
    "            angle = math.pi / (2 ** (j - i))\n",
    "            circuit.cp(i, j, angle)\n",
    "    \n",
    "    # Bit reversal\n",
    "    for i in range(n // 2):\n",
    "        circuit.swap(i, n - 1 - i)\n",
    "    \n",
    "    return circuit\n",
    "\n",
    "def inverse_qft(n: int) -> qs.Circuit:\n",
    "    \"\"\"Build an n-qubit inverse QFT circuit.\"\"\"\n",
    "    circuit = qs.Circuit(n, name=f\"iQFT-{n}\")\n",
    "    \n",
    "    for i in range(n // 2):\n",
    "        circuit.swap(i, n - 1 - i)\n",
    "    \n",
    "    for i in range(n - 1, -1, -1):\n",
    "        for j in range(n - 1, i, -1):\n",
    "            angle = -math.pi / (2 ** (j - i))\n",
    "            circuit.cp(i, j, angle)\n",
    "        circuit.h(i)\n",
    "    \n",
    "    return circuit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cd0b70d7",
   "metadata": {},
   "outputs": [],
   "source": [
    "# QFT on |000> (should stay |000> since FT of delta at 0 is uniform)\n",
    "circuit = qs.Circuit(3)\n",
    "# Apply QFT\n",
    "qft_circ = qft(3)\n",
    "for gate in qft_circ.gates:\n",
    "    circuit._gates.append(gate)  # Append gates\n",
    "circuit.measure_all()\n",
    "\n",
    "result = qs.run(circuit, shots=2000, seed=42)\n",
    "print(\"QFT|000> (should be uniform):\")\n",
    "for bs, count in sorted(result.counts.items()):\n",
    "    print(f\"  |{bs}>: {count/2000:.3f}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "014e9915",
   "metadata": {},
   "outputs": [],
   "source": [
    "# QFT then iQFT should be identity\n",
    "n = 3\n",
    "circuit = qs.Circuit(n)\n",
    "circuit.x(0).x(2)  # Prepare |101>\n",
    "# Apply QFT gates\n",
    "for gate in qft(n).gates:\n",
    "    circuit._gates.append(gate)\n",
    "# Apply iQFT gates\n",
    "for gate in inverse_qft(n).gates:\n",
    "    circuit._gates.append(gate)\n",
    "circuit.measure_all()\n",
    "\n",
    "result = qs.run(circuit, shots=100, seed=42)\n",
    "print(f\"QFT then iQFT on |101>: {result.most_likely} (should be 101)\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "362eff16",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Circuit stats\n",
    "for n in [2, 3, 4, 5]:\n",
    "    circuit = qft(n)\n",
    "    print(f\"QFT-{n}: {circuit.gate_count} gates, depth {circuit.depth}\")"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}