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

Вентиль Фредкина (CSWAP от англ. Controlled SWAP — управляемый обмен) — универсальный трехвходовый логический вентиль класса C-U (контролируемые операции U), достаточный для построения схем любой степени сложности. Обладает обратимостью — зная состояние выходов можно точно установить состояния входов элемента, таким образом на его базе можно строить обратимые вычисления и обратимые логические схемы. В частности, может использоваться как квантовый вентиль при реализации квантовых компьютеров. Назван в честь Edward Fredkin — версия статьи «Фредкин, Эдвард» на английском языке Эдварда Фредкина (англ.) (рус., предложившего этот вентиль^[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].

ПримечанияПравить

↑ «Фейнмановские чтения по вычислениям»: «…В его честь, мы будем называть его вентилем Фредкина…»
↑ 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. Параметры |author= и |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. Параметры |author= и |last= дублируют друг друга (справка)
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»

[1] «Фейнмановские чтения по вычислениям»: «…В его честь, мы будем называть его вентилем Фредкина…»

[2] 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.»

[3] 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.»

[4] 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…»

[5] 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. Параметры |author= и |last= дублируют друг друга (справка)

[1]

[2]

[3]

[4]

[5]