This repository provides the source code and reproducible experiments presented in Single-Qubit Gates Matter for Optimising Quantum Circuit Depth in Qubit Mapping by Sanjiang Li, Ky Dan Nguyen, Zachary Clare, and Yuan Feng, which was accepted to ICCAD '23.
For enquiries, contact [email protected] (Sanjiang Li) or [email protected] (Ky Dan Nguyen).
Most existing quantum circuit transformation (QCT, or qubit mapping) algorithms prioritise minimising circuit size, potentially overlooking the impact of single-qubit gates on circuit depth. In the past several years, we have seen the size of quantum computer increases from 5 to 433 qubits, but qubit coherence time in NISQ devices remains very short. This implies that we can only run a very limited number of quantum operations on each qubit; in other words, we cannot extract meaningful information from very deep quantum circuits on NISQ devices. Thus, minimising the depth of transformed circuits is perhaps a more important objective.
SQGM (Single-Qubit Gates Matter) promises a simple and effective method that takes into account the impact of single-qubit gates on circuit depth. Our method can be integrated with existing QCT algorithms. In this source code, we demonstrate the effectiveness of SQGM by embedding it in Qiskit's SabreSwap
module, which is an implementation of the state-of-the-art SABRE (SWAP-based Bidirectional Heuristic Search Algorithm).
SQGM uses modules from the Qiskit libraries, in particular, Qiskit Terra. Information on installing Qiskit can be found here. The version used for experiments was 0.39.4, the latest version at the time. In addition, the NetworkX library is used to construct architecture graphs. Information on installing Networkx can be found here.
All experiments conducted used architecture graphs of the following quantum devices as target backends:
ourense
: IBM Q Ourense (5 qubits),tokyo
: IBM Q Tokyo (20 qubits),rochester
: IBM Q Rochester (53 qubits),sycamore53
,sycamore54
: Google Sycamore (53 and 54 qubits).
Note that Google Sycamore was originally designed with 54 qubits, but ended up with 1 bad qubit; both the designed and actual versions were used in the experiments. Architecture graphs were modelled using NetworkX, and can be found in ag.py
. A visualisation of these graphs can be found in display.ipynb
.
All experiments conducted used Qiskit 0.39.4's SabreLayout
module is used to generate initial mappings. Nonetheless, /mapper
provides the Qiskit 0.33.0's SabreLayout
module for reference and use, if needed.
The source code for SQGMSwap
(written on top of SabreSwap
) as well as Qiskit 0.33.0's SabreSwap
module are provided in /router
. The experiments also used Qiskit 0.39.4's SabreSwap
module and NASSCSwap
module, the original implementation of the NASSC (Not All SWAPs Have the Same Cost), retrieved from the author's repository solely for experimental purposes. TOQM (Time-Optimal Qubit Mapping) was also used for comparisons; its source code (written in C++) is available in the author's repository.
All benchmarks used in experiments are provided in /benchmark
. Contained in the directory are selected circuits from QUEKO, QUEKNO, and MQT Bench. In addition, /example_4q
contains the original circuit, and initial mapping, of the running example in the paper (refer to Fig. 1).
Original experiment results are archived in /sqgm_data
. Within the directory:
/example_4q-out
provides the output transformed circuits of the originalexample_4q
circuit found in/benchmark
./mqtbench-init
provides the initial mappings of each of the MQT Bench circuits found in/benchmark
./exps
provides the results of the original experiments.sqgm-data.xlsx
provides a summary of all results presented in the paper.
Details of the original experiments, in JSON format, can be found in /exp-in
. This includes the validity test of the running example example_4q
, whose result is provided in display.ipynb
.
All of the original experiments can be reproduced via their respective JSON configuration files in /exp-in
. Each file contains the following information:
Field | Description |
---|---|
bench_path |
File path to the benchmarks to be used as input circuits. |
bench_filter |
Filter for specific circuit within the benchmark specified by bench_path . Only circuits containing bench_filter in their names are run. |
qasm_path |
File path to the directory where the exported output circuit QASM files are exported. |
csv_path |
File path to the CSV file in which numerical results are exported. |
ag |
Architecture graph of the target backend. |
reps |
Number of reps. |
objective |
Indicate whether depth (transformed circuit depth) or size (number of 2-qubit gates in the transformed circuit) should be optimised. |
mode |
Indicate whether to record the best result, or all results amongst the specified number of reps. |
rep_splits |
Rep numbers to be reported in the exported CSV file. Each split corresponds to a column in the CSV, which reports the best result up to that split. This field is only relevant for all mode. |
base_routers |
Routers (amongst those provided by /router ) to be run. |
heuristics |
Heuristics to be used. |
inc_cc |
Indicate whether or not to include, on top of each base router, an augmented router with Qiskit's commutative gate cancellation pass during post-routing optimisations. This field is only relevant when some router other than NASSC is included in base_routers (since NASSCSwap includes this pass by default). |
inc_naive_h |
Indicate whether or not to include, on top of the original SQGM, a variation where SABRE's original base_routers . |
exp_qasm |
Indicate whether or not to export the output circuit QASM files. Note that if a QASM file of the same name exists, it will be overwritten. |
exp_csv |
Indicate whether or not to export numerical results to the CSV file. Note that if a CSV of the same name exists, it will be overwritten. |
To run an experiment, simply run main.py
and supply the path to the respective JSON configuration file as a command line argument. Additionally, a --verbose
, or its shorthand -v
, can be included to toggle the display of detailed information on each rep. For example, to run exp1
in verbose mode:
$ python main.py ./exp-in/exp1.json --verbose
For experiments using a pre-defined initial mapping, i.e., skipping initial mapping generation with SabreLayout
, the initial mapping (in QASM format) can be supplied as an additional command line argument, immediately following the JSON configuration file path. For example, to run the validity test of example_4q
with example_4q-init
as the initial mapping:
$ python main.py ./example_4q.json ./benchmark/example_4q/example_4q-init.qasm
Note that the QASM file of the initial mapping must represent the circuit of the target backend with the logical circuit mapped onto it, i.e., the qubits defined in the file are those of the quantum device, not the logical circuit. See display.ipynb
for a visualisation of example_4q-init
as an example.
It is simple to customise, or define a new, experiment: simply edit the respective, or create a new, JSON configuration file as appropriate. Note that:
bench_path
andqasm_path
must be suffixed with/
.- If
bench_filter
is left blank, i.e.,""
, all circuits inbench_path
will be run. - The value of
ag
must be one of the keys ofARCHGRAPHS
, found inutil.py
. reps
must be a non-zero positive integer.- If
rep_splits
is left empty inall
mode, there will be a column for every rep number in the exported CSV file. - Each value in
base_routers
must be one of the keys ofROUTERS
, found inutil.py
.
An empty JSON configuration file exp_template.json
has been provided, and may be used to define new experiments.
It is possible to add new architecture graphs and routers to be used for new experiments.
To add a new architecture graph, define a new function in ag.py
which constructs and returns a Graph
object (from NetworkX). Next, in util.py
, add a new key-value pair for ARCHGRAPHS
, where key is the name and value is a call to the function. Then, experiments can be conducted with the new architecture graph by specifying its key in the ag
field of the respective JSON configuration file.
To add a new router, add the source code of that router in /router
. Note that the router must be compatible in nature with Qiskit's SabreSwap
, i.e., its constructor must have have at least the following parameters:
coupling_map
(CouplingMap
);heuristics
(str
), which must be eitherbasic
,lookahead
, ordecay
;seed
(int
); andfake_run
(bool
).
Next, in util.py
, import the router's module and add a new key-value pair for ROUTERS
, where key is the name and value is the relevant module. Then, experiments can be conducted with the new router by including its key in the base_routers
field of the respective JSON configuration file.