A Dynamic Programming Based Graph Traversal Approach for Efficient Implementation of Nearest Neighbor Architecture in 2D

In the fascinating realm of quantum circuit design, tackling the intricacies of swap gate insertion presents a host of challenges. Among these, the prominent issue of the nearest neighbor condition emerges as a pivotal hurdle. This constraint not only shapes the layout and connectivity of the quantum circuit but also amplifies the complexity of orchestrating efficient quantum computations. While navigating the Quantum Realm, unraveling the overhead conundrum in swap Gate insertion, motivated us to propose an efficient 2D transformation scheme for NN quantum circuit realization with a primary objective of forming efficient NN structures while minimizing SWAP usage. The design phase involves the introduction of a new parameter to calculate qubit interactions in the circuit. We then employ a dynamic graph-based algorithm to determine the qubit interaction order. Finally, the resultant order is placed on the suitable grid to calculate the number of SWAP gates required. Our approach is extensively tested with various benchmarks, and it outperforms some state-of-the-art design works. In addition to this work, we also have shown how this NN designs can be transformed into Clifford +T based NN compliant architecture to get fault-tolerant property.