THEORETICAL FUNDAMENTALS
OF INFORMATION TECHNOLOGY
SIZE OF REVERSIBLE CIRCUITS AS A MEASURE
OF EVEN PERMUTATION COMPLEXITY
D.V. Zakablukov
Bauman Moscow State Technical University, Moscow, Russian Federation
e-mail:
dmitriy.zakablukov@gmail.comThe article considers even permutation complexity by estimating the size of
reversible circuits composed of NOT, CNOT and 2-CNOT gates implementing
these permutations. It is proved that every even permutation of
Z
n
2
set can be
implemented by a reversible circuit with the gate complexity equivalent up to about
n
2
n
/
log
2
n
order, without the use of additional inputs; all other even permutations
can be implemented by reversible circuit with less gate complexity, without the
use of additional inputs. It is established that every even permutation of
Z
n
2
set
can be implemented by a reversible circuit with
.
2
n
+1
gate complexity, using
∼
5
∙
2
n
/n
additional inputs. For every even permutation usage of additional inputs
allows decreasing the gate complexity of reversible circuits by implementing them.
Keywords
:
reversible circuits, gate complexity, even permutation complexity.
Introduction.
In discrete mathematics a measure of transformation
complexity is introduced to estimate the complexity of this transformation.
The gate complexity is often considered as the measure of Boolean function
complexity, that is the minimal size of any circuit computing this function.
It was first suggested by K. Shannon in work [1], which is the origin of the
circuit complexity theory. Nowadays, the complexity of Boolean functions
is well researched: the lower asymptotic bound (Shannon’s theorem)
and the upper asymptotic bound (Lupanov’s theorem), as well as their
asymptotic equation
2
n
/n
for the
n
-ary Boolean function [2] have been
proved. In work [3] the problem about complexity of
Z
n
2
→
Z
n
2
Boolean
transformations is considered: it has been proved that the complexity of this
transformation does not exceed
O
n
2
n
n
+ log
2
n
; it is proved by explicit
construction of the circuit defining this transformation and composed of
NOT, AND and XOR gates.
In this article the gate complexity of circuits composed of reversible
gates NOT, CNOT and 2-CNOT is considered. The definition of reversible
gates NOT and
k
-CNOT, as well as the definition of reversible circuits
including these gates, are presented, for example, in the work [4]. In works
[5, 6] it is proved that:
•
gates NOT, CNOT and 2-CNOT define even permutation in the
circuit with
n >
3
inputs;
•
the set of permutations defined by gates NOT, CNOT and 2-CNOT
with
n
inputs, given
n
6
3
generating a symmetric group
S
(
Z
n
2
)
, but given
n >
3
alternating-sign group
A
(
Z
n
2
)
.
ISSN 0236-3933. HERALD of the BMSTU. Series “Instrument Engineering”. 2015. No. 1 67