Вентиль Фредкина

Вентиль Фредкина (CSWAP от англ. Controlled SWAP — управляемый обмен) — универсальный трехвходовый логический вентиль класса C-U (контролируемые операции U), достаточный для построения схем любой степени сложности. Обладает обратимостью — зная состояние выходов можно точно установить состояния входов элемента, таким образом на его базе можно строить обратимые вычисления и обратимые логические схемы. В частности, может использоваться как квантовый вентиль при реализации квантовых компьютеров. Назван в честь Эдварда Фредкина, предложившего этот вентиль^[1].

Условное обозначение вентиля Фредкина в квантовых схемах. Верхний кубит — управляющий, средний и нижний — управляемые.

Вентиль имеет три входа и три выхода — (C, A, B). При наличии сигнала управляющей линии (первый вход, c) сигналы двух управляемых линий (второй и третий вход, a и b) меняются местами. При отсутствии управляющего сигнала сигналы управляемых линий проходят напрямую, без действия обмена. Первый выход представляет собой неизмененный сигнал управляющей линии^[2].

Технические характеристики

В целом, в работе схож с вентилем «управляемое не» (CNOT), однако равнозначность позитивной и негативной логики в сочетании с двумя коммутируемыми входами делают его универсальным и самодостаточным в отличие от «управляемых не».

Причина симметричности вентиля также указана Ричардом Фейнманом в его книге:

Фредкин добавил дополнительное ограничение на входы и выходы рассмотренных им вентилей. Он требовал, чтобы не только вентиль был обратимым, но и чтобы количество единиц и нулей никогда не менялось. На это не было весомой причины, но всё же он это сделал.

Оригинальный текст (англ.)

Fredkin added an extra constraint on the outputs and inputs of the gates he considered. He demanded that not only must a gate be reversible, but the number of 1s and 0s should never change. There is no good reason for this, but he did it anyway. He introduced a gate performing a contorolled exchange operation.

— Фейнмановские чтения по вычислениям, 2.3 "More on gates: Reversible Gates"

Благодаря сбалансированности количества нулей и единиц (консервативности) этот вентиль может быть реализован на бильярдном компьютере, также предложенном Фредкиным^[3].

Таблица истинности^[4]:

C	A	B	C'	A'	B'
0	0	0	0	0	0
0	0	1	0	0	1
0	1	0	0	1	0
0	1	1	0	1	1
1	0	0	1	0	0
1	0	1	1	1	0
1	1	0	1	0	1
1	1	1	1	1	1

Вентиль Фредкина, наряду с вентилем Тоффоли, являются широко известными универсальными обратимыми трехвходовыми вентилями, с помощью любого из них возможна реализация любой обратимой логической функции^[5]. Докажем это. Из таблицы истинности можно заключить, что при фиксированном значении на входе B=0 значение на выходе B'= A AND C. Тем самым данный вентиль может выполнить операцию логического И. С другой стороны при фиксированных входах A=1 и B=0 выход A'= NOT C. А с помощью операций И и НЕ уже можно смоделировать любой логический вентиль с любым числом входов и выходов.