4 / 16
•
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