Русская Википедия:Вентиль Фредкина
Вентиль Фредкина (CSWAP от Шаблон:Lang-en — управляемый обмен) — универсальный трехвходовый логический вентиль класса C-U (контролируемые операции U), достаточный для построения схем любой степени сложности. Обладает обратимостью — зная состояние выходов можно точно установить состояния входов элемента, таким образом на его базе можно строить обратимые вычисления и обратимые логические схемы. В частности, может использоваться как квантовый вентиль при реализации квантовых компьютеров. Назван в честь Эдварда Фредкина, предложившего этот вентиль[1].
Вентиль имеет три входа и три выхода — (C, A, B). При наличии сигнала управляющей линии (первый вход, c) сигналы двух управляемых линий (второй и третий вход, a и b) меняются местами. При отсутствии управляющего сигнала сигналы управляемых линий проходят напрямую, без действия обмена. Первый выход представляет собой неизмененный сигнал управляющей линии[2].
Технические характеристики
В целом, в работе схож с вентилем «управляемое не» (CNOT), однако равнозначность позитивной и негативной логики в сочетании с двумя коммутируемыми входами делают его универсальным и самодостаточным в отличие от «управляемых не».
Причина симметричности вентиля также указана Ричардом Фейнманом в его книге: Шаблон:Начало цитатыФредкин добавил дополнительное ограничение на входы и выходы рассмотренных им вентилей. Он требовал, чтобы не только вентиль был обратимым, но и чтобы количество единиц и нулей никогда не менялось. На это не было весомой причины, но всё же он это сделал. Шаблон:Oq Шаблон:Конец цитаты Благодаря сбалансированности количества нулей и единиц (консервативности) этот вентиль может быть реализован на бильярдном компьютере, также предложенном Фредкиным[3].
Таблица истинности[4]:
| C | A | B | C' | A' | B' |
|---|---|---|---|---|---|
| 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 |
Вентиль Фредкина, наряду с вентилем Тоффоли, являются широко известными универсальными обратимыми трехвходовыми вентилями, с помощью любого из них возможна реализация любой обратимой логической функции[5].
Примечания
Литература
- Technical Report MIT/LCS/TM-151 (1980), также
- Шаблон:Книга Chapter 5 «Reversible Computation and the Thermodynamics of Computing»
- ↑ «Фейнмановские чтения по вычислениям»: «…В его честь, мы будем называть его вентилем Фредкина…»
- ↑ Michael A. Nielsen, Isaac L. Chuang, Quantum Computation and Quantum Information: 10th Anniversary Edition Шаблон:Wayback // Cambridge, 2010, ISBN 9781139495486, page 156 «reversible universal logic gate known as the Fredkin gate. … The Fredkin gate has three input bits and three output bits, … The bit c is a control bit, whose balue is not changed by the action of the Fredkin gate. .. If c is set to 0 then a and b are left alone… If c is set to 1, a and b are swapped.»
- ↑ Part 7. Fundamental Limits in Computation Шаблон:Wayback // MIT EECS 6-701 Introduction to nanoelectronics, spring 2010Шаблон:Ref-en: « Perhaps the best known reversible computer is the billiard ball computer pioneered by Fredkin. … Fig. 7.11. The symbol for the Fredkin gate. … Fig. 7.12. A Fredkin gate constructed from four billiard ball switches. After Feynman, Lectures on Computation. Editors A.J.G. Hey and R.W. Allen, Addison-Wesley 1996.»
- ↑ Michael A. Nielsen, Isaac L. Chuang, Quantum Computation and Quantum Information: 10th Anniversary Edition Шаблон:Wayback // Cambridge, 2010, ISBN 9781139495486, page 157 «Figure 3.15 Fredkin gate truth table…»
- ↑ Technical Report MIT/LCS/TM-151 Шаблон:Wayback (1980), также Шаблон:Cite conference
