{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "f739d465",
   "metadata": {},
   "source": [
    "# 10 - Bernstein-Vazirani Algorithm\n",
    "\n",
    "Find a hidden binary string with a single quantum query.\n",
    "\n",
    "**Concepts:** Hidden string, phase kickback, linear algebra"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b9d334ef",
   "metadata": {},
   "outputs": [],
   "source": [
    "import quantsdk as qs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "df13a8cb",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bernstein_vazirani(secret: str) -> qs.Circuit:\n",
    "    \"\"\"Build a Bernstein-Vazirani circuit to find the secret string.\"\"\"\n",
    "    n = len(secret)\n",
    "    circuit = qs.Circuit(n + 1, name=f\"BV-{secret}\")\n",
    "    \n",
    "    # Initialize ancilla\n",
    "    circuit.x(n)\n",
    "    \n",
    "    # Hadamard all\n",
    "    for i in range(n + 1):\n",
    "        circuit.h(i)\n",
    "    \n",
    "    # Oracle: CNOT from qubit i to ancilla where secret[i] = '1'\n",
    "    circuit.barrier()\n",
    "    for i, bit in enumerate(secret):\n",
    "        if bit == '1':\n",
    "            circuit.cx(i, n)\n",
    "    circuit.barrier()\n",
    "    \n",
    "    # Hadamard input qubits\n",
    "    for i in range(n):\n",
    "        circuit.h(i)\n",
    "    \n",
    "    # Measure\n",
    "    for i in range(n):\n",
    "        circuit.measure(i)\n",
    "    \n",
    "    return circuit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "be7bbdac",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test with various secret strings\n",
    "secrets = [\"101\", \"1101\", \"11010\", \"10110011\"]\n",
    "\n",
    "for secret in secrets:\n",
    "    circuit = bernstein_vazirani(secret)\n",
    "    result = qs.run(circuit, shots=1, seed=42)  # Just 1 shot needed!\n",
    "    found = result.most_likely\n",
    "    match = \"MATCH\" if found == secret else \"MISMATCH\"\n",
    "    print(f\"Secret={secret:10s} Found={found:10s} [{match}]\")\n",
    "\n",
    "print(f\"\\nClassical would need {len(secrets[-1])} queries for the last one.\")\n",
    "print(f\"Quantum needs just 1!\")"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}