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

f

(

n

)

&

g

(

n

)

, если для любого

ε >

0

найдется

N

=

N

(

ε

)

такое, что

при любом

n

>

N

верно неравенство

(1

ε

)

g

(

n

)

6

f

(

n

)

(функция

f

(

n

)

асимптотически больше или равна

функции

g

(

n

)

);

f

(

n

)

g

(

n

)

, если

f

(

n

)

&

g

(

n

)

и

g

(

n

)

&

f

(

n

)

(функции

f

(

n

)

и

g

(

n

)

асимптотически равны

, или

эквивалентны

), в настоящем случае

lim

n

→∞

f

(

n

)

/g

(

n

) = 1

;

f

(

n

)

g

(

n

)

, если

0

< c

1

< f

(

n

)

/g

(

n

)

< c

2

(функции

f

(

n

)

и

g

(

n

)

эквивалентны с точностью до порядка

).

Теперь можно перейти к оценке вентильной сложности обрати-

мой схемы, состоящей из вентилей NOT, CNOT и 2-CNOT, задающей

четную подстановку

h

A

(

Z

n

2

)

.

Асимптотическая нижняя оценка вентильной сложности.

Вве-

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

Ω

m

n

, состоящее из всех вентилей

NOT и

k

-CNOT,

k

6

m

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

n

входов.

Всего существует

(

n

k

) (

n

k

)

различных вентилей

k

-CNOT, имею-

щих ровно

n

входов. Нас интересует множество

Ω

2

n

, состоящее из всех

возможных вентилей NOT, CNOT и 2-CNOT с

n

входами, мощность

которого равна

|

Ω

2

n

|

=

2

X

k

=0

(

n

k

)

k

n

=

n

+

n

(

n

1)+

n

(

n

1)(

n

2)

2

=

O

(

n

3

)

.

(1)

В рассматриваемой модели обратимой схемы возможна ситуация,

когда перестановка двух соседних вентилей схемы порождает эквива-

лентную ей схему (задающую такую же четную подстановку), если эти

вентили

независимы

. Условия независимости двух вентилей

k

-CNOT

были рассмотрены в работе [4].

В множестве

Ω

2

n

все вентили имеют не более двух контролирую-

щих входов, поэтому при

n

→ ∞

несколько подряд идущих венти-

лей могут быть попарно независимыми. Определим вероятность со-

бытия, что

k

таких вентилей являются попарно независимыми. При-

мем следующее: вентиль

C

I

;

t

независим с каждым предшествующим

ему вентилем, если не существует такого вентиля

C

I

0

;

t

0

, стоящего до

рассматриваемого вентиля, что

t

I

0

или

t

0

I

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

P

i

вероятность того, что эти условия выполняются для

i

-го вентиля в

последовательности,

P

1

= 1

. Тогда вероятность

P

(

k

)

того, что

k

после-

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

P

(

k

) =

k

Y

i

=1

P

i

.

Для вентилей NOT и CNOT вероятность

P

i

выше, чем для венти-

лей 2-CNOT, так как они имеют меньше контролирующих входов. Для

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

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