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

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

Вентиль Фредкіна (також 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	$\left[\begin{array}{cccccccc}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{array}\right]$

Він має корисну властивість, таку що кількість 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 року дослідники Шаблон:Li та Університету Квінсленда оголосили, що побудували квантовий вентиль Фредкіна, який використовує квантову сплутаність частинок світла для обміну кубіті. Наявність квантового вентиля Фредкіна може полегшити побудову квантового комп'ютера.

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

• Шаблон:Cite journal