AQuCiDe: Architecture Aware Decomposition of Quantum Circuits

With the availability of moderate sized noisy quantum computers, researchers have been exploring various methods to execute quantum circuits using these devices. In some of these platforms (e.g. those using superconducting qubits), the qubit coupling architecture imposes constraints on 2-qubit gate operations. This is referred to as Nearest Neighbor (NN) constraint, which requires the interacting qubits to be adjacent. To make a quantum circuit NN-complaint, additional gates are required to be added that may compromise on the computational reliability. Quantum algorithms that involve Toffoli gate operations, must be first re-described using 1- and 2-qubit elementary quantum gates. Broadly two major approaches exist for decomposing larger Toffoli gates into elementary gates: (i) using dirty ancilla, (ii) using clean ancilla. The dirty ancilla based approach introduces more 2-qubit gates to describe a Toffoli netlist, while reducing the requirement of additional qubits during decomposition. On the other hand, clean ancilla based approach requires less number of 2-qubit gates at the cost of additional clean ancilla qubits. None of the methods available in the literature consider architectural information during decomposition. In this work to the best of our knowledge, for the first time we propose an architecture-aware decomposition approach, which exploits the Qubit Interaction Graph structure of Toffoli gates. The Clifford+T gate library is used for the final decomposed netlist. From the conducted experiments on various Toffoli netlists, it is observed that the architecture-aware approach generates netlists with comparable number of 2-qubit gates as in clean ancilla based approach when more physical qubits are available. Moreover, mapping the resulting netlists on physical architectures (viz. Hex20 and IBM27) reveals that the architectural information during decomposition is beneficial in reducing gate overhead.