Runtime router

[ritu-thombre99]

Context:

Original PR: https://github.com/PennyLaneAI/catalyst/pull/1928#issue-3251031857 Description of the Change:

When running a quantum circuit on a hardware with certain connectivity constraints, two-qubit gates like CNOTs can only be executed using physical qubits that are connected by an edge on the hardware.

Hence, necessary SWAPs need to be inserted in order to route the logical qubits so that they are mapped to an edge on the device, while respecting other compiling constraint i.e. order the gate dependencies from the input quantum circuit, and ensuring compiled quantum circuit is equivalent to the input quantum circuit.

Following image shows a simple example:

Benefits:

1. This will support qubit mapping and routing in the runtime
2. Analogue to qml.transpile transform
3. Circuits with control structure will also be supported since they will already be optimized by Catalyst passes and unrolled in the runtime.

Possible Drawbacks:

1. Modification of RuntimeCAPI
2. Currently, not checking if device supports SWAP
3. There are multi-qubit gates like Toffoli, MultiRZ, QubitUnitary in RuntimeCAPI.cpp. Routing is not applied to these qubits yet.

Related GitHub Issues:

Example usage:

Currently, seeing what SWAP gates are added can be viewed by using null.qubit done by printing NamedOperation in runtime/lib/backend/null_qubit/NullQubit.hpp

import pennylane as qml
import numpy as np
dev = qml.device("null.qubit", wires = [(0,1),(1,2),(2,3)])
@qml.qjit(autograph=True)
@qml.qnode(dev)
def circuit(c: bool, x: int, y: int):
    if c:
        qml.Hadamard(x)
    qml.Hadamard(y)
    qml.CRZ(0.4,[x,y])
    qml.CNOT([x,2])
    qml.CRX(0.6,[2,y])
    qml.CRY(0.2,[x,y])
    qml.IsingXX(0.24,[0,y])
    qml.CNOT([2,4])
    qml.CNOT([0,5])
    return qml.state()
print(circuit(True,0,3))

Output:

Name: Hadamard
Wires : 0,
Name: Hadamard
Wires : 3,
Name: SWAP
Wires : 0,1,
Name: SWAP
Wires : 1,2,
Name: CRZ
Wires : 2,3,
Name: CNOT
Wires : 2,1,
Name: SWAP
Wires : 1,2,
Name: CRX
Wires : 2,3,
Name: SWAP
Wires : 1,2,
Name: CRY
Wires : 2,3,
Name: IsingXX
Wires : 2,3,
Name: SWAP
Wires : 1,2,
Name: SWAP
Wires : 2,3,
Name: CNOT
Wires : 3,4,
Name: SWAP
Wires : 1,2,
Name: SWAP
Wires : 2,3,
Name: SWAP
Wires : 3,4,
Name: CNOT
Wires : 4,5,
Name: SWAP
Wires : 1,3,
Name: SWAP
Wires : 0,1,
Name: SWAP
Wires : 4,0,
[1.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j
 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j
 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j
 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j
 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j
 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j
 0.+0.j 0.+0.j 0.+0.j 0.+0.j]

[ritu-thombre99]

Updates:

1. Fixed the initial wires permuted during routing by adding a sequence of SWAPs at the end here, which gets called before any measurement in runtime/lib/capi/RuntimeCAPI.cpp
2. Added an integration test to verify all measurements are not affected by routing here

[ritu-thombre99]

Need some help with how to write runtime tests for routing. Is it possible to use resource tracking with null.qubit to see what original operations were and what SWAPs are inserted at runtime?

[dime10]

Need some help with how to write runtime tests for routing. Is it possible to use resource tracking with null.qubit to see what original operations were and what SWAPs are inserted at runtime?

Great idea, I think that should be possible! The resource tracking is quite good now

Thank you for providing the update btw, it will be exiting functionality to have in Catalyst!