Implement SWAP gate disentangling at compile time

[paul0403]

Context

In quantum circuits, sometimes CNOT gates are not necessary, or can be decomposed into two single-wire gates. For example, if we know that the control wire is in state |1>, then the CNOT is unnecessary, and can be replaced by a single PauliX gate on the target wire.

An interesting paper that lists these optimizations is Relaxed Peephole Optimization: A Novel Compiler Optimization for Quantum Circuits, by Ji Liu, Luciano Bello, and Huiyang Zhou (here and after known as "the paper"). In table 1 (page 5) of the paper, a transformation table for CNOT gate is listed. Note that the paper uses the symbol "T" for a general state that is not one of the six Pauli eigenstates.

To use the table and perform the transformation at compile time, we would need to gather quantum state information at compile time. In other words, we need to infer the states at the input to the CNOT gate at compile time, without actually running the circuit.

This is actually easily doable, because we know the effects of various gates on various states. For example, we know that |0> going into a Hadamard gate turns into |+>, |1> going into a PauliX turns into |0>, etc. In other words, the state propagation can be done via a simple finite state machine. This is demonstrated by figure 5 (page 6) in the paper.

In #1154, the finite state machine and the CNOT decomposition table was implemented.

Goal

In table 6 (page 13) of the paper, a similar decomposition table for SWAP gate is presented. We would like to implement the SWAP table as well.

Requirements:

• Similar to the DisentangleCNOTPass in Create a finite state machine analysis pass to propagate Pauli basis states, and use it to disentangle CNOTs #1154, we would like a DisentangleSWAPPass.
• In Catalyst mlir, when the inputs to a SWAP gate is known to be one of the special configurations in the table, the pass should replace the SWAP gate by the corresponding subcircuit in the table entry.
• For other inputs to a SWAP gate, the pass should do nothing.

Note that there is a non standard gate notation in table 6 of the paper. It is defined in equation (3), on page 4.

Technical details

1. Catalyst has its own mlir quantum dialect. The operation definitions are in QuantumOps.td. The operation of particular interest to us is the CustomOp, which corresponds to a general named gate, with the name being stored as a string. See the tests in Create a finite state machine analysis pass to propagate Pauli basis states, and use it to disentangle CNOTs #1154 for some example Catalyst mlir snippets, and how circuits are represented.

2. We currently already have the finite state machine implemented in Create a finite state machine analysis pass to propagate Pauli basis states, and use it to disentangle CNOTs #1154, and the fsm is already used by the CNOT disentangling pass. You can consult them for the intended usage, alongside how to register a new pass.

3. To compile your pass, run make dialects from the top-level catalyst directory. This will build all passes in Catalyst and run all filecheck tests in mlir/test.

You can also invoke individual passes on an arbitrary input mlir file with catalyst/mlir/build/bin/quantum-opt, and use it like the standard mlir opt. At the top of each mlir test file, you can see how each pass is invoked.

You can use quantum-opt --help to see all available passes.

4. You might want to see what Catalyst mlir a frontend PennyLane python program would produce. To lower frontend PennyLane python code to mlir, you can use the keep_intermediate option in qjit. See here.

5. There is no need to read the entire paper. The above context should suffice.

Installation help

Complete instructions to install Catalyst from source can be found here. Note that due to the size of the llvm-project it can take a while (~3 hrs on a personal laptop) to compile.

[IMPORTANT] As of now, #1154 is not merged into Catalyst's main branch yet. This means when following the catalyst installation guide, after cloning the Catalyst repository, you need to first checkout #1154's branch (named qstate_mlir_interpreter_fsm), then follow the guide to build Catalyst from source.

For the purposes of this assessment, it suffices to open a PR targeting #1154's branch, instead of Catalyst's main branch.

[ritu-thombre99]

I have two questions

1. I ran make test on the catalyst from #1154 locally, but I get 4 test failed errors. What do I do about these?

2. Should I open a PR targeting to merge into #1154 or the main branch?

[paul0403]

Hi @ritu-thombre99 !

1. I ran make test on the catalyst from #1154 locally, but I get 4 test failed errors. What do I do about these?

You can safely ignore them. As the issue lies entirely in the mlir layer, you can use the quantum-opt tool like described in the issue, and does not need to go through the python frontend.

2. Should I open a PR targeting to merge into #1154 or the main branch?

Let's target the branch in #1154 , since the main branch does not have the fsm analysis.

[ritu-thombre99]

Hi,

I implemented a few cases of disentangling SWAP (when both qubits of SWAP are equal, in that case SWAP is removed and no further action is taken).

But it's only working for |0> and |0>, I get the following error in PropagateStateAnalysisPass when comparing the values of qubits to basis states (i.e. working when in |0>, but error when in |1>,|+>,|->)

Please let me know how this can be resolved, so I can proceed further.

Should I also submit a separate bug report?

[ritu-thombre99]

I also tried adding LLVM_SYMBOLIZER_PATH as a PATH but it didn't work

[paul0403]

Can you open a PR? Just so I can see your code and test case.

Looking at the error message, I have a theory as to what's happening, but I would need to check the code to make sure. I think after the first SWAP transformation, the propagate state analysis is not being run again, which means the second SWAP transformation has qubit values that are not in the map.

[ritu-thombre99]

#1297

I'm yet to add the tests. Currently, checking the code on external .mlir files using catalyst-cli