Перегляд вихідного коду сторінки Вентиль Фредкіна

[[Файл:Fredkin gate.svg|150px|thumb|Позначення вентиля Фредкіна на схемі]]
'''Вентиль Фредкіна''' (також '''CSWAP-вентиль''')&nbsp;— це обчислювальна схема, придатна для [[Оборотні обчислення|оборотних]] обчислень, винайдена Едвардом Фредкіним. Він є універсальним, що означає, що будь-яка логічна або арифметична операція може бути повністю побудована з вентилів Фредкіна. Вентиль Фрейдкіна&nbsp;— це схема або пристрій з трьома входами і трьома виходами, які передають перший біт незмінним і міняють місцями два останніх біта, якщо і тільки якщо перший біт дорівнює 1.

== Визначення ==
Основний вентиль Фредкіна<ref>{{Cite book
|url=https://books.google.com/books?id=ECWm59h2pLAC&pg=PAS8
|title=Quest for the Quantum Computer
|last=Brown
|first=Julian
|date=2001-08-14
|publisher=Simon and Schuster
|language=en
|isbn=978-0-684-87004-5
}}</ref> це контрольований квантовий вентиль, який відображає три входи (''C'', ''I''<sub>1</sub>, ''I''<sub>2</sub>) у три виходи (''C'', ''O''<sub>1</sub>, ''O''<sub>2</sub>). Вхід ''C'' відображається прямо у вихід ''C''. Якщо ''C'' = 0, обміну не виконується; ''I''<sub>1</sub> відображається у ''O''<sub>1</sub>, і ''I''<sub>2</sub> відображається у ''O''<sub>2</sub>. В іншому випадку два виходи міняються місцями так, що ''I''<sub>1</sub> відображається у ''O''<sub>2</sub>, і ''I''<sub>2</sub> відображається у ''O''<sub>1</sub>. Неважко помітити, що ця схема є оборотною, тобто «скасовує» себе при запуску назад. Узагальнений ''n'' × ''n'' вентиль Фредкіна передає свої перші n''&nbsp;— 2'' входи незмінними до відповідних виходів, і міняє місцями два останніх виходи тоді і тільки тоді, коли перші n''&nbsp;— 2'' входів дорівнюють 1.
{|
! Таблиця істинності !! [[Матриця перестановки]]
|-
|
{| class="wikitable"
|-
! colspan="3" | ВХІД
! colspan="3" | ВИХІД
|- align="center"
! ''C'' !! ''I''<sub>1</sub> !! ''I''<sub>2</sub>
! ''C'' !! ''O''<sub>1</sub> !! ''O''<sub>2</sub>
|- align="center"
| &nbsp;0&nbsp; || &nbsp;0&nbsp; || &nbsp;0&nbsp;
| &nbsp;0&nbsp; || &nbsp;0&nbsp; || &nbsp;0&nbsp;
|- align="center"
| 0 || 0 || 1 || 0 || 0 || 1
|- align="center"
| 0 || 1 || 0 || 0 || 1 || 0
|- align="center"
| 0 || 1 || 1 || 0 || 1 || 1
|- align="center"
| 1 || 0 || 0 || 1 || 0 || 0
|- align="center"
| 1 || 0 || 1 || 1 || 1 || 0
|- align="center"
| 1 || 1 || 0 || 1 || 0 || 1
|- align="center"
| 1 || 1 || 1 || 1 || 1 || 1
|}
|
<math>
\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}
</math>
|}

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

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

: ''O''<sub>1</sub> = ''I''<sub>1</sub> XOR ''S''
: ''O''<sub>2</sub> = ''I''<sub>2</sub> XOR ''S''
: ''C''<sub>out</sub>= ''C''<sub>in</sub>

де ''S'' = (''I''<sub>1</sub> XOR ''I''<sub>2</sub>) AND ''C''

Інакше:

: ''O''<sub>1</sub> = (NOT ''C'' AND ''I''<sub>1</sub>) OR (''C'' AND ''I''<sub>2</sub>)
: ''O''<sub>2</sub> = (''C'' AND ''I''<sub>1</sub>) OR (NOT ''C'' AND ''I''<sub>2</sub>)
: ''C''<sub>out</sub>= ''C''<sub>in</sub>

== Повнота ==

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

: якщо ''I''<sub>2</sub> = 0, тоді ''O''<sub>2</sub> = ''C'' AND ''I''<sub>1</sub>.
: якщо ''I''<sub>2</sub> = 1, тоді ''O''<sub>1</sub> = ''C'' OR ''I''<sub>1</sub>.
: якщо ''I''<sub>1</sub> = 0 і ''I''<sub>2</sub> = 1, тоді ''O''<sub>2</sub> = NOT ''C''.

== Приклад ==
[[Файл:Full Adder using reversible Fredkin gates.svg|thumb|300px|Трибітний сумматор з переносом на п'ятьох вентилях Фредкіна]]
Трибітний повний суматор (додавання з переносом) за допомогою п'яти вентилів Фредкіна. Вихідний сміттєвий біт «g» дорівнює (p [[Стрілка Пірса|NOR]] q), якщо r = 0, і (p [[Штрих Шефера|NAND]] q), якщо r = 1.

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

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

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

== Квантовий вентиль Фредкіна ==
25 березня 2016 року дослідники {{li|Університет Гріффіта|text=Університету Гріффіта|Q=Q1202292}} та [[Університет Квінсленда|Університету Квінсленда]] оголосили, що побудували квантовий вентиль Фредкіна, який використовує [[Сплутані квантові стани|квантову сплутаність]] частинок світла для обміну кубіті. Наявність квантового вентиля Фредкіна може полегшити побудову квантового комп'ютера.<ref>{{Cite web|url=http://www.pcworld.com/article/3048763/hardware/quantum-computing-is-now-a-big-step-closer-thanks-to-this-new-breakthrough.html|title=Quantum computing is now a big step closer thanks to a new breakthrough: the Fredkin gate|archive-url=https://web.archive.org/web/20180817004140/https://www.pcworld.com/article/3048763/hardware/quantum-computing-is-now-a-big-step-closer-thanks-to-this-new-breakthrough.html|archive-date=17 серпня 2018|accessdate=4 грудня 2020}}</ref><ref>{{Cite news|url=https://www.science.org/doi/10.1126/sciadv.1501531|title=A quantum Fredkin gate|last=Patel|first=Raj B.|last2=Ho|first2=Joseph|last3=Ferreyrol|first3=Franck|last4=Ralph|first4=Timothy C.|last5=Pryde|first5=Geoff J.|date=2016-03-04|language=en|work=[[Science Advances]]|volume=2|doi=10.1126/sciadv.1501531|issn=2375-2548|pmc=PMC4820377|pmid=27051868|issue=3|access-date=2025-01-04}}</ref>

== Примітки ==
{{reflist}}

== Для подальшого вивчення ==
* {{cite journal|title=Conservative Logic |first1=Edward |last1=Fredkin |authorlink1=Edward Fredkin |first2=Tommaso |last2=Toffoli |authorlink2=Tommaso Toffoli |journal={{li|International Journal of Theoretical Physics|Q=Q2400540}} |volume=21 |issue=3-4 |year=1982 |pages=219–253 |doi=10.1007/BF01857727 |url=http://www.digitalphilosophy.org/download_documents/ConservativeLogic.pdf |url-status=dead |archiveurl=https://web.archive.org/web/20061017232512/http://www.digitalphilosophy.org/download_documents/ConservativeLogic.pdf |archivedate=October 17, 2006 }}
{{Квантовий комп'ютер}}
[[Категорія:Квантова електроніка]]
[[Категорія:Квантова інформатика]]