Abstract
While mapping a quantum circuit to the physical layer one has to
consider the numerous constraints imposed by the underlying hardware
architecture. Connectivity of the physical qubits is one such constraint
that restricts two-qubit operations, such as CNOT, to “connected’‘
qubits. SWAP gates can be used to place the logical qubits on admissible
physical qubits, but they entail a significant increase in CNOT-count.
In this paper we consider the problem of reducing the CNOT-count in
Clifford+T circuits on connectivity constrained architectures, like
noisy intermediate-scale quantum (NISQ) computing devices. We “slice’‘
the circuit at the position of Hadamard gates and “build” the
intermediate {CNOT,T} sub-circuits using Steiner trees, significantly
improving on previous methods. We compared the performance of our
algorithms while mapping different benchmark and random circuits to some
well-known architectures such as 9-qubit square grid, 16-qubit square
grid, Rigetti 16-qubit Aspen, 16-qubit IBM QX5 and 20-qubit IBM Tokyo.
Our methods give less CNOT-count compared to Qiskit transpiler as well
as using SWAP gates. Assuming most of the errors in a NISQ circuit
implementation are due to CNOT errors, then our method would allow
circuits with few times more CNOT gates be reliably implemented than the
previous methods would permit.