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

независимости, рассмотренного ранее. Поэтому без ограничения общ-

ности при расчете

P

(

k

)

примем, что все вентили являются вентилями

2-CNOT.

Первый вентиль

C

{

j

1

,l

1

}

;

t

1

можно выбрать любым возможным спо-

собом. При выборе второго вентиля

C

{

j

2

,l

2

}

;

t

2

, независимого от перво-

го, необходимо выбрать значения

j

2

и

l

2

так, чтобы они не совпада-

ли со значением

t

1

: всего существует (

n

1

2

) способов выполнить это.

Значение

t

2

не должно совпадать со значениями

j

1

,

l

1

,

j

2

,

l

2

: всего

есть

n

4

способов выбрать значение

t

2

. Аналогичные рассуждения

можно провести и для третьего вентиля

C

{

j

3

,l

3

}

;

t

3

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

(

n

2

2

) способов выбрать значения

j

3

и

l

3

и

n

6

способов — значение

t

3

. Отсюда следует, что вероятность

P

k

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

P

k

>

(

n

2

k

)

n

k

+1

2

(

n

2) (

n

2

)

, или

P

k

>

(

n

2

k

)(

n

k

+ 1)(

n

k

)

(

n

2)

n

(

n

1)

. Знак

>

” означает, что в реальной схеме больше способов выбрать

i

-й вен-

тиль так, чтобы он был независим с каждым предыдущим вентилем.

При

k

=

o

(

n

)

и

n

→ ∞

вероятность

P

k

>

1

o

(1)

,

P

k

1

, тогда, и

P

(

k

)

1

. Следовательно, доля обратимых схем, состоящих из венти-

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

Ω

2

n

, у которых из

k

=

o

(

n

)

подряд идущих вентилей

найдется хотя бы два зависимых вентиля, стремится к нулю.

Докажем с помощью оценки числа различных неэквивалентных

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

h

A

(

Z

n

2

)

,

которая не может быть задана обратимой схемой, состоящей из вен-

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

Ω

2

n

и не использующей дополнительные входы с

вентильной сложностью

.

n

2

n

1

/

log

2

n

.

Сложность минимальной обратимой схемы, состоящей из вентилей

множества

Ω

2

n

, не использующей дополнительные входы и задающей

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

h

A

(

Z

n

2

)

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

L

(

h

)

. Определим

функцию Шеннона

L

(

n

) = max

h

A

(

Z

n

2

)

L

(

h

)

. Аналогично рассмотрим ве-

личины

L

(

h

)

и

L

(

n

)

для обратимых схем, использующих дополни-

тельные входы.

Теорема 1.

L

(

n

)

&

n

2

n

1

/

log

2

n

.

J

Покажем, что имеет место неравенство

L

(

h

)

&

n

2

n

1

/

log

2

n

по-

чти для всех подстановок

h

A

(

Z

n

2

)

. Оценим число обратимых схем,

состоящих из вентилей множества

Ω

2

n

, которые задают различные чет-

ные подстановки на множестве

Z

n

2

и имеют вентильную сложность

s

.

Обозначим эту величину через

C

(

n, s

)

.

Если

r

=

|

Ω

2

n

|

, то

C

(

n, s

)

6

r

s

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

C

(

n, s

)

общее

число различных, неэквивалентных обратимых схем, состоящих из

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

Ω

2

n

и имеющих вентильную сложность не более

s

:

C

(

n, s

) =

s

P

i

=0

C

(

n, i

)

6

r

s

+1

1

r

1

.

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