{"cells":[{"cell_type":"markdown","metadata":{},"source":["# Qubit mapping and routing\n","\n","**Download this notebook - {nb-download}`mapping_example.ipynb`**"]},{"cell_type":"markdown","metadata":{},"source":["In this tutorial we will show how the problem of mapping from logical quantum circuits to physically permitted circuits is solved automatically in TKET. The basic examples require only the installation of pytket, ```pip install pytket```."]},{"cell_type":"markdown","metadata":{},"source":["There is a wide variety of different blueprints for realising quantum computers, including the well known superconducting and ion trap devices. Different devices come with different constraints, such as a limited primitive gate set for universal quantum computing. Often this limited gate set accommodates an additional constraint, that two-qubit gates can not be executed between all pairs of qubits."]},{"cell_type":"markdown","metadata":{},"source":["In software, typically this constraint is presented as a \"connectivity\" graph where vertices connected by an edge represents pairs of physical qubits which two-qubit gates can be executed on. As programmers usually write logical quantum circuits with no sense of architecture (or may want to run their circuit on a range of hardware with different connectivity constraints), most quantum software development kits offer the means to automatically solve this constraint. One common way is to automatically add logical ```SWAP``` gates to a Circuit, changing the position of logical qubits on physical qubits until a two-qubit gate can be realised. This is an active area of research in quantum computing and a problem we discuss in our paper \"On The Qubit Routing Problem\" - arXiv:1902.08091."]},{"cell_type":"markdown","metadata":{},"source":["In TKET this constraint is represented by the ```Architecture``` class. An Architecture object requires a coupling map to be created, a list of pairs of qubits which defines where two-qubit primitives may be executed. A coupling map can be produced naively by the integer indexing of nodes and edges in some architecture."]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["from pytket.architecture import Architecture\n","from pytket.circuit import Node"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["import networkx as nx\n","from typing import List, Union, Tuple"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["def draw_graph(coupling_map: List[Union[Tuple[int, int], Tuple[Node, Node]]]):\n","    coupling_graph = nx.Graph(coupling_map)\n","    nx.draw(coupling_graph, labels={node: node for node in coupling_graph.nodes()})"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["simple_coupling_map = [(0, 1), (1, 2), (2, 3)]\n","simple_architecture = Architecture(simple_coupling_map)\n","draw_graph(simple_coupling_map)"]},{"cell_type":"markdown","metadata":{},"source":["Alternatively we could use the `Node` class to assign our nodes - you will see why this can be helpful later. Lets create an Architecture with an identical graph:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["node_0 = Node(\"e0\", 0)\n","node_1 = Node(\"e1\", 1)\n","node_2 = Node(\"e2\", 2)\n","node_3 = Node(\"e3\", 3)"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["id_coupling_map = [(node_0, node_1), (node_1, node_2), (node_2, node_3)]\n","id_architecture = Architecture(id_coupling_map)\n","draw_graph(id_coupling_map)"]},{"cell_type":"markdown","metadata":{},"source":["We can also create an ID with an arbitrary-dimensional index. Let us make a 2x2x2 cube:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["node_000 = Node(\"cube\", [0, 0, 0])\n","node_001 = Node(\"cube\", [0, 0, 1])\n","node_010 = Node(\"cube\", [0, 1, 0])\n","node_011 = Node(\"cube\", [0, 1, 1])\n","node_100 = Node(\"cube\", [1, 0, 0])\n","node_101 = Node(\"cube\", [1, 0, 1])\n","node_110 = Node(\"cube\", [1, 1, 0])\n","node_111 = Node(\"cube\", [1, 1, 1])"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["cube_coupling_map = [\n","    (node_000, node_001),\n","    (node_000, node_010),\n","    (node_010, node_011),\n","    (node_001, node_011),\n","    (node_000, node_100),\n","    (node_001, node_101),\n","    (node_010, node_110),\n","    (node_011, node_111),\n","    (node_100, node_101),\n","    (node_100, node_110),\n","    (node_110, node_111),\n","    (node_101, node_111),\n","]"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["cube_architecture = Architecture(cube_coupling_map)\n","draw_graph(cube_coupling_map)"]},{"cell_type":"markdown","metadata":{},"source":["To avoid that tedium though we could just use our SquareGrid Architecture:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["from pytket.architecture import SquareGrid"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["alternative_cube_architecture = SquareGrid(2, 2, 2)\n","draw_graph(alternative_cube_architecture.coupling)"]},{"cell_type":"markdown","metadata":{},"source":["The current range of quantum computers are commonly referred to as Noisy-Intermediate-Scale-Quantum devices i.e. NISQ devices. The impact of noise is a primary concern during compilation and incentivizes producing physically permitted circuits that have a minimal number of gates. For this reason benchmarking in this area is often completed by comparing the final number of two-qubit (or particularly SWAP gates) in compiled circuits."]},{"cell_type":"markdown","metadata":{},"source":["However it is important to remember that adding logical SWAP gates to minimise gate count is not the only way this constraint can be met, with large scale architecture-aware synthesis methods and fidelity aware methods amongst other approaches producing viable physically permitted circuits. It is likely that no SINGLE approach is better for all circuits, but the ability to use different approaches where best fitted will give the best results during compilation."]},{"cell_type":"markdown","metadata":{},"source":["Producing physically valid circuits is completed via the `MappingManager` class, which aims to accomodate a wide range of approaches."]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["from pytket.mapping import MappingManager"]},{"cell_type":"markdown","metadata":{},"source":["A `MappingManager` object requires an `Architecture` object at construction."]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["mapping_manager = MappingManager(id_architecture)"]},{"cell_type":"markdown","metadata":{},"source":["All mapping is done through the `MappingManager.route_circuit` method. The `MappingManager.route_circuit` method has two arguments, the first a Circuit to be routed (which is mutated), the second a `List[RoutingMethodCircuit]` object that defines how the mapping is completed."]},{"cell_type":"markdown","metadata":{},"source":["Later we will look at defining our own `RoutingMethodCircuit` objects, but initially lets consider one thats already available."]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["from pytket.mapping import LexiLabellingMethod, LexiRouteRoutingMethod"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["lexi_label = LexiLabellingMethod()\n","lexi_route = LexiRouteRoutingMethod(10)"]},{"cell_type":"markdown","metadata":{},"source":["The `lexi_route` object here is of little use outside `MappingManager`. Note that it takes a lookahead parameter, which will affect the performance of the method, defining the number of two-qubit gates it considers when finding `SWAP` gates to add."]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["from pytket import Circuit, OpType\n","from pytket.circuit import display"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["c = (\n","    Circuit(4)\n","    .CX(0, 1)\n","    .CX(1, 2)\n","    .CX(0, 2)\n","    .CX(0, 3)\n","    .CX(2, 3)\n","    .CX(1, 3)\n","    .CX(0, 1)\n","    .measure_all()\n",")\n","display.render_circuit_jupyter(c)"]},{"cell_type":"markdown","metadata":{},"source":["We can also look at which logical qubits are interacting."]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["from pytket.utils import Graph"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["Graph(c).get_qubit_graph()"]},{"cell_type":"markdown","metadata":{},"source":["By running the `MappingManager.route_circuit` method on our circuit `c` with the `LexiLabellingMethod` and `LexiRouteRoutingMethod` objects as an argument, qubits in `c` with some physical requirements will be relabelled and the qubit graph modified (by the addition of SWAP gates and relabelling some CX as BRIDGE gates) such that the qubit graph is isomorphic to some subgraph of the full architecture."]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["mapping_manager.route_circuit(c, [lexi_label, lexi_route])\n","display.render_circuit_jupyter(c)"]},{"cell_type":"markdown","metadata":{},"source":["The graph:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["Graph(c).get_qubit_graph()"]},{"cell_type":"markdown","metadata":{},"source":["The resulting circuit may also change if we reduce the lookahead parameter."]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["c = (\n","    Circuit(4)\n","    .CX(0, 1)\n","    .CX(1, 2)\n","    .CX(0, 2)\n","    .CX(0, 3)\n","    .CX(2, 3)\n","    .CX(1, 3)\n","    .CX(0, 1)\n","    .measure_all()\n",")\n","mapping_manager.route_circuit(c, [lexi_label, LexiRouteRoutingMethod(1)])\n","display.render_circuit_jupyter(c)"]},{"cell_type":"markdown","metadata":{},"source":["We can also pass multiple `RoutingMethod` options for Routing in a ranked List. Each `RoutingMethod` option has a function for checking whether it can usefully modify a subcircuit at a stage in Routing. To choose, each method in the List is checked in order until one returns True. This will be discussed more later."]},{"cell_type":"markdown","metadata":{},"source":["We can aid the mapping procedure by relabelling qubits in advance. This can be completed using the `Placement` class."]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["from pytket.placement import Placement, LinePlacement, GraphPlacement"]},{"cell_type":"markdown","metadata":{},"source":["The default ```Placement``` assigns logical qubits to physical qubits as they are encountered during routing. ```LinePlacement``` uses a strategy described in https://arxiv.org/abs/1902.08091. ```GraphPlacement``` is described in Section 7.1 of https://arxiv.org/abs/2003.10611. Lets look at how we can use the ```LinePlacement``` class.`"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["line_placement = LinePlacement(id_architecture)"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["c = (\n","    Circuit(4)\n","    .CX(0, 1)\n","    .CX(1, 2)\n","    .CX(0, 2)\n","    .CX(0, 3)\n","    .CX(2, 3)\n","    .CX(1, 3)\n","    .CX(0, 1)\n","    .measure_all()\n",")\n","line_placement.place(c)"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["display.render_circuit_jupyter(c)"]},{"cell_type":"markdown","metadata":{},"source":["Note that one qubit remains unplaced in this example. `LexiRouteRoutingMethod` will dynamically assign it during mapping."]},{"cell_type":"markdown","metadata":{},"source":["Different placements will lead to different selections of SWAP gates being added. However each different routed circuit will preserve the original unitary action of the full circuit while respecting connectivity constraints."]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["mapping_manager.route_circuit(c, [lexi_label, lexi_route])\n","display.render_circuit_jupyter(c)"]},{"cell_type":"markdown","metadata":{},"source":["The graph:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["Graph(c).get_qubit_graph()"]},{"cell_type":"markdown","metadata":{},"source":["However, small changes to the depth of lookahead or the original assignment of `Architecture` `Node` can greatly affect the resulting physical circuit for the `LexiRouteRoutingMethod` method. Considering this variance, it should be possible to easily throw additional computational resources at the problem if necessary, which is something TKET is leaning towards with the ability to define custom `RoutingCircuitMethod` objects."]},{"cell_type":"markdown","metadata":{},"source":["To define a new `RoutingMethodCircuit` method though, we first need to understand how it is used in `MappingManager` and routing. The `MappingManager.route_circuit` method treats the global problem of mapping to physical circuits as many sequential sub-problems. Consider the following problem."]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["from pytket import Circuit"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["from pytket.placement import place_with_map"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["circ = Circuit(4).CX(0, 1).CX(1, 2).CX(0, 2).CX(0, 3).CX(2, 3).CX(1, 3).CX(0, 1)\n","naive_map = {\n","    circ.qubits[0]: node_0,\n","    circ.qubits[1]: node_1,\n","    circ.qubits[2]: node_2,\n","    circ.qubits[3]: node_3,\n","}\n","place_with_map(circ, naive_map)\n","Graph(circ).get_DAG()"]},{"cell_type":"markdown","metadata":{},"source":["So what happens when we run the following?"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["mapping_manager.route_circuit(circ, [lexi_route])\n","Graph(circ).get_DAG()"]},{"cell_type":"markdown","metadata":{},"source":["Sequential mapping typically works by partitioning the circuit into two, a first partition comprising a connected subcircuit that is physically permitted, a second partition that is not. Therefore, the first thing `MappingManager.route_circuit` does is find this partition for the passed circuit, by iterating through gates in the circuit."]},{"cell_type":"markdown","metadata":{},"source":["We will construct the partitions ourselves for illustrative purposes. Lets assume we are routing for the four qubit line architecture (qubits are connected to adjacent indices) \"simple_architecture\" we constructed earlier."]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["circ_first_partition = Circuit(4).CX(0, 1).CX(1, 2)\n","place_with_map(circ_first_partition, naive_map)\n","Graph(circ_first_partition).get_DAG()"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["circ_second_partition = Circuit(4).CX(0, 2).CX(0, 3).CX(2, 3).CX(1, 3).CX(0, 1)\n","place_with_map(circ_second_partition, naive_map)\n","Graph(circ_second_partition).get_DAG()"]},{"cell_type":"markdown","metadata":{},"source":["Note that there are gates in the second partition that would be physically permitted, if they were not dependent on other gates that are not."]},{"cell_type":"markdown","metadata":{},"source":["The next step is to modify the second partition circuit to move it closer being physically permitted. Here the `LexiRouteRoutingMethod` as before will either insert a SWAP gate at the start of the partition, or will substitute a CX gate in the first slice of the partition with a BRIDGE gate."]},{"cell_type":"markdown","metadata":{},"source":["The option taken by `LexiRouteRoutingethod(1)` is to insert a SWAP gate between the first two nodes of the architecture, swapping their logical states. How does this change the second partition circuit?"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["circ_second_partition = (\n","    Circuit(4).SWAP(0, 1).CX(1, 2).CX(1, 3).CX(2, 3).CX(0, 3).CX(1, 0)\n",")\n","place_with_map(circ_second_partition, naive_map)\n","Graph(circ_second_partition).get_DAG()"]},{"cell_type":"markdown","metadata":{},"source":["Leaving the full circuit as:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["full_circuit = (\n","    Circuit(4).CX(0, 1).CX(1, 2).SWAP(0, 1).CX(1, 2).CX(1, 3).CX(2, 3).CX(0, 3).CX(1, 0)\n",")\n","place_with_map(full_circuit, naive_map)\n","Graph(full_circuit).get_DAG()"]},{"cell_type":"markdown","metadata":{},"source":["After a modification is made the partition is updated."]},{"cell_type":"markdown","metadata":{},"source":["The first partition:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["circ_first_partition = Circuit(4).CX(0, 1).CX(1, 2).SWAP(0, 1).CX(1, 2)\n","place_with_map(circ_first_partition, naive_map)\n","Graph(circ_first_partition).get_DAG()"]},{"cell_type":"markdown","metadata":{},"source":["The second partition:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["circ_second_partition = Circuit(4).CX(1, 3).CX(2, 3).CX(0, 3).CX(1, 0)\n","place_with_map(circ_second_partition, naive_map)\n","Graph(circ_second_partition).get_DAG()"]},{"cell_type":"markdown","metadata":{},"source":["This pattern of modification and upating the partition is repeated until the partition has reached the end of the circuit, i.e.  the back side of the partition has no gates in it. Also note that the process of updating the partition has been simplified for this example with \"physically permitted\" encapsulating two-qubit gate constraints only - in the future we expect other arity gates to provide constraints that need to be met. Also note that any modification to the second circuit can willfully modify the qubit labelling and a token swapping network will be automatically added to conform to the new labelling."]},{"cell_type":"markdown","metadata":{},"source":["We now enough about how `MappingManager` works to add our own `RoutingMethodCircuit`. While `LexiRouteRoutingMethod` is implemented in c++ TKET, giving it some advantages, via lambda functions we can define our own `RoutingMethodCircuit` in python."]},{"cell_type":"markdown","metadata":{},"source":["A python defined `RoutingMethodCircuit` requires three arguments. The first is a function that given a Circuit (the circuit after the partition) and an Architecture, returns a bool (determining whether the new circuit should be substitued in a full routing process), a new Circuit (a modification of the original circuit such as an added SWAP) a Dict between qubits reflecting any relabelling done in the method, and a Dict between qubits giving any implicit permutation of qubits (such as by adding a SWAP). For some clarity (we will write an example later), lets look at an example function declaration."]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["from typing import Dict"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["def route_subcircuit_func(\n","    circuit: Circuit, architecture: Architecture\n",") -> Tuple[bool, Circuit, Dict[Node, Node], Dict[Node, Node]]:\n","    return ()"]},{"cell_type":"markdown","metadata":{},"source":["The first return is a bool which detemrines if a given `RoutingMethodCircuit` is suitable for providing a solution at a given partition. `MappingManager.route_circuit` accepts a List of of `RoutingMethod` defining how solutions are found. At the point the partition circuit is modified, the circuit is passed to `RoutingMethodCircuit.routing_method` which additionally to finding a subcircuit substitution, should determine whether it can or can't helpfully modify the partition boundary circuit, and return True if it can. The first `RoutingMethodCircuit` to return True is then used for modification - meaning the ordering of List elements is important."]},{"cell_type":"markdown","metadata":{},"source":["The third argument sets the maximum number of gates given in the passed Circuit and the fourth argument sets the maximum depth in the passed Circuit."]},{"cell_type":"markdown","metadata":{},"source":["`LexiRouteRoutingMethod` will always return True, because it can always find some helpful SWAP to insert, and it can dynamically assign logical to physical qubits. Given this, lets construct a more specialised modification - an architecture-aware decomposition of a distance-2 CRy gate. Lets write our function type declarations for each method:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["def distance2_CRy_decomp(\n","    circuit: Circuit, architecture: Architecture\n",") -> Tuple[bool, Circuit, Dict[Node, Node], Dict[Node, Node]]:\n","    return (False, Circuit(), {}, {})"]},{"cell_type":"markdown","metadata":{},"source":["Where do we start? Lets define a simple scope for our solution: for a single gate in the passed circuit (the circuit after the partition) that has OpType CRy, if the two qubits it's acting on are at distance 2 on the architecture, decompose the gate using BRIDGE gates."]},{"cell_type":"markdown","metadata":{},"source":["The first restriction is to only have a single gate from the first slice - we can achieve this by setting both the maximum depth and size parameters to 1."]},{"cell_type":"markdown","metadata":{},"source":["The second restriction is for the gate to have OpType CRy and for the qubits to be at distance 2 - we can check this restriction in a `distance2_CRy_check` method."]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["def distance2_CRy_check(circuit: Circuit, architecture: Architecture) -> bool:\n","    if circuit.n_gates != 1:\n","        raise ValueError(\n","            \"Circuit for CRy check should only have 1 gate, please change parameters of method declaration.\"\n","        )\n","    command = circuit.get_commands()[0]\n","    if command.op.type == OpType.CRy:\n","        # Architecture stores qubits under `Node` identifier\n","        n0 = Node(command.qubits[0].reg_name, command.qubits[0].index)\n","        n1 = Node(command.qubits[1].reg_name, command.qubits[1].index)\n","        # qubits could not be placed in circuit, so check before finding distance\n","        if n0 in architecture.nodes and n1 in architecture.nodes:\n","            # means we can run the decomposition\n","            if architecture.get_distance(n0, n1) == 2:\n","                return True\n","    return False"]},{"cell_type":"markdown","metadata":{},"source":["The `distance2_CRy_check` confirms whether the required restrictions are respected. Given this, if the `distance2_CRy_decomp` method is called we know where to add the decomposition."]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["def distance2_CRy_decomp(\n","    circuit: Circuit, architecture: Architecture\n",") -> Tuple[bool, Circuit, Dict[Node, Node], Dict[Node, Node]]:\n","    worthwhile_substitution = distance2_CRy_check(circuit, architecture)\n","    if worthwhile_substitution == False:\n","        return (False, Circuit(), {}, {})\n","    command = circuit.get_commands()[0]\n","    qubits = command.qubits\n","    # Architecture stores qubits under `Node` identifier\n","    n0 = Node(qubits[0].reg_name, qubits[0].index)\n","    n1 = Node(qubits[1].reg_name, qubits[1].index)\n","\n","    # need to find connecting node for decomposition\n","    adjacent_nodes_0 = architecture.get_adjacent_nodes(n0)\n","    adjacent_nodes_1 = architecture.get_adjacent_nodes(n1)\n","    connecting_nodes = adjacent_nodes_0.intersection(adjacent_nodes_1)\n","    if len(connecting_nodes) == 0:\n","        raise ValueError(\"Qubits for distance-2 CRy decomp are not at distance 2.\")\n","    connecting_node = connecting_nodes.pop()\n","    c = Circuit()\n","\n","    # the \"relabelling map\" empty, and the permutation map is qubit to qubit, so add here\n","    permutation_map = dict()\n","    for q in circuit.qubits:\n","        permutation_map[q] = q\n","        c.add_qubit(q)\n","    # rotation, can assume only parameter as CRy\n","    angle = command.op.params[0]\n","    c.Ry(angle, qubits[1])\n","    # distance-2 CX decomp\n","    c.CX(qubits[0], connecting_node).CX(connecting_node, qubits[1])\n","    c.CX(qubits[0], connecting_node).CX(connecting_node, qubits[1])\n","    # rotation\n","    c.Ry(-1 * angle, qubits[1])\n","    # distance-2 CX decomp\n","    c.CX(qubits[0], connecting_node).CX(connecting_node, qubits[1])\n","    c.CX(qubits[0], connecting_node).CX(connecting_node, qubits[1])\n","\n","    # the \"relabelling map\" is just qubit to qubit\n","    return (True, c, {}, permutation_map)"]},{"cell_type":"markdown","metadata":{},"source":["Before turning this into a `RoutingMethod` we can try it ourselves."]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["test_c = Circuit(4)\n","test_c.CRy(0.6, 0, 2)\n","place_with_map(test_c, naive_map)\n","Graph(test_c).get_DAG()"]},{"cell_type":"markdown","metadata":{},"source":["As we can see, our circuit has one CRy gate at distance two away."]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["print(distance2_CRy_check(test_c, id_architecture))"]},{"cell_type":"markdown","metadata":{},"source":["Our method returns True, as expected! We should also test cases where it returns errors or False."]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["test_c_false = Circuit(4)\n","test_c_false.CRy(0.4, 0, 1)\n","place_with_map(test_c_false, naive_map)\n","print(distance2_CRy_check(test_c_false, id_architecture))"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["test_c_error = Circuit(4)\n","test_c_error.CRy(0.6, 0, 2)\n","test_c_error.CRy(0.4, 0, 1)\n","place_with_map(test_c_error, naive_map)\n","try:\n","    distance2_CRy_check(test_c_error, id_architecture)\n","except ValueError:\n","    print(\"Error reached!\")"]},{"cell_type":"markdown","metadata":{},"source":["Does the decomposition work?"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["test_c = Circuit(4)\n","test_c.CRy(0.6, 0, 2)\n","place_with_map(test_c, naive_map)\n","decomp = distance2_CRy_decomp(test_c, id_architecture)\n","display.render_circuit_jupyter(decomp[1])"]},{"cell_type":"markdown","metadata":{},"source":["Great! Our check function and decomposition method are both working. Lets wrap them into a `RoutingMethodCircuit` and try them out."]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["from pytket.mapping import RoutingMethodCircuit"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["cry_rmc = RoutingMethodCircuit(distance2_CRy_decomp, 1, 1)"]},{"cell_type":"markdown","metadata":{},"source":["We can use our original `MappingManager` object as it is defined for the same architecture. Lets try it out on a range of circumstances."]},{"cell_type":"markdown","metadata":{},"source":["If we pass it a full CX circuit without `LexiRouteRoutingMethod`, we should find that `MappingManager` throws an error, as none of the passed methods can route for the given circuit."]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["c = (\n","    Circuit(4)\n","    .CX(0, 1)\n","    .CX(1, 2)\n","    .CX(0, 2)\n","    .CX(0, 3)\n","    .CX(2, 3)\n","    .CX(1, 3)\n","    .CX(0, 1)\n","    .measure_all()\n",")\n","place_with_map(c, naive_map)\n","try:\n","    mapping_manager.route_circuit(c, [cry_rmc])\n","except RuntimeError:\n","    print(\"Error reached!\")"]},{"cell_type":"markdown","metadata":{},"source":["Alternatively, we can add `LexiRouteRoutingMethod` on top:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["c = (\n","    Circuit(4)\n","    .CX(0, 1)\n","    .CX(1, 2)\n","    .CX(0, 2)\n","    .CX(0, 3)\n","    .CX(2, 3)\n","    .CX(1, 3)\n","    .CX(0, 1)\n","    .measure_all()\n",")\n","place_with_map(c, naive_map)\n","mapping_manager.route_circuit(c, [cry_rmc, LexiRouteRoutingMethod(10)])\n","display.render_circuit_jupyter(c)"]},{"cell_type":"markdown","metadata":{},"source":["However as there are no CRy gates our new method is unused. We can add one:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["c = (\n","    Circuit(4)\n","    .CRy(0.6, 0, 2)\n","    .CX(0, 1)\n","    .CX(1, 2)\n","    .CX(0, 2)\n","    .CX(0, 3)\n","    .CX(2, 3)\n","    .CX(1, 3)\n","    .CX(0, 1)\n","    .measure_all()\n",")\n","mapping_manager.route_circuit(c, [lexi_label, cry_rmc, LexiRouteRoutingMethod(10)])\n","display.render_circuit_jupyter(c)"]},{"cell_type":"markdown","metadata":{},"source":["This time we can see our decomposition! If we reorder the methods though `LexiRouteRoutingMethod` is checked first (and returns True), so our new method is unused. The order is important!"]},{"cell_type":"markdown","metadata":{},"source":["Finally, lets see what happens if the gate is not at the right distance initially."]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["c = (\n","    Circuit(4)\n","    .CRy(0.6, 0, 3)\n","    .CX(0, 1)\n","    .CX(1, 2)\n","    .CX(0, 2)\n","    .CX(0, 3)\n","    .CX(2, 3)\n","    .CX(1, 3)\n","    .CX(0, 1)\n","    .measure_all()\n",")\n","mapping_manager.route_circuit(c, [lexi_label, cry_rmc, LexiRouteRoutingMethod(10)])\n","display.render_circuit_jupyter(c)"]},{"cell_type":"markdown","metadata":{},"source":["Above a SWAP gate is inserted by `LexiRouteRoutingMethod` before anything else."]},{"cell_type":"markdown","metadata":{},"source":["For anyone interested, a simple extension exercise could be to extend this to additionally work for distance-2 CRx and CRz. Alternatively one could improve on the method itself - this approach always decomposes a CRy at distance-2, but is this a good idea?"]},{"cell_type":"markdown","metadata":{},"source":["Also note that higher performance solutions are coded straight into the TKET c++ codebase. This provides advantages, including that Circuit construction and substitution is unncessary (as with python) as the circuit can be directly modified, however the ability to produce prototypes at the python level is very helpful. If you have a great python implementation but are finding some runtime bottlenecks, why not try implementing it straight into TKET (the code is open source at https://github.com/CQCL/tket)."]},{"cell_type":"markdown","metadata":{},"source":["Besides the `LexiRouteRoutingMethod()` and the `LexiLabellingMethod()` there are other routing methods in pytket, such as the `AASRouteRoutingMethod()` and the corresponding `AASLabellingMethod()`, which are used to route phase-polynomial boxes using architecture-aware synthesis. Usually circuits contain non-phase-polynomial operations as well, so it is a good idea to combine them with the `LexiRouteRoutingMethod()`, as in the following example:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["from pytket.mapping import AASRouteRoutingMethod, AASLabellingMethod\n","from pytket.circuit import PhasePolyBox, Qubit\n","import numpy as np"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["c = Circuit(3, 3)\n","n_qb = 3\n","qubit_indices = {Qubit(0): 0, Qubit(1): 1, Qubit(2): 2}\n","phase_polynomial = {(True, False, True): 0.333, (False, False, True): 0.05}\n","linear_transformation = np.array([[1, 0, 0], [0, 1, 0], [0, 0, 1]])\n","p_box = PhasePolyBox(n_qb, qubit_indices, phase_polynomial, linear_transformation)\n","c.add_phasepolybox(p_box, [0, 1, 2])\n","c.CX(0, 1).CX(0, 2).CX(1, 2)\n","display.render_circuit_jupyter(c)\n","nodes = [Node(\"test\", 0), Node(\"test\", 1), Node(\"test\", 2)]\n","arch = Architecture([[nodes[0], nodes[1]], [nodes[1], nodes[2]]])\n","mm = MappingManager(arch)\n","mm.route_circuit(\n","    c,\n","    [\n","        AASRouteRoutingMethod(1),\n","        LexiLabellingMethod(),\n","        LexiRouteRoutingMethod(),\n","        AASLabellingMethod(),\n","    ],\n",")\n","display.render_circuit_jupyter(c)"]},{"cell_type":"markdown","metadata":{},"source":["In this case the order of the methods is not very relevant, because in each step of the routing only one of the methods is suitable. In the first part of the circuit the mapping is done without inserting swaps by the AAS method; in the second part one swap gate is added to the circuit."]}],"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.6.4"}},"nbformat":4,"nbformat_minor":2}