Background Image
Previous Page  6 / 14 Next Page
Information
Show Menu
Previous Page 6 / 14 Next Page
Page Background

2

n

log

2

n

+

n

n

log

2

log

2

n

log

2

n

n

2

n

=

log

2

n

;

s

=

n

2

n

+

o

(

n

2

n

)

2 log

2

n

+

o

(log

2

n

)

.

It is obvious that given the value of

s

,

log

2

(

C

(

n, s

)

/

|

A

(

Z

n

2

)

|

)

→ −∞

given

n

→ ∞

, i.e. the part of reversible circuits composed of

gates from

Ω

2

n

set without the use of additional inputs, with a complexity

less than

s

, tends to zero.

It is important that if the above described values of

s

and

k

, the

conditions

k

=

o

(

n

)

, k

=

o

(

s

)

are fulfilled, therefore the application of

formula (2) is correct. Then

s

n

2

n

1

/

log

2

n

. That shows the validity of

the theorem.

I

Asymptotic upper bound

. In paper [7] the algorithm of synthesis of

reversible circuits, composed of gates NOT, CNOT and 2-CNOT, based

on the theory of permutation groups, was proposed. It was proved that the

gate complexity of the synthesized circuit satisfies the following ratio:

L

(

n

)

.

7

n

2

n

.

(3)

This algorithm is based on the representing of permutation as the

production of pairs of independent transpositions followed by the imple-

mentation of these pairs using reversible gates. Generalizing this algorithm

for the synthesis of the large number of independent transpositions, it is

possible to obtain an asymptotic upper bound of the circuit-size complexity

L

(

n

)

.

Theorem 2.

L

(

n

)

.

52

n

2

n

/

log

2

n

.

J

Let us demonstrate that

L

(

h

)

.

52

n

2

n

/

log

2

n

for all values of

h

A

(

Z

n

2

)

. Any permutation

h

A

(

Z

n

2

)

can be represented as a

composition of disjoint cycles so that the sum of the lengths of these

cycles does not exceed 2

n

. For the composition of two independent cycles

the following equation is true:

(

i

1

, i

2

, . . . , i

l

1

)

(

j

1

, j

2

, . . . , j

l

2

) =

= (

i

1

, i

2

)

(

j

1

, j

2

)

(

i

1

, i

3

, . . . , i

l

1

)

(

j

1

, j

3

, . . . , j

l

2

)

,

(4)

and for the cycle with the length

l

>

5

the following equation is true

(

i

1

, i

2

, . . . , i

l

) = (

i

1

, i

2

)

(

i

3

, i

4

)

(

i

1

, i

3

, i

5

, i

6

, . . . , i

l

)

.

(5)

We represent the permutation

h

as a composition of independent

transposition groups, with

K

transpositions in each group, and the remaining

permutation

h

0

:

h

=

x

t

,

y

t

Z

n

2

((x

1

,

y

1

)

. . .

(x

K

,

y

K

))

h

0

.

(6)

72 ISSN 0236-3933. HERALD of the BMSTU. Series “Instrument Engineering”. 2015. No. 1