Naive Qubit Mapping and Routing Algorithm in Runtime

[ritu-thombre99]

Context:

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]

[github-actions[bot]]

Hello. You may have forgotten to update the changelog! Please edit doc/releases/changelog-dev.md on your branch with:

• A one-to-two sentence description of the change. You may include a small working example for new features.
• A link back to this PR.
• Your name (or GitHub username) in the contributors section.

[dime10]

@ritu-thombre99 can you fix the checks?