✨ MLIR - Port QMAP to MLIR

[ystade]

Problem Statement

MLIR is a convenient way to define representations of programs, i.e., quantum programs. It also allows for easy interface with other tools by defining conversions between the different representations. In the usual compilation flow, quantum circuit mapping is a crucial step to get from the algorithmic to the hardware level and to make the quantum program executable on a certain hardware. In MQT, this task is performed by QMAP. Unfortunately, QMAP uses the (old) custom representation QuantumComputation and is not compatible with the MLIR infrastructure.

Proposed Solution

A modern re-implementation of QMAP directly in the MLIR framework facilitates a conversion from a hardware-agnostic dialect like MQTDyn to a hardware-specific dialect, e.g., MQTMem that assigns algorithmic qubits to specific hardware/physical qubits. The necessary steps for the implementation of QMAP in terms of MLIR are described in further detail in the related sub-issues.

[MatthiasReumann]

Some thoughts on this issue (these sub-issues):

Dialect

Lowering to LLVM IR
The exit dialect will likely be LLVM. Do you have any thoughts on how quantum operations should be mapped to LLVM IR? These considerations might influence the definition of MQTMem.

Conversion

Prerequisites
Most mapping algorithms assume the circuit has already been decomposed into elementary gates (such as CNOT and U). For starters, we could assume that this is "done manually," but eventually, this should also be the job of the compiler. I could imagine the following custom pipeline:

MQTOpt --naive conversion--> MQTMem --decompose--> MQTMem --route--> MQTMem (--conversion--> LLVM IR)

Moreover, based on the given architecture, the routing pass might already use a decomposed, hardware-native swap gate.

Architecture Information
At some point, QDMI might aid this process. However, until then, would it be okay to hardcode architecture in code to avoid an additional dependency on a JSON/YAML parser? Batteries included, so to say.

Furthermore, carrying an architecture.json around is a rather unsexy necessity. I think it should work as seamlessly as --march. One could imagine that, given a list of architectures, the compilation of the compiler only includes the selected ones to reduce the compiler binary's footprint. HPC centers could then provide access to this binary that is tailored to their available quantum machines.

Circuit Mapping
Essentially, how to define the start and the end of a circuit? Naively, all operations between alloc and free. However, as of now, it is possible to nest alloc statements. Consequently, it would be necessary to keep track of which qubit belongs to which register.

Semantically, I think it makes sense to limit the number of quantum registers in a given region to one. I can't think of an example where it would be necessary to have multiple ones. Even in the case of Shor's algorithm, which uses two registers (different from the ones we allocate), one can always allocate N + M qubits and split these (could be an MLIR Op).

Moreover, MLIR has great multithreading capabilities. Limiting the amount of allocs in a specialized region to one allows us to route multiple circuits in parallel without any additional work.

Algorithmic Details

QMAP Layer Calculation
It should be possible to use MLIR's def-use chains to partition the circuit in layers (or calculate layers just-in-time) rather efficiently, I think.

Loops
The mapping algorithm should be able to handle loops (eventually). Take the O(√N) repeats in Grover's algorithm as an example.

Theoretically, the swaps required in the loop body should always be the same when starting from the same initial permutation.
To my knowledge, all existing mapping algorithms route unrolled circuits (Is this true?). Nonetheless, this could be a potential avenue for optimizations and solid speed-ups, albeit potentially higher SWAP counts.

[burgholzer]

Some thoughts on this issue (these sub-issues):

Some thoughts in reply ;o)

Dialect

Lowering to LLVM IR The exit dialect will likely be LLVM. Do you have any thoughts on how quantum operations should be mapped to LLVM IR? These considerations might influence the definition of MQTMem.

That's exactly what the Quantum Intermediate Representation (QIR) was designed for.
See https://github.com/qir-alliance/qir-spec and maybe https://arxiv.org/abs/2411.18682 for a brief introduction. When looking at the spec, always rather look at the in-development version.
We are planning to lower our quantum dialects to QIR. Support for that is tracked since what feels forever in #429, but the issue has not been updated yet to mention MLIR.
QIR, similar to OpenQASM, defines a version of programs with static addresses (hardware qubits) and a version with dynamic addresses and register allocations.
QIR itself uses reference semantics.

Conversion

Prerequisites Most mapping algorithms assume the circuit has already been decomposed into elementary gates (such as CNOT and U). For starters, we could assume that this is "done manually," but eventually, this should also be the job of the compiler. I could imagine the following custom pipeline:

MQTOpt --naive conversion--> MQTMem --decompose--> MQTMem --route--> MQTMem (--conversion--> LLVM IR)

Moreover, based on the given architecture, the routing pass might already use a decomposed, hardware-native swap gate.

For starters, we need to assume that circuits are already decomposed.
In case of QMAP, we need to, at least, assume that the circuit has been decomposed into 1- and 2-qubit gates.
The typical compilation toolchain is

General program 
--optimizations-->
--decomposition of >=3qb gates-->
--optimization-->
--layout and routing (this is where the translation from dynamic to static addresses takes place)-->
--optimizations preserving the connectivity-->
--decomposition to native gate set-->
--optimizations preserving the connectivity and native gate set-->

See also https://quantum.cloud.ibm.com/docs/en/api/qiskit/transpiler#preset-pass-managers, for how Qiskit models this.
This issue should really only be concerned with the layout and routing part of the above.
An interesting consequence of the above though: If we define two separate dialects for the addressing mode, we also need to implement the respective transformation/optimization passes for both of these dialects. That could amount to quite some duplication.

Architecture Information At some point, QDMI might aid this process. However, until then, would it be okay to hardcode architecture in code to avoid an additional dependency on a JSON/YAML parser? Batteries included, so to say.

Furthermore, carrying an architecture.json around is a rather unsexy necessity. I think it should work as seamlessly as --march. One could imagine that, given a list of architectures, the compilation of the compiler only includes the selected ones to reduce the compiler binary's footprint. HPC centers could then provide access to this binary that is tailored to their available quantum machines.

Long-term or even mid-term, QDMI should be the solution here.
For starters, hard-coding the connectivity of a device seems fine.
Although we already depend on the nlohmann_json library throughout mqt-core. So parsing of JSON would not be that critical.

Catalyst/Pennylane feeds this information in from the frontend (pennylane) through device decorators. See https://pennylane.ai/devices and https://docs.pennylane.ai/projects/catalyst/en/stable/dev/devices.html and
NVIDIA probably does something similar in CUDA-Q: https://nvidia.github.io/cuda-quantum/latest/using/backends/backends.html
I think both actually boild down to something very similar to what you are alluding to with -march. Their compilers catalyst or nvq++ simply get something like --target <provider> --quantum-machine <actual machine identifier> passed on the command-line.

Circuit Mapping Essentially, how to define the start and the end of a circuit? Naively, all operations between alloc and free. However, as of now, it is possible to nest alloc statements. Consequently, it would be necessary to keep track of which qubit belongs to which register.

Semantically, I think it makes sense to limit the number of quantum registers in a given region to one. I can't think of an example where it would be necessary to have multiple ones. Even in the case of Shor's algorithm, which uses two registers (different from the ones we allocate), one can always allocate N + M qubits and split these (could be an MLIR Op).

Moreover, MLIR has great multithreading capabilities. Limiting the amount of allocs in a specialized region to one allows us to route multiple circuits in parallel without any additional work.

Defining what constitutes a quantum circuit that can be mapped is indeed tricky.
I would argue that tracking operations between alloc and free seems reasonable. This is also what the first conversion passes that try to convert from the MLIR dialect to our QuantumComputation try to do. See https://github.com/munich-quantum-toolkit/core/blob/main/mlir/lib/Dialect/MQTOpt/Transforms/ToQuantumComputationPattern.cpp and https://github.com/munich-quantum-toolkit/core/blob/main/mlir/lib/Dialect/MQTOpt/Transforms/FromQuantumComputationPattern.cpp

I am not quite sure I would agree with your statement on the number of allocations. One always has to keep in mind that these programs come from users that write these programs in some source language. All of these allow the definition of multiple registers, which would be translated to multiple alloc operations in the initial lowering to MLIR.
It should not be too hard to support multiple allocations, though. We basically want to form a maximally large region of operations from the first allocation to the last delocation.

CUDA-Q and Catalyst/Pennylane both seem to manage this through some explicit "kernel" definition.
See for example https://nvidia.github.io/cuda-quantum/latest/specification/cudaq/kernels.html or https://docs.pennylane.ai/en/stable/introduction/circuits.html
Anything part of the kernel is supposed to be manageable by the compiler.

In previous discussions with the colleagues from Xanadu, we reached the conclusion that it is probably best to first consider straight-line programs only (pure quantum circuits, no classical control flow or other logic), before moving to more complicated problems/programs.
Although we should keep the more complicated case in mind.

Algorithmic Details

QMAP Layer Calculation It should be possible to use MLIR's def-use chains to partition the circuit in layers (or calculate layers just-in-time) rather efficiently, I think.

I would assume this should work, yeah.

Loops The mapping algorithm should be able to handle loops (eventually). Take the O(√N) repeats in Grover's algorithm as an example.

Theoretically, the swaps required in the loop body should always be the same when starting from the same initial permutation. To my knowledge, all existing mapping algorithms route unrolled circuits (Is this true?). Nonetheless, this could be a potential avenue for optimizations and solid speed-ups, albeit potentially higher SWAP counts.

I would target compilation of classical control flow constructs as a follow-up to the initial implementation.
In principle, it should be possible to support these (if, for, while).
Qiskit's routing method has some support for such operations that might be worth looking into. See Qiskit/qiskit#9417 for the respective tracking issue containing lots of pointers.

---

@ystade your thoughts/comments on the above would be appreciated!

[ystade]

Nice, you both already covered quite a lot. The most totally makes sense and I do not have to add anything right now. Just one minor detail that I stumbled over: The decomposition to the native gate set should not happen in the memory dialect, this should happen before, probably in the optimization dialect.

[burgholzer]

Nice, you both already covered quite a lot. The most totally makes sense and I do not have to add anything right now. Just one minor detail that I stumbled over: The decomposition to the native gate set should not happen in the memory dialect, this should happen before, probably in the optimization dialect.

That is debatable. The routing will produce a circuit using hardware qubits (memory dialect). However, it is not a pre-requisite for routing that the circuit is already in the native gate-set. In fact, the SWAPs that are typically inserted as part of the routing process will typically only be decomposed to native gates afterwards.
The decomposition into 1- and 2-qubit gates should happen in the optimization dialect though.