13 / 14
with
f
h
(
h
a
1
, . . . , a
k
, x
k
+1
, . . . , x
n
i
)
transformation outputs, where values
are to be taken from the outputs of multi-terminal circuit. XOR gate from
formula (10) is implemented by 2-CNOT gate, so at this stage
N
4
=
n
additional inputs are needed. The values of the outputs that correspond to
these additional inputs are outputs of
f
h
transform.
Now it is possible to estimate
L
∗
(
h
)
value:
L
∗
(
h
)
6
L
1
+
L
2
+
L
3
+
+2
k
L
4
;
L
∗
(
h
)
6
2
2
n
−
k
+1
+2
k
+2
k
+1
+
n
2
k
= 2
2
n
−
k
+1
+2
k
+2
k
(
n
+2)
. Also
we estimate a number of the required additional inputs:
N
=
N
1
+
N
2
+
+
N
3
+
N
4
;
N
= 2
2
n
−
k
−
(
n
−
k
)+
k
+2
k
+1
−
4+
n
= 2
2
n
−
k
+2
k
+2
k
+1
−
4
.
In work [3] it was stated, that:
n
−
k
= log
2
(
n
−
log
2
n
)
L
∗
(
h
)
≤
2
n
+1
n
+ 2(
n
−
log
2
(
n
−
log
2
n
)) +
(
n
+ 2)2
n
+1
n
−
log
2
n
.
2
n
+1
;
N
=
2
n
n
+ 2(
n
−
log
2
(
n
−
log
2
n
)) +
2
n
+2
n
−
log
2
n
−
4
∼
5
∙
2
n
n
.
I
The conclusion can be drawn about dependency of circuit-size complexi-
ty on the number of additional inputs, relying on theorem 4.
Statement 1.
For almost all permutations
h
∈
A
(
Z
n
2
)
usage of
additional inputs allows reducing their circuit-size complexity.
J
Based on theorems 3 and 4.
I
Conclusion.
When synthesizing a reversible circuit, implementing
some even permutation, it is necessary to find a compromise between
circuit-size complexity and number of additional inputs in the circuit.
In this paper several asymptotic bounds of reversible circuits composed
of NOT, CNOT and 2-CNOT gates have been proved. It was stated that
among all minimal reversible circuits without the usage of additional inputs
maximal circuit-size complexity is equivalent to the accuracy up to an
order of
n
2
n
/
log
2
n
. At the same time
∼
5
∙
2
n
/n
additional inputs allow
to construct a reversible circuit, implementing the given even permutation
with
.
2
n
+1
circuit-size complexity.
Further investigations focuse on the dependency of the reversible
circuits compexity composed of NOT, CNOT and 2-CNOT gates from the
number of additional inputs being used in the scheme.
REFERENCES
[1] Shannon C.E. The synthesis of two-terminal switching circuits. Bell Syst. Tech. J.,
1949, vol. 28, no. 1, pp. 59–98.
[2] Yablonskiy S.V. Vvedenie v diskretnuyu matematiku [Introduction to discrete
mathematics]. Moscow, Nauka Publ., 1986. 384 p.
[3] Interlando J.C. Toward a theory of one-way functions via gate complexity of boolean
functions. Ph. D. Dissertation, USA, Indiana, University of Notre Dame, 2006. 100 p.
ISSN 0236-3933. HERALD of the BMSTU. Series “Instrument Engineering”. 2015. No. 1 79