Harmony-search algorithm for 2D nearest neighbor quantum circuits realization

Motivated by its promising applications, quantum computing is an emerging area of research. This paper addresses the NP-complete problem of finding Nearest Neighbor (NN) realization of quantum circuits on a 2-Dimensional grid. In certain quantum technologies, only physically adjacent qubits are allowed to interact with each other hence the need for NN requirement. Circuits with distant qubits are made NN-compliant by introducing swap gates, hence increasing cost In this work, we present a Harmony Search (HS) based intelligent metaheuristic algorithm to efficiently realize low cost NN circuits utilizing input line reordering. The distinct feature of the proposed technique is that initial qubits placement is found using HS based metaheuristic followed by an efficient, problem-specific local heuristic to perform swap gate insertion. The effectiveness of the proposed algorithm is demonstrated by comparing its performance to a number of recent published approaches. Solutions found by the proposed technique show reduction in the number of swaps needed in the range of 4% - 36% on average when compared to state-of-the-art techniques. Compared to other approaches, the implemented algorithm is scalable and was able to find optimized circuits within 4 seconds in the worst case. (C) 2016 Elsevier Ltd. All rights reserved.