Quantum Circuit Mapping

Many quantum computing architectures limit the pairs of qubits that two-qubit operations can be applied to. This is commonly described by a device’s coupling map. To execute a generic quantum circuit (with arbitrary interactions between its qubits) on such an architecture, the circuit needs to be mapped. This involves qubit allocation, where logical qubits are assigned to physical qubits in an initial layout, and routing, where the original circuit is augmented with SWAP gates such that it adheres to the target device’s coupling map.

Consider the following circuit.

from qiskit import QuantumCircuit

qc = QuantumCircuit(4)
qc.h(0)
qc.cx(0, 1)
qc.cx(0, 2)
qc.cx(0, 3)

qc.barrier()

qc.t(0)
qc.t(1)
qc.t(2)
qc.t(3)

qc.barrier()

qc.cx(0, 3)
qc.cx(0, 2)
qc.cx(0, 1)

qc.measure_all()

qc.draw(output="mpl")

Now assume this circuit shall be mapped to a \(4\)-qubit architecture defined by the following coupling map:

In QMAP this architecture can be manually defined as follows.

from mqt import qmap

arch = qmap.Architecture(
    4,
    {
        (0, 1),
        (1, 0),
        (1, 2),
        (2, 1),
        (2, 3),
        (3, 2),
    },
)

The quantum circuit qc can not be run directly on this architecture since it contains gates that act on qubits not connected on the device architecture. Naively inserting SWAP gates that permute the logical-to-physical qubit mapping on the fly may yield the following compiled circuit.

            ┌───┐                      ░ ┌───┐ ░                       ░ ┌─┐
q_0 -> q_0: ┤ H ├──■───X───────────────░─┤ T ├─░───────────────X───■───░─┤M├─────────
            └───┘┌─┴─┐ │               ░ ├───┤ ░               │ ┌─┴─┐ ░ └╥┘┌─┐
q_1 -> q_1: ─────┤ X ├─X───■───X───────░─┤ T ├─░───────X───■───X─┤ X ├─░──╫─┤M├──────
                 └───┘   ┌─┴─┐ │       ░ ├───┤ ░       │ ┌─┴─┐   └───┘ ░  ║ └╥┘┌─┐
q_2 -> q_2: ─────────────┤ X ├─X───■───░─┤ T ├─░───■───X─┤ X ├─────────░──╫──╫─┤M├───
                         └───┘   ┌─┴─┐ ░ ├───┤ ░ ┌─┴─┐   └───┘         ░  ║  ║ └╥┘┌─┐
q_3 -> q_3: ─────────────────────┤ X ├─░─┤ T ├─░─┤ X ├─────────────────░──╫──╫──╫─┤M├
                                 └───┘ ░ └───┘ ░ └───┘                 ░  ║  ║  ║ └╥┘
    meas: 4/══════════════════════════════════════════════════════════════╩══╩══╩══╩═
                                                                          0  1  2  3

Over the course of the mapping, four SWAP gates have been introduced to satisfy the connectivity constraints of the device’s architecture. Since every additional gate increases the probability of errors, this is a very costly overhead for such a small circuit.

Keeping the number of additionally introduced gates as small as possible is key for ensuring the successful execution of the quantum circuit. Finding an optimal mapping for a quantum circuit is an NP-hard problem [2]. QMAP offers two dedicated techniques for tackling that problem: - An exact mapping approach (based on [3], [4]) that guarantees (gate-optimal) solutions and is typically suitable for up to 8 qubits. - A heuristic mapping approach (based on [5], [6]) that allows to determine efficient mapping solutions in a scalable fashion for up to hundreds of qubits.

Exact Mapping

The exact mapper implemented in QMAP maps quantum circuits using the minimal number of SWAP gates. To this end, it encodes the mapping task as a MaxSAT problem and subsequently solves it using the SMT solver Z3. Due to the NP-hardness of the mapping task, this approach is only scalable up to roughly eight qubits in most scenarios.

Note

On directional architectures, it can be significantly cheaper to surround a CNOT gate with four Hadamard operations (effectively exchanging its control and target) instead of adding a SWAP gate. For these architectures, QMAP minimizes the number of additional SWAP and H gates.

Using the exact mapper is as simple as:

qc_mapped, res = qmap.compile(qc, arch, method="exact", post_mapping_optimizations=False)

qc_mapped.draw(output="mpl")

print("Additional SWAPs: %d" % res.output.swaps)
print(f"Runtime:          {res.time:f}")

Additional SWAPs: 2
Runtime:          1.706222

The resulting solution only requires two SWAP gates for mapping the circuit.

Note

The exact mapping method implemented in QMAP is optimal with respect to the number of additional SWAP gates needed for mapping a given circuit. It is not guaranteed to be optimal with respect to the number of additional gates needed for mapping a given circuit, e.g., any sequence of a SWAP gate and a CNOT gate acting on the same qubits can be simplified to just two CNOT gates. Such an optimization pass is conducted by default in the compile method after the circuit has been mapped. However, this cost reduction is not accounted for in the SAT formulation at the moment.

Heuristic Mapping

The heuristic mapper implemented in QMAP uses A*-search to efficiently traverse the immense search space of the mapping problem. It effectively trades optimality for runtime. This allows to reliably determine suitable mappings for circuits with up to hundreds of qubits. Using the heuristic mapper works completely analogous to the exact mapper.

qc_mapped, res = qmap.compile(qc, arch, method="heuristic", post_mapping_optimizations=False)

qc_mapped.draw(output="mpl")

print("Additional SWAPs: %d" % res.output.swaps)
print(f"Runtime:          {res.time:f}")

Additional SWAPs: 3
Runtime:          0.000062

While this solution is not optimal anymore it only requires one more SWAP gate and even for such a small example the heuristic mapper is orders of magnitudes faster than the exact mapper.

Teleportation in Heuristic Mapping

Using quantum teleportation can reduce the number of swap gates when the algorithm requires fewer qubits than the architecture has available. In that case, the spare qubits are initialized in a Bell state and used as “teleportation channel” when suitable later in the quantum circuit.

Below you find an illustration of the circuitry for teleportation, i.e., setting up the Bell state, initializing the teleportation, and subsequent measurements to correct possible bit- and phase flips.

                        ░      ┌───┐ ░ ┌─┐    ░
    |ψ⟩ q_0: ───────────░───■──┤ H ├─░─┤M├────░─────────────── |0⟩ or |1⟩
             ┌───┐      ░ ┌─┴─┐└───┘ ░ └╥┘┌─┐ ░
    |0⟩ a_0: ┤ H ├──■───░─┤ X ├──────░──╫─┤M├─░─────────────── |0⟩ or |1⟩
             └───┘┌─┴─┐ ░ └───┘      ░  ║ └╥┘ ░  ┌───┐  ┌───┐
    |0⟩ a_1: ─────┤ X ├─░────────────░──╫──╫──░──┤ X ├──┤ Z ├─ |ψ⟩
                  └───┘ ░            ░  ║  ║  ░  └─┬─┘  └─┬─┘
                                        ║  ║    ┌──┴──┐   │
  bitflip: 1/═══════════════════════════╩══╬════╡ = 1 ╞═══╪═══
                                        0  ║    └─────┘┌──┴──┐
phaseflip: 1/══════════════════════════════╩═══════════╡ = 1 ╞
                                           0           └─────┘

The following cell contains a brief demonstration on how teleportation can be used in a linear coupling map.

from mqt import qmap

arch = qmap.Architecture(
    6,
    {
        (0, 1),
        (1, 0),
        (1, 2),
        (2, 1),
        (2, 3),
        (3, 2),
        (3, 4),
        (4, 3),
        (4, 5),
        (5, 4),
    },
)

qc_mapped_w_teleport, res = qmap.compile(qc, arch, method="heuristic", use_teleportation=True, teleportation_seed=2)

qc_mapped_w_teleport.draw(output="mpl")

Visualizing search graphs

For deeper insight into a specific mapping process one can visualize the search graphs generated during heuristic mapping.

from mqt.qmap import compile
from mqt.qmap.visualization import SearchVisualizer

visualizer = SearchVisualizer()
qc_mapped, res = compile(qc, arch, method="heuristic", visualizer=visualizer)
visualizer.visualize_search_graph()

There exist a wide range of customizations for these visualizations. Please refer to the reference documentation for more information.