{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "0a3994e5",
   "metadata": {},
   "source": [
    "# Two oracle algorithms: recover bits and recover a hidden XOR period\n",
    "\n",
    "**Level:** Undergraduate · **Book connections:** P06, P08, P09, P11, P13, A04, A05\n",
    "\n",
    "After this notebook you can:\n",
    "\n",
    "- Build a supplied oracle separately from the algorithm that queries it.\n",
    "- Recover a Bernstein–Vazirani string from a real circuit.\n",
    "- Collect Simon equations and solve their nullspace over GF(2).\n",
    "\n",
    "Run cells from top to bottom in the pinned environment described in `README.md`. All default execution is local. Exact amplitudes are simulator information; a QPU supplies sampled outcomes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b2b83c35",
   "metadata": {},
   "outputs": [],
   "source": [
    "from importlib.metadata import version\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from IPython.display import display\n",
    "from qiskit import QuantumCircuit\n",
    "from qiskit.quantum_info import Statevector\n",
    "\n",
    "EXPECTED = {\"qiskit\": \"2.6.1\", \"qiskit-aer\": \"0.18.2\", \"qiskit-ibm-runtime\": \"0.51.0\"}\n",
    "for package, expected in EXPECTED.items():\n",
    "    actual = version(package)\n",
    "    assert actual == expected, f\"Use the supplied environment: {package}={actual}, expected {expected}\"\n",
    "print(\"Verified package versions:\", EXPECTED)\n",
    "plt.rcParams.update({\"figure.figsize\": (8, 3.5), \"font.size\": 11, \"axes.spines.top\": False,\n",
    "                     \"axes.spines.right\": False, \"axes.prop_cycle\": plt.cycler(color=[\"#006DAE\", \"#00A6B2\", \"#9E4A78\"])})\n",
    "SEED = 20261106\n",
    "\n",
    "def draw(circuit):\n",
    "    \"\"\"Render a real circuit; each wire is a qubit, time runs left to right.\"\"\"\n",
    "    fig = circuit.draw(output=\"mpl\", fold=90, style=\"iqp\")\n",
    "    display(fig)\n",
    "    plt.close(fig)\n",
    "\n",
    "def book_label(qiskit_label):\n",
    "    \"\"\"For a single register, show q0 first as in the book.\"\"\"\n",
    "    return qiskit_label[::-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0a6a1758",
   "metadata": {},
   "source": [
    "**Read the wires and bit strings carefully.** Qiskit draws `q0` on the top wire, but a\n",
    "standard statevector basis label or measured single-register count key is written\n",
    "`q(n−1)…q1q0`: `q0` has integer weight $2^0$. The book often writes `q0` first.\n",
    "These notebooks keep native Qiskit labels in calculations and use `book_label`\n",
    "only for an explicitly labelled display. Reversing a label changes the display;\n",
    "it does not apply a SWAP gate. All count examples here use one classical register\n",
    "with measurement `qj → cj`; do not reverse arbitrary multi-register strings."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eee03a37",
   "metadata": {},
   "source": [
    "## 1. Bernstein–Vazirani: one query in the ideal oracle model\n",
    "\n",
    "The supplied function is $f_s(x)=s\\cdot x\\pmod2$. An oracle acts as\n",
    "$U_f|x\\rangle|b\\rangle=|x\\rangle|b\\oplus f_s(x)\\rangle$. Preparing its\n",
    "answer qubit in $|{-}\\rangle$ turns function values into phases:\n",
    "\n",
    "$$\\frac1{\\sqrt{2^n}}\\sum_x|x\\rangle|{-}\\rangle\n",
    "  \\xrightarrow{U_f}\\frac1{\\sqrt{2^n}}\\sum_x(-1)^{s\\cdot x}|x\\rangle|{-}\\rangle\n",
    "  \\xrightarrow{H^{\\otimes n}}|s\\rangle|{-}\\rangle.$$\n",
    "\n",
    "We know the secret while constructing a test oracle. The recovery circuit\n",
    "receives the oracle and its width, not a direct copy of the answer. The query\n",
    "advantage assumes access to that oracle; constructing a real data oracle has a cost."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d1cfc210",
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit.primitives import StatevectorSampler\n",
    "def bv_oracle(secret_q0_first):\n",
    "    n = len(secret_q0_first)\n",
    "    oracle = QuantumCircuit(n+1, name=\"U_f\")\n",
    "    for q, bit in enumerate(secret_q0_first):\n",
    "        if bit:\n",
    "            oracle.cx(q, n)\n",
    "    return oracle.to_gate()\n",
    "\n",
    "def bv_circuit(oracle, n):\n",
    "    circuit = QuantumCircuit(n+1, n)\n",
    "    circuit.x(n)\n",
    "    circuit.h(range(n+1))\n",
    "    circuit.append(oracle, range(n+1))\n",
    "    circuit.h(range(n))\n",
    "    circuit.measure(range(n), range(n))\n",
    "    return circuit\n",
    "\n",
    "supplied_secret = [1, 0, 1, 1]  # q0 first; oracle-instance construction only.\n",
    "bv = bv_circuit(bv_oracle(supplied_secret), len(supplied_secret))\n",
    "draw(bv.decompose(gates_to_decompose=\"U_f\"))\n",
    "bv_counts = StatevectorSampler(seed=SEED).run([bv], shots=64).result()[0].data.c.get_counts()\n",
    "recovered_native = max(bv_counts, key=bv_counts.get)\n",
    "assert len(bv_counts) == 1\n",
    "assert book_label(recovered_native) == \"\".join(map(str, supplied_secret))\n",
    "print(\"Recovered native label:\", recovered_native, \"; q0-first display:\", book_label(recovered_native))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "17a7ae36",
   "metadata": {},
   "source": [
    "## 2. Simon: each shot gives a linear equation\n",
    "\n",
    "For nonzero $s$, a promised two-to-one function obeys\n",
    "$f(x)=f(x\\oplus s)$ and has no other collisions. After H, oracle, H on the input\n",
    "register, a measured $y$ satisfies\n",
    "\n",
    "$$s\\cdot y=0\\pmod2.$$\n",
    "\n",
    "One shot usually leaves several candidates. Collect independent equations,\n",
    "then find a nullspace over the two-element field GF(2). We create a family of\n",
    "genuine two-to-one linear oracles by choosing a nonzero pivot bit of $s$ and\n",
    "returning $x\\oplus x_p s$. Its pivot output is always zero and its kernel is\n",
    "exactly $\\{0,s\\}$. This supplies a simple instance of Simon's promise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "840a138c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def simon_oracle(secret_q0_first):\n",
    "    secret = list(secret_q0_first)\n",
    "    if not any(secret) or any(bit not in [0, 1] for bit in secret):\n",
    "        raise ValueError(\"Choose a nonzero binary secret\")\n",
    "    n = len(secret)\n",
    "    pivot = secret.index(1)\n",
    "    oracle = QuantumCircuit(2*n, name=\"U_f\")\n",
    "    for j in range(n):\n",
    "        if j != pivot:\n",
    "            oracle.cx(j, n+j)\n",
    "            if secret[j]:\n",
    "                oracle.cx(pivot, n+j)\n",
    "    return oracle.to_gate()\n",
    "\n",
    "def simon_circuit(oracle, n):\n",
    "    circuit = QuantumCircuit(2*n, n)\n",
    "    circuit.h(range(n))\n",
    "    circuit.append(oracle, range(2*n))\n",
    "    circuit.h(range(n))\n",
    "    circuit.measure(range(n), range(n))\n",
    "    return circuit\n",
    "\n",
    "supplied_s = [1, 1, 0]  # q0-first construction; deliberately asymmetric.\n",
    "n = len(supplied_s)\n",
    "simon = simon_circuit(simon_oracle(supplied_s), n)\n",
    "draw(simon.decompose(gates_to_decompose=\"U_f\"))\n",
    "simon_counts = StatevectorSampler(seed=SEED).run([simon], shots=64).result()[0].data.c.get_counts()\n",
    "rows = [[int(bit) for bit in key[::-1]] for key in simon_counts]\n",
    "print(\"Observed native q2q1q0 counts:\", simon_counts)\n",
    "print(\"Equations' coefficients in q0-first order:\", rows)\n",
    "for row in rows:\n",
    "    assert np.dot(row, supplied_s) % 2 == 0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "30d8382f",
   "metadata": {},
   "source": [
    "## 3. Solve the equations, rather than returning the stored secret\n",
    "\n",
    "Gaussian elimination uses XOR in place of row subtraction. A rank $n-1$\n",
    "equation matrix has one free variable and hence a one-dimensional nullspace.\n",
    "Its unique nonzero vector is the recovered period. More shots may repeat old\n",
    "equations; use a rank condition instead of assuming every shot is useful."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d9cc30cd",
   "metadata": {},
   "outputs": [],
   "source": [
    "def gf2_nullspace(rows, width):\n",
    "    matrix = np.array(rows, dtype=np.uint8).reshape(-1, width).copy() % 2\n",
    "    pivots = []\n",
    "    r = 0\n",
    "    for col in range(width):\n",
    "        choices = np.flatnonzero(matrix[r:, col])\n",
    "        if len(choices) == 0:\n",
    "            continue\n",
    "        k = r + choices[0]\n",
    "        matrix[[r, k]] = matrix[[k, r]]\n",
    "        for other in range(len(matrix)):\n",
    "            if other != r and matrix[other, col]:\n",
    "                matrix[other] ^= matrix[r]\n",
    "        pivots.append(col)\n",
    "        r += 1\n",
    "        if r == len(matrix):\n",
    "            break\n",
    "    basis = []\n",
    "    for free in [j for j in range(width) if j not in pivots]:\n",
    "        vector = np.zeros(width, dtype=np.uint8)\n",
    "        vector[free] = 1\n",
    "        for row, pivot in enumerate(pivots):\n",
    "            vector[pivot] = matrix[row, free]\n",
    "        basis.append(vector)\n",
    "    return basis, len(pivots)\n",
    "\n",
    "basis, rank = gf2_nullspace(rows, n)\n",
    "assert rank == n-1, \"Collect more equations until the rank reaches n-1\"\n",
    "assert len(basis) == 1\n",
    "recovered = basis[0].tolist()  # This computation has no access to supplied_s.\n",
    "assert recovered == supplied_s  # Separate test oracle checks the result.\n",
    "print(\"Rank:\", rank, \"recovered q0-first period:\", recovered)\n",
    "\n",
    "# Verify the oracle promise independently on all eight classical inputs.\n",
    "# This exhaustive test is deliberately small; it is not part of the quantum query count.\n",
    "oracle = simon_oracle(supplied_s)\n",
    "classical_outputs = []\n",
    "for x in range(2**n):\n",
    "    trial = QuantumCircuit(2*n)\n",
    "    for j in range(n):\n",
    "        if (x >> j) & 1:\n",
    "            trial.x(j)\n",
    "    trial.append(oracle, range(2*n))\n",
    "    output = Statevector.from_instruction(trial).probabilities(qargs=list(range(n, 2*n)))\n",
    "    assert np.isclose(output.max(), 1)\n",
    "    classical_outputs.append(int(np.argmax(output)))\n",
    "mask = sum(bit << j for j, bit in enumerate(supplied_s))\n",
    "for x in range(2**n):\n",
    "    partners = [z for z in range(2**n) if classical_outputs[z] == classical_outputs[x]]\n",
    "    assert set(partners) == {x, x ^ mask}\n",
    "print(\"Two-to-one promise checked for this small instance.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c3ee78c8",
   "metadata": {},
   "source": [
    "## Checkpoint and practice\n",
    "\n",
    "Does a `000` Simon sample prove that the hidden string is zero?\n",
    "**No:** it gives the equation $0=0$, which every string satisfies. It adds no rank.\n",
    "\n",
    "1. Try each nonzero three-bit secret and repeat the rank-based recovery test.\n",
    "2. Change one CNOT in the oracle. Test the promise before interpreting recovery.\n",
    "3. Draw the amplitude signs immediately before the final H gates in BV. Connect\n",
    "   the signs to the deterministic output rather than treating H as a magic decoder.\n",
    "\n",
    "**Takeaway:** verify the promised input structure and the classical post-processing,\n",
    "not merely a familiar-looking final histogram."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5fec4f83",
   "metadata": {},
   "source": [
    "## Sources\n",
    "\n",
    "- [IBM: bit ordering](https://quantum.cloud.ibm.com/docs/en/guides/bit-ordering)\n",
    "- [IBM: Statevector API](https://quantum.cloud.ibm.com/docs/en/api/qiskit/qiskit.quantum_info.Statevector)\n",
    "- [Bernstein and Vazirani: Quantum complexity theory (original paper)](https://doi.org/10.1137/S0097539796300921)\n",
    "- [Simon: On the power of quantum computation (original paper)](https://doi.org/10.1137/S0097539796298637)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Quantum book (pinned Python)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.13.2"
  },
  "quantum_book": {
   "chapters": [
    "P06",
    "P08",
    "P09",
    "P11",
    "P13",
    "A04",
    "A05"
   ],
   "expected_packages": {
    "qiskit": "2.6.1",
    "qiskit-aer": "0.18.2",
    "qiskit-ibm-runtime": "0.51.0"
   },
   "level": "Undergraduate",
   "network_on_default_run": false,
   "verified_release_date": "2026-11-06"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}