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

время сложность булевых функций хорошо изучена: доказаны ниж-

няя асимптотическая оценка сложности (теорема Шеннона) и верхняя

асимптотическая оценка сложности (теорема Лупанова), а также их

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

2

n

/n

для булевой функции

n

перемен-

ных [2]. В работе [3] изучен вопрос сложности булева преобразо-

вания

Z

n

2

Z

n

2

: доказано, что сложность такого преобразования не

превышает

O

n

2

n

n

+ log

2

n

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

го построения схемы, задающей это преобразование и состоящей из

функциональных элементов NOT, AND и XOR.

В настоящей работе рассмотрен вопрос вентильной сложности

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

2-CNOT. Определение обратимых вентилей NOT и

k

-CNOT, а также

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

например, в работе [4]. В работах [5, 6] было доказано следующее:

вентили NOT, CNOT и 2-CNOT задают четную подстановку в

схеме с

n >

3

входами;

множество подстановок, задаваемых вентилями NOT, CNOT и

2-CNOT с

n

входами, при

n

6

3

генерирует симметрическую группу

S

(

Z

n

2

)

, а при

n >

3

— знакопеременную группу

A

(

Z

n

2

)

.

В связи с изложенным в качестве меры сложности четной подста-

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

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

и 2-CNOT.

В работах [5–13] предложены различные алгоритмы синтеза обра-

тимых схем и в некоторых случаях дана оценка сверху вентильной

сложности синтезированной схемы. Однако до сих пор не были из-

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

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

щей какую-либо четную подстановку из группы

A

(

Z

n

2

)

.

В настоящей работе с помощью оценки числа различных неэквива-

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

подстановка

h

A

(

Z

n

2

)

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

мой, состоящей из вентилей NOT, CNOT и 2-CNOT и не использую-

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

.

n

2

n

1

/

log

2

n

.

Также будет доказано, что любая четная подстановка

h

A

(

Z

n

2

)

мо-

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

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

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

.

52

n

2

n

/

log

2

n

. Будет показано, что любая чет-

ная подстановка

h

A

(

Z

n

2

)

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

мой, состоящей из вентилей NOT, CNOT и 2-CNOT и использующей

5

2

n

/n

дополнительных входов с вентильной сложностью

.

2

n

+1

.

Основные понятия.

Рассмотрим следующую модель обратимой

схемы: все вентили в схеме имеют одинаковое число входов, выходы

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