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

• Published in: Expert systems with applications 2016-11, Vol.61, p.16-27
• Main Authors: Alfailakawi, Mohammad Gh, Ahmad, Imtiaz, Hamdan, Suha
• Format: Article
• Language: English
• Subjects: 2D Nearest neighbor; Algorithm; Algorithms; Circuits; Expert systems; Gates; Harmony search; Heuristic methods; Neural networks; Quantum circuit; Quantum computing; Qubits (quantum computing); Reversible circuit
• ISSN: 0957-4174; 1873-6793
• DOI: 10.1016/j.eswa.2016.04.038

•The emerging field of quantum computing is addressed in this work.•A Harmony Search (HS) based algorithm is proposed to efficiently realize quantum circuits on two dimension grids.•The objective is to minimize the number of SWAP gates for two dimension nearest neighbor architecture.•A local optimization heuristic is embedded with HS algorithm to further improve the solution quality.•Experimental results on real benchmarks demonstrate the scalability and effectiveness of the proposed technique. 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.