Background Image
Previous Page  7 / 16 Next Page
Information
Show Menu
Previous Page 7 / 16 Next Page
Page Background

из вентилей NOT, CNOT и 2-CNOT, основанный на теории групп под-

становок. Было доказано, что вентильная сложность синтезированной

схемы удовлетворяет соотношению

L

(

n

)

.

7

n

2

n

.

(3)

Этот алгоритм основан на представлении подстановки в виде произ-

ведения пар независимых транспозиций с последующей реализацией

этих пар с помощью обратимых вентилей. Если обобщить этот алго-

ритм для синтеза большего числа независимых транспозиций, можно

получить асимптотическую верхнюю оценку сложности

L

(

n

)

.

Теорема 2.

L

(

n

)

.

52

n

2

n

/

log

2

n

.

J

Покажем, что

L

(

h

)

.

52

n

2

n

/

log

2

n

для всех

h

A

(

Z

n

2

)

. Любую

подстановку

h

A

(

Z

n

2

)

можно представить в виде композиции непе-

ресекающихся циклов так, чтобы сумма длин этих циклов не превос-

ходила

2

n

. Для композиции двух независимых циклов верно равенство

(

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)

а для цикла длиной

l

>

5

— равенство

(

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)

Представим подстановку

h

в виде композиции групп независимых

транспозиций, по

K

транспозиций в каждой группе, и оставшейся

подстановки

h

0

:

h

=

x

t

,

y

t

Z

n

2

((x

1

,

y

1

)

. . .

(x

K

,

y

K

))

h

0

.

(6)

Для подстановки

h

0

оценим число независимых циклов и их длину

в разложении. Согласно формулам (4) и (5), в разложении

h

0

нельзя

получить

K

независимых транспозиций, если число независимых ци-

клов строго меньше

K

и их длина строго меньше 5. Отсюда следует,

что сумма длин циклов в разложении

h

0

не превосходит

4(

K

1)

.

Обозначим через

M

g

множество подвижных точек произвольной

подстановки

g

S

(

Z

n

2

)

:

M

g

=

{

x

Z

n

2

|

g

(x)

6

= x

}

. С учетом изложен-

ного выше,

|

M

h

|

6

2

n

,

|

M

h

0

|

6

4(

K

1)

.

В соответствии с формулами (4)–(6), в декомпозиции подстановки

h

можно получить не более

|

M

h

|

/K

групп, в каждой из которых

K

независимых транспозиций, а в декомпозиции подстановки

h

0

— не

более

|

M

h

0

|

/

2

пар независимых транспозиций и не более одной пары

зависимых транспозиций.

Пара зависимых транспозиций

(

i, j

)

(

i, k

)

выражается через

произведение двух пар независимых транспозиций:

(

i, j

)

(

i, k

) =

= ((

i, j

)

(

r, s

))

((

r, s

)

(

i, k

))

.

ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 1 73