Synthesis of Reversible Circuits with Reduced Nearest-Neighbor Cost Using Kronecker Functional Decision Diagrams

Motivated by the importance of fault tolerance in quantum computing, there has been renewed interest in quantum circuits that are realized with Clifford+T gates. Quantum computers that are based on ion-trap technology, superconducting, and quantum dots need to fulfill certain nearest-neighbor (NN) constraints. Fault-tolerant implementations of quantum circuits also require restricted interactions among neighboring quantum bits. The insertion of SWAP-gates is often deployed to make quantum circuits nearest-neighbor (NN) compliant. As quantum operations are prone to various errors, it is important to reduce the nearest-neighbor cost (NNC) which is a marker to the number of SWAP-gates needed to make a quantum circuit NN-compliant. Such an optimization problem arises while synthesizing reversible circuits using the Kronecker functional decision diagram (KFDD). In this work, we propose a method based on KFDD that reduces NNC during synthesis. Considering the Clifford+T quantum mapping for NOT, CNOT, and Toffoli (NCT) gates, and mixed-polarity Peres (MPP) gates, NNC metrics are defined for reversible circuits. Governed by NNC metrics, the nodes are then ranked for reducing NNC in resulting reversible circuits. Furthermore, local transformations are applied on node functions while mapping a node to a cascade of reversible gates. Experimental results on several benchmark functions reveal that the proposed synthesis technique reduces NNC in many cases while slightly impacting the number of qubits, T-depth, and T-count. Compared to prior methods based on functional decision diagrams or binary decision diagrams, the proposed synthesis technique reduces quantum cost for NCV-realizations (i.e., with NOT, CNOT, V, and V\(^\dagger\) gates) in most of the cases.