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

Для получения матрицы

A

1

потребуется

L

1

6

2

n

вентилей CNOT.

Для всех элементов

a

1

,i

= 1

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

g

(

K

)

1

дей-

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

N

i

. Для этого

потребуется

L

2

6

2

k

+1

вентилей NOT. В итоге получим подстановку

g

(

K

)

2

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

A

2

:

A

2

=

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

0

. . .

0

b

2

,

1

∙ ∙ ∙

b

2

,

2

k

∙ ∙ ∙

∙ ∙ ∙

∙ ∙ ∙

b

k

1

,

1

∙ ∙ ∙

b

k

1

,

2

k

b

k,

1

∙ ∙ ∙

b

k,

2

k

0

∙ ∙ ∙

0

0

∙ ∙ ∙

0

∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙

0

∙ ∙ ∙

0

0

∙ ∙ ∙

0

| {z }

n

2

k

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

.

Элементы матрицы

A

2

обозначены через

b

i,j

, чтобы показать их

возможное отличие от элементов матрицы

A

1

.

Поставим в соответствие вектору число с помощью отображения

ϕ

m

:

Z

m

2

Z

2

m

:

ϕ

m

(

h

x

1

, . . . , x

m

i

) =

m

X

i

=1

x

i

2

i

1

. Будем последователь-

но действовать сопряжением на подстановку

g

(

K

)

2

, рассматривая все

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

A

2

начиная со второй. Пусть текущая строка име-

ет номер

i

. Эта строка попарно отличается от всех строк, чей номер

меньше

i

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

A

2

различны. Возможны два

варианта.

1. Существует элемент матрицы

b

i,j

= 1

,

j >

log

2

k

. В таком случае

для всех элементов

b

i,j

0

= 1

,

j

0

6

=

j

,

j

0

>

log

2

k

, применяем действие

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

C

j

;

j

0

. Для этого по-

требуется не более

2(2

k

log

2

k

1)

вентилей CNOT. Затем для всех

j

0

6

log

2

k

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

мой вентилем

C

j

;

j

0

, так, чтобы выполнялось условие

ϕ

log

2

k

(

h

b

0

i,

1

, . . . , b

0

i,

log

2

k

i

) =

i

1

.

(9)

Для этого необходимо не более

2 log

2

k

вентилей CNOT. На послед-

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

вентилем

C

{

1

,...,

log

2

k

}

;

j

. Перед этим и после этого, возможно, потребует-

ся инвертировать не более

log

2

k

значений

b

0

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].

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

торой все элементы с индексом больше

log

2

k

являются нулевыми, а

первые ее

log

2

k

элементов удовлетворяют условию (9). В сумме для

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