{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "76558078",
   "metadata": {},
   "source": [
    "# 09 - Deutsch-Jozsa Algorithm\n",
    "\n",
    "Determine if a function is constant or balanced with a single quantum query.\n",
    "\n",
    "**Concepts:** Oracle, quantum parallelism, deterministic speedup"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f0b0a0d4",
   "metadata": {},
   "outputs": [],
   "source": [
    "import quantsdk as qs"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "00f12fa8",
   "metadata": {},
   "source": [
    "## Helper: Build Deutsch-Jozsa Circuit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "75285776",
   "metadata": {},
   "outputs": [],
   "source": [
    "def deutsch_jozsa(n: int, oracle_type: str) -> qs.Circuit:\n",
    "    \"\"\"Build a Deutsch-Jozsa circuit.\n",
    "    \n",
    "    Args:\n",
    "        n: Number of input qubits.\n",
    "        oracle_type: 'constant_0', 'constant_1', or 'balanced'.\n",
    "    \"\"\"\n",
    "    circuit = qs.Circuit(n + 1, name=f\"DJ-{oracle_type}\")\n",
    "    \n",
    "    # Initialize ancilla to |1>\n",
    "    circuit.x(n)\n",
    "    \n",
    "    # Hadamard all qubits\n",
    "    for i in range(n + 1):\n",
    "        circuit.h(i)\n",
    "    \n",
    "    # Oracle\n",
    "    circuit.barrier()\n",
    "    if oracle_type == 'constant_0':\n",
    "        pass  # f(x) = 0 for all x\n",
    "    elif oracle_type == 'constant_1':\n",
    "        circuit.x(n)  # f(x) = 1 for all x\n",
    "    elif oracle_type == 'balanced':\n",
    "        for i in range(n):\n",
    "            circuit.cx(i, n)  # f(x) = x0 XOR x1 XOR ...\n",
    "    circuit.barrier()\n",
    "    \n",
    "    # Hadamard input qubits\n",
    "    for i in range(n):\n",
    "        circuit.h(i)\n",
    "    \n",
    "    # Measure input qubits only\n",
    "    for i in range(n):\n",
    "        circuit.measure(i)\n",
    "    \n",
    "    return circuit"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "042fdad4",
   "metadata": {},
   "source": [
    "## Test with Different Oracles"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dd9fb567",
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 3  # 3 input qubits\n",
    "\n",
    "for oracle in ['constant_0', 'constant_1', 'balanced']:\n",
    "    circuit = deutsch_jozsa(n, oracle)\n",
    "    result = qs.run(circuit, shots=100, seed=42)\n",
    "    outcome = result.most_likely\n",
    "    is_constant = all(b == '0' for b in outcome)\n",
    "    verdict = \"CONSTANT\" if is_constant else \"BALANCED\"\n",
    "    print(f\"Oracle={oracle:12s}: outcome={outcome} -> {verdict}\")\n",
    "\n",
    "print(\"\\nAll correct with just ONE quantum query!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e5ed3891",
   "metadata": {},
   "source": [
    "## Scaling"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f1548a03",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Works for any n — still just 1 query\n",
    "for n in [2, 4, 6, 8, 10]:\n",
    "    circuit = deutsch_jozsa(n, 'balanced')\n",
    "    result = qs.run(circuit, shots=1, seed=42)\n",
    "    outcome = result.most_likely\n",
    "    is_balanced = any(b == '1' for b in outcome)\n",
    "    print(f\"n={n:2d}: {outcome} -> {'BALANCED' if is_balanced else 'CONSTANT'} (classical needs {2**(n-1)+1} queries)\")"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}