Вентиль Фредкіна також CSWAP вентиль це обчислювальна схема придатна для оборотних обчислень винайдена Едвардом Фредкіни

Вентиль Фредкіна (також 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	I₁	I₂	C	O₁	O₂
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 зберігається протягом виконання, що в ^[en] означає, що на виході отримується така ж кількість кульок. Це добре відповідає закону збереження маси у фізиці та допомагає показати, що модель безвідходна.

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

Примітки

Brown, Julian, The Quest for the Quantum Computer [ 25 листопада 2021 у Wayback Machine.], New York: Touchstone, 2000.
. Архів оригіналу за 17 серпня 2018. Процитовано 4 грудня 2020.{{}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title ()
A quantum Fredkin gate [ 29 березня 2016 у Wayback Machine.] Raj B. Patel, Joseph Ho, Franck Ferreyrol, Timothy C. Ralph and Geoff J. Pryde, Science Advances, 25 Mar 2016, Vol. 2, no. 3, e1501531, DOI: 10.1126/sciadv.1501531

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

Fredkin, Edward; (1982). (PDF). . 21 (3-4): 219—253. doi:10.1007/BF01857727. Архів оригіналу (PDF) за 17 жовтня 2006.

[1] Brown, Julian, The Quest for the Quantum Computer [ 25 листопада 2021 у Wayback Machine.], New York: Touchstone, 2000.

[2] . Архів оригіналу за 17 серпня 2018. Процитовано 4 грудня 2020.{{}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title ()

[3] A quantum Fredkin gate [ 29 березня 2016 у Wayback Machine.] Raj B. Patel, Joseph Ho, Franck Ferreyrol, Timothy C. Ralph and Geoff J. Pryde, Science Advances, 25 Mar 2016, Vol. 2, no. 3, e1501531, DOI: 10.1126/sciadv.1501531