  Linear Nearest Neighbor (LNN) synthesis in reversible circuits has emerged as
an important issue in terms of technological implementation for quantum
computation. The objective is to obtain a LNN architecture with minimum gate
cost. As achieving optimal synthesis is a hard problem, heuristic methods have
been proposed in recent literature. In this work we present a graph
partitioning based approach for LNN synthesis with reduction in circuit cost.
In particular, the number of SWAP gates required to convert a given gate-level
quantum circuit to its equivalent LNN configuration is minimized. Our algorithm
determines the reordering of indices of the qubit line(s) for both single
control and multiple controlled gates. Experimental results for placing the
target qubits of Multiple Controlled Toffoli (MCT) library of benchmark
circuits show a significant reduction in gate count and quantum gate cost
compared to those of related research works.
