Quantum Genetic Algorithm for Binary Decision Diagram Ordering Problem

Abstract

Summary The Binary Decision Diagram (BDD) is used to represent in symbolic manner a set of states. It’s largely used in the field of formal checking. The variable ordering is a very important step in the BDD optimization process. A good order of variables will reduce considerably the size of a BDD. Unfortunately, the search for the best variables ordering has been showed NP-difficult. In this article, we propose a new iterative approach called QGABDD based on a Quantum Genetic Algorithm. QGABDD is based on a basic core defined by a suitable quantum representation and an adapted quantum evolutionary dynamic. The obtained results are encouraging and attest the feasibility and the effectiveness of our approach. QGABDD is distinguished by a reduced population size and a reasonable number of iterations to find the best order, thanks to the principles of quantum computing