{
   "cells": [
      {
         "cell_type": "markdown",
         "metadata": {},
         "source": [
            "# How to automatically find detectors?\n",
            "\n",
            "This notebook show in a simple example how automatic detector computation is performed."
         ]
      },
      {
         "cell_type": "markdown",
         "metadata": {},
         "source": [
            "## Build the quantum circuit\n",
            "\n",
            "In most cases, your QEC implementation will be encoded in a quantum circuit structure. Due to its omnipresence in QEC-related tasks, `stim.Circuit` is the quantum circuit representation that is expected by the package.\n",
            "\n",
            "Note that the quantum circuit does not have to represent a complete error-corrected computation. In particular, you might want to use knowledge about the quantum error-correction code used to only submit a sub-circuit of the whole computation. For example, if you know that you code is local and that detectors will only include measurements close to each other, it might be interesting to only compute the detectors on a small sub-circuit and re-use the computed detectors on a larger circuit. \n",
            "\n",
            "For the purposes of demonstration, we will use a repetition code of distance `3`, performing memory operations for `10` rounds."
         ]
      },
      {
         "cell_type": "code",
         "execution_count": null,
         "metadata": {},
         "outputs": [],
         "source": [
            "import stim\n",
            "\n",
            "circuit = stim.Circuit(\"\"\"\n",
            "QUBIT_COORDS(0) 0\n",
            "QUBIT_COORDS(1) 1\n",
            "QUBIT_COORDS(2) 2\n",
            "QUBIT_COORDS(3) 3\n",
            "QUBIT_COORDS(4) 4\n",
            "R 0 1 2 3 4\n",
            "TICK\n",
            "CX 0 1 2 3\n",
            "TICK\n",
            "CX 2 1 4 3\n",
            "TICK\n",
            "M 1 3\n",
            "TICK\n",
            "REPEAT 9 {\n",
            "    R 1 3\n",
            "    TICK\n",
            "    CX 0 1 2 3\n",
            "    TICK\n",
            "    CX 2 1 4 3\n",
            "    TICK\n",
            "    M 1 3\n",
            "    TICK\n",
            "}\n",
            "M 0 2 4\"\"\")\n",
            "circuit.diagram(\"timeline-svg\")"
         ]
      },
      {
         "cell_type": "markdown",
         "metadata": {},
         "source": [
            "Note that the quantum circuit generated by `stim.Circuit.generated` includes a few structures that are not supported by the package. As such, you should ensure that the circuits provided are checking a few pre-conditions. \n",
            "\n",
            "That is one of the reasons why the circuit is explicitly provided above and not directly generated with a call to `stim.Circuit.generated`."
         ]
      },
      {
         "cell_type": "markdown",
         "metadata": {},
         "source": [
            "## Split the quantum circuit\n",
            "\n",
            "Once the quantum circuit is built and adhere to the pre-conditions imposed by the package, we need to split that circuit into a sequence of fragments. "
         ]
      },
      {
         "cell_type": "code",
         "execution_count": null,
         "metadata": {},
         "outputs": [],
         "source": [
            "from tqec.circuit.detectors.fragment import split_stim_circuit_into_fragments\n",
            "\n",
            "fragments = split_stim_circuit_into_fragments(circuit)"
         ]
      },
      {
         "cell_type": "markdown",
         "metadata": {},
         "source": [
            "We can explore the fragments built:"
         ]
      },
      {
         "cell_type": "code",
         "execution_count": null,
         "metadata": {},
         "outputs": [],
         "source": [
            "for fragment in fragments:\n",
            "    print(\"=\" * 80)\n",
            "    print(fragment)"
         ]
      },
      {
         "cell_type": "markdown",
         "metadata": {},
         "source": [
            "## Pre-computing flows\n",
            "\n",
            "Now that the quantum circuit is adequately split into fragments, we can start pre-computing the flows for each fragment. \n",
            "\n",
            "For the moment, the package is limited to detectors that only include measurements from `2` fragments: the current one and the one before. Due to that limitation, we do not have to compute any \"propagation\" flow: only \"creation\" and \"destruction\" flows are needed to find such detectors."
         ]
      },
      {
         "cell_type": "code",
         "execution_count": null,
         "metadata": {},
         "outputs": [],
         "source": [
            "from tqec.circuit.detectors.flow import build_flows_from_fragments\n",
            "\n",
            "flows = build_flows_from_fragments(fragments)"
         ]
      },
      {
         "cell_type": "markdown",
         "metadata": {},
         "source": [
            "Just like fragments, it is interesting to explore and visualise the different flows computed."
         ]
      },
      {
         "cell_type": "code",
         "execution_count": null,
         "metadata": {},
         "outputs": [],
         "source": [
            "for flow in flows:\n",
            "    print(\"=\" * 80)\n",
            "    print(\"Flow(\")\n",
            "    print(\"  creation = [\")\n",
            "    for creation in flow.creation:\n",
            "        print(f\"    {creation}\")\n",
            "    print(\"  ],\")\n",
            "    print(\"  destruction = [\")\n",
            "    for destruction in flow.destruction:\n",
            "        print(f\"    {destruction}\")\n",
            "    print(\"  ],\")\n",
            "    print(f\"total_number_of_measurements = {flow.total_number_of_measurements}\")\n",
            "    print(\")\")"
         ]
      },
      {
         "cell_type": "markdown",
         "metadata": {},
         "source": [
            "Let's use the first fragment and its associated flows as an example and illustrate using [Crumble](https://algassert.com/crumble), a nice tool that can be used to explore stabilizer propagation.\n",
            "\n",
            "The first \"creation\" stabilizer is\n",
            "\n",
            "```\n",
            "BoundaryStabilizers(\n",
            "    stabilizer=Z0, \n",
            "    collapsing_operations=[Z3, Z1], \n",
            "    involved_measurements=[],\n",
            "    source_qubits={0}\n",
            ")\n",
            "```\n",
            "\n",
            "which originate from the propagation described below:"
         ]
      },
      {
         "cell_type": "code",
         "execution_count": null,
         "metadata": {},
         "outputs": [],
         "source": [
            "from IPython.display import IFrame\n",
            "\n",
            "IFrame(\n",
            "    \"https://algassert.com/crumble#circuit=Q(0,0)0;Q(1,0)1;Q(2,0)2;Q(3,0)3;Q(4,0)4;R_0_1_2_3_4;MARKZ(0)0;TICK;CX_0_1_2_3;TICK;CX_2_1_4_3;TICK;M_1_3\",\n",
            "    \"100%\",\n",
            "    350,\n",
            ")"
         ]
      },
      {
         "cell_type": "markdown",
         "metadata": {},
         "source": [
            "A more interesting propagation is the second \"creation\" boundary stabilizer:\n",
            "\n",
            "```\n",
            "BoundaryStabilizers(\n",
            "    stabilizer=Z0*Z1*Z2, \n",
            "    collapsing_operations=[Z3, Z1], \n",
            "    involved_measurements=[RelativeMeasurementLocation(offset=-2, qubit_index=1)],\n",
            "    source_qubits={1}\n",
            ")\n",
            "```\n",
            "\n",
            "resulting from the propagation:"
         ]
      },
      {
         "cell_type": "code",
         "execution_count": null,
         "metadata": {},
         "outputs": [],
         "source": [
            "from IPython.display import IFrame\n",
            "\n",
            "IFrame(\n",
            "    \"https://algassert.com/crumble#circuit=Q(0,0)0;Q(1,0)1;Q(2,0)2;Q(3,0)3;Q(4,0)4;R_0_1_2_3_4;MARKZ(0)1;TICK;CX_0_1_2_3;TICK;CX_2_1_4_3;TICK;M_1_3;MARKZ(0)1\",\n",
            "    \"100%\",\n",
            "    350,\n",
            ")"
         ]
      },
      {
         "cell_type": "markdown",
         "metadata": {},
         "source": [
            "Note that the `BoundaryStabilizer` stores the state of the stabilizer propagation **before** any non-reversible collapsing operations. That way, from a `BoundaryStabilizer` instance, you have a direct access to the stabilizer resulting from the propagation before any collapsing operation and you can compute the stabilizer obtained after the collapsing operations."
         ]
      },
      {
         "cell_type": "markdown",
         "metadata": {},
         "source": [
            "Let's take one last example, but this time the \"destruction\" flow\n",
            "```\n",
            "BoundaryStabilizers(\n",
            "    stabilizer=Z0*Z1*Z2,\n",
            "    collapsing_operations=[Z1, Z3, Z2, Z4, Z0], \n",
            "    involved_measurements=[RelativeMeasurementLocation(offset=-2, qubit_index=1)],\n",
            "    source_qubits={1}\n",
            ")\n",
            "```\n",
            "that can be visualised below:"
         ]
      },
      {
         "cell_type": "code",
         "execution_count": null,
         "metadata": {},
         "outputs": [],
         "source": [
            "from IPython.display import IFrame\n",
            "\n",
            "IFrame(\n",
            "    \"https://algassert.com/crumble#circuit=Q(0,0)0;Q(1,0)1;Q(2,0)2;Q(3,0)3;Q(4,0)4;R_0_1_2_3_4;MARKZ(0)0_1_2;TICK;CX_0_1_2_3;TICK;CX_2_1_4_3;TICK;M_1_3;MARKZ(0)1\",\n",
            "    \"100%\",\n",
            "    350,\n",
            ")"
         ]
      },
      {
         "cell_type": "markdown",
         "metadata": {},
         "source": [
            "In this step, we pre-computed the necessary information to find detectors: creation and destruction flows. The next step is to use that information to try to find detectors."
         ]
      },
      {
         "cell_type": "markdown",
         "metadata": {},
         "source": [
            "## Finding detectors\n",
            "\n",
            "The problem of finding a detector can be rephrased as finding one or more flow(s) that, when considered together, do not propagate and are fully collapsed by collapsing operations.\n",
            "\n",
            "The destruction flow visualised above is a good example: it is generated by the measurement on the second qubit, back-propagates in the fragment, and end up on 3 reset instructions that collapse entirely the flow. This means that all the measurements touched by that flow (i.e., for that example, the measurement on the second qubit) form a detector.\n",
            "\n",
            "The package has an iterative approach to find detectors:\n",
            "\n",
            "1. Try to find detectors fully contained within a single flow (the example of a destruction flow above is exactly in this case).\n",
            "2. For each adjacent flows `f1 -- f2`, try to find detectors spanning across these two flows:\n",
            "    1. First by trying to match `1` creation flow from `f1` to `1` destruction flow from `f2`.\n",
            "    2. Then by trying to find:\n",
            "        - `n > 1` creation flows from `f1` that, when combined, match with `1` destruction flow from `f2`.\n",
            "        - `1` creation flow from `f1` that match with `n > 1` destruction flows from `f2` when combined.\n",
            "\n",
            "The above methodology is only applied on flows that commute with their collapsing operations. For example, the flow"
         ]
      },
      {
         "cell_type": "code",
         "execution_count": null,
         "metadata": {},
         "outputs": [],
         "source": [
            "from IPython.display import IFrame\n",
            "\n",
            "IFrame(\n",
            "    \"https://algassert.com/crumble#circuit=Q(0,0)0;Q(1,0)1;Q(2,0)2;Q(3,0)3;Q(4,0)4;R_0_1_2_3_4;MARKZ(0)1;TICK;CX_0_1_2_3;TICK;CX_2_1_4_3;TICK;H_1;TICK;M_1_3;MARKZ(0)1\",\n",
            "    \"100%\",\n",
            "    350,\n",
            ")"
         ]
      },
      {
         "cell_type": "markdown",
         "metadata": {},
         "source": [
            "does not commute with its collapsing operation (the measurement). This can be seen quite easily from the `BoundaryStabilizer` instance that would represent this flow:\n",
            "\n",
            "```\n",
            "BoundaryStabilizers(\n",
            "    stabilizer=Z0*X1*Z2, \n",
            "    collapsing_operations=[Z3, Z1], \n",
            "    involved_measurements=[RelativeMeasurementLocation(offset=-2, qubit_index=1)],\n",
            "    source_qubits={1}\n",
            ")\n",
            "```\n",
            "\n",
            "The stabilizer `Z0*X1*Z2` does not commute with the collapsing operation `Z1`.\n",
            "\n",
            "In such cases, there is an intermediary step `1.5` that consist in try to merge several anti-commuting flows together to form new commuting flows.\n",
            "\n",
            "Coming back to the code, detectors can be listed by calling `match_detectors_from_flows_shallow`:"
         ]
      },
      {
         "cell_type": "code",
         "execution_count": null,
         "metadata": {},
         "outputs": [],
         "source": [
            "from tqec.circuit.detectors.match import match_detectors_from_flows_shallow\n",
            "\n",
            "qubit_coordinates = {\n",
            "    q: tuple(coords) for q, coords in circuit.get_final_qubit_coordinates().items()\n",
            "}\n",
            "matched_detectors = match_detectors_from_flows_shallow(flows, qubit_coordinates)"
         ]
      },
      {
         "cell_type": "markdown",
         "metadata": {},
         "source": [
            "This function will return, for each of the provided flows, a list of detectors:"
         ]
      },
      {
         "cell_type": "code",
         "execution_count": null,
         "metadata": {},
         "outputs": [],
         "source": [
            "for i, detectors in enumerate(matched_detectors):\n",
            "    print(f\"Detectors found for fragment number {i}:\")\n",
            "    for detector in detectors:\n",
            "        print(\"  \", detector.to_instruction())"
         ]
      },
      {
         "cell_type": "markdown",
         "metadata": {},
         "source": [
            "## Wrapping up\n",
            "\n",
            "In the previous sections, you have seen the process used to compute detectors. In practice, this process is long and tedious to write, so a function performing all the above steps and constructing an equivalent quantum circuit with the computed detectors has been included in the package: `annotate_detectors_automatically`.\n",
            "\n",
            "One example of its usage is available below."
         ]
      },
      {
         "cell_type": "code",
         "execution_count": null,
         "metadata": {},
         "outputs": [],
         "source": [
            "from tqec.circuit.detectors.construction import annotate_detectors_automatically\n",
            "from tqec.circuit.detectors.utils import remove_annotations\n",
            "\n",
            "print(remove_annotations(circuit))\n",
            "annotated_circuit = annotate_detectors_automatically(remove_annotations(circuit))"
         ]
      },
      {
         "cell_type": "code",
         "execution_count": null,
         "metadata": {},
         "outputs": [],
         "source": [
            "print(annotated_circuit)\n",
            "annotated_circuit.diagram(\"timeline-svg\")"
         ]
      }
   ],
   "metadata": {
      "ExecuteTime": {
         "end_time": "2024-02-06T13:27:46.308991Z",
         "start_time": "2024-02-06T13:27:39.049848Z"
      },
      "kernelspec": {
         "display_name": "qec",
         "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.5"
      }
   },
   "nbformat": 4,
   "nbformat_minor": 2
}