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

Позначення вентиля Фредкіна на схемі

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

Визначення

Основний вентиль Фредкіна це контрольований квантовий вентиль, який відображає три входи (C, I₁, I₂) у три виходи (C, O₁, O₂). Вхід C відображається прямо у вихід C. Якщо C = 0, обміну не виконується; I₁ відображається у O₁, і I₂ відображається у O₂. В іншому випадку два виходи міняються місцями так, що I₁ відображається у O₂, і I₂ відображається у O₁. Неважко помітити, що ця схема є оборотною, тобто «скасовує» себе при запуску назад. Узагальнений n × n вентиль Фредкіна передає свої перші n — 2 входи незмінними до відповідних виходів, і міняє місцями два останніх виходи тоді і тільки тоді, коли перші n — 2 входів дорівнюють 1.

Таблиця істинності	Матриця перестановки
ВХІД ВИХІД C I1 I2 C O1 O2  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	${\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}}$

Він має корисну властивість, таку що кількість 0 і 1 зберігається протягом виконання, що в комп'ютері з більярдних куль означає, що на виході отримується така ж кількість кульок. Це добре відповідає закону збереження маси у фізиці та допомагає показати, що модель безвідходна.

Функція істинності з AND, OR, XOR та NOT

Вентиль Фредкіна можна визначити, використовуючи функції істинності з І (AND), АБО (OR), Виключне АБО (XOR) та НЕ (NOT) наступним чином:

O₁ = I₁ XOR S

O₂ = I₂ XOR S

C_out= C_in

де S = (I₁ XOR I₂) AND C

Інакше:

O₁ = (NOT C AND I₁) OR (C AND I₂)

O₂ = (C AND I₁) OR (NOT C AND I₂)

C_out= C_in

Повнота

Одним із способів переконатися, що вентиль Фредкіна є універсальними, є спостереження, що його можна використовувати для реалізації І, НЕ та АБО:

якщо I₂ = 0, тоді O₂ = C AND I₁.

якщо I₂ = 1, тоді O₁ = C OR I₁.

якщо I₁ = 0 і I₂ = 1, тоді O₂ = NOT C.

Приклад

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

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

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

Потім лінія переносу та лінія зворотної парності міняються місцями, якщо встановлено біт парності, і знову міняються місцями, якщо встановлений один із вхідних бітів p або q (не має значення, який із них використовується), а отриманий результат перенесення з'явиться на 3-ій лінії.

Входи p та q використовуються лише як елементи керування вентилями, тому вони залишаються незмінними на виході.

Квантовий вентиль Фредкіна

25 березня 2016 року дослідники Університету Гріффіта та Університету Квінсленда оголосили, що побудували квантовий вентиль Фредкіна, який використовує квантову сплутаність частинок світла для обміну кубіті. Наявність квантового вентиля Фредкіна може полегшити побудову квантового комп'ютера.

Для подальшого вивчення

• Fredkin, Edward; Toffoli, Tommaso (1982). Conservative Logic (PDF). International Journal of Theoretical Physics. 21 (3-4): 219—253. doi:10.1007/BF01857727. Архів оригіналу (PDF) за 17 жовтня 2006.