Nowe reguły przesuwania bramek w układach odwracalnych

Marek Szyprowski , Paweł Kerntopf

Abstract

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.
Author Marek Szyprowski (FEIT / IN)
Marek Szyprowski,,
- The Institute of Computer Science
, Paweł Kerntopf
Paweł Kerntopf,,
-
Journal seriesMeasurement Automation Monitoring, [Pomiary Automatyka Kontrola], ISSN 2450-2855, [0032-4140]
Issue year2013
Vol59
No8
Pages787-789
Keywords in Polishukłady odwracalne, synteza logiczna, układy kwantowe
Keywords in Englishreversible circuits, logic synthesis, quantum circuits
Abstract in PolishJedną 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.
ProjectDevelopment of new methods and algorithms in the following areas: computer graphics, artificial intelligence, and information systems, and distributed systems . Project leader: Rybiński Henryk, , Phone: +48 22 234 7731, start date 29-05-2012, planned end date 31-12-2012, end date 30-11-2013, II/2012/DS/1, Completed
WEiTI Działalność statutowa
Languagepl polski
Score (nominal)11
Score sourcejournalList
ScoreMinisterial score = 7.0, 01-02-2020, ArticleFromJournal
Ministerial score (2013-2016) = 11.0, 01-02-2020, ArticleFromJournal
Citation count*
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back
Confirmation
Are you sure?