{"cells":[{"cell_type":"markdown","metadata":{},"source":["# Compilation passes\n","\n","**Download this notebook - {nb-download}`compilation_example.ipynb`**"]},{"cell_type":"markdown","metadata":{},"source":["There are numerous ways to optimize circuits in `pytket`. In this notebook we will introduce the basics of compilation passes and how to combine and apply them.<br>\n","<br>\n","We assume familiarity with the `pytket` `Circuit` class. The objective is to transform one `Circuit` into another, equivalent, `Circuit`, that:<br>\n","* satisfies the connectivity constraints of a given architecture;<br>\n","* satisfies some further user-defined constraints (such as restricted gate sets);<br>\n","* minimizes some cost function (such as CX count)."]},{"cell_type":"markdown","metadata":{},"source":["## Passes"]},{"cell_type":"markdown","metadata":{},"source":["The basic mechanism of compilation is the 'pass', which is a transform that can be applied to a circuit. There is an extensive library of passes in `pytket`, and several standard ways in which they can be combined to form new passes. For example:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["from pytket.passes import DecomposeMultiQubitsCX"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["pass1 = DecomposeMultiQubitsCX()"]},{"cell_type":"markdown","metadata":{},"source":["This pass converts all multi-qubit gates into CX and single-qubit gates. So let's create a circuit containing some non-CX multi-qubit gates:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["from pytket.circuit import Circuit"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["circ = Circuit(3)\n","circ.CRz(0.5, 0, 1)\n","circ.T(2)\n","circ.CSWAP(2, 0, 1)"]},{"cell_type":"markdown","metadata":{},"source":["In order to apply a pass to a circuit, we must first create a `CompilationUnit` from it. We can think of this as a 'bridge' between the circuit and the pass. The `CompilationUnit` is constructed from the circuit; the pass is applied to the `CompilationUnit`; and the transformed circuit is extracted from the `CompilationUnit`:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["from pytket.predicates import CompilationUnit"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["cu = CompilationUnit(circ)\n","pass1.apply(cu)\n","circ1 = cu.circuit"]},{"cell_type":"markdown","metadata":{},"source":["Let's have a look at the result of the transformation:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["print(circ1.get_commands())"]},{"cell_type":"markdown","metadata":{},"source":["## Predicates"]},{"cell_type":"markdown","metadata":{},"source":["Every `CompilationUnit` has associated with it a set of 'predicates', which describe target properties that can be checked against the circuit. There are many types of predicates available in `pytket`. For example, the `GateSetPredicate` checks whether all gates in a circuit belong to a particular set:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["from pytket.predicates import GateSetPredicate\n","from pytket.circuit import OpType"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["pred1 = GateSetPredicate({OpType.Rz, OpType.T, OpType.Tdg, OpType.H, OpType.CX})"]},{"cell_type":"markdown","metadata":{},"source":["When we construct a `CompilationUnit`, we may pass a list of target predicates as well as the circuit:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["cu = CompilationUnit(circ, [pred1])"]},{"cell_type":"markdown","metadata":{},"source":["To check whether the circuit associated to a `CompilationUnit` satisfies its target predicates, we can call the `check_all_predicates()` method:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["cu.check_all_predicates()"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["pass1.apply(cu)\n","cu.check_all_predicates()"]},{"cell_type":"markdown","metadata":{},"source":["We can also directly check whether a given circuit satisfies a given predicate, using the predicate's `verify()` method:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["pred1.verify(circ1)"]},{"cell_type":"markdown","metadata":{},"source":["### In-place compilation"]},{"cell_type":"markdown","metadata":{},"source":["The example above produced a new circuit, leaving the original circuit untouched. It is also possible to apply a pass to a circuit in-place:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["DecomposeMultiQubitsCX().apply(circ)\n","print(circ.get_commands())"]},{"cell_type":"markdown","metadata":{},"source":["## Combining passes"]},{"cell_type":"markdown","metadata":{},"source":["There are various ways to combine the elementary passes into more complex ones.<br>\n","<br>\n","To combine several passes in sequence, we use a `SequencePass`:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["from pytket.passes import SequencePass, OptimisePhaseGadgets"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["seqpass = SequencePass([DecomposeMultiQubitsCX(), OptimisePhaseGadgets()])"]},{"cell_type":"markdown","metadata":{},"source":["This pass will apply the two transforms in succession:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["cu = CompilationUnit(circ)\n","seqpass.apply(cu)\n","circ1 = cu.circuit\n","print(circ1.get_commands())"]},{"cell_type":"markdown","metadata":{},"source":["The `apply()` method for an elementary pass returns a boolean indicating whether or not the pass had any effect on the circuit. For a `SequencePass`, the return value indicates whether _any_ of the constituent passes had some effect.<br>\n","<br>\n","A `RepeatPass` repeatedly calls `apply()` on a pass until it returns `False`, indicating that there was no effect:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["from pytket.passes import CommuteThroughMultis, RemoveRedundancies, RepeatPass"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["seqpass = SequencePass([CommuteThroughMultis(), RemoveRedundancies()])\n","reppass = RepeatPass(seqpass)"]},{"cell_type":"markdown","metadata":{},"source":["This pass will repeatedly apply `CommuteThroughMultis` (which commutes single-qubit operations through multi-qubit operations where possible towards the start of the circuit) and `RemoveRedundancies` (which cancels inverse pairs, merges coaxial rotations and removes redundant gates before measurement) until neither pass has any effect on the circuit.<br>\n","<br>\n","Let's use `pytket`'s built-in visualizer to see the effect on a circuit:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["from pytket.circuit.display import render_circuit_jupyter"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["circ = Circuit(3)\n","circ.X(0).Y(1).CX(0, 1).Z(0).Rx(1.3, 1).CX(0, 1).Rz(0.4, 0).Ry(0.53, 0).H(1).H(2).Rx(\n","    1.5, 2\n",").Rx(0.5, 2).H(2)"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["render_circuit_jupyter(circ)"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["cu = CompilationUnit(circ)\n","reppass.apply(cu)\n","circ1 = cu.circuit"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["render_circuit_jupyter(circ1)"]},{"cell_type":"markdown","metadata":{},"source":["If we want to repeat a pass until the circuit satisfies some desired property, we first define a boolean function to test for that property, and then pass this function to the constructor of a `RepeatUntilSatisfied` pass:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["from pytket.passes import RepeatUntilSatisfiedPass"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["def no_CX(circ):\n","    return circ.n_gates_of_type(OpType.CX) == 0"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["circ = (\n","    Circuit(2)\n","    .CX(0, 1)\n","    .X(1)\n","    .CX(0, 1)\n","    .X(1)\n","    .CX(0, 1)\n","    .X(1)\n","    .CX(0, 1)\n","    .Z(1)\n","    .CX(1, 0)\n","    .Z(1)\n","    .CX(1, 0)\n",")"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["custom_pass = RepeatUntilSatisfiedPass(seqpass, no_CX)\n","cu = CompilationUnit(circ)\n","custom_pass.apply(cu)\n","circ1 = cu.circuit"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["render_circuit_jupyter(circ1)"]},{"cell_type":"markdown","metadata":{},"source":["The `RepeatWithMetricPass` provides another way of generating more sophisticated passes. This is defined in terms of a cost function and another pass type; the pass is applied repeatedly until the cost function stops decreasing.<br>\n","<br>\n","For example, suppose we wish to associate a cost to each gate in out circuit, with $n$-qubit gates having a cost of $n^2$:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["def cost(circ):\n","    return sum(pow(len(x.args), 2) for x in circ)"]},{"cell_type":"markdown","metadata":{},"source":["Let's construct a new circuit:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["circ = Circuit(2)\n","circ.CX(0, 1).X(1).Y(0).CX(0, 1).X(1).Z(0).CX(0, 1).X(1).Y(0).CX(0, 1).Z(1).CX(1, 0).Z(\n","    1\n",").X(0).CX(1, 0)"]},{"cell_type":"markdown","metadata":{},"source":["We will repeatedly apply `CommuteThroughMultis`, `DecomposeMultiQubitsCX` and `RemoveRedundancies` until the `cost` function stops decreasing:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["from pytket.passes import RepeatWithMetricPass"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["pass1 = SequencePass(\n","    [CommuteThroughMultis(), DecomposeMultiQubitsCX(), RemoveRedundancies()]\n",")\n","pass2 = RepeatWithMetricPass(pass1, cost)"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["cu = CompilationUnit(circ)\n","pass2.apply(cu)\n","print(cu.circuit.get_commands())"]},{"cell_type":"markdown","metadata":{},"source":["## Targeting architectures"]},{"cell_type":"markdown","metadata":{},"source":["If we are given a target architecture, we can generate passes tailored to it.<br>\n","<br>\n","In `pytket` an architecture is defined by a connectivity graph, i.e. a list of pairs of qubits capable of executing two-qubit operations. For example, we can represent a 5-qubit linear architecture, with qubits labelled `n[i]`, as follows:"]},{"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":["n = [Node(\"n\", i) for i in range(5)]"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["arc = Architecture([[n[0], n[1]], [n[1], n[2]], [n[2], n[3]], [n[3], n[4]]])"]},{"cell_type":"markdown","metadata":{},"source":["Suppose we have a circuit that we wish to run on this architecture:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["circ = Circuit(5)\n","circ.CX(0, 1)\n","circ.H(0)\n","circ.Z(1)\n","circ.CX(0, 3)\n","circ.Rx(1.5, 3)\n","circ.CX(2, 4)\n","circ.X(2)\n","circ.CX(1, 4)\n","circ.CX(0, 4)"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["render_circuit_jupyter(circ)"]},{"cell_type":"markdown","metadata":{},"source":["A mapping pass lets us rewrite this circuit for our architecture:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["from pytket.passes import DefaultMappingPass"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["mapper = DefaultMappingPass(arc)\n","cu = CompilationUnit(circ)\n","mapper.apply(cu)\n","circ1 = cu.circuit"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["render_circuit_jupyter(circ1)"]},{"cell_type":"markdown","metadata":{},"source":["If we want to decompose all SWAP and BRIDGE gates to CX gates in the final circuit, we can use another pass:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["from pytket.passes import DecomposeSwapsToCXs"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["pass1 = DecomposeSwapsToCXs(arc)\n","pass1.apply(cu)\n","circ2 = cu.circuit"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["render_circuit_jupyter(circ2)"]},{"cell_type":"markdown","metadata":{},"source":["Note that the pass we just ran also performed some clean-up: the SWAP gate was decomposed into three CX gates, one of which was cancelled by a preceding CX gate; the cancelling gates were removed from the circuit.<br>\n","<br>\n","Every compilation pass has associated sets of preconditions and postconditions on the circuit. If all preconditions are satisfied before the pass, all postconditions are guaranteed to be satisfied afterwards. When we apply a pass to a circuit, we can optionally pass `SafetyMode.Audit` as the second parameter; this will tell the pass to check all preconditions explicitly. By default, there is only limited checking of preconditions and `pytket` relies on the programmer assuring these.<br>\n","<br>\n","For example, the `NoClassicalControl` predicate is a precondition of the `PauliSimp` pass. Let's add a classically controlled gate to our circuit:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["from pytket.passes import PauliSimp, SafetyMode\n","from pytket.circuit import Qubit, Bit"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["q = [Qubit(\"q\", i) for i in range(5)]\n","c = Bit(\"c\")\n","circ.add_bit(c)\n","circ.Measure(q[3], c)\n","circ.CY(q[0], q[1], condition_bits=[c], condition_value=1)\n","cu = CompilationUnit(circ)\n","try:\n","    PauliSimp().apply(cu, safety_mode=SafetyMode.Audit)\n","except RuntimeError as e:\n","    print(\"Error:\", str(e))"]},{"cell_type":"markdown","metadata":{},"source":["The preconditions and postconditions of all the elementary predicates are documented in their string representations:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["PauliSimp()"]},{"cell_type":"markdown","metadata":{},"source":["## Backends and default passes"]},{"cell_type":"markdown","metadata":{},"source":["A `pytket` `Backend` may have a default compilation pass, which will guarantee that the circuit can run on it. This is given by the `default_compilation_pass` property. For example, the default pass for Qiskit's `AerBackend` just converts all gates to U1, U2, U3 and CX:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["from pytket.extensions.qiskit import AerBackend"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["b = AerBackend()\n","b.default_compilation_pass"]},{"cell_type":"markdown","metadata":{},"source":["To compile a circuit using the default pass of a `Backend` we can simply use the `get_compiled_circuit()` method:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["circ = Circuit(2).X(0).Y(1).CRz(0.5, 1, 0)\n","circ1 = b.get_compiled_circuit(circ)\n","render_circuit_jupyter(circ1)"]},{"cell_type":"markdown","metadata":{},"source":["Every `Backend` will have a certain set of requirements that must be met by any circuit in order to run. These are exposed via the `required_predicates` property:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["b.required_predicates"]},{"cell_type":"markdown","metadata":{},"source":["We can test whether a given circuit satisfies these requirements using the `valid_circuit()` method:"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["b.valid_circuit(circ)"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["b.valid_circuit(circ1)"]}],"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}