Fast Algorithms for Synthesis of Quantum Reversible Logic Circuits Based on Hash Table

Quantum reversible logic circuits are basic elements of quantum computer. The quantum computer can be constructed by cascading and combining the quantum gates. Synthesis of quantum reversible logic circuits automatically constructs the desired quantum reversible logic circuits with minimal quantum cost. By absorbing all kinds of ideas of synthesis of reversible logic circuits, a novel and efficient algorithm is presented, which can construct optimal quantum reversible logic circuits with various types of gates and quantum costs by constructing minimal perfect Hash function. A universal algorithm is proposed, which can automatically construct all kinds of quantum gate libraries through the permutations of quantum lines, to ensure the realization of the automation of quantum circuit synthesis. Judging by the internationally recognized reversible functions of three variables, the algorithm presented not only synthesizes all optimal reversible logic circuits, but also runs extremely faster than other ones. The experimental results show that the average speed of the algorithm, which synthesizes circuit with minimum length or at minimum cost, is 49.15 and 365.13 times that of currently best result respectively.