A Heuristic for Linear Nearest Neighbor Realization of Quantum Circuits by SWAP Gate Insertion Using -Gate Lookahead
Abhoy Kole, Kamalika Datta, Indranil Sengupta · IEEE Journal on Emerging and Selected Topics in Circuits and Systems · 2016
With recent interest in reversible and quantum computation, research in synthesis of reversible and quantum circuits has increased in momentum. With additional requirements of neighborhood interactions among qubits (with two basis states) being a necessity in some physical realizations, several works on obtaining nearest neighbor quantum gate realization by inserting SWAP gates have been reported. These methods are based on two broad optimization approaches, one based on global ordering, where qubits are ordered over the whole netlist, and the other based on local ordering for minimizing SWAP gate insertions on smaller segments of netlists. Further reductions in cost are possible by using multi-valued qudits that have more than two basis states. The present paper considers a quantum circuit based on the NCV library, and proposes a better SWAP gate insertion method based on local ordering that uses an N-gate lookahead approach to reduce cost. Experimental results on benchmark circuits and comparison against published works confirm the benefits of the proposed approach, with improvements over reported works obtained in the range of 27%-43% on the average and 54%-63% in the best case. The method is also scalable for larger circuits, with the longest runtime observed as 10 minutes.