{
  "cells": [
    {
      "cell_type": "markdown",
      "id": "4cb32582",
      "metadata": {},
      "source": [
        "---\n",
        "title: Work with DAGs in transpiler passes\n",
        "description: How to use Directed Acyclic Graphs (DAGs) to analyze and transform quantum circuits in Qiskit transpiler passes\n",
        "---\n",
        "\n",
        "{/* cspell:ignore subdag DAGOpNode qargs cargs dag_drawer couplinglist */}\n",
        "\n",
        "# Work with DAGs in transpiler passes\n",
        "\n",
        "In Qiskit, within the transpilation stages, circuits are represented using a DAG. In general, a DAG is composed of vertices (also known as \"nodes\") and directed edges that connect pairs of vertices in a particular orientation. This representation is stored using `qiskit.dagcircuit.DAGCircuit` objects that are composed of individual `DagNode` objects. The advantage of this representation over a pure list of gates (that is, a netlist) is that the flow of information between operations is explicit, making it easier to make transformation decisions.\n",
        "\n",
        "This guide demonstrates how to work with DAGs and use them to write custom transpiler passes. It will start with building a simple circuit and examining its DAG representation, then explores basic DAG operations and implements a custom `BasicMapper` pass.\n",
        "\n",
        "## Build a circuit and examine its DAG\n",
        "\n",
        "The code snippet below illustrates the DAG by creating a simple circuit that prepares a Bell state and applies an $R_Z$ rotation, depending on the measurement outcome.\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "version-info-cell",
      "metadata": {
        "tags": [
          "version-info"
        ]
      },
      "source": [
        "{/*\n",
        "  DO NOT EDIT THIS CELL!!!\n",
        "  This cell's content is generated automatically by a script. Anything you add\n",
        "  here will be removed next time the notebook is run. To add new content, create\n",
        "  a new cell before or after this one.\n",
        "  */}\n",
        "\n",
        "<Accordion>\n",
        "  <AccordionItem title=\"Package versions\">\n",
        "    The code on this page was developed using the following requirements.\n",
        "    We recommend using these versions or newer.\n",
        "\n",
        "    ```\n",
        "    qiskit[all]~=2.5.2\n",
        "    ```\n",
        "  </AccordionItem>\n",
        "</Accordion>\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "id": "1d16892a",
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "<Image src=\"/docs/images/guides/DAG-representation/extracted-outputs/1d16892a-0.svg\" alt=\"Output of the previous code cell\" />"
            ]
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit\n",
        "from qiskit.converters import circuit_to_dag\n",
        "from qiskit.visualization import circuit_drawer\n",
        "from qiskit.visualization.dag_visualization import dag_drawer\n",
        "\n",
        "# Create circuit\n",
        "q = QuantumRegister(3, \"q\")\n",
        "c = ClassicalRegister(3, \"c\")\n",
        "circ = QuantumCircuit(q, c)\n",
        "circ.h(q[0])\n",
        "circ.cx(q[0], q[1])\n",
        "circ.measure(q[0], c[0])\n",
        "\n",
        "# Qiskit 2.0 uses if_test instead of c_if\n",
        "with circ.if_test((c, 2)):\n",
        "    circ.rz(0.5, q[1])\n",
        "\n",
        "circuit_drawer(circ, output=\"mpl\")"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "5971b6ed",
      "metadata": {},
      "source": [
        "In the DAG, there are three kinds of graph nodes: qubit/clbit input nodes (green), operation nodes (blue), and output nodes (red). Each edge indicates data flow (or dependency) between two nodes. Use the qiskit.tools.visualization.dag\\_drawer() function to view this circuit's DAG. (Install the [Graphviz library](https://graphviz.org/download/) to run this.)\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "id": "e498faa3",
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "<Image src=\"/docs/images/guides/DAG-representation/extracted-outputs/e498faa3-0.avif\" alt=\"Output of the previous code cell\" />"
            ]
          },
          "execution_count": 2,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "# Convert to DAG\n",
        "dag = circuit_to_dag(circ)\n",
        "dag_drawer(dag)"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "3b728136",
      "metadata": {},
      "source": [
        "## Basic DAG operations\n",
        "\n",
        "The code examples below demonstrate common operations with DAGs, including accessing nodes, adding operations, and substituting subcircuits. These operations form the foundation for building transpiler passes.\n",
        "\n",
        "## Get all operation nodes in the DAG\n",
        "\n",
        "The `op_nodes()` method returns an iterable list of `DAGOpNode` objects in the circuit:\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "id": "4f848695",
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "[DAGOpNode(op=Instruction(name='h', num_qubits=1, num_clbits=0, params=[]), qargs=(<Qubit register=(3, \"q\"), index=0>,), cargs=()),\n",
              " DAGOpNode(op=Instruction(name='cx', num_qubits=2, num_clbits=0, params=[]), qargs=(<Qubit register=(3, \"q\"), index=0>, <Qubit register=(3, \"q\"), index=1>), cargs=()),\n",
              " DAGOpNode(op=Instruction(name='measure', num_qubits=1, num_clbits=1, params=[]), qargs=(<Qubit register=(3, \"q\"), index=0>,), cargs=(<Clbit register=(3, \"c\"), index=0>,)),\n",
              " DAGOpNode(op=Instruction(name='if_else', num_qubits=1, num_clbits=3, params=[<qiskit.circuit.quantumcircuit.QuantumCircuit object at 0x7f0a4e275490>, None]), qargs=(<Qubit register=(3, \"q\"), index=1>,), cargs=(<Clbit register=(3, \"c\"), index=0>, <Clbit register=(3, \"c\"), index=1>, <Clbit register=(3, \"c\"), index=2>))]"
            ]
          },
          "execution_count": 3,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "dag.op_nodes()"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "8f2676b9",
      "metadata": {},
      "source": [
        "Each node is an instance of the `DAGOpNode` class:\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "id": "5866159f",
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "node name: if_else\n",
            "op: Instruction(name='if_else', num_qubits=1, num_clbits=3, params=[<qiskit.circuit.quantumcircuit.QuantumCircuit object at 0x7f0a4e1b0650>, None])\n",
            "qargs: (<Qubit register=(3, \"q\"), index=1>,)\n",
            "cargs: (<Clbit register=(3, \"c\"), index=0>, <Clbit register=(3, \"c\"), index=1>, <Clbit register=(3, \"c\"), index=2>)\n",
            "condition: (ClassicalRegister(3, 'c'), 2)\n"
          ]
        }
      ],
      "source": [
        "node = dag.op_nodes()[3]\n",
        "print(\"node name:\", node.name)\n",
        "print(\"op:\", node.op)\n",
        "print(\"qargs:\", node.qargs)\n",
        "print(\"cargs:\", node.cargs)\n",
        "print(\"condition:\", node.op.condition)"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "f2560cc1",
      "metadata": {},
      "source": [
        "## Add an operation to the back\n",
        "\n",
        "An operation is added to the end of the DAGCircuit using the `apply_operation_back()` method. This appends the specified gate to act on the given qubits after all existing operations in the circuit.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "id": "3c144b49",
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "<Image src=\"/docs/images/guides/DAG-representation/extracted-outputs/3c144b49-0.avif\" alt=\"Output of the previous code cell\" />"
            ]
          },
          "execution_count": 5,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "from qiskit.circuit.library import HGate\n",
        "\n",
        "dag.apply_operation_back(HGate(), qargs=[q[0]])\n",
        "dag_drawer(dag)"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "80af1d3d",
      "metadata": {},
      "source": [
        "## Add an Operation to the Front\n",
        "\n",
        "An operation is added to the beginning of the DAGCircuit using the `apply_operation_front()` method. This inserts the specified gate before all existing operations in the circuit, effectively making it the first operation executed.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 6,
      "id": "ed80a69f",
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "<Image src=\"/docs/images/guides/DAG-representation/extracted-outputs/ed80a69f-0.avif\" alt=\"Output of the previous code cell\" />"
            ]
          },
          "execution_count": 6,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "from qiskit.circuit.library import CCXGate\n",
        "\n",
        "dag.apply_operation_front(CCXGate(), qargs=[q[0], q[1], q[2]])\n",
        "dag_drawer(dag)"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "4bcdf5fe",
      "metadata": {},
      "source": [
        "## Substitute a node with a subcircuit\n",
        "\n",
        "A node representing a specific operation in the DAGCircuit is replaced with a subcircuit. First, a new sub-DAG is constructed with the desired sequence of gates, then the target node is substituted by this sub-DAG using `substitute_node_with_dag()`, preserving the connections to the rest of the circuit.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 7,
      "id": "fdb3dd70",
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "<Image src=\"/docs/images/guides/DAG-representation/extracted-outputs/fdb3dd70-0.avif\" alt=\"Output of the previous code cell\" />"
            ]
          },
          "execution_count": 7,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "from qiskit.dagcircuit import DAGCircuit\n",
        "from qiskit.circuit.library import CHGate, U2Gate, CXGate\n",
        "\n",
        "# Build sub-DAG\n",
        "mini_dag = DAGCircuit()\n",
        "p = QuantumRegister(2, \"p\")\n",
        "mini_dag.add_qreg(p)\n",
        "mini_dag.apply_operation_back(CHGate(), qargs=[p[1], p[0]])\n",
        "mini_dag.apply_operation_back(U2Gate(0.1, 0.2), qargs=[p[1]])\n",
        "\n",
        "# Replace CX with mini_dag\n",
        "cx_node = dag.op_nodes(op=CXGate).pop()\n",
        "dag.substitute_node_with_dag(cx_node, mini_dag, wires=[p[0], p[1]])\n",
        "dag_drawer(dag)"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "028566f7",
      "metadata": {},
      "source": [
        "After all transformations are completed, the DAG can be converted back into a regular `QuantumCircuit` object. This is how the transpiler pipeline operates. A circuit is taken, processed in DAG form, and a transformed circuit is produced as output.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 8,
      "id": "786571f7",
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "<Image src=\"/docs/images/guides/DAG-representation/extracted-outputs/786571f7-0.svg\" alt=\"Output of the previous code cell\" />"
            ]
          },
          "execution_count": 8,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "from qiskit.converters import dag_to_circuit\n",
        "\n",
        "new_circ = dag_to_circuit(dag)\n",
        "circuit_drawer(new_circ, output=\"mpl\")"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "f743bb3b",
      "metadata": {},
      "source": [
        "## Implement a BasicMapper pass\n",
        "\n",
        "The DAG structure can be leveraged for writing transpiler passes. In the example below, a `BasicMapper` pass is implemented to map an arbitrary circuit onto a device with restricted qubit connectivity. For additional guidance, refer to the guide on [writing custom transpiler passes](/docs/guides/custom-transpiler-pass).\n",
        "\n",
        "The pass is defined as a `TransformationPass`, meaning that it modifies the circuit. It does so by traversing the DAG layer-by-layer, checking whether each instruction satisfies the constraints imposed by the device's coupling map. If a violation is detected, a swap path is determined and the necessary SWAP gates are inserted accordingly.\n",
        "\n",
        "When creating a transpiler pass, the first decision involves selecting whether the pass should inherit from `TransformationPass` or `AnalysisPass`. Transformation passes are designed to modify the circuit, whereas analysis passes are intended only to extract information for use by subsequent passes. The main functionality is then implemented in the `run(dag)` method. Finally, the pass should be registered within the `qiskit.transpiler.passes` module.\n",
        "\n",
        "In this specific pass, the DAG is traversed layer-by-layer (where each layer contains operations that act on disjoint sets of qubits and can thus be executed independently). For each operation, if the coupling map constraints are not met, a suitable swap path is identified, and the required swaps are inserted to bring the involved qubits into adjacency.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 9,
      "id": "8c0d7e5a",
      "metadata": {},
      "outputs": [],
      "source": [
        "from qiskit.transpiler.basepasses import TransformationPass\n",
        "from qiskit.transpiler import Layout\n",
        "from qiskit.circuit.library import SwapGate\n",
        "\n",
        "\n",
        "class BasicSwap(TransformationPass):\n",
        "    def __init__(self, coupling_map, initial_layout=None):\n",
        "        super().__init__()\n",
        "        self.coupling_map = coupling_map\n",
        "        self.initial_layout = initial_layout\n",
        "\n",
        "    def run(self, dag):\n",
        "        new_dag = DAGCircuit()\n",
        "        for qreg in dag.qregs.values():\n",
        "            new_dag.add_qreg(qreg)\n",
        "        for creg in dag.cregs.values():\n",
        "            new_dag.add_creg(creg)\n",
        "\n",
        "        if self.initial_layout is None:\n",
        "            self.initial_layout = Layout.generate_trivial_layout(\n",
        "                *dag.qregs.values()\n",
        "            )\n",
        "\n",
        "        current_layout = self.initial_layout.copy()\n",
        "\n",
        "        for layer in dag.serial_layers():\n",
        "            subdag = layer[\"graph\"]\n",
        "            for gate in subdag.two_qubit_ops():\n",
        "                q0, q1 = gate.qargs\n",
        "                p0 = current_layout[q0]\n",
        "                p1 = current_layout[q1]\n",
        "\n",
        "                if self.coupling_map.distance(p0, p1) != 1:\n",
        "                    path = self.coupling_map.shortest_undirected_path(p0, p1)\n",
        "                    for i in range(len(path) - 2):\n",
        "                        wire1, wire2 = path[i], path[i + 1]\n",
        "                        qubit1 = current_layout[wire1]\n",
        "                        qubit2 = current_layout[wire2]\n",
        "                        new_dag.apply_operation_back(\n",
        "                            SwapGate(), qargs=[qubit1, qubit2]\n",
        "                        )\n",
        "                        current_layout.swap(wire1, wire2)\n",
        "\n",
        "            new_dag.compose(\n",
        "                subdag, qubits=current_layout.reorder_bits(new_dag.qubits)\n",
        "            )\n",
        "\n",
        "        return new_dag"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "4a95eaab",
      "metadata": {},
      "source": [
        "The pass can now be tested on a small example circuit. A pass manager is constructed with the newly defined pass included. The example circuit is then provided to this pass manager, and a new, transformed circuit is obtained as the output.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 10,
      "id": "2f35375f",
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "<Image src=\"/docs/images/guides/DAG-representation/extracted-outputs/2f35375f-0.svg\" alt=\"Output of the previous code cell\" />"
            ]
          },
          "execution_count": 10,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "from qiskit.transpiler import CouplingMap, PassManager\n",
        "from qiskit import QuantumRegister, QuantumCircuit\n",
        "\n",
        "q = QuantumRegister(7, \"q\")\n",
        "in_circ = QuantumCircuit(q)\n",
        "in_circ.h(q[0])\n",
        "in_circ.cx(q[0], q[4])\n",
        "in_circ.cx(q[2], q[3])\n",
        "in_circ.cx(q[6], q[1])\n",
        "in_circ.cx(q[5], q[0])\n",
        "in_circ.rz(0.1, q[2])\n",
        "in_circ.cx(q[5], q[0])\n",
        "\n",
        "coupling = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 6]]\n",
        "coupling_map = CouplingMap(couplinglist=coupling)\n",
        "\n",
        "pm = PassManager()\n",
        "pm.append(BasicSwap(coupling_map))\n",
        "\n",
        "out_circ = pm.run(in_circ)\n",
        "\n",
        "in_circ.draw(output=\"mpl\")\n",
        "out_circ.draw(output=\"mpl\")"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "56b80ce3",
      "metadata": {},
      "source": [
        "## Next steps\n",
        "\n",
        "<Admonition type=\"tip\" title=\"Recommendations\">\n",
        "  * Review the guide on creating a [custom transpiler pass](/docs/guides/custom-transpiler-pass)\n",
        "  * Learn how to [Create and transpile against custom backends](/docs/guides/custom-backend)\n",
        "  * Try the [Compare transpiler settings](/docs/guides/circuit-transpilation-settings) guide.\n",
        "  * Review the [DAG Circuit API documentation](/docs/api/qiskit/dagcircuit).\n",
        "</Admonition>\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "id": "a1b8767d",
      "source": "© IBM Corp., 2017-2026"
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "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"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 5
}