Nowe reguły przesuwania bramek w układach odwracalnych

Jedną z możliwości redukcji układów odwracalnych daje przesuwanie bramek. W pracy zaproponowano nowe reguły takich przesunięć dla układów budowanych ze standardowej biblioteki bramek odwracalnych NCT. Umożliwiają one eliminację bramek o dużej liczbie wejść/wyjść, które mają największy tzw. koszt kwantowy. Opracowane przez nas reguły mogą być stosowane dla dowolnej liczby wejść układu. Umożliwia to projektowanie układów odwracalnych o zredukowanym koszcie kwantowym. Podane przez nas przykłady pokazują, że oszczędności w porównaniu z układami publikowanymi w literaturze mogą być znaczne.

Synthesis of reversible logic circuits is the most intensively studied topic of the research area called reversible computation (circuits are reversible if they represent bijective mappings). This new research area has applications in many fields of computer science, e.g. quantum computing, nanotechnologies, optical computing, digital signal processing, communications, bioinformatics, cryptography as well as in low power computation. Recent advances consist in reducing numbers of gates, garbage bits or quantum cost. Some reversible circuit synthesis algorithms generate circuits in which majority of gates have large or even maximal size (i.e. equal to the number of inputs/outputs. However, quantum cost of multi-control generalized Toffoli gates is very high. In this paper it is shown how to reduce the quantum cost of circuits by eliminating most of large gates or even all of them. Namely, a new subset of moving rules useful for reducing the quantum cost is presented. Using this subset, it is possible to reduce the number of maximal-size gates to zero for even functions, and to one for odd functions, according to the known theorem. In the paper substantial savings in the quantum cost are presented for designs taken from recent publications.