An ant colony based mapping of quantum circuits to nearest neighbor architectures

Anirban Bhattacharjee, Chandan Bandyopadhyay, Angshu Mukherje, Robert Wille, Rolf Drechsler, Hafizur Rahamana

In: Integration, the VLSI Journal 78 Seiten 11-24 ScienceDirect 2021.


Although this decade is witnessing tremendous advancements in fabrication technologies for quantum circuits, this industry is facing several design challenges and technological constraints. Nearest Neighbor (NN) enforcement is one such design constraint that demands the physical qubits to be adjacent. In the last couple of years, this domain has made progress starting from designing advanced algorithms to improved synthesis methodologies, even though developing efficient design solutions remains an active area of research. Here, we propose such a synthesis technique that efficiently transforms quantum circuits to NN designs. To find the NN solution, we have taken help of an ant colony algorithm which completes the circuit conversion in two phases: in the first phase, it finds the global qubit ordering for the input circuit and, in the second phase, a heuristic driven look-ahead scheme is executed for local reordering of gates. The proposed algorithm is first fitted into a 1D design and, later, mapped to 2D and 3D configurations. The combination of such heuristic and the meta-heuristic schemes has resulted promising solutions in the transformation of quantum circuits to NN-compliant architectures. We have tested our algorithm over a wide spectrum of benchmarks and comparisons with state-of-the-art design approaches showed considerable improvements.

Deutsches Forschungszentrum für Künstliche Intelligenz
German Research Center for Artificial Intelligence