Implement Quantum Gate commutation rules in Catalyst

[dime10]

Context

We would like to extend Catalyst's compiler with the ability to reorder quantum instructions according to gate commutation relations. The most common quantum instructions in Catalyst's program representation (IR) are those representing quantum operators (also called quantum logic gates, or just gates), which we describe using linear algebra. A sequence of quantum instructions corresponds to the composition of their operators. When talking about gate commutation, what we mean is the commutativity of the operators under composition. When two operators commute, we can exchange their order in the composition without affecting the result, that is we are free to reorder the corresponding instructions with respect to each other.

Goal

Concretely, we want to add a transformation to Catalyst that will reorder instructions into a canonical order whenever possible. Catalyst is built on the MLIR compiler framework, and defines a quantum dialect to represent quantum computation (more details in the next section). We'll consider the following quantum gates, listed in the chosen canonical order:

{ CNOT, RZ, PauliX }

Note that these gates do not all have the same dimensionality, that is, they don't all act on the same number of inputs (qubits).

Requirements:

• Determine the commutativity between each pair of gates from the set above.
• Implement an IR transformation that reorders gates into the canonical order when allowed by commutation rules. The transformation should be part of Catalyst's quantum dialect and use appropriate MLIR tools (you are free to chose the transformation mechanism you think is most appropriate).
• Add IR tests using FileCheck to ensure effectiveness and safety of the transformation, following best practices.

Technical details

1. Catalyst is made up of three modules, a frontend, compiler core, and runtime. You can ignore the frontend and runtime, and focus on the core compiler, in the particular the quantum mlir dialect.

2. Most quantum gates are represented by the CustomOp in the quantum dialect. The name attribute contains the conventional name of the gate, like "RZ" and "CNOT".

3. Quantum gates might have two additional kinds of input: floating parameters (not relevant for this transformation), and input and output qubits. Catalyst's IR uses SSA values to represent the quantum dataflow between operations, where the data is the "state" of qubits. Of course, the state or value of a qubit cannot easily be stored on a classical computer, so these values are really just symbolic. But they do allow us to encode the order and connectivity of quantum gates, and allows for easy traversal of operations via the SSA graph.

Installation help

Please refer to the official build from source instructions to install Catalyst on Linux or macOS. Due to the size of the LLVM project it can take a while to compile (up to a few hours, depending on hardware).