### 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.

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

# Related Articles

**2019-04-15**

1904.06920 | cs.ET

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

**2019-04-01**

1904.01072 | quant-ph

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

**2019-04-05**

1904.03294 | cs.ET

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

**2019-02-17**

1902.06229 | quant-ph

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

**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

**2018-09-29**

1810.00129 | cs.ET

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

**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

**2018-07-29**

1807.11103 | cs.LO

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

**2019-01-21**

1901.07023 | cs.AI

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

**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

**2018-08-22**

1808.07199 | cs.CC

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

**2018-10-01**

1810.01486 | cs.ET

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

**2019-06-05**

1906.02352 | quant-ph

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

**2017-09-10**

1709.03067 | cs.ET

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

**2018-03-29**

1803.11017 | cs.ET

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

**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