Nnizer: Swap Insertion Solver

A lot of quantum chips have connectivity constraints. For instance two-qubit gates may only be applicable between some pairs of qubits, but not all.

This module provides a plugin which solves the SWAP insertion problem, i.e the problem of inserting SWAPs into a circuit to fit it into any hardware topology.

This plugin is contained in the class Nnizer, which will add SWAP gates in a circuit to make it compliant with the connectivity constraints of a hardware. The specifications of a hardware (including connectivity constraints / topology) are defined by an instance of the class HardwareSpecs.

The following example defines a QPU which has a limited connectivity. The use of the Nnizer plugin transforms this QPU into a QPU accepting any circuit:

from qat.plugins import QuameleonPlugin
from qat.qpus import LinAlg
from qat.core import HardwareSpecs, Topology, TopologyType
from qat.plugins import Nnizer

# Defines a QPU with a limited connectivity (LNN connectivity)
specs = HardwareSpecs(topology=Topology(type=TopologyType.LNN))
qpu = QuameleonPlugin(specs=specs) | LinAlg()

# The 'qpu' object is a QPU with a limited connectivity.
# Adding the Nnizer plugin remove the connectivity constraint
# by solving the "swap insertion problem". Circuits processed by
# the Nnizer have a connectivity compliant with the QPU
final_qpu = Nnizer() | qpu


from qat.lang.AQASM import Program
from qat.lang.AQASM.qftarith import QFT

# Define a All to All circuit (not compliant with LNN constraints)
prog = Program()
qbits = prog.qalloc(3)
prog.apply(QFT(3), qbits)
job = prog.to_circ(inline=True).to_job()

# Submit to QPU
result = final_qpu.submit(job)


# Sending circuit directly to the QPU may raise an error
from qat.comm.exceptions.ttypes import PluginException

try:
    qpu.submit(job)

except PluginException as exception:
    print("The job (not processed by the Nnizer) can't be " +
          "executed by the QPU:\n" + exception.message)

The job (not processed by the Nnizer) can't be executed by the QPU:
Hardware topology does not support [2, 0] interactions

Jupyter notebook Satisfying Connectivity Constaint explains how to use the Nnizer plugin

References

LDX19: Gushu Li, Yufei Ding, and Yan Xie. Tackling the qubit mapping problem for nisq-era quantum devices. In ASPLOS: Architectural Support for Programming Languages and Operating Systems, 1001–1014. April 2019. URL: https://doi.org/10.1145/3297858.3304023.
SWD11: Mehdi Saeedi, Robert Wille, and Rolf Drechsler. Synthesis of quantum circuits for linear nearest neighbor architectures. Quantum Information Processing, 10(3):355–377, Jun 2011. URL: https://doi.org/10.1007/s11128-010-0201-2, doi:10.1007/s11128-010-0201-2.
HirataNakanishiYamashitaNakashima09: Y. Hirata, M. Nakanishi, S. Yamashita, and Y. Nakashima. An efficient method to convert arbitrary quantum circuits to ones on a linear nearest neighbor architecture. In 2009 Third International Conference on Quantum, Nano and Micro Technologies, 26–33. 2009. URL: https://ieeexplore.ieee.org/document/4782917.
ZulehnerPalerWille18: A. Zulehner, A. Paler, and R. Wille. Efficient mapping of quantum circuits to the ibm qx architectures. In 2018 Design, Automation Test in Europe Conference Exhibition (DATE), 1135–1138. 2018. URL: https://ieeexplore.ieee.org/document/8342181.