A reversible circuit synthesis algorithm with progressive increase of controls in generalized Toffoli gates
We present a new algorithm for synthesis of reversible circuits for arbitrary n-bit bijective functions. This algorithm uses generalized Toffoli gates, which include positive and negative controls. Our algorithm is divided into two parts. First, we use partially controlled gen- eralized Toffoli gate...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Graz University of Technology
2021-06-01
|
| Series: | Journal of Universal Computer Science |
| Subjects: | |
| Online Access: | https://lib.jucs.org/article/69617/download/pdf/ |
| _version_ | 1818882774268903424 |
|---|---|
| author | Edinelço Dalcumune Luis Antonio Brasil Kowada André da Cunha Ribeiro Celina Miraglia Herrera de Figueiredo Franklin de Lima Marquezino |
| author_facet | Edinelço Dalcumune Luis Antonio Brasil Kowada André da Cunha Ribeiro Celina Miraglia Herrera de Figueiredo Franklin de Lima Marquezino |
| author_sort | Edinelço Dalcumune |
| collection | DOAJ |
| description | We present a new algorithm for synthesis of reversible circuits for arbitrary n-bit bijective functions. This algorithm uses generalized Toffoli gates, which include positive and negative controls. Our algorithm is divided into two parts. First, we use partially controlled gen- eralized Toffoli gates, progressively increasing the number of controls. Second, exploring the properties of the representation of permutations in disjoint cycles, we apply generalized Toffoli gates with controls on all lines except for the target line. Therefore, new in the method is the fact that the obtained circuits use first low cost gates and consider increasing costs towards the end of the synthesis. In addition, we employ two bidirectional synthesis strategies to improve the gate count, which is the metric used to compare the results obtained by our algorithm with the results presented in the literature. Accordingly, our experimental results consider all 3-bit bijective functions and twenty widely used benchmark functions. The results obtained by our synthesis algorithm are competitive when compared with the best results known in the literature, considering as a complexity metric just the number of gates, as done by alternative best heuristics found in the literature. For example, for all 3-bit bijective functions using generalized Toffoli gates library, we obtained the best so far average count of 5.23. |
| first_indexed | 2024-12-19T15:23:06Z |
| format | Article |
| id | doaj.art-10f8e42d094d4a4685de39a3601001ab |
| institution | Directory Open Access Journal |
| issn | 0948-6968 |
| language | English |
| last_indexed | 2024-12-19T15:23:06Z |
| publishDate | 2021-06-01 |
| publisher | Graz University of Technology |
| record_format | Article |
| series | Journal of Universal Computer Science |
| spelling | doaj.art-10f8e42d094d4a4685de39a3601001ab2022-12-21T20:15:57ZengGraz University of TechnologyJournal of Universal Computer Science0948-69682021-06-0127654456310.3897/jucs.6961769617A reversible circuit synthesis algorithm with progressive increase of controls in generalized Toffoli gatesEdinelço Dalcumune0Luis Antonio Brasil Kowada1André da Cunha Ribeiro2Celina Miraglia Herrera de Figueiredo3Franklin de Lima Marquezino4Universidade Federal dos Vales do Jequitinhonha e MucuriUniversidade Federal FluminenseInstituto Federal GoianoUniversidade Federal do Rio de JaneiroUniversidade Federal do Rio de JaneiroWe present a new algorithm for synthesis of reversible circuits for arbitrary n-bit bijective functions. This algorithm uses generalized Toffoli gates, which include positive and negative controls. Our algorithm is divided into two parts. First, we use partially controlled gen- eralized Toffoli gates, progressively increasing the number of controls. Second, exploring the properties of the representation of permutations in disjoint cycles, we apply generalized Toffoli gates with controls on all lines except for the target line. Therefore, new in the method is the fact that the obtained circuits use first low cost gates and consider increasing costs towards the end of the synthesis. In addition, we employ two bidirectional synthesis strategies to improve the gate count, which is the metric used to compare the results obtained by our algorithm with the results presented in the literature. Accordingly, our experimental results consider all 3-bit bijective functions and twenty widely used benchmark functions. The results obtained by our synthesis algorithm are competitive when compared with the best results known in the literature, considering as a complexity metric just the number of gates, as done by alternative best heuristics found in the literature. For example, for all 3-bit bijective functions using generalized Toffoli gates library, we obtained the best so far average count of 5.23.https://lib.jucs.org/article/69617/download/pdf/design of algorithmsreversible computingcircui |
| spellingShingle | Edinelço Dalcumune Luis Antonio Brasil Kowada André da Cunha Ribeiro Celina Miraglia Herrera de Figueiredo Franklin de Lima Marquezino A reversible circuit synthesis algorithm with progressive increase of controls in generalized Toffoli gates Journal of Universal Computer Science design of algorithms reversible computing circui |
| title | A reversible circuit synthesis algorithm with progressive increase of controls in generalized Toffoli gates |
| title_full | A reversible circuit synthesis algorithm with progressive increase of controls in generalized Toffoli gates |
| title_fullStr | A reversible circuit synthesis algorithm with progressive increase of controls in generalized Toffoli gates |
| title_full_unstemmed | A reversible circuit synthesis algorithm with progressive increase of controls in generalized Toffoli gates |
| title_short | A reversible circuit synthesis algorithm with progressive increase of controls in generalized Toffoli gates |
| title_sort | reversible circuit synthesis algorithm with progressive increase of controls in generalized toffoli gates |
| topic | design of algorithms reversible computing circui |
| url | https://lib.jucs.org/article/69617/download/pdf/ |
| work_keys_str_mv | AT edinelcodalcumune areversiblecircuitsynthesisalgorithmwithprogressiveincreaseofcontrolsingeneralizedtoffoligates AT luisantoniobrasilkowada areversiblecircuitsynthesisalgorithmwithprogressiveincreaseofcontrolsingeneralizedtoffoligates AT andredacunharibeiro areversiblecircuitsynthesisalgorithmwithprogressiveincreaseofcontrolsingeneralizedtoffoligates AT celinamiragliaherreradefigueiredo areversiblecircuitsynthesisalgorithmwithprogressiveincreaseofcontrolsingeneralizedtoffoligates AT franklindelimamarquezino areversiblecircuitsynthesisalgorithmwithprogressiveincreaseofcontrolsingeneralizedtoffoligates AT edinelcodalcumune reversiblecircuitsynthesisalgorithmwithprogressiveincreaseofcontrolsingeneralizedtoffoligates AT luisantoniobrasilkowada reversiblecircuitsynthesisalgorithmwithprogressiveincreaseofcontrolsingeneralizedtoffoligates AT andredacunharibeiro reversiblecircuitsynthesisalgorithmwithprogressiveincreaseofcontrolsingeneralizedtoffoligates AT celinamiragliaherreradefigueiredo reversiblecircuitsynthesisalgorithmwithprogressiveincreaseofcontrolsingeneralizedtoffoligates AT franklindelimamarquezino reversiblecircuitsynthesisalgorithmwithprogressiveincreaseofcontrolsingeneralizedtoffoligates |