Grover's search for RNA design.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/Advanced-Research-Centre/QraftRNA/blob/main/Grover's%20search%20for%20RNA%20design.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Zjdd0h6VfDF6"
      },
      "source": [
        "# Grover's serach for RNA design"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "Jj78cf_wfDF9"
      },
      "outputs": [],
      "source": [
        "import numpy as np\n",
        "from math import pi,log2,floor,ceil\n",
        "from qiskit import *\n",
        "from qiskit.circuit import *\n",
        "from qiskit.extensions import *\n",
        "from qiskit.circuit.library import *\n",
        "from qiskit.extensions.simulator.snapshot import snapshot\n",
        "from qiskit.quantum_info.operators import Operator\n",
        "from qiskit.extensions.simulator.snapshot import snapshot\n",
        "from scipy import optimize\n",
        "from matplotlib.pyplot import plot,show\n",
        "%matplotlib inline\n",
        "%config InlineBackend.figure_format = 'svg' # Makes the images look nice"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "t4bK-MslfDGF"
      },
      "source": [
        "## 1 - Addition\n",
        "\n",
        "Let's implement the circuit in [1] modified to add mod 2^n."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "iRSBWK-gfDGF",
        "outputId": "f6278983-4e7b-440c-896a-d5fce416c36e"
      },
      "outputs": [
        {
          "data": {
            "text/html": [
              "<pre style=\"word-wrap: normal;white-space: pre;background: #fff0;line-height: 1.1;font-family: &quot;Courier New&quot;,Courier,monospace\">       ┌──────┐                                                                »\n",
              "q1499: ┤0     ├────────────────────────────────────────────────────────────────»\n",
              "       │      │┌──────┐                                                        »\n",
              "  =_0: ┤2     ├┤0     ├────────────────────────────────────────────────────────»\n",
              "       │      ││      │┌──────┐                                                »\n",
              "  =_1: ┤      ├┤2     ├┤0     ├────────────────────────────────────────────────»\n",
              "       │      ││      ││      │┌──────┐                                ┌──────┐»\n",
              "  =_2: ┤      ├┤      ├┤2     ├┤0     ├────────────────────────────────┤0     ├»\n",
              "       │  MAJ ││      ││      ││      │┌──────┐                ┌──────┐│      │»\n",
              "  =_3: ┤      ├┤      ├┤      ├┤2     ├┤0     ├────────────────┤0     ├┤2     ├»\n",
              "       │      ││  MAJ ││      ││      ││      │┌──────┐┌──────┐│      ││      │»\n",
              "  =_4: ┤      ├┤      ├┤      ├┤      ├┤2     ├┤0     ├┤0     ├┤2     ├┤      ├»\n",
              "       │      ││      ││  MAJ ││      ││      ││      ││      ││      ││      │»\n",
              "  =_5: ┤      ├┤      ├┤      ├┤      ├┤      ├┤2     ├┤2     ├┤      ├┤      ├»\n",
              "       │      ││      ││      ││  MAJ ││      ││      ││      ││      ││  UMA │»\n",
              " ->_0: ┤1     ├┤      ├┤      ├┤      ├┤      ├┤      ├┤      ├┤      ├┤      ├»\n",
              "       └──────┘│      ││      ││      ││  MAJ ││      ││      ││  UMA ││      │»\n",
              " ->_1: ────────┤1     ├┤      ├┤      ├┤      ├┤      ├┤      ├┤      ├┤      ├»\n",
              "               └──────┘│      ││      ││      ││  MAJ ││  UMA ││      ││      │»\n",
              " ->_2: ────────────────┤1     ├┤      ├┤      ├┤      ├┤      ├┤      ├┤      ├»\n",
              "                       └──────┘│      ││      ││      ││      ││      ││      │»\n",
              " ->_3: ────────────────────────┤1     ├┤      ├┤      ├┤      ├┤      ├┤1     ├»\n",
              "                               └──────┘│      ││      ││      ││      │└──────┘»\n",
              " ->_4: ────────────────────────────────┤1     ├┤      ├┤      ├┤1     ├────────»\n",
              "                                       └──────┘│      ││      │└──────┘        »\n",
              " ->_5: ────────────────────────────────────────┤1     ├┤1     ├────────────────»\n",
              "                                               └──────┘└──────┘                »\n",
              "«                       ┌──────┐\n",
              "«q1499: ────────────────┤0     ├\n",
              "«               ┌──────┐│      │\n",
              "«  =_0: ────────┤0     ├┤2     ├\n",
              "«       ┌──────┐│      ││      │\n",
              "«  =_1: ┤0     ├┤2     ├┤      ├\n",
              "«       │      ││      ││      │\n",
              "«  =_2: ┤2     ├┤      ├┤      ├\n",
              "«       │      ││      ││  UMA │\n",
              "«  =_3: ┤      ├┤      ├┤      ├\n",
              "«       │      ││  UMA ││      │\n",
              "«  =_4: ┤      ├┤      ├┤      ├\n",
              "«       │  UMA ││      ││      │\n",
              "«  =_5: ┤      ├┤      ├┤      ├\n",
              "«       │      ││      ││      │\n",
              "« ->_0: ┤      ├┤      ├┤1     ├\n",
              "«       │      ││      │└──────┘\n",
              "« ->_1: ┤      ├┤1     ├────────\n",
              "«       │      │└──────┘        \n",
              "« ->_2: ┤1     ├────────────────\n",
              "«       └──────┘                \n",
              "« ->_3: ────────────────────────\n",
              "«                               \n",
              "« ->_4: ────────────────────────\n",
              "«                               \n",
              "« ->_5: ────────────────────────\n",
              "«                               </pre>"
            ],
            "text/plain": [
              "       ┌──────┐                                                                »\n",
              "q1499: ┤0     ├────────────────────────────────────────────────────────────────»\n",
              "       │      │┌──────┐                                                        »\n",
              "  =_0: ┤2     ├┤0     ├────────────────────────────────────────────────────────»\n",
              "       │      ││      │┌──────┐                                                »\n",
              "  =_1: ┤      ├┤2     ├┤0     ├────────────────────────────────────────────────»\n",
              "       │      ││      ││      │┌──────┐                                ┌──────┐»\n",
              "  =_2: ┤      ├┤      ├┤2     ├┤0     ├────────────────────────────────┤0     ├»\n",
              "       │  MAJ ││      ││      ││      │┌──────┐                ┌──────┐│      │»\n",
              "  =_3: ┤      ├┤      ├┤      ├┤2     ├┤0     ├────────────────┤0     ├┤2     ├»\n",
              "       │      ││  MAJ ││      ││      ││      │┌──────┐┌──────┐│      ││      │»\n",
              "  =_4: ┤      ├┤      ├┤      ├┤      ├┤2     ├┤0     ├┤0     ├┤2     ├┤      ├»\n",
              "       │      ││      ││  MAJ ││      ││      ││      ││      ││      ││      │»\n",
              "  =_5: ┤      ├┤      ├┤      ├┤      ├┤      ├┤2     ├┤2     ├┤      ├┤      ├»\n",
              "       │      ││      ││      ││  MAJ ││      ││      ││      ││      ││  UMA │»\n",
              " ->_0: ┤1     ├┤      ├┤      ├┤      ├┤      ├┤      ├┤      ├┤      ├┤      ├»\n",
              "       └──────┘│      ││      ││      ││  MAJ ││      ││      ││  UMA ││      │»\n",
              " ->_1: ────────┤1     ├┤      ├┤      ├┤      ├┤      ├┤      ├┤      ├┤      ├»\n",
              "               └──────┘│      ││      ││      ││  MAJ ││  UMA ││      ││      │»\n",
              " ->_2: ────────────────┤1     ├┤      ├┤      ├┤      ├┤      ├┤      ├┤      ├»\n",
              "                       └──────┘│      ││      ││      ││      ││      ││      │»\n",
              " ->_3: ────────────────────────┤1     ├┤      ├┤      ├┤      ├┤      ├┤1     ├»\n",
              "                               └──────┘│      ││      ││      ││      │└──────┘»\n",
              " ->_4: ────────────────────────────────┤1     ├┤      ├┤      ├┤1     ├────────»\n",
              "                                       └──────┘│      ││      │└──────┘        »\n",
              " ->_5: ────────────────────────────────────────┤1     ├┤1     ├────────────────»\n",
              "                                               └──────┘└──────┘                »\n",
              "«                       ┌──────┐\n",
              "«q1499: ────────────────┤0     ├\n",
              "«               ┌──────┐│      │\n",
              "«  =_0: ────────┤0     ├┤2     ├\n",
              "«       ┌──────┐│      ││      │\n",
              "«  =_1: ┤0     ├┤2     ├┤      ├\n",
              "«       │      ││      ││      │\n",
              "«  =_2: ┤2     ├┤      ├┤      ├\n",
              "«       │      ││      ││  UMA │\n",
              "«  =_3: ┤      ├┤      ├┤      ├\n",
              "«       │      ││  UMA ││      │\n",
              "«  =_4: ┤      ├┤      ├┤      ├\n",
              "«       │  UMA ││      ││      │\n",
              "«  =_5: ┤      ├┤      ├┤      ├\n",
              "«       │      ││      ││      │\n",
              "« ->_0: ┤      ├┤      ├┤1     ├\n",
              "«       │      ││      │└──────┘\n",
              "« ->_1: ┤      ├┤1     ├────────\n",
              "«       │      │└──────┘        \n",
              "« ->_2: ┤1     ├────────────────\n",
              "«       └──────┘                \n",
              "« ->_3: ────────────────────────\n",
              "«                               \n",
              "« ->_4: ────────────────────────\n",
              "«                               \n",
              "« ->_5: ────────────────────────\n",
              "«                               "
            ]
          },
          "execution_count": 51,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "#MAJ\n",
        "q=QuantumRegister(3)\n",
        "MAJ = QuantumCircuit(q)\n",
        "\n",
        "MAJ.cnot(q[2],q[1])\n",
        "MAJ.cnot(q[2],q[0])\n",
        "MAJ.ccx(q[0],q[1],q[2])\n",
        "\n",
        "maj = MAJ.to_gate(label='MAJ')\n",
        "\n",
        "#UMA\n",
        "q=QuantumRegister(3)\n",
        "UMA = QuantumCircuit(q)\n",
        "\n",
        "UMA.ccx(q[0],q[1],q[2])\n",
        "UMA.cnot(q[2],q[0])\n",
        "UMA.cnot(q[0],q[1])\n",
        "\n",
        "uma = UMA.to_gate(label='UMA')\n",
        "\n",
        "#add\n",
        "def add_circuit(nb_bits):\n",
        "    concerved = QuantumRegister(nb_bits, name=\"=\")\n",
        "    not_concerved = QuantumRegister(nb_bits, name=\"->\")\n",
        "    initial_carry = QuantumRegister(1)\n",
        "    add = QuantumCircuit(initial_carry,concerved,not_concerved)\n",
        "    add.append(maj,[initial_carry,not_concerved[0],concerved[0]])\n",
        "    for i in range(1,nb_bits):\n",
        "        add.append(maj,[concerved[i-1],not_concerved[i],concerved[i]])\n",
        "    for i in range(nb_bits-1,0,-1):\n",
        "        add.append(uma,[concerved[i-1],not_concerved[i],concerved[i]])\n",
        "    add.append(uma,[initial_carry,not_concerved[0],concerved[0]])\n",
        "    return add\n",
        "\n",
        "def add_gate(nb_bits):\n",
        "    return add_circuit(nb_bits).to_gate(label=\"add{}\".format(nb_bits))\n",
        "\n",
        "add_circuit(6).draw()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "XX2RXPaDfDGG"
      },
      "source": [
        "## 2 - Matchnig parentesis"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Y3R1x1DMfDGG"
      },
      "source": [
        "`(`, `.` and `)` are encoded respectively by 1, 0 and -1, which are encoded with one's complement representation."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "YyccHdtYfDGH",
        "outputId": "7d1d0b7b-ba61-4d50-9ade-075309b7b449"
      },
      "outputs": [
        {
          "data": {
            "text/html": [
              "<pre style=\"word-wrap: normal;white-space: pre;background: #fff0;line-height: 1.1;font-family: &quot;Courier New&quot;,Courier,monospace\">                                          ┌───┐                         »\n",
              "change_encoding: ─────────────────────────┤ X ├──■──────────────────────»\n",
              "                 ┌───┐┌───┐┌───┐          └─┬─┘  │                      »\n",
              "      (/./h/)_0: ┤ H ├┤ H ├┤ X ├────────────o────┼────■─────────────────»\n",
              "                 ├───┤└─┬─┘└─┬─┘┌───┐┌───┐  │  ┌─┴─┐  │                 »\n",
              "      (/./h/)_1: ┤ H ├──┼────┼──┤ H ├┤ X ├──■──┤ X ├──┼─────────────────»\n",
              "                 ├───┤  │    │  └─┬─┘└─┬─┘     └───┘  │                 »\n",
              "    k_folding_0: ┤ H ├──o────o────o────o────■─────────┼────■────────────»\n",
              "                 ├───┤  │    │    │    │    │         │    │            »\n",
              "    k_folding_1: ┤ H ├──o────o────o────o────┼────■────┼────┼────■───────»\n",
              "                 └───┘                      │    │  ┌─┴─┐  │    │       »\n",
              "        count_0: ───────────────────────────┼────┼──┤ X ├──┼────┼────■──»\n",
              "                                            │    │  └─┬─┘  │    │    │  »\n",
              "        count_1: ───────────────────────────┼────┼────┼────┼────┼────┼──»\n",
              "                 ┌───┐                    ┌─┴─┐  │    │  ┌─┴─┐  │    │  »\n",
              "      k_count_0: ┤ H ├──■─────────────────┤ X ├──┼────o──┤ X ├──┼────┼──»\n",
              "                 ├───┤  │                 └───┘┌─┴─┐  │  └───┘┌─┴─┐  │  »\n",
              "      k_count_1: ┤ H ├──┼────■─────────────────┤ X ├──o───────┤ X ├──┼──»\n",
              "                 ├───┤  │    │                 └───┘          └───┘  │  »\n",
              "  continue_scan: ┤ X ├──┼────┼───────────────────────────────────────┼──»\n",
              "                 ├───┤  │    │                                     ┌─┴─┐»\n",
              " continue_match: ┤ X ├──┼────┼─────────────────────────────────────┤ X ├»\n",
              "                 ├───┤  │    │                                     └───┘»\n",
              "            one: ┤ X ├──┼────┼──────────────────────────────────────────»\n",
              "                 └───┘  │    │                                          »\n",
              "         zero_0: ───────┼────┼──────────────────────────────────────────»\n",
              "                        │    │                                          »\n",
              "         zero_1: ───────┼────┼──────────────────────────────────────────»\n",
              "                      ┌─┴─┐  │                                          »\n",
              "      k_match_0: ─────┤ X ├──┼──────────────────────────────────────────»\n",
              "                      └───┘┌─┴─┐                                        »\n",
              "      k_match_1: ──────────┤ X ├────────────────────────────────────────»\n",
              "                           └───┘                                        »\n",
              "         loop_0: ───────────────────────────────────────────────────────»\n",
              "                                                                        »\n",
              "         loop_1: ───────────────────────────────────────────────────────»\n",
              "                                                                        »\n",
              "    loop_type_0: ───────────────────────────────────────────────────────»\n",
              "                                                                        »\n",
              "    loop_type_1: ───────────────────────────────────────────────────────»\n",
              "                                                                        »\n",
              "    loop_type_2: ───────────────────────────────────────────────────────»\n",
              "                                                                        »\n",
              "    incorrect_0: ───────────────────────────────────────────────────────»\n",
              "                                                                        »\n",
              "    incorrect_1: ───────────────────────────────────────────────────────»\n",
              "                                                                        »\n",
              "        correct: ───────────────────────────────────────────────────────»\n",
              "                                                                        »\n",
              "«                                                                          »\n",
              "«change_encoding: ─────────────────────────────────────────────────────────»\n",
              "«                                                  ┌─────────────────┐     »\n",
              "«      (/./h/)_0: ─────────────────────────────────┤3                ├─────»\n",
              "«                                                  │                 │     »\n",
              "«      (/./h/)_1: ─────────────────────────────────┤4                ├─────»\n",
              "«                                                  │                 │     »\n",
              "«    k_folding_0: ─────────────────────────■───────┤                 ├─────»\n",
              "«                                          │       │                 │     »\n",
              "«    k_folding_1: ─────────────────────────┼────■──┤                 ├─────»\n",
              "«                                          │    │  │                 │┌───┐»\n",
              "«        count_0: ─────────────────────────┼────┼──┤1                ├┤ X ├»\n",
              "«                                          │    │  │                 │└─┬─┘»\n",
              "«        count_1: ─────────────────────────┼────┼──┤2                ├──┼──»\n",
              "«                          ┌───────┐     ┌─┴─┐  │  │                 │  │  »\n",
              "«      k_count_0: ─────────┤3      ├──o──┤ X ├──┼──o  circuit-364295 ├──┼──»\n",
              "«                          │       │  │  └───┘┌─┴─┐│                 │  │  »\n",
              "«      k_count_1: ─────────┤4      ├──o───────┤ X ├o                 ├──┼──»\n",
              "«                          │       │┌─┴─┐     └───┘│                 │  │  »\n",
              "«  continue_scan: ────■────┤       ├┤ X ├──────────■                 ├──┼──»\n",
              "«                 ┌───┴───┐│       │└───┘          │                 │  │  »\n",
              "« continue_match: ┤1      ├┤  add2 ├───────────────┤                 ├──┼──»\n",
              "«                 │       ││       │               │                 │  │  »\n",
              "«            one: ┤       ├┤1      ├───────────────┤                 ├──■──»\n",
              "«                 │       ││       │               │                 │     »\n",
              "«         zero_0: ┤2      ├┤2      ├───────────────┤                 ├─────»\n",
              "«                 │  add2 ││       │               │                 │     »\n",
              "«         zero_1: ┤0      ├┤0      ├───────────────┤0                ├─────»\n",
              "«                 │       │└───────┘               └─────────────────┘     »\n",
              "«      k_match_0: ┤3      ├────────────────────────────────────────────────»\n",
              "«                 │       │                                                »\n",
              "«      k_match_1: ┤4      ├────────────────────────────────────────────────»\n",
              "«                 └───────┘                                                »\n",
              "«         loop_0: ─────────────────────────────────────────────────────────»\n",
              "«                                                                          »\n",
              "«         loop_1: ─────────────────────────────────────────────────────────»\n",
              "«                                                                          »\n",
              "«    loop_type_0: ─────────────────────────────────────────────────────────»\n",
              "«                                                                          »\n",
              "«    loop_type_1: ─────────────────────────────────────────────────────────»\n",
              "«                                                                          »\n",
              "«    loop_type_2: ─────────────────────────────────────────────────────────»\n",
              "«                                                                          »\n",
              "«    incorrect_0: ─────────────────────────────────────────────────────────»\n",
              "«                                                                          »\n",
              "«    incorrect_1: ─────────────────────────────────────────────────────────»\n",
              "«                                                                          »\n",
              "«        correct: ─────────────────────────────────────────────────────────»\n",
              "«                                                                          »\n",
              "«                                                                           »\n",
              "«change_encoding: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«      (/./h/)_0: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«      (/./h/)_1: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    k_folding_0: ──────────────────────■───────────────────────────────────»\n",
              "«                                       │                                   »\n",
              "«    k_folding_1: ──────────────────────┼────■──────────────────────────────»\n",
              "«                           ┌───┐       │    │                              »\n",
              "«        count_0: ───────o──┤ X ├───────┼────┼────o─────────────────────────»\n",
              "«                 ┌───┐  │  └─┬─┘┌───┐  │    │    │                         »\n",
              "«        count_1: ┤ X ├──o────┼──┤ X ├──┼────┼────o─────────────────────────»\n",
              "«                 └─┬─┘  │    │  └─┬─┘┌─┴─┐  │    │           ┌───────┐     »\n",
              "«      k_count_0: ──┼────o────┼────┼──┤ X ├──┼────┼───────────┤3      ├──o──»\n",
              "«                   │    │    │    │  └───┘┌─┴─┐  │           │       │  │  »\n",
              "«      k_count_1: ──┼────o────┼────┼───────┤ X ├──┼───────────┤4      ├──o──»\n",
              "«                   │    │    │    │       └───┘  │           │       │┌─┴─┐»\n",
              "«  continue_scan: ──┼────■────┼────┼──────────────┼──────■────┤       ├┤ X ├»\n",
              "«                   │    │    │    │            ┌─┴─┐┌───┴───┐│       │└───┘»\n",
              "« continue_match: ──┼────■────┼────┼────────────┤ X ├┤1      ├┤  add2 ├─────»\n",
              "«                   │    │    │    │            └───┘│       ││       │     »\n",
              "«            one: ──┼────┼────■────┼─────────────────┤       ├┤1      ├─────»\n",
              "«                   │    │         │                 │       ││       │     »\n",
              "«         zero_0: ──■────┼─────────■─────────────────┤2      ├┤2      ├─────»\n",
              "«                        │                           │  add2 ││       │     »\n",
              "«         zero_1: ───────┼───────────────────────────┤0      ├┤0      ├─────»\n",
              "«                        │                           │       │└───────┘     »\n",
              "«      k_match_0: ───────┼───────────────────────────┤3      ├──────────────»\n",
              "«                        │                           │       │              »\n",
              "«      k_match_1: ───────┼───────────────────────────┤4      ├──────────────»\n",
              "«                      ┌─┴─┐                         └───────┘              »\n",
              "«         loop_0: ─────┤ X ├────────────────────────────────────────────────»\n",
              "«                      └───┘                                                »\n",
              "«         loop_1: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    loop_type_0: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    loop_type_1: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    loop_type_2: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    incorrect_0: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    incorrect_1: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«        correct: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«                                                                           »\n",
              "«change_encoding: ──────────────────────────────────────────────────────────»\n",
              "«                           ┌─────────────────┐                             »\n",
              "«      (/./h/)_0: ──────────┤3                ├─────────────────────────────»\n",
              "«                           │                 │                             »\n",
              "«      (/./h/)_1: ──────────┤4                ├─────────────────────────────»\n",
              "«                           │                 │                             »\n",
              "«    k_folding_0: ──■───────┤                 ├─────────────────────────────»\n",
              "«                   │       │                 │                             »\n",
              "«    k_folding_1: ──┼────■──┤                 ├─────────────────────────────»\n",
              "«                   │    │  │                 │┌─────────────────┐┌───┐     »\n",
              "«        count_0: ──┼────┼──┤1                ├┤1                ├┤ X ├─────»\n",
              "«                   │    │  │                 ││                 │└─┬─┘┌───┐»\n",
              "«        count_1: ──┼────┼──┤2                ├┤2                ├──┼──┤ X ├»\n",
              "«                 ┌─┴─┐  │  │                 ││                 │  │  └─┬─┘»\n",
              "«      k_count_0: ┤ X ├──┼──o  circuit-364295 ├o                 ├──┼────┼──»\n",
              "«                 └───┘┌─┴─┐│                 ││                 │  │    │  »\n",
              "«      k_count_1: ─────┤ X ├o                 ├o                 ├──┼────┼──»\n",
              "«                      └───┘│                 ││                 │  │    │  »\n",
              "«  continue_scan: ──────────■                 ├┤  circuit-364295 ├──┼────┼──»\n",
              "«                           │                 ││                 │  │    │  »\n",
              "« continue_match: ──────────■                 ├o                 ├──┼────┼──»\n",
              "«                           │                 ││                 │  │    │  »\n",
              "«            one: ──────────┤                 ├┤3                ├──■────┼──»\n",
              "«                           │                 ││                 │       │  »\n",
              "«         zero_0: ──────────┤                 ├┤4                ├───────■──»\n",
              "«                           │                 ││                 │          »\n",
              "«         zero_1: ──────────┤0                ├┤0                ├──────────»\n",
              "«                           └─────────────────┘└─────────────────┘          »\n",
              "«      k_match_0: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«      k_match_1: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«         loop_0: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«         loop_1: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    loop_type_0: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    loop_type_1: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    loop_type_2: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    incorrect_0: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    incorrect_1: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«        correct: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«                                                                      »\n",
              "«change_encoding: ─────────────────────────────────────────────────────»\n",
              "«                                                                      »\n",
              "«      (/./h/)_0: ─────────────────────────────────────────────────────»\n",
              "«                                                                      »\n",
              "«      (/./h/)_1: ─────────────────────────────────────────────────────»\n",
              "«                                                                      »\n",
              "«    k_folding_0: ───────────────────────────────■─────────────────────»\n",
              "«                                                │                     »\n",
              "«    k_folding_1: ───────────────────────────────┼────■────────────────»\n",
              "«                                    ┌───┐       │    │                »\n",
              "«        count_0: ─────────o─────────┤ X ├───────┼────┼────o───────────»\n",
              "«                          │         └─┬─┘┌───┐  │    │    │           »\n",
              "«        count_1: ─────────o───────────┼──┤ X ├──┼────┼────o───────────»\n",
              "«                          │           │  └─┬─┘┌─┴─┐  │    │           »\n",
              "«      k_count_0: ─────────o───────────┼────┼──┤ X ├──┼────┼───────────»\n",
              "«                          │           │    │  └───┘┌─┴─┐  │           »\n",
              "«      k_count_1: ─────────o───────────┼────┼───────┤ X ├──┼───────────»\n",
              "«                          │           │    │       └───┘  │           »\n",
              "«  continue_scan: ─────────■───────────┼────┼──────────────┼──────■────»\n",
              "«                 ┌────────┴────────┐  │    │            ┌─┴─┐┌───┴───┐»\n",
              "« continue_match: ┤3                ├──┼────┼────────────┤ X ├┤1      ├»\n",
              "«                 │                 │  │    │            └───┘│       │»\n",
              "«            one: ┤                 ├──■────┼─────────────────┤       ├»\n",
              "«                 │                 │       │                 │       │»\n",
              "«         zero_0: ┤4                ├───────■─────────────────┤2      ├»\n",
              "«                 │                 │                         │  add2 │»\n",
              "«         zero_1: ┤0                ├─────────────────────────┤0      ├»\n",
              "«                 │  circuit-364295 │                         │       │»\n",
              "«      k_match_0: ┤                 ├─────────────────────────┤3      ├»\n",
              "«                 │                 │                         │       │»\n",
              "«      k_match_1: ┤                 ├─────────────────────────┤4      ├»\n",
              "«                 │                 │                         └───────┘»\n",
              "«         loop_0: ┤1                ├──────────────────────────────────»\n",
              "«                 │                 │                                  »\n",
              "«         loop_1: ┤2                ├──────────────────────────────────»\n",
              "«                 └─────────────────┘                                  »\n",
              "«    loop_type_0: ─────────────────────────────────────────────────────»\n",
              "«                                                                      »\n",
              "«    loop_type_1: ─────────────────────────────────────────────────────»\n",
              "«                                                                      »\n",
              "«    loop_type_2: ─────────────────────────────────────────────────────»\n",
              "«                                                                      »\n",
              "«    incorrect_0: ─────────────────────────────────────────────────────»\n",
              "«                                                                      »\n",
              "«    incorrect_1: ─────────────────────────────────────────────────────»\n",
              "«                                                                      »\n",
              "«        correct: ─────────────────────────────────────────────────────»\n",
              "«                                                                      »\n",
              "«                                                            »\n",
              "«change_encoding: ───────────────────────────────────────────»\n",
              "«                                         ┌─────────────────┐»\n",
              "«      (/./h/)_0: ────────────────────────┤3                ├»\n",
              "«                                         │                 │»\n",
              "«      (/./h/)_1: ────────────────────────┤4                ├»\n",
              "«                                         │                 │»\n",
              "«    k_folding_0: ────────────────■───────┤                 ├»\n",
              "«                                 │       │                 │»\n",
              "«    k_folding_1: ────────────────┼────■──┤                 ├»\n",
              "«                                 │    │  │                 │»\n",
              "«        count_0: ────────────────┼────┼──┤1                ├»\n",
              "«                                 │    │  │                 │»\n",
              "«        count_1: ────────────────┼────┼──┤2                ├»\n",
              "«                 ┌───────┐     ┌─┴─┐  │  │                 │»\n",
              "«      k_count_0: ┤3      ├──o──┤ X ├──┼──o  circuit-364295 ├»\n",
              "«                 │       │  │  └───┘┌─┴─┐│                 │»\n",
              "«      k_count_1: ┤4      ├──o───────┤ X ├o                 ├»\n",
              "«                 │       │┌─┴─┐     └───┘│                 │»\n",
              "«  continue_scan: ┤       ├┤ X ├──────────■                 ├»\n",
              "«                 │       │└───┘          │                 │»\n",
              "« continue_match: ┤  add2 ├───────────────■                 ├»\n",
              "«                 │       │               │                 │»\n",
              "«            one: ┤1      ├───────────────┤                 ├»\n",
              "«                 │       │               │                 │»\n",
              "«         zero_0: ┤2      ├───────────────┤                 ├»\n",
              "«                 │       │               │                 │»\n",
              "«         zero_1: ┤0      ├───────────────┤0                ├»\n",
              "«                 └───────┘               └─────────────────┘»\n",
              "«      k_match_0: ───────────────────────────────────────────»\n",
              "«                                                            »\n",
              "«      k_match_1: ───────────────────────────────────────────»\n",
              "«                                                            »\n",
              "«         loop_0: ───────────────────────────────────────────»\n",
              "«                                                            »\n",
              "«         loop_1: ───────────────────────────────────────────»\n",
              "«                                                            »\n",
              "«    loop_type_0: ───────────────────────────────────────────»\n",
              "«                                                            »\n",
              "«    loop_type_1: ───────────────────────────────────────────»\n",
              "«                                                            »\n",
              "«    loop_type_2: ───────────────────────────────────────────»\n",
              "«                                                            »\n",
              "«    incorrect_0: ───────────────────────────────────────────»\n",
              "«                                                            »\n",
              "«    incorrect_1: ───────────────────────────────────────────»\n",
              "«                                                            »\n",
              "«        correct: ───────────────────────────────────────────»\n",
              "«                                                            »\n",
              "«                                                                           »\n",
              "«change_encoding: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«      (/./h/)_0: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«      (/./h/)_1: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    k_folding_0: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    k_folding_1: ──────────────────────────────────────────────────────────»\n",
              "«                 ┌─────────────────┐┌───┐                        ┌───┐     »\n",
              "«        count_0: ┤1                ├┤ X ├──────────────o─────────┤ X ├─────»\n",
              "«                 │                 │└─┬─┘┌───┐         │         └─┬─┘┌───┐»\n",
              "«        count_1: ┤2                ├──┼──┤ X ├─────────o───────────┼──┤ X ├»\n",
              "«                 │                 │  │  └─┬─┘         │           │  └─┬─┘»\n",
              "«      k_count_0: o                 ├──┼────┼───────────o───────────┼────┼──»\n",
              "«                 │                 │  │    │           │           │    │  »\n",
              "«      k_count_1: o                 ├──┼────┼───────────o───────────┼────┼──»\n",
              "«                 │                 │  │    │           │           │    │  »\n",
              "«  continue_scan: ┤  circuit-364295 ├──┼────┼───────────■───────────┼────┼──»\n",
              "«                 │                 │  │    │  ┌────────┴────────┐  │    │  »\n",
              "« continue_match: o                 ├──┼────┼──┤3                ├──┼────┼──»\n",
              "«                 │                 │  │    │  │                 │  │    │  »\n",
              "«            one: ┤3                ├──■────┼──┤                 ├──■────┼──»\n",
              "«                 │                 │       │  │                 │       │  »\n",
              "«         zero_0: ┤4                ├───────■──┤4                ├───────■──»\n",
              "«                 │                 │          │                 │          »\n",
              "«         zero_1: ┤0                ├──────────┤0                ├──────────»\n",
              "«                 └─────────────────┘          │  circuit-364295 │          »\n",
              "«      k_match_0: ─────────────────────────────┤                 ├──────────»\n",
              "«                                              │                 │          »\n",
              "«      k_match_1: ─────────────────────────────┤                 ├──────────»\n",
              "«                                              │                 │          »\n",
              "«         loop_0: ─────────────────────────────┤1                ├──────────»\n",
              "«                                              │                 │          »\n",
              "«         loop_1: ─────────────────────────────┤2                ├──────────»\n",
              "«                                              └─────────────────┘          »\n",
              "«    loop_type_0: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    loop_type_1: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    loop_type_2: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    incorrect_0: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    incorrect_1: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«        correct: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«                                                                              \n",
              "«change_encoding: ─────────────────────────────────────────────────────────────\n",
              "«                                                                              \n",
              "«      (/./h/)_0: ─────────────────────────────────────────────────────────────\n",
              "«                                                                              \n",
              "«      (/./h/)_1: ─────────────────────────────────────────────────────────────\n",
              "«                                                                              \n",
              "«    k_folding_0: ──■──────────────────────────────────────────────────────────\n",
              "«                   │                                                          \n",
              "«    k_folding_1: ──┼────■─────────────────────────────────────────────────────\n",
              "«                   │    │                                                     \n",
              "«        count_0: ──┼────┼────o────────────────────────────────────────────────\n",
              "«                   │    │    │                                                \n",
              "«        count_1: ──┼────┼────o────────────────────────────────────────────────\n",
              "«                 ┌─┴─┐  │    │  ┌───────┐                                     \n",
              "«      k_count_0: ┤ X ├──┼────┼──┤1      ├──o──────■────────o────────■─────────\n",
              "«                 └───┘┌─┴─┐  │  │       │  │      │        │        │         \n",
              "«      k_count_1: ─────┤ X ├──┼──┤2      ├──o──────o────────■────────■─────────\n",
              "«                      └───┘  │  │       │  │      │        │        │         \n",
              "«  continue_scan: ────────────┼──┤       ├──┼──────┼────────┼────────┼─────────\n",
              "«                           ┌─┴─┐│       │  │  ┌───┴───┐┌───┴───┐┌───┴───┐     \n",
              "« continue_match: ──────────┤ X ├┤  add2 ├──o──┤1      ├┤1      ├┤1      ├─────\n",
              "«                           └───┘│       │  │  │       ││       ││       │     \n",
              "«            one: ───────────────┤4      ├──┼──┤       ├┤       ├┤       ├─────\n",
              "«                                │       │  │  │       ││       ││       │     \n",
              "«         zero_0: ───────────────┤3      ├──┼──┤2      ├┤2      ├┤2      ├─────\n",
              "«                                │       │  │  │       ││       ││       │     \n",
              "«         zero_1: ───────────────┤0      ├──┼──┤0      ├┤0      ├┤0      ├─────\n",
              "«                                └───────┘  │  │       ││       ││       │     \n",
              "«      k_match_0: ──────────────────────────┼──┤       ├┤       ├┤       ├─────\n",
              "«                                           │  │       ││       ││       │     \n",
              "«      k_match_1: ──────────────────────────┼──┤       ├┤       ├┤       ├─────\n",
              "«                                           │  │       ││       ││       │     \n",
              "«         loop_0: ──────────────────────────┼──┤  add2 ├┤  add2 ├┤  add2 ├─────\n",
              "«                                           │  │       ││       ││       │     \n",
              "«         loop_1: ──────────────────────────┼──┤       ├┤       ├┤       ├─────\n",
              "«                                           │  │       ││       ││       │     \n",
              "«    loop_type_0: ──────────────────────────┼──┤       ├┤       ├┤       ├─────\n",
              "«                                           │  │       ││       ││       │     \n",
              "«    loop_type_1: ──────────────────────────┼──┤       ├┤       ├┤       ├─────\n",
              "«                                           │  │       ││       ││       │     \n",
              "«    loop_type_2: ──────────────────────────┼──┤       ├┤       ├┤       ├─────\n",
              "«                                         ┌─┴─┐│       ││       ││       │     \n",
              "«    incorrect_0: ────────────────────────┤ X ├┤3      ├┤3      ├┤3      ├──o──\n",
              "«                                         └───┘│       ││       ││       │  │  \n",
              "«    incorrect_1: ─────────────────────────────┤4      ├┤4      ├┤4      ├──o──\n",
              "«                                              └───────┘└───────┘└───────┘┌─┴─┐\n",
              "«        correct: ────────────────────────────────────────────────────────┤ X ├\n",
              "«                                                                         └───┘</pre>"
            ],
            "text/plain": [
              "                                          ┌───┐                         »\n",
              "change_encoding: ─────────────────────────┤ X ├──■──────────────────────»\n",
              "                 ┌───┐┌───┐┌───┐          └─┬─┘  │                      »\n",
              "      (/./h/)_0: ┤ H ├┤ H ├┤ X ├────────────o────┼────■─────────────────»\n",
              "                 ├───┤└─┬─┘└─┬─┘┌───┐┌───┐  │  ┌─┴─┐  │                 »\n",
              "      (/./h/)_1: ┤ H ├──┼────┼──┤ H ├┤ X ├──■──┤ X ├──┼─────────────────»\n",
              "                 ├───┤  │    │  └─┬─┘└─┬─┘     └───┘  │                 »\n",
              "    k_folding_0: ┤ H ├──o────o────o────o────■─────────┼────■────────────»\n",
              "                 ├───┤  │    │    │    │    │         │    │            »\n",
              "    k_folding_1: ┤ H ├──o────o────o────o────┼────■────┼────┼────■───────»\n",
              "                 └───┘                      │    │  ┌─┴─┐  │    │       »\n",
              "        count_0: ───────────────────────────┼────┼──┤ X ├──┼────┼────■──»\n",
              "                                            │    │  └─┬─┘  │    │    │  »\n",
              "        count_1: ───────────────────────────┼────┼────┼────┼────┼────┼──»\n",
              "                 ┌───┐                    ┌─┴─┐  │    │  ┌─┴─┐  │    │  »\n",
              "      k_count_0: ┤ H ├──■─────────────────┤ X ├──┼────o──┤ X ├──┼────┼──»\n",
              "                 ├───┤  │                 └───┘┌─┴─┐  │  └───┘┌─┴─┐  │  »\n",
              "      k_count_1: ┤ H ├──┼────■─────────────────┤ X ├──o───────┤ X ├──┼──»\n",
              "                 ├───┤  │    │                 └───┘          └───┘  │  »\n",
              "  continue_scan: ┤ X ├──┼────┼───────────────────────────────────────┼──»\n",
              "                 ├───┤  │    │                                     ┌─┴─┐»\n",
              " continue_match: ┤ X ├──┼────┼─────────────────────────────────────┤ X ├»\n",
              "                 ├───┤  │    │                                     └───┘»\n",
              "            one: ┤ X ├──┼────┼──────────────────────────────────────────»\n",
              "                 └───┘  │    │                                          »\n",
              "         zero_0: ───────┼────┼──────────────────────────────────────────»\n",
              "                        │    │                                          »\n",
              "         zero_1: ───────┼────┼──────────────────────────────────────────»\n",
              "                      ┌─┴─┐  │                                          »\n",
              "      k_match_0: ─────┤ X ├──┼──────────────────────────────────────────»\n",
              "                      └───┘┌─┴─┐                                        »\n",
              "      k_match_1: ──────────┤ X ├────────────────────────────────────────»\n",
              "                           └───┘                                        »\n",
              "         loop_0: ───────────────────────────────────────────────────────»\n",
              "                                                                        »\n",
              "         loop_1: ───────────────────────────────────────────────────────»\n",
              "                                                                        »\n",
              "    loop_type_0: ───────────────────────────────────────────────────────»\n",
              "                                                                        »\n",
              "    loop_type_1: ───────────────────────────────────────────────────────»\n",
              "                                                                        »\n",
              "    loop_type_2: ───────────────────────────────────────────────────────»\n",
              "                                                                        »\n",
              "    incorrect_0: ───────────────────────────────────────────────────────»\n",
              "                                                                        »\n",
              "    incorrect_1: ───────────────────────────────────────────────────────»\n",
              "                                                                        »\n",
              "        correct: ───────────────────────────────────────────────────────»\n",
              "                                                                        »\n",
              "«                                                                          »\n",
              "«change_encoding: ─────────────────────────────────────────────────────────»\n",
              "«                                                  ┌─────────────────┐     »\n",
              "«      (/./h/)_0: ─────────────────────────────────┤3                ├─────»\n",
              "«                                                  │                 │     »\n",
              "«      (/./h/)_1: ─────────────────────────────────┤4                ├─────»\n",
              "«                                                  │                 │     »\n",
              "«    k_folding_0: ─────────────────────────■───────┤                 ├─────»\n",
              "«                                          │       │                 │     »\n",
              "«    k_folding_1: ─────────────────────────┼────■──┤                 ├─────»\n",
              "«                                          │    │  │                 │┌───┐»\n",
              "«        count_0: ─────────────────────────┼────┼──┤1                ├┤ X ├»\n",
              "«                                          │    │  │                 │└─┬─┘»\n",
              "«        count_1: ─────────────────────────┼────┼──┤2                ├──┼──»\n",
              "«                          ┌───────┐     ┌─┴─┐  │  │                 │  │  »\n",
              "«      k_count_0: ─────────┤3      ├──o──┤ X ├──┼──o  circuit-364295 ├──┼──»\n",
              "«                          │       │  │  └───┘┌─┴─┐│                 │  │  »\n",
              "«      k_count_1: ─────────┤4      ├──o───────┤ X ├o                 ├──┼──»\n",
              "«                          │       │┌─┴─┐     └───┘│                 │  │  »\n",
              "«  continue_scan: ────■────┤       ├┤ X ├──────────■                 ├──┼──»\n",
              "«                 ┌───┴───┐│       │└───┘          │                 │  │  »\n",
              "« continue_match: ┤1      ├┤  add2 ├───────────────┤                 ├──┼──»\n",
              "«                 │       ││       │               │                 │  │  »\n",
              "«            one: ┤       ├┤1      ├───────────────┤                 ├──■──»\n",
              "«                 │       ││       │               │                 │     »\n",
              "«         zero_0: ┤2      ├┤2      ├───────────────┤                 ├─────»\n",
              "«                 │  add2 ││       │               │                 │     »\n",
              "«         zero_1: ┤0      ├┤0      ├───────────────┤0                ├─────»\n",
              "«                 │       │└───────┘               └─────────────────┘     »\n",
              "«      k_match_0: ┤3      ├────────────────────────────────────────────────»\n",
              "«                 │       │                                                »\n",
              "«      k_match_1: ┤4      ├────────────────────────────────────────────────»\n",
              "«                 └───────┘                                                »\n",
              "«         loop_0: ─────────────────────────────────────────────────────────»\n",
              "«                                                                          »\n",
              "«         loop_1: ─────────────────────────────────────────────────────────»\n",
              "«                                                                          »\n",
              "«    loop_type_0: ─────────────────────────────────────────────────────────»\n",
              "«                                                                          »\n",
              "«    loop_type_1: ─────────────────────────────────────────────────────────»\n",
              "«                                                                          »\n",
              "«    loop_type_2: ─────────────────────────────────────────────────────────»\n",
              "«                                                                          »\n",
              "«    incorrect_0: ─────────────────────────────────────────────────────────»\n",
              "«                                                                          »\n",
              "«    incorrect_1: ─────────────────────────────────────────────────────────»\n",
              "«                                                                          »\n",
              "«        correct: ─────────────────────────────────────────────────────────»\n",
              "«                                                                          »\n",
              "«                                                                           »\n",
              "«change_encoding: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«      (/./h/)_0: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«      (/./h/)_1: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    k_folding_0: ──────────────────────■───────────────────────────────────»\n",
              "«                                       │                                   »\n",
              "«    k_folding_1: ──────────────────────┼────■──────────────────────────────»\n",
              "«                           ┌───┐       │    │                              »\n",
              "«        count_0: ───────o──┤ X ├───────┼────┼────o─────────────────────────»\n",
              "«                 ┌───┐  │  └─┬─┘┌───┐  │    │    │                         »\n",
              "«        count_1: ┤ X ├──o────┼──┤ X ├──┼────┼────o─────────────────────────»\n",
              "«                 └─┬─┘  │    │  └─┬─┘┌─┴─┐  │    │           ┌───────┐     »\n",
              "«      k_count_0: ──┼────o────┼────┼──┤ X ├──┼────┼───────────┤3      ├──o──»\n",
              "«                   │    │    │    │  └───┘┌─┴─┐  │           │       │  │  »\n",
              "«      k_count_1: ──┼────o────┼────┼───────┤ X ├──┼───────────┤4      ├──o──»\n",
              "«                   │    │    │    │       └───┘  │           │       │┌─┴─┐»\n",
              "«  continue_scan: ──┼────■────┼────┼──────────────┼──────■────┤       ├┤ X ├»\n",
              "«                   │    │    │    │            ┌─┴─┐┌───┴───┐│       │└───┘»\n",
              "« continue_match: ──┼────■────┼────┼────────────┤ X ├┤1      ├┤  add2 ├─────»\n",
              "«                   │    │    │    │            └───┘│       ││       │     »\n",
              "«            one: ──┼────┼────■────┼─────────────────┤       ├┤1      ├─────»\n",
              "«                   │    │         │                 │       ││       │     »\n",
              "«         zero_0: ──■────┼─────────■─────────────────┤2      ├┤2      ├─────»\n",
              "«                        │                           │  add2 ││       │     »\n",
              "«         zero_1: ───────┼───────────────────────────┤0      ├┤0      ├─────»\n",
              "«                        │                           │       │└───────┘     »\n",
              "«      k_match_0: ───────┼───────────────────────────┤3      ├──────────────»\n",
              "«                        │                           │       │              »\n",
              "«      k_match_1: ───────┼───────────────────────────┤4      ├──────────────»\n",
              "«                      ┌─┴─┐                         └───────┘              »\n",
              "«         loop_0: ─────┤ X ├────────────────────────────────────────────────»\n",
              "«                      └───┘                                                »\n",
              "«         loop_1: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    loop_type_0: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    loop_type_1: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    loop_type_2: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    incorrect_0: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    incorrect_1: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«        correct: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«                                                                           »\n",
              "«change_encoding: ──────────────────────────────────────────────────────────»\n",
              "«                           ┌─────────────────┐                             »\n",
              "«      (/./h/)_0: ──────────┤3                ├─────────────────────────────»\n",
              "«                           │                 │                             »\n",
              "«      (/./h/)_1: ──────────┤4                ├─────────────────────────────»\n",
              "«                           │                 │                             »\n",
              "«    k_folding_0: ──■───────┤                 ├─────────────────────────────»\n",
              "«                   │       │                 │                             »\n",
              "«    k_folding_1: ──┼────■──┤                 ├─────────────────────────────»\n",
              "«                   │    │  │                 │┌─────────────────┐┌───┐     »\n",
              "«        count_0: ──┼────┼──┤1                ├┤1                ├┤ X ├─────»\n",
              "«                   │    │  │                 ││                 │└─┬─┘┌───┐»\n",
              "«        count_1: ──┼────┼──┤2                ├┤2                ├──┼──┤ X ├»\n",
              "«                 ┌─┴─┐  │  │                 ││                 │  │  └─┬─┘»\n",
              "«      k_count_0: ┤ X ├──┼──o  circuit-364295 ├o                 ├──┼────┼──»\n",
              "«                 └───┘┌─┴─┐│                 ││                 │  │    │  »\n",
              "«      k_count_1: ─────┤ X ├o                 ├o                 ├──┼────┼──»\n",
              "«                      └───┘│                 ││                 │  │    │  »\n",
              "«  continue_scan: ──────────■                 ├┤  circuit-364295 ├──┼────┼──»\n",
              "«                           │                 ││                 │  │    │  »\n",
              "« continue_match: ──────────■                 ├o                 ├──┼────┼──»\n",
              "«                           │                 ││                 │  │    │  »\n",
              "«            one: ──────────┤                 ├┤3                ├──■────┼──»\n",
              "«                           │                 ││                 │       │  »\n",
              "«         zero_0: ──────────┤                 ├┤4                ├───────■──»\n",
              "«                           │                 ││                 │          »\n",
              "«         zero_1: ──────────┤0                ├┤0                ├──────────»\n",
              "«                           └─────────────────┘└─────────────────┘          »\n",
              "«      k_match_0: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«      k_match_1: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«         loop_0: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«         loop_1: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    loop_type_0: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    loop_type_1: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    loop_type_2: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    incorrect_0: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    incorrect_1: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«        correct: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«                                                                      »\n",
              "«change_encoding: ─────────────────────────────────────────────────────»\n",
              "«                                                                      »\n",
              "«      (/./h/)_0: ─────────────────────────────────────────────────────»\n",
              "«                                                                      »\n",
              "«      (/./h/)_1: ─────────────────────────────────────────────────────»\n",
              "«                                                                      »\n",
              "«    k_folding_0: ───────────────────────────────■─────────────────────»\n",
              "«                                                │                     »\n",
              "«    k_folding_1: ───────────────────────────────┼────■────────────────»\n",
              "«                                    ┌───┐       │    │                »\n",
              "«        count_0: ─────────o─────────┤ X ├───────┼────┼────o───────────»\n",
              "«                          │         └─┬─┘┌───┐  │    │    │           »\n",
              "«        count_1: ─────────o───────────┼──┤ X ├──┼────┼────o───────────»\n",
              "«                          │           │  └─┬─┘┌─┴─┐  │    │           »\n",
              "«      k_count_0: ─────────o───────────┼────┼──┤ X ├──┼────┼───────────»\n",
              "«                          │           │    │  └───┘┌─┴─┐  │           »\n",
              "«      k_count_1: ─────────o───────────┼────┼───────┤ X ├──┼───────────»\n",
              "«                          │           │    │       └───┘  │           »\n",
              "«  continue_scan: ─────────■───────────┼────┼──────────────┼──────■────»\n",
              "«                 ┌────────┴────────┐  │    │            ┌─┴─┐┌───┴───┐»\n",
              "« continue_match: ┤3                ├──┼────┼────────────┤ X ├┤1      ├»\n",
              "«                 │                 │  │    │            └───┘│       │»\n",
              "«            one: ┤                 ├──■────┼─────────────────┤       ├»\n",
              "«                 │                 │       │                 │       │»\n",
              "«         zero_0: ┤4                ├───────■─────────────────┤2      ├»\n",
              "«                 │                 │                         │  add2 │»\n",
              "«         zero_1: ┤0                ├─────────────────────────┤0      ├»\n",
              "«                 │  circuit-364295 │                         │       │»\n",
              "«      k_match_0: ┤                 ├─────────────────────────┤3      ├»\n",
              "«                 │                 │                         │       │»\n",
              "«      k_match_1: ┤                 ├─────────────────────────┤4      ├»\n",
              "«                 │                 │                         └───────┘»\n",
              "«         loop_0: ┤1                ├──────────────────────────────────»\n",
              "«                 │                 │                                  »\n",
              "«         loop_1: ┤2                ├──────────────────────────────────»\n",
              "«                 └─────────────────┘                                  »\n",
              "«    loop_type_0: ─────────────────────────────────────────────────────»\n",
              "«                                                                      »\n",
              "«    loop_type_1: ─────────────────────────────────────────────────────»\n",
              "«                                                                      »\n",
              "«    loop_type_2: ─────────────────────────────────────────────────────»\n",
              "«                                                                      »\n",
              "«    incorrect_0: ─────────────────────────────────────────────────────»\n",
              "«                                                                      »\n",
              "«    incorrect_1: ─────────────────────────────────────────────────────»\n",
              "«                                                                      »\n",
              "«        correct: ─────────────────────────────────────────────────────»\n",
              "«                                                                      »\n",
              "«                                                            »\n",
              "«change_encoding: ───────────────────────────────────────────»\n",
              "«                                         ┌─────────────────┐»\n",
              "«      (/./h/)_0: ────────────────────────┤3                ├»\n",
              "«                                         │                 │»\n",
              "«      (/./h/)_1: ────────────────────────┤4                ├»\n",
              "«                                         │                 │»\n",
              "«    k_folding_0: ────────────────■───────┤                 ├»\n",
              "«                                 │       │                 │»\n",
              "«    k_folding_1: ────────────────┼────■──┤                 ├»\n",
              "«                                 │    │  │                 │»\n",
              "«        count_0: ────────────────┼────┼──┤1                ├»\n",
              "«                                 │    │  │                 │»\n",
              "«        count_1: ────────────────┼────┼──┤2                ├»\n",
              "«                 ┌───────┐     ┌─┴─┐  │  │                 │»\n",
              "«      k_count_0: ┤3      ├──o──┤ X ├──┼──o  circuit-364295 ├»\n",
              "«                 │       │  │  └───┘┌─┴─┐│                 │»\n",
              "«      k_count_1: ┤4      ├──o───────┤ X ├o                 ├»\n",
              "«                 │       │┌─┴─┐     └───┘│                 │»\n",
              "«  continue_scan: ┤       ├┤ X ├──────────■                 ├»\n",
              "«                 │       │└───┘          │                 │»\n",
              "« continue_match: ┤  add2 ├───────────────■                 ├»\n",
              "«                 │       │               │                 │»\n",
              "«            one: ┤1      ├───────────────┤                 ├»\n",
              "«                 │       │               │                 │»\n",
              "«         zero_0: ┤2      ├───────────────┤                 ├»\n",
              "«                 │       │               │                 │»\n",
              "«         zero_1: ┤0      ├───────────────┤0                ├»\n",
              "«                 └───────┘               └─────────────────┘»\n",
              "«      k_match_0: ───────────────────────────────────────────»\n",
              "«                                                            »\n",
              "«      k_match_1: ───────────────────────────────────────────»\n",
              "«                                                            »\n",
              "«         loop_0: ───────────────────────────────────────────»\n",
              "«                                                            »\n",
              "«         loop_1: ───────────────────────────────────────────»\n",
              "«                                                            »\n",
              "«    loop_type_0: ───────────────────────────────────────────»\n",
              "«                                                            »\n",
              "«    loop_type_1: ───────────────────────────────────────────»\n",
              "«                                                            »\n",
              "«    loop_type_2: ───────────────────────────────────────────»\n",
              "«                                                            »\n",
              "«    incorrect_0: ───────────────────────────────────────────»\n",
              "«                                                            »\n",
              "«    incorrect_1: ───────────────────────────────────────────»\n",
              "«                                                            »\n",
              "«        correct: ───────────────────────────────────────────»\n",
              "«                                                            »\n",
              "«                                                                           »\n",
              "«change_encoding: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«      (/./h/)_0: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«      (/./h/)_1: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    k_folding_0: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    k_folding_1: ──────────────────────────────────────────────────────────»\n",
              "«                 ┌─────────────────┐┌───┐                        ┌───┐     »\n",
              "«        count_0: ┤1                ├┤ X ├──────────────o─────────┤ X ├─────»\n",
              "«                 │                 │└─┬─┘┌───┐         │         └─┬─┘┌───┐»\n",
              "«        count_1: ┤2                ├──┼──┤ X ├─────────o───────────┼──┤ X ├»\n",
              "«                 │                 │  │  └─┬─┘         │           │  └─┬─┘»\n",
              "«      k_count_0: o                 ├──┼────┼───────────o───────────┼────┼──»\n",
              "«                 │                 │  │    │           │           │    │  »\n",
              "«      k_count_1: o                 ├──┼────┼───────────o───────────┼────┼──»\n",
              "«                 │                 │  │    │           │           │    │  »\n",
              "«  continue_scan: ┤  circuit-364295 ├──┼────┼───────────■───────────┼────┼──»\n",
              "«                 │                 │  │    │  ┌────────┴────────┐  │    │  »\n",
              "« continue_match: o                 ├──┼────┼──┤3                ├──┼────┼──»\n",
              "«                 │                 │  │    │  │                 │  │    │  »\n",
              "«            one: ┤3                ├──■────┼──┤                 ├──■────┼──»\n",
              "«                 │                 │       │  │                 │       │  »\n",
              "«         zero_0: ┤4                ├───────■──┤4                ├───────■──»\n",
              "«                 │                 │          │                 │          »\n",
              "«         zero_1: ┤0                ├──────────┤0                ├──────────»\n",
              "«                 └─────────────────┘          │  circuit-364295 │          »\n",
              "«      k_match_0: ─────────────────────────────┤                 ├──────────»\n",
              "«                                              │                 │          »\n",
              "«      k_match_1: ─────────────────────────────┤                 ├──────────»\n",
              "«                                              │                 │          »\n",
              "«         loop_0: ─────────────────────────────┤1                ├──────────»\n",
              "«                                              │                 │          »\n",
              "«         loop_1: ─────────────────────────────┤2                ├──────────»\n",
              "«                                              └─────────────────┘          »\n",
              "«    loop_type_0: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    loop_type_1: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    loop_type_2: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    incorrect_0: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«    incorrect_1: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«        correct: ──────────────────────────────────────────────────────────»\n",
              "«                                                                           »\n",
              "«                                                                              \n",
              "«change_encoding: ─────────────────────────────────────────────────────────────\n",
              "«                                                                              \n",
              "«      (/./h/)_0: ─────────────────────────────────────────────────────────────\n",
              "«                                                                              \n",
              "«      (/./h/)_1: ─────────────────────────────────────────────────────────────\n",
              "«                                                                              \n",
              "«    k_folding_0: ──■──────────────────────────────────────────────────────────\n",
              "«                   │                                                          \n",
              "«    k_folding_1: ──┼────■─────────────────────────────────────────────────────\n",
              "«                   │    │                                                     \n",
              "«        count_0: ──┼────┼────o────────────────────────────────────────────────\n",
              "«                   │    │    │                                                \n",
              "«        count_1: ──┼────┼────o────────────────────────────────────────────────\n",
              "«                 ┌─┴─┐  │    │  ┌───────┐                                     \n",
              "«      k_count_0: ┤ X ├──┼────┼──┤1      ├──o──────■────────o────────■─────────\n",
              "«                 └───┘┌─┴─┐  │  │       │  │      │        │        │         \n",
              "«      k_count_1: ─────┤ X ├──┼──┤2      ├──o──────o────────■────────■─────────\n",
              "«                      └───┘  │  │       │  │      │        │        │         \n",
              "«  continue_scan: ────────────┼──┤       ├──┼──────┼────────┼────────┼─────────\n",
              "«                           ┌─┴─┐│       │  │  ┌───┴───┐┌───┴───┐┌───┴───┐     \n",
              "« continue_match: ──────────┤ X ├┤  add2 ├──o──┤1      ├┤1      ├┤1      ├─────\n",
              "«                           └───┘│       │  │  │       ││       ││       │     \n",
              "«            one: ───────────────┤4      ├──┼──┤       ├┤       ├┤       ├─────\n",
              "«                                │       │  │  │       ││       ││       │     \n",
              "«         zero_0: ───────────────┤3      ├──┼──┤2      ├┤2      ├┤2      ├─────\n",
              "«                                │       │  │  │       ││       ││       │     \n",
              "«         zero_1: ───────────────┤0      ├──┼──┤0      ├┤0      ├┤0      ├─────\n",
              "«                                └───────┘  │  │       ││       ││       │     \n",
              "«      k_match_0: ──────────────────────────┼──┤       ├┤       ├┤       ├─────\n",
              "«                                           │  │       ││       ││       │     \n",
              "«      k_match_1: ──────────────────────────┼──┤       ├┤       ├┤       ├─────\n",
              "«                                           │  │       ││       ││       │     \n",
              "«         loop_0: ──────────────────────────┼──┤  add2 ├┤  add2 ├┤  add2 ├─────\n",
              "«                                           │  │       ││       ││       │     \n",
              "«         loop_1: ──────────────────────────┼──┤       ├┤       ├┤       ├─────\n",
              "«                                           │  │       ││       ││       │     \n",
              "«    loop_type_0: ──────────────────────────┼──┤       ├┤       ├┤       ├─────\n",
              "«                                           │  │       ││       ││       │     \n",
              "«    loop_type_1: ──────────────────────────┼──┤       ├┤       ├┤       ├─────\n",
              "«                                           │  │       ││       ││       │     \n",
              "«    loop_type_2: ──────────────────────────┼──┤       ├┤       ├┤       ├─────\n",
              "«                                         ┌─┴─┐│       ││       ││       │     \n",
              "«    incorrect_0: ────────────────────────┤ X ├┤3      ├┤3      ├┤3      ├──o──\n",
              "«                                         └───┘│       ││       ││       │  │  \n",
              "«    incorrect_1: ─────────────────────────────┤4      ├┤4      ├┤4      ├──o──\n",
              "«                                              └───────┘└───────┘└───────┘┌─┴─┐\n",
              "«        correct: ────────────────────────────────────────────────────────┤ X ├\n",
              "«                                                                         └───┘"
            ]
          },
          "execution_count": 70,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "nb_bits_bracket_dot = 2\n",
        "nb_bits_loop_type = 3\n",
        "\n",
        "def n_to_ctrl_state(n,nb_bits):\n",
        "    return format(n,\"0{}b\".format(nb_bits))\n",
        "\n",
        "#if test_concerved == tested_to_0 then tested_to_0 is set to 0 and will trigger the application of some gate in then_append(circuit,tested_to_0,nb_bits_test,gate,...)\n",
        "def start_if_equal(circuit,tested_to_0,nb_bits_test,test_concerved):\n",
        "    for i in range(nb_bits_test):\n",
        "        circuit.cx(test_concerved[i],tested_to_0[i])\n",
        "\n",
        "end_if_equal=start_if_equal\n",
        "\n",
        "def then_append(circuit,test_0,nb_bits_test,gate,qbits_list):\n",
        "    circuit.append(gate.control(nb_bits_test,ctrl_state=\"0\"*nb_bits_test),[test_0[i] for i in range(nb_bits_test)]+qbits_list)\n",
        "\n",
        "def matching_parenthesis_circuit(length):\n",
        "    nb_bits_position=ceil(log2(length+1)) #length+1 because we add a ( at the begining to check the folding is well formed\n",
        "    add_positions=add_gate(nb_bits_position)\n",
        "\n",
        "    #input\n",
        "    #semantics of folding\n",
        "    #. == \"00\"\n",
        "    #h == \"10\"\n",
        "    #) == \"11\"\n",
        "    #( == \"01\"\n",
        "    folding = QuantumRegister(nb_bits_position,name=\"(/./h/)\")\n",
        "\n",
        "    #auxillary qbits\n",
        "    k_folding = QuantumRegister(nb_bits_position,name=\"k_folding\")\n",
        "    count = QuantumRegister(nb_bits_position,name=\"count\") #count how many parenthesis still need to be closed. count[k+1] corresponds to folding[k] and count[0] is initiallised to ( and is used to check that there is no extra ) that would match in the folding\n",
        "    k_count = QuantumRegister(nb_bits_position,name=\"k_count\")\n",
        "    continue_searching_right_matching_left = QuantumRegister(1,name=\"continue_match\") #continue_searching_right_matching_left[k] corresponds to count[k]\n",
        "\n",
        "    change_folding_encoding = QuantumRegister(1,name=\"change_encoding\")\n",
        "    continue_scanning = QuantumRegister(1,name=\"continue_scan\")\n",
        "    zeros = QuantumRegister(nb_bits_position,name=\"zero\")\n",
        "    one = QuantumRegister(1,name=\"one\")\n",
        "\n",
        "    #results\n",
        "    k_right_matching_left = QuantumRegister(nb_bits_position,name=\"k_match\") #k_right_matching_left[k_left] is initialised to k_left and is incremented until count[k_left+1]==0, that is until k_right_matching_left[k_left] is the indice of the ) matching the ( ~ folding[k_left-1]\n",
        "    loop = QuantumRegister(nb_bits_position,name=\"loop\") #length of the loop starting at folding[k_left]==(. loop[k_left] is initialised to 0 and is incremented each time count[k_left]==1 until count[k_left]==0\n",
        "    #semantics of loop_type\n",
        "    #interior -> ?\n",
        "    #buggle   -> ?\n",
        "    #multi    -> ?\n",
        "    #hairpin  -> ?\n",
        "    #stack    -> ?\n",
        "    loop_type = QuantumRegister(nb_bits_loop_type,name=\"loop_type\")\n",
        "    incorrect_folding = QuantumRegister(nb_bits_position,name=\"incorrect\")\n",
        "    correct_folding = QuantumRegister(1,name=\"correct\")\n",
        "\n",
        "    circuit = QuantumCircuit(change_folding_encoding,folding,k_folding,count,k_count,continue_scanning,continue_searching_right_matching_left,one,zeros,k_right_matching_left,loop,loop_type,incorrect_folding,correct_folding)\n",
        "\n",
        "\n",
        "    #1) Superposition at the begining of the Groover search\n",
        "\n",
        "    #initialize k_kolding\n",
        "    circuit.h(k_folding)\n",
        "\n",
        "    #any symbol at any position\n",
        "    for i in range(nb_bits_bracket_dot):\n",
        "        circuit.h(folding[i])\n",
        "\n",
        "    #except at position \"0\"*nb_bits_position, where it is necessarily a ( == \"11\" to check if the folding is well formed\n",
        "    for i in range(nb_bits_bracket_dot):\n",
        "        circuit.append(HGate().control(nb_bits_position,ctrl_state=n_to_ctrl_state(0,nb_bits_position)),[k_folding[j] for j in range(nb_bits_position)]+[folding[i]])\n",
        "        circuit.append(MCXGate(        nb_bits_position,ctrl_state=n_to_ctrl_state(0,nb_bits_position)),[k_folding[j] for j in range(nb_bits_position)]+[folding[i]])\n",
        "\n",
        "    #except at positions k > length, where folding[k] is set to .\n",
        "    for k in range(length+1,2**nb_bits_position):\n",
        "        for i in range(nb_bits_bracket_dot):\n",
        "            circuit.append(HGate().control(nb_bits_position,ctrl_state=n_to_ctrl_state(k,nb_bits_position)),[k_folding[j] for j in range(nb_bits_position)]+[folding[i]])\n",
        "\n",
        "    #if this symbol is h == \"10\", then change it to be . == \"00\"\n",
        "    #OPTIMISATION here ?\n",
        "    circuit.ccx(*[folding[i] for i in range(nb_bits_bracket_dot)],change_folding_encoding,ctrl_state=\"10\")\n",
        "    circuit.cnot(change_folding_encoding,folding[nb_bits_bracket_dot-1])\n",
        "\n",
        "\n",
        "    #2) Initialisation of the oracle\n",
        "\n",
        "    #initialise one to 1\n",
        "    circuit.x(one)\n",
        "\n",
        "    #when folding[k_left] == ( (which will be checked by there <*>) then there is initially 1 parenthesis to be closed\n",
        "    circuit.x(continue_searching_right_matching_left)\n",
        "\n",
        "    #initialise k_count to k_left\n",
        "    circuit.h(k_count)\n",
        "    #initialise k_right_matching_left[k_count] to k_left (and it will then be incremented up to the matchning k_right)\n",
        "    for i in range(nb_bits_position):\n",
        "        circuit.cx(k_count[i],k_right_matching_left[i])\n",
        "\n",
        "    #extend folding\n",
        "    #folding[0:nb_bits_bracket_dot] -> folding[0:nb_bits_position]\n",
        "    #. == \"00\" ->  0 == \"0...000\"\n",
        "    #do nothing\n",
        "    #( == \"01\" ->  1 == \"0...001\"\n",
        "    #do nothing\n",
        "    #) == \"11\" -> -1 == \"1...111\"\n",
        "    if nb_bits_bracket_dot < nb_bits_position:\n",
        "        circuit.append(MCMT(XGate(),nb_bits_bracket_dot,nb_bits_position-nb_bits_bracket_dot),[folding[i] for i in range(nb_bits_position)])\n",
        "\n",
        "    #if k_folding == k_count\n",
        "    start_if_equal(circuit,k_count,nb_bits_position,k_folding)\n",
        "\n",
        "    #initialise count with folding\n",
        "    #folding -> count\n",
        "    #. == \"00\" -> 0 == \"0...000\"\n",
        "    #do nothing\n",
        "    #) == \"11\" -> 0 == \"0...000\"\n",
        "    #do nothing\n",
        "    #( == \"01\" -> 1 == \"0...001\"\n",
        "    then_append(circuit,k_count,nb_bits_position,CXGate(),[folding[0],count[0]])\n",
        "\n",
        "    #end if k_folding == k_count\n",
        "    end_if_equal(circuit,k_count,nb_bits_position,k_folding)\n",
        "\n",
        "    #initialise continue_searching_right_matching_left=1 when count == (\n",
        "    circuit.cnot(count[0],continue_searching_right_matching_left)\n",
        "\n",
        "    #initialise continue_scanning=1\n",
        "    circuit.x(continue_scanning)\n",
        "\n",
        "\n",
        "    #3) Compute parameters by scanning the folding\n",
        "\n",
        "    for k in range(length):\n",
        "        #<*> if it has been checked that there is a matching ) to find, then continue_searching_right_matching_left[k_left]==1, otherwise continue_searching_right_matching_left[k_left]==0\n",
        "\n",
        "        #increment k_right_matching_left[k_left] if continue_searching_right_matching_left[k_left]==1\n",
        "        circuit.append(add_positions.control(),[continue_scanning,zeros[nb_bits_position-1],continue_searching_right_matching_left]+[zeros[i] for i in range(nb_bits_position-1)]+[k_right_matching_left[i] for i in range(nb_bits_position)])\n",
        "\n",
        "        #go to the next position\n",
        "        #increment k_count\n",
        "        circuit.append(add_positions,[zeros[nb_bits_position-1],one]+[zeros[i] for i in range(nb_bits_position-1)]+[k_count[i] for i in range(nb_bits_position)])\n",
        "\n",
        "        #if the end has been reached, that is if k_count == 0\n",
        "        #then do not continue_scanning\n",
        "        circuit.append(MCXGate(nb_bits_position,ctrl_state=n_to_ctrl_state(0,nb_bits_position)),[k_count[i] for i in range(nb_bits_position)]+[continue_scanning])\n",
        "\n",
        "        #if k_folding == k_count\n",
        "        start_if_equal(circuit,k_count,nb_bits_position,k_folding)\n",
        "\n",
        "        #if continue_searching_right_matching_left[k_left]==1, then update count[k_left] for the next candidate\n",
        "        if 0 == k:\n",
        "            #necessarily if folding[k_left]==( then continue_searching_right_matching_left[k_left]==1\n",
        "            #so it is ok not controlling by continue_searching_right_matching_left here\n",
        "            then_append(circuit,k_count,nb_bits_position,add_positions.control()              ,[continue_scanning,zeros[nb_bits_position-1]]+[count[i] for i in range(nb_bits_position)]+[folding[i] for i in range(nb_bits_position)])\n",
        "        else:\n",
        "            then_append(circuit,k_count,nb_bits_position,add_positions.control(2)             ,[continue_scanning,continue_searching_right_matching_left,zeros[nb_bits_position-1]]+[count[i] for i in range(nb_bits_position)]+[folding[i] for i in range(nb_bits_position)])\n",
        "\n",
        "\n",
        "        #if continue_searching_right_matching_left[k_left]==0, then simply increment count[k_left] so that it never equals 0 again\n",
        "        #it is ok not controlling by continue_scanning here\n",
        "        if 0 != k:\n",
        "            #as stated previously, if 0==k then necessarily if folding[k_left]==( then continue_searching_right_matching_left[k_left]==1\n",
        "            #so there is no need doing this if 0==k\n",
        "            then_append(circuit,k_count,nb_bits_position,add_positions.control(ctrl_state=\"0\"),[continue_searching_right_matching_left,zeros[nb_bits_position-1]]+[count[i] for i in range(nb_bits_position)]+[one]+[zeros[i] for i in range(nb_bits_position-1)])\n",
        "\n",
        "        #if 1 == count[k_left]\n",
        "        start_if_equal(circuit,count,nb_bits_position,[one]+[zeros[i] for i in range(nb_bits_position-1)])\n",
        "\n",
        "        #if 1 == continue_searching_right_matching_left[k_left] then increment loop[k_left]\n",
        "        if 0==k:\n",
        "            #since the value 0==loop[k_left] is known then there is no need to add in order to increment\n",
        "            #a CXGate() is sufficient\n",
        "            then_append(circuit,[k_count[i] for i in range(nb_bits_position)]+[count[i] for i in range(nb_bits_position)],2*nb_bits_position,CCXGate(),[continue_scanning,continue_searching_right_matching_left,loop[0]])\n",
        "        else:\n",
        "            then_append(circuit,[k_count[i] for i in range(nb_bits_position)]+[count[i] for i in range(nb_bits_position)],2*nb_bits_position,add_positions.control(),[continue_scanning,zeros[nb_bits_position-1]]+[loop[i] for i in range(nb_bits_position)]+[continue_searching_right_matching_left]+[zeros[i] for i in range(nb_bits_position-1)])\n",
        "\n",
        "        #end if 1 == count[k_left]\n",
        "        end_if_equal(circuit,count,nb_bits_position,[one]+[zeros[i] for i in range(nb_bits_position-1)])\n",
        "        #end if k_folding == k_count\n",
        "        end_if_equal(circuit,k_count,nb_bits_position,k_folding)\n",
        "\n",
        "        #if count[k_left] == 0\n",
        "        #then there is no matching ) to find\n",
        "        circuit.append(MCXGate(nb_bits_position,ctrl_state=n_to_ctrl_state(0,nb_bits_position)),[count[i] for i in range(nb_bits_position)]+[continue_searching_right_matching_left])\n",
        "\n",
        "    #set k_count to its initial value by adding it 2**nb_bits_position - length\n",
        "    first_one = -1\n",
        "    for i,bit in enumerate(n_to_ctrl_state(2**nb_bits_position - length,nb_bits_position)):\n",
        "        if '1'==bit:\n",
        "            if 0 > first_one:\n",
        "                first_one = i\n",
        "            else:\n",
        "                circuit.x(zeros[i])\n",
        "    circuit.append(add_positions,[zeros[first_one]]+[k_count[i] for i in range(nb_bits_position)]+[(one if first_one == i else zeros[i]) for i in range(nb_bits_position)])\n",
        "\n",
        "    #restore zeros\n",
        "    first_one = -1\n",
        "    for i,bit in enumerate(n_to_ctrl_state(2**nb_bits_position - length,nb_bits_position)):\n",
        "        if '1'==bit:\n",
        "            if 0 > first_one:\n",
        "                first_one = i\n",
        "            else:\n",
        "                circuit.x(zeros[i])\n",
        "\n",
        "    #Computed parameters\n",
        "    #folding[kleft] -> continue_searching_right_matching_left[k_left] * k_right_matching_left[k_left] * loop                                 * k_count[k_left] * count[k_left]\n",
        "    #(              -> 0 if a matching ) has been found               * k_right_matching_left         * number of . (at level 1) in the loop * k_left          * unspecified\n",
        "    #(              -> 1 if a matching ) has not been found           * !=k_left                      * unspecified                          * k_left          * unspecified\n",
        "    #. or )         -> 0                                              * k_left                        * 0                                    * k_left          * unspecified\n",
        "\n",
        "\n",
        "    #4) Aggregating results\n",
        "\n",
        "    #if each ( of the folding has a matching ) and if an extra ( at the beginning does not have a matching ), then it is a correst folding\n",
        "\n",
        "    #checking if there is an exceeding )\n",
        "    #there is if 0 == continue_searching_right_matching_left[k_left=0]\n",
        "    #since the value 0==incorrect_folding is known then there is no need to add in order to increment\n",
        "    #a CXGate() is sufficient\n",
        "    circuit.append(MCXGate(nb_bits_position+1,ctrl_state=\"0\"+n_to_ctrl_state(0,nb_bits_position)),[k_count[i] for i in range(nb_bits_position)]+[continue_searching_right_matching_left,incorrect_folding[0]])\n",
        "\n",
        "    #sum all the incorrect flags continue_searching_right_matching_left (1 per position) into incorrect_folding\n",
        "    #the sum cannot overflow since if the flag continue_searching_right_matching_left[k_left=0] == 0 (at k_left=0 incorrect beeing 0) then there is a ) somewhere\n",
        "    #so continue_searching_right_matching_left[k_left=somewhere] == 0\n",
        "    #so incorrect_folding is not incremented at each position\n",
        "    for k in range(1,length+1):\n",
        "        circuit.append(add_positions.control(nb_bits_position,ctrl_state=n_to_ctrl_state(k,nb_bits_position)),[k_count[i] for i in range(nb_bits_position)]+[zeros[nb_bits_position-1],continue_searching_right_matching_left]+[zeros[i] for i in range(nb_bits_position-1)]+[incorrect_folding[i] for i in range(nb_bits_position)])\n",
        "\n",
        "    circuit.append(MCXGate(nb_bits_position,ctrl_state=n_to_ctrl_state(0,nb_bits_position)),[incorrect_folding[i] for i in range(nb_bits_position)]+[correct_folding])\n",
        "\n",
        "    return circuit\n",
        "\n",
        "def matching_parenthesis_gate(length):\n",
        "    return matching_parenthesis_circuit(length).to_gate(label=\"matching\")\n",
        "\n",
        "circ=matching_parenthesis_circuit(3)\n",
        "\n",
        "circ.draw()\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "D-0GvmAefDGI"
      },
      "source": [
        "statistics"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "VV2gDWlofDGJ",
        "outputId": "a25e2c98-2a49-4829-9644-2149c23ae4bf"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "width 24 ; depth 42\n"
          ]
        }
      ],
      "source": [
        "print(\"width {} ; depth {}\".format(circ.width(),circ.depth()))"
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3 (ipykernel)",
      "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.11.3"
    },
    "colab": {
      "provenance": [],
      "include_colab_link": true
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}