Skip to main content Skip to main navigation


An Improved Heuristic Technique for Nearest Neighbor Realization of Quantum Circuits in 2D Architecture

Anirban Bhattacharjee; Chandan Bandyopadhyay; Philipp Niemann; Bappaditya Mondal; Rolf Drechsler; Hafizur Rahaman
In: Integration, the VLSI Journal, Vol. 76, Pages 40-54, Elsevier, 2021.


Last couple of years has witnessed tremendous advancements in the field of quantum computing and even it has started providing technological footprints in the design industry. Though advancements in the physical implementation of quantum circuits has taken a giant leap but it has faced with several design challenges and one such design constraint is Nearest Neighbor (NN) criteria which demands the operating qubits of the quantum gates to be adjacent. Focusing on the design issue, here, we show a heuristic design technique for efficient transformation of quantum circuits to NN based designs in 2D configuration. Our entire strategy is based on initial qubit mapping policy, where we have introduced three different mapping techniques 1) Influence Index, 2) Adjacency Matrix and 3) Distance Ratio based strategy. After placing the qubits in appropriate positions, we also undertake a dynamic windowing based local reordering scheme to further reduce the SWAP requirement in the designs. At the end of the work, to check the effectiveness of our transformation algorithms, we have tested a wide range of benchmarks over our algorithms and a comparative study over state-of-the-art design techniques also has been undertaken.