3 / 14
Let us consider an arbitrary even permutation
h
∈
A
(
Z
n
2
)
that defines
f
h
:
Z
n
2
→
Z
n
2
Boolean transformation. Let us introduce definitions of
reversible circuits, implementing
f
h
transformation either with or without
additional inputs.
Definition 1
.
Reversible circuit
S
g
implements transformation
f
h
without the use of extra inputs (extra memory), if it has precisely n
inputs, in addition there exists such permutation
π
∈
S
(
Z
n
)
, that Boolean
transformation
g
:
Z
n
2
→
Z
n
2
defined by this circuit fulfils
ψ
π
n,n
(
g
(x)) =
=
f
h
(x)
,
(x)
∈
Z
n
2
condition.
Definition 2
.
Reversible circuit
S
g
implements transformation
f
h
using
k >
0
extra inputs (extra memory) if it has
n
+
k
inputs; in addition
there is such permutation
π
∈
S
(
Z
n
+
k
)
, that Boolean transformation
g
:
Z
n
+
k
2
→
Z
n
+
k
2
defined by this circuit fulfils
ψ
π
n
+
k,n
(
g
(
ϕ
n,n
+
k
(x))) =
=
f
h
(x)
,
(x)
∈
Z
n
2
condition.
Let us note that a reversible circuit
S
g
defines transformation
f
h
when
g
(x) =
f
h
(x)
.
We recall some notions from the mathematical analysis [2]. If
f
(
n
)
and
g
(
n
)
are real-valued positive functions of natural variable
n
, then:
•
f
(
n
)
&
g
(
n
)
, if for any
ε >
0
there is
N
=
N
(
ε
)
,
then for any
n
>
N
inequation
(1
−
ε
)
g
(
n
)
6
f
(
n
)
(function
f
(
n
)
asymptotically exceeds or is
equal to
g
(
n
)
function) is true;
•
f
(
n
)
∼
g
(
n
)
, if
f
(
n
)
&
g
(
n
)
and
g
(
n
)
&
f
(
n
)
(
f
(
n
)
and
g
(
n
)
functions are
asymptotically equal or equivalent
), then
lim
n
→∞
f
(
n
)
/g
(
n
) = 1
;
•
f
(
n
)
g
(
n
)
if
0
< c
1
< f
(
n
)
/g
(
n
)
< c
2
(
f
(
n
)
and
g
(
n
)
functions
are equivalent with the order accuracy
).
Now we can proceed to the estimation of the gate complexity of a
reversible circuit, composed of gates NOT, CNOT and 2-CNOT, defining
even permutation
h
∈
A
(
Z
n
2
)
.
Asymptotic lower bound.
Let us introduce a set of reversible gates
named
Ω
m
n
, that includes all NOT and
k
-CNOT gates,
k
6
m
, each has
exactly
n
inputs.
There are total
(
n
−
k
)
k
n
different
k
-CNOT gates having
n
inputs.
We are interested in
Ω
2
n
set that consists of all possible NOT, CNOT and
2-CNOT gates with
n
inputs. The size of this set is equal to
|
Ω
2
n
|
=
2
X
k
=0
(
n
−
k
)
k
n
=
n
+
n
(
n
−
1)+
n
(
n
−
1)(
n
−
2)
2
=
O
(
n
3
)
.
(1)
In the reversible circuit model in question this situation is possible,
when rearrangement of two adjacent gates produces the equivalent circuit
ISSN 0236-3933. HERALD of the BMSTU. Series “Instrument Engineering”. 2015. No. 1 69