Фредкин ворота - Fredkin gate

Схематическое изображение ворот Фредкина

В Фредкин ворота (также CSWAP шлюз) - вычислительная схема, подходящая для обратимые вычисления, изобретенный Эдвард Фредкин. это универсальный, что означает, что любая логическая или арифметическая операция может быть полностью построена из вентилей Фредкина. Вентиль Фредкина - это схема или устройство с тремя входами и тремя выходами, которое передает первый бит без изменений и меняет местами последние два бита, если и только если первый бит равен 1.

Определение

Основные ворота Фредкина^[1] это контролируемый своп ворота это карты три входа (C, я₁, я₂) на три выхода (C, О₁, О₂). В C ввод отображается непосредственно на C вывод. Если C = 0, своп не выполняется; я₁ сопоставляется с О₁, и я₂ сопоставляется с О₂. В противном случае два выхода меняются местами, так что я₁ сопоставляется с О₂, и я₂ сопоставляется с О₁. Легко видеть, что эта схема обратима, то есть «разворачивается» при движении назад. Обобщенный п×п Ворота Фредкина проходят первые п-2 входа без изменений на соответствующие выходы и меняет местами два последних выхода, если и только если первый п-2 входа - все 1.

Вентиль Фредкина - это обратимый трехбитовый вентиль, который меняет местами последние два бита, если и только если первый бит равен 1.

Таблица истинности	Матрица перестановок форма
ВВОД ВЫВОД C я1 я2 C О1 О2  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	${\displaystyle {\begin{bmatrix}1&0&0&0&0&0&0&0\\0&1&0&0&0&0&0&0\\0&0&1&0&0&0&0&0\\0&0&0&1&0&0&0&0\\0&0&0&0&1&0&0&0\\0&0&0&0&0&0&1&0\\0&0&0&0&0&1&0&0\\0&0&0&0&0&0&0&1\\\end{bmatrix}}}$

У него есть то полезное свойство, что повсюду сохраняются числа нулей и единиц, что в бильярдный шар означает, что на входе выводится такое же количество шаров. Это хорошо соответствует сохранение массы по физике и помогает показать, что модель не расточительна.

Истинные функции с AND, OR, XOR и NOT

Ворота Фредкина можно определить с помощью функции истины с участием И, ИЛИ, XOR, и НЕ, следующим образом:

О₁ = я₁ XOR S

О₂ = я₂ XOR S

C_вне= C_в

где S = (я₁ XOR я₂) И C

Альтернативно:

О₁ = (НЕ C И я₁) ИЛИ (C И я₂)

О₂ = (C И я₁) ИЛИ НЕТ C И я₂)

C_вне= C_в

Полнота

Один из способов убедиться в универсальности гейт Фредкина - это заметить, что его можно использовать для реализации И, НЕ и ИЛИ:

Если я₂ = 0, то О₂ = C И я₁.

Если я₂ = 1, тогда О₁ = C ИЛИ я₁.

Если я₁ = 0 и я₂ = 1, тогда О₂ = НЕ C.

пример

Трехбитный полный сумматор (добавить с переносом) с использованием пяти ворот Фредкина

Трехбитный полный сумматор (добавить с переносом) с помощью пяти ворот Фредкина. Бит вывода мусора «g» равен (p NOR q), если r = 0, и (p NAND q), если r = 1.

Входные данные слева, включая две константы, проходят через три логических элемента для быстрого определения четности. Биты 0 и 1 меняются местами для каждого установленного входного бита, в результате получается бит четности в 4-й строке и инверсия четности в 5-й строке.

Затем строка переноса и строка обратной четности меняются местами, если бит четности установлен, и меняются местами снова, если установлен один из входных битов p или q (не имеет значения, какой используется), и результирующий вывод переноса появляется в третьей строке. .

Входы p и q используются только в качестве элементов управления вентилем, поэтому на выходе они отображаются без изменений.

Квантовые ворота Фредкина

25 марта 2016 г. исследователи из Университет Гриффита и Университет Квинсленда объявили, что построили квантовые ворота Фредкина, использующие квантовая запутанность частиц света для обмена кубиты. Наличие квантовых вентилей Фредкина может облегчить построение квантовые компьютеры.^[2][3]

Смотрите также

• Квантовые вычисления
• Квантовые ворота
  • Квантовая схема
• Квантовое программирование
• Ворота Тоффоли, который является управляемый-управляемый-НЕ ворота.

использованная литература

1. Браун, Джулиан, В поисках квантового компьютера, Нью-Йорк: Пробный камень, 2000.
2. http://www.pcworld.com/article/3048763/hardware/quantum-computing-is-now-a-big-step-closer-thanks-to-this-new-breakthrough.html
3. Квантовые ворота Фредкина Радж Б. Патель, Джозеф Хо, Франк Феррейрол, Тимоти С. Ральф и Джефф Дж. Прайд, Science Advances, 25 марта 2016 г., Vol. 2, вып. 3, e1501531, DOI: 10.1126 / sciadv.1501531

дальнейшее чтение

• Фредкин, Эдвард; Тоффоли, Томмазо (1982). «Консервативная логика» (PDF). Международный журнал теоретической физики. 21 (3–4): 219–253. Дои:10.1007 / BF01857727. Архивировано из оригинал (PDF) 17 октября 2006 г.