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

этого потребуется

L

(

i

)

3

вентилей множества

Ω

2

n

:

L

(

i

)

3

6

2(2

k

log

2

k

1) + 2 log

2

k

+ 2(log

2

k

+ 8(log

2

k

3) + log

2

k

);

L

(

i

)

3

6

2

k

+1

+ 20 log

2

k.

2. Не существует такого элемента

b

i,j

матрицы

A

2

, что

b

i,j

= 1

,

j >

log

2

k

. Тогда можно утверждать, что для всех

i

0

< i

верно неравен-

ство:

ϕ

log

2

k

(

h

b

i,

1

, . . . , b

i,

log

2

k

i

)

6

=

ϕ

log

2

k

(

h

b

i

0

,

1

, . . . , b

i

0

,

log

2

k

i

)

. В против-

ном случае нашлись бы две одинаковые строки в матрице

A

2

, что про-

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

g

(

K

)

2

. Применяем действие

сопряжением подстановкой, задаваемой вентилем

C

{

1

,...,

log

2

k

}

;log

2

k

+1

так, чтобы в итоге этого действия

b

i,

log

2

k

+1

= 1

. Перед этим и по-

сле этого, возможно, потребуется инвертировать не более

log

2

k

зна-

чений

b

i,j

0

= 0

,

j

0

6

log

2

k

, с помощью подстановок, задаваемых вен-

тилями NOT. Вентиль

C

{

1

,...,

log

2

k

}

;

j

имеет

log

2

k

контролирующих вхо-

дов, таким образом, он может быть заменен композицией не более

8(log

2

k

3)

вентилей 2-CNOT [5].

Далее выполняем те же действия, что и в предыдущем вариан-

те. Следовательно, для приведения

i

-й строки к такому же виду, что

и в предыдущем случае (см. п. 1), в сумме потребуется

L

(

i

)

3

венти-

лей множества

Ω

2

n

:

L

(

i

)

3

6

2(log

2

k

+ 8(log

2

k

3) + log

2

k

) + 2

k

+1

+

+ 20 log

2

k

= 2

k

+1

+ 40 log

2

k

.

В результате последовательного применения указанных действий

ко всем строкам матрицы

A

2

начиная со второй, будет получена новая

подстановка

g

(

K

)

3

и соответствующая ей матрица

A

3

:

A

3

=

 

0 0 0

. . .

0

1 0 0

. . .

0

. . . . . . . . . . . . . . .

0 1 1

. . .

1

1 1 1

. . .

1

|

{z

}

log

2

k

0

. . .

0

0

. . .

0

. . . . . . . . .

0

. . .

0

0

. . .

0

| {z }

n

log

2

k

 

.

Для этого в сумме потребуется

L

3

вентилей множества

Ω

2

n

:

L

3

=

=

k

X

i

=2

L

(

i

)

3

6

(

k

1)(2

k

+1

+ 40 log

2

k

)

.

Теперь для всех

i >

log

2

k

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

g

(

K

)

3

дей-

ствие сопряжением подстановкой, задаваемой вентилем

N

i

. Для этого

необходимо

L

4

6

2(

n

log

2

k

)

вентилей NOT. Получим итоговую под-

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