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 like 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 talk we consider the problem of reducing the CNOT-count in Clifford+T circuits on connectivity constrained architectures. We “slice” the circuit at the position of Hadamard gates and “build” the intermediate portions. We investigate two kinds of partitioning – (i) partitioning the gates of the input circuit based on the locality of H gates and (ii) partitioning the phase polynomial of the input circuit. The intermediate {CNOT,T} sub-circuits are synthesized using Steiner trees, similar to the work of Nash, Gheorghiu, Mosca in 2020 and Kissinger, de Griend in 2019. Our algorithms have certain procedural differences that also help to further reduce the CNOT-count. In our experiment, we compared the performances of our algorithms while mapping different benchmark circuits as well as random circuits to some popular architectures like 9-qubit square grid, 16-qubit square grid, Rigetti 16-qubit Aspen, 16-qubit IBM QX5, 20-qubit IBM Tokyo. We found that for both the benchmark and random circuits our first algorithm using the simple slicing technique performs much better i.e. gives much less CNOT-count than the count obtained by using SWAP gates. Our second slice-and-build algorithm performs reasonably well for benchmark circuits.
