Вентиль Фредкина
Вентиль Фредкина (CSWAP от англ. Controlled SWAP — управляемый обмен) — универсальный трехвходовый логический вентиль класса C-U (контролируемые операции U), достаточный для построения схем любой степени сложности. Обладает обратимостью — зная состояние выходов можно точно установить состояния входов элемента, таким образом на его базе можно строить обратимые вычисления и обратимые логические схемы. В частности, может использоваться как квантовый вентиль при реализации квантовых компьютеров. Назван в честь Эдварда Фредкина, предложившего этот вентиль[1].
Вентиль имеет три входа и три выхода — (C, A, B). При наличии сигнала управляющей линии (первый вход, c) сигналы двух управляемых линий (второй и третий вход, a и b) меняются местами. При отсутствии управляющего сигнала сигналы управляемых линий проходят напрямую, без действия обмена. Первый выход представляет собой неизмененный сигнал управляющей линии[2].
Технические характеристики
В целом, в работе схож с вентилем «управляемое не» (CNOT), однако равнозначность позитивной и негативной логики в сочетании с двумя коммутируемыми входами делают его универсальным и самодостаточным в отличие от «управляемых не».
Причина симметричности вентиля также указана Ричардом Фейнманом в его книге:
Фредкин добавил дополнительное ограничение на входы и выходы рассмотренных им вентилей. Он требовал, чтобы не только вентиль был обратимым, но и чтобы количество единиц и нулей никогда не менялось. На это не было весомой причины, но всё же он это сделал.
Оригинальный текст (англ.)Fredkin added an extra constraint on the outputs and inputs of the gates he considered. He demanded that not only must a gate be reversible, but the number of 1s and 0s should never change. There is no good reason for this, but he did it anyway. He introduced a gate performing a contorolled exchange operation.— Фейнмановские чтения по вычислениям, 2.3 "More on gates: Reversible Gates"
Благодаря сбалансированности количества нулей и единиц (консервативности) этот вентиль может быть реализован на бильярдном компьютере, также предложенном Фредкиным[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]. Докажем это. Из таблицы истинности можно заключить, что при фиксированном значении на входе B=0 значение на выходе B'= A AND C. Тем самым данный вентиль может выполнить операцию логического И. С другой стороны при фиксированных входах A=1 и B=0 выход A'= NOT C. А с помощью операций И и НЕ уже можно смоделировать любой логический вентиль с любым числом входов и выходов.
Примечания
- ↑ «Фейнмановские чтения по вычислениям»: «…В его честь, мы будем называть его вентилем Фредкина…»
- ↑ Michael A. Nielsen, Isaac L. Chuang, Quantum Computation and Quantum Information: 10th Anniversary Edition Архивная копия от 5 марта 2016 на Wayback Machine // 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 Архивная копия от 14 мая 2015 на Wayback Machine // MIT EECS 6-701 Introduction to nanoelectronics, spring 2010 (англ.): « 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 Архивная копия от 4 марта 2016 на Wayback Machine // Cambridge, 2010, ISBN 9781139495486, page 157 «Figure 3.15 Fredkin gate truth table…»
- ↑ Technical Report MIT/LCS/TM-151 Архивная копия от 4 января 2015 на Wayback Machine (1980), также Toffoli, Tommaso (1980). J. W. de Bakker and J. van Leeuwen (ed.). Reversible computing. Automata, Languages and Programming, Seventh Colloquium (англ.). Noordwijkerhout, Netherlands: Springer Verlag. pp. 632–644. doi:10.1007/3-540-10003-2_104. ISBN 3-540-10003-2.
{{cite conference}}: Указан более чем один параметр|author=and|last=()
Литература
- Technical Report MIT/LCS/TM-151 (1980), также
- Toffoli, Tommaso (1980). J. W. de Bakker and J. van Leeuwen (ed.). Reversible computing. Automata, Languages and Programming, Seventh Colloquium (англ.). Noordwijkerhout, Netherlands: Springer Verlag. pp. 632–644. doi:10.1007/3-540-10003-2_104. ISBN 3-540-10003-2.
{{cite conference}}: Указан более чем один параметр|author=and|last=()
- Toffoli, Tommaso (1980). J. W. de Bakker and J. van Leeuwen (ed.). Reversible computing. Automata, Languages and Programming, Seventh Colloquium (англ.). Noordwijkerhout, Netherlands: Springer Verlag. pp. 632–644. doi:10.1007/3-540-10003-2_104. ISBN 3-540-10003-2.
- Richard Phillips Feynman. Feynman Lectures On Computation. — Boston: Addison-Wesley Longman Publishing, 1998. — ISBN 0-201-38628-3. Chapter 5 «Reversible Computation and the Thermodynamics of Computing»
