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

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

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

Визначення

Основний вентиль Фредкіна[1] це контрольований квантовий вентиль, який відображає три входи (C, I1, I2) у три виходи (C, O1, O2). Вхід C відображається прямо у вихід C. Якщо C = 0, обміну не виконується; I1 відображається у O1, і I2 відображається у O2. В іншому випадку два виходи міняються місцями так, що I1 відображається у O2, і I2 відображається у O1. Неважко помітити, що ця схема є оборотною, тобто «скасовує» себе при запуску назад. Узагальнений 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

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

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

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

O1 = I1 XOR S
O2 = I2 XOR S
Cout= Cin

де S = (I1 XOR I2) AND C

Інакше:

O1 = (NOT C AND I1) OR (C AND I2)
O2 = (C AND I1) OR (NOT C AND I2)
Cout= Cin

Повнота

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

якщо I2 = 0, тоді O2 = C AND I1.
якщо I2 = 1, тоді O1 = C OR I1.
якщо I1 = 0 і I2 = 1, тоді O2 = NOT C.

Приклад

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

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

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

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

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

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

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

Примітки

  1. ↑ Brown, Julian, The Quest for the Quantum Computer [Архівовано 25 листопада 2021 у Wayback Machine.], New York: Touchstone, 2000.
  2. ↑ Архівована копія. Архів оригіналу за 17 серпня 2018. Процитовано 4 грудня 2020.{{cite web}}: Обслуговування 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

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