Вентиль Фредкина (CSWAP от — управляемый обмен) — универсальный трехвходовый логический вентиль класса C-U (контролируемые операции U), достаточный для построения схем любой степени сложности. Обладает обратимостью — зная состояние выходов можно точно установить состояния входов элемента, таким образом на его базе можно строить обратимые вычисления и обратимые логические схемы. В частности, может использоваться как квантовый вентиль при реализации квантовых компьютеров. Назван в честь Эдварда Фредкина, предложившего этот вентиль.
Вентиль имеет три входа и три выхода — (C, A, B). При наличии сигнала управляющей линии (первый вход, c) сигналы двух управляемых линий (второй и третий вход, a и b) меняются местами. При отсутствии управляющего сигнала сигналы управляемых линий проходят напрямую, без действия обмена. Первый выход представляет собой неизмененный сигнал управляющей линии.
Технические характеристики В целом, в работе схож с вентилем «управляемое не» (CNOT), однако равнозначность позитивной и негативной логики в сочетании с двумя коммутируемыми входами делают его универсальным и самодостаточным в отличие от «управляемых не».
Причина симметричности вентиля также указана Ричардом Фейнманом в его книге: Фредкин добавил дополнительное ограничение на входы и выходы рассмотренных им вентилей. Он требовал, чтобы не только вентиль был обратимым, но и чтобы количество единиц и нулей никогда не менялось. На это не было весомой причины, но всё же он это сделал.
Благодаря сбалансированности количества нулей и единиц (консервативности) этот вентиль может быть реализован на бильярдном компьютере, также предложенном Фредкиным.
Таблица истинности:
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
Вентиль Фредкина, наряду с вентилем Тоффоли, являются широко известными универсальными обратимыми трехвходовыми вентилями, с помощью любого из них возможна реализация любой обратимой логической функции. Из таблицы истинности можно заключить, что при фиксированном значении на входе B=0 значение на выходе B'= A AND C. Тем самым данный вентиль может выполнить операцию логического И. С другой стороны при фиксированных входах A=1 и B=0 выход A'= NOT C. А с помощью операций И и НЕ уже можно смоделировать любой логический вентиль с любым числом входов и выходов.
Примечания
Литература
Категория:Логические элементы Категория:Квантовый компьютер