ML p(r)ior | Reversible Logic Circuit Complexity Analysis via Functional Decomposition

Reversible Logic Circuit Complexity Analysis via Functional Decomposition

2016-01-30
1602.00101 | cs.ET
Reversible computation is gaining increasing relevance in the context of several post-CMOS technologies, the most prominent of those being Quantum computing. One of the key theoretical problem pertaining to reversible logic synthesis is the upper bound of the gate count. Compared to the known bounds, the results obtained by optimal synthesis methods are significantly less. In this paper, we connect this problem with the multiplicative complexity analysis of classical Boolean functions. We explore the possibility of relaxing the ancilla and if that approach makes the upper bound tighter. Our results are negative. The ancilla-free synthesis methods by using transformations and by starting from an Exclusive Sum-of-Product (ESOP) formulation remain, theoretically, the synthesis methods for achieving least gate count for the cases where the number of variables $n$ is $< 8$ and otherwise, respectively.
PDF

Highlights - Most important sentences from the article

Login to like/save this paper, take notes and configure your recommendations

Related Articles

2019-04-15

Physical implementation of scalable quantum architectures faces an immense challenge in form of frag… show more
PDF

Highlights - Most important sentences from the article

2019-04-01

We introduce an open source software package UniversalQCompiler written in Mathematica that allows t… show more
PDF

Highlights - Most important sentences from the article

2019-04-05

Crosstalk computing, involving engineered interference between nanoscale metal lines, offers a fresh… show more
PDF

Highlights - Most important sentences from the article

2019-02-17
1902.06229 | quant-ph

Previous work has provided methods for decomposing unitary matrices to series of quantum multiplexer… show more
PDF

Highlights - Most important sentences from the article

2018-10-12
1810.05603 | cs.CC

We consider the power of Boolean circuits with MOD$_{6}$ gates. First, we introduce a few basic noti… show more
PDF

Highlights - Most important sentences from the article

2018-09-29

IBM has made several quantum computers available to researchers around the world via cloud services.… show more
PDF

Highlights - Most important sentences from the article

2018-10-09
1810.03811 | cs.CC

In this work we investigate into energy complexity, a Boolean function measure related to circuit co… show more
PDF

Highlights - Most important sentences from the article

2018-07-29

We present an exact synthesis approach for computing Exclusive-or Sum-of-Products (ESOP) forms with … show more
PDF

Highlights - Most important sentences from the article

2019-01-21
1901.07023 | cs.AI

Totally self-checking (TSC) circuits are synthesised with a grid of computers running a distributed … show more
PDF

Highlights - Most important sentences from the article

2018-08-18
1808.06928 | cs.ET

The distribution of reversible programs tends to a limit as their size increases. For problems with … show more
PDF

Highlights - Most important sentences from the article

2018-08-22

$\newcommand{\EC}{\mathsf{EC}}\newcommand{\KW}{\mathsf{KW}}\newcommand{\DT}{\mathsf{DT}}\newcommand{… show more
PDF

Highlights - Most important sentences from the article

2018-10-01

Due to technology advancements and circuits miniaturization, the study of logic systems that can be … show more
PDF

Highlights - Most important sentences from the article

2019-06-05

Research on quantum computing has recently gained significant momentum since first physical devices … show more
PDF

Highlights - Most important sentences from the article

2017-09-10
1709.03067 | cs.ET

Polymorphic circuits are a special kind of digital logic components, which possess multiple build-in… show more
PDF

Highlights - Most important sentences from the article

2018-03-29

Power dissipation is the main limitation of all the nano electronics design techniques including Qua… show more
PDF

Highlights - Most important sentences from the article

2015-05-10
1505.02372 | cs.CC

The reversible logic can be used in various research areas, e.g. quantum computation, cryptography a… show more
PDF

Highlights - Most important sentences from the article