Quantum-chain

A tool chain to generate nearest neighbour complaint circuit for arbitrary topologies. Please cite the following paper if you use the tool in your work.

@inproceedings{bhattacharjee2019muqut,
  title={MUQUT: Multi-constraint quantum circuit mapping on NISQ computers},
  author={Bhattacharjee, Debjyoti and Saki, Abdullah Ash and Alam, Mahabubul and Chattopadhyay, Anupam and Ghosh, Swaroop},
  booktitle={38th IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2019},
  pages={8942132},
  year={2019},
  organization={Institute of Electrical and Electronics Engineers Inc.}
}

Tool chain workflow

The toolchain takes two primary parameters as input

• Quantum circuit in real format [(Specification details)[http://www.informatik.uni-bremen.de/rev_lib/doc/docu/revlib_2_0_1.pdf]]
• Quantum Computer Qubit interaction graph. The IBM Q16 qubit interaction graph is shown below.

Let’s say that the circuit C has n qubits and the graph G has k qubits

Topology extraction

Multiple subgraphs of n qubits are extracted from the graph G. Each subgraph has a unique topology and no two subgraphs are isomorphic. A probabilistic approach is used for choosing the subgraph. 128 tries are made to extract the topologies. Let the topology graph be T.

NN-circuit generation

We use an ILP solver to optimally generate a NN-complaint circuit from the input circuit C and a topology graph T. Furthermore, we use n*n steps for generating the NN circuit. Another interesting constraint is the mapping of the individual qubits in the circuit to the vertices in the topology graph T. We consider some random mappings of the qubits to the vertices for generating multiple variants of NN-complaint circuit.

Tool chain usage

Installation

The tool is implemented in Python3 and tested on Ubuntu 18.04. Install the depedencies from requirements.txt.

You need a valid installation of Gurobi along with the Python wrapper. Academic license can be obtained for free via their website.

Running instructions

We demonstrate the usage of the tool by means of an example.

• sample_ckt.real : Input quantum circuit with 4 qubits (a, b, c and d)
• qx15.gml : Quantum computer graph with 16 qubits

cd quantum-chain
python3 qchain.py ./tests/sample_ckt.real ./tests/qx15.gml 

Output

The output is written to ./genfiles/sample_ckt folder. The name of the subfolder in genfiles is same as the name of the input quantum circuit. Multiple solutions are generated by the tool.

• sample_ckt_i.cfg : The qubit configuration of i^th solution. The first number denotes the vertex id and the second number indicates the qubit. This file is saved in the following sub-directory under /genfiles/sample_ckt/allmaps/cfg
• topofiles/qx15_4_2.gml : 2nd Topology graph extracted from qx15 with 4 qubits. Saved in /genfiles/sample_ckt/allmaps/gmlfiles
• sample_ckt_qx15_4_2_i.real: The ith NN complaint Quantum circuit for topology graph qx15_4_2. Saved in /genfiles/sample_ckt/real
• i_ibm.txt: The IBM combatible netlist generated from the ith NN compliant Quantum Circuit in .real format. Saved in /genfiles/sample_ckt/netlist_ibm
• i_fidelity.txt: Fidelity (or, succcess probability) of various mappings of the ith Quantum Circuit. Saved in /genfiles/sample_ckt/fidelity

Remarks

• The ILP scales exponentially. Large benchmarks might take a long time (read days) to complete execution generating a single solution.
• Usually quantum computer natively supports a set of gates (target gate library). The tool currently does not check if the input quantum circuit has other gates. Proper synthesis to target gate library must be done before invoking the tool.
• Some of the qubit interaction graphs are directed. The ILP currently doesnt support directed graphs.