5 / 16
независимости, рассмотренного ранее. Поэтому без ограничения общ-
ности при расчете
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