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

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

Визначення[ред. | ред. код]

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

Примітки[ред. | ред. код]

↑ Brown, Julian, The Quest for the Quantum Computer [Архівовано 25 листопада 2021 у Wayback Machine.], New York: Touchstone, 2000.
↑ Архівована копія. Архів оригіналу за 17 серпня 2018. Процитовано 4 грудня 2020.{{cite web}}: Обслуговування 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; Toffoli, Tommaso (1982). Conservative Logic (PDF). International Journal of Theoretical Physics. 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.{{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

[1]

[2]

[3]