{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "parity-00",
   "metadata": {},
   "source": [
    "# Parity with measurement and feed-forward\n",
    "\n",
    "**Download Notebook** - {nb-download}`parity_laqcc.ipynb`\n",
    "\n",
    "- `parity_laqcc` combines several input qubits into one parity target. It XORs the input parity into the target:\n",
    "\n",
    "$$\n",
    "|x_0,\\ldots,x_{n-1}\\rangle|t\\rangle\n",
    "\\longmapsto\n",
    "|x_0,\\ldots,x_{n-1}\\rangle\n",
    "\\left|t\\oplus\\bigoplus_{j=0}^{n-1}x_j\\right\\rangle.\n",
    "$$\n",
    "\n",
    "- An odd number of input ones flips the target; an even number leaves it unchanged. The target can start in either state.\n",
    "- The operation also works coherently on superpositions. Internal ancilla measurements drive corrections rather than reading out the input parity.\n",
    "- Run from a source checkout with development dependencies installed. The repository default is little endian."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "parity-01",
   "metadata": {
    "tags": [
     "hide-input"
    ]
   },
   "outputs": [],
   "source": [
    "import itertools\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "from guppylang import guppy\n",
    "from guppylang.std.builtins import array, output\n",
    "from guppylang.std.quantum import (\n",
    "    collect_measurements, measure, measure_array, qubit, x, h, discard_array,\n",
    ")\n",
    "from guppylang.std.debug import state_output\n",
    "from selene_sim import QuantumReplay, Quest\n",
    "from guppyalgos.primitives.subroutines.parity import (\n",
    "    parity_laqcc, parity_laqcc_total_qubits, parity_sequential,\n",
    ")\n",
    "from guppyalgos.utils import qarray, transversal\n",
    "from guppyalgos.tests.helpers import assert_allclose_ignorephase"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "parity-02",
   "metadata": {},
   "source": [
    "## 1. Choose the implementation\n",
    "\n",
    "- `parity_sequential` uses controlled gates without extra qubits.\n",
    "- For four or more inputs, `parity_laqcc` uses two ancilla registers and classical feed-forward to arrange the quantum gates in constant-depth layers. This trades extra qubits and measurement feedback for quantum depth; it does not imply constant execution time on every device.\n",
    "- With fewer than four inputs, it falls back to the sequential circuit. Both implementations use the same call: `parity(target, qreg)`.\n",
    "- Use the built-in helper to size the simulator:\n",
    "\n",
    "$$\n",
    "N_{\\mathrm{total}}=n+1+2\\max(n-3,0).\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "parity-03",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 inputs + 1 target + 2 ancillas = 7 qubits\n"
     ]
    }
   ],
   "source": [
    "n_inputs = 4\n",
    "total_qubits = parity_laqcc_total_qubits(n_inputs)\n",
    "print(f\"{n_inputs} inputs + 1 target + {total_qubits - n_inputs - 1} ancillas = {total_qubits} qubits\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "parity-04",
   "metadata": {},
   "source": [
    "## 2. Check even and odd parity\n",
    "\n",
    "- Prepare a computational-basis input, apply parity, and measure both registers.\n",
    "- For $|1,0,1,1\\rangle$, the input parity is $1\\oplus0\\oplus1\\oplus1=1$. The target flips from $0$ to $1$, or from $1$ to $0$.\n",
    "- Compile once and reuse the emulator for each input. The table also checks that the input bits are preserved."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "parity-05",
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "Input bits Parity Initial target Final target\n1, 0, 1, 1    Odd              0            1\n1, 0, 1, 1    Odd              1            0\n1, 0, 1, 0   Even              0            0\n1, 0, 1, 0   Even              1            1\n"
     ]
    }
   ],
   "source": [
    "@guppy\n",
    "def basis_example(bits: array[bool, 4], target_bit: bool) -> None:\n",
    "    qreg = qarray(n_inputs)\n",
    "    target = qubit()\n",
    "    for i in range(n_inputs):\n",
    "        if bits[i]:\n",
    "            x(qreg[i])\n",
    "    if target_bit:\n",
    "        x(target)\n",
    "    parity_laqcc(target, qreg)\n",
    "    output(\"inputs\", collect_measurements(measure_array(qreg)))\n",
    "    output(\"target\", measure(target).read())\n",
    "\n",
    "\n",
    "emulator = basis_example.emulator(total_qubits).with_seed(42)\n",
    "rows = []\n",
    "for bits in [[True, False, True, True], [True, False, True, False]]:\n",
    "    for target_bit in [False, True]:\n",
    "        shot = emulator.run(bits=bits, target_bit=target_bit).collated_shots()[0]\n",
    "        expected = target_bit ^ (sum(bits) % 2 == 1)\n",
    "        assert shot[\"inputs\"][0] == bits\n",
    "        assert shot[\"target\"][0] == expected\n",
    "        rows.append({\n",
    "            \"Input bits\": \", \".join(str(int(bit)) for bit in bits),\n",
    "            \"Parity\": \"Odd\" if sum(bits) % 2 else \"Even\",\n",
    "            \"Initial target\": int(target_bit), \"Final target\": int(shot[\"target\"][0]),\n",
    "        })\n",
    "print(pd.DataFrame(rows).to_string(index=False, float_format=lambda value: f\"{value:.4f}\"))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "parity-06",
   "metadata": {},
   "source": [
    "## 3. Check coherence across measurement branches\n",
    "\n",
    "- Start with $|+\\rangle^{\\otimes4}|0\\rangle$. Parity entangles the target with the inputs:\n",
    "\n",
    "$$\n",
    "\\frac14\\sum_{x\\in\\{0,1\\}^4}|x\\rangle|0\\rangle\n",
    "\\longmapsto\n",
    "\\frac14\\sum_x|x\\rangle|\\operatorname{parity}(x)\\rangle.\n",
    "$$\n",
    "\n",
    "- Apply `parity_sequential` afterward to undo that operation. If the LAQCC corrections preserve coherence, the inputs return to $|+\\rangle^{\\otimes4}$ and the target returns to $|0\\rangle$.\n",
    "- Force each of the four internal measurement branches with `QuantumReplay`. Statevector checks verify relative phases as well as probabilities; a basis-state truth table alone would miss dephasing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "parity-07",
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "Ancilla outcomes Restored input fidelity Final target\n            0, 0              1.00000000            0\n            0, 1              1.00000000            0\n            1, 0              1.00000000            0\n            1, 1              1.00000000            0\n"
     ]
    }
   ],
   "source": [
    "@guppy\n",
    "def coherence_example() -> None:\n",
    "    qreg = qarray(n_inputs)\n",
    "    target = qubit()\n",
    "    transversal(h, qreg)\n",
    "    parity_laqcc(target, qreg)\n",
    "    parity_sequential(target, qreg)\n",
    "    state_output(\"inputs\", qreg)\n",
    "    output(\"target\", measure(target).read())\n",
    "    discard_array(qreg)\n",
    "\n",
    "\n",
    "branches = [list(bits) for bits in itertools.product([False, True], repeat=2)]\n",
    "replay = QuantumReplay(\n",
    "    simulator=Quest(), measurements=branches, resume_with_measurement=True,\n",
    ")\n",
    "result = coherence_example.emulator(total_qubits).with_simulator(replay).with_shots(4).run()\n",
    "expected_state = np.ones(2**n_inputs) / np.sqrt(2**n_inputs)\n",
    "rows = []\n",
    "for branch, shot, measured in zip(branches, result.results, result.collated_shots()):\n",
    "    actual = Quest.extract_states_dict(shot)[\"inputs\"].get_single_state()\n",
    "    assert_allclose_ignorephase(actual, expected_state)\n",
    "    assert not measured[\"target\"][0]\n",
    "    rows.append({\n",
    "        \"Ancilla outcomes\": \", \".join(str(int(bit)) for bit in branch),\n",
    "        \"Restored input fidelity\": abs(np.vdot(expected_state, actual))**2,\n",
    "        \"Final target\": int(measured[\"target\"][0]),\n",
    "    })\n",
    "print(pd.DataFrame(rows).to_string(index=False, float_format=lambda value: f\"{value:.8f}\"))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "parity-08",
   "metadata": {},
   "source": [
    "- All replayed branches restore the coherent input after uncomputation. The forced outcomes test corrections; they do not estimate branch probabilities.\n",
    "- Parity collects information from several inputs into one target. Fanout applies one control to several targets; the two operations serve different roles."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "guppyalgos (3.13.5)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}