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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Условное обозначение вентиля Фредкина в квантовых схемах. Верхний кубит - управляющий, средний и нижний - управляемые.

Вентиль Фредкина (CSWAP от англ. Controlled SWAP - управляемый обмен) — универсальный трехвходовый логический вентиль класса C-U (контролируемые операции U), достаточный для построения схем любой степени сложности. Обладает обратимостью — зная состояние выходов можно точно установить состояния входов элемента, таким образом на его базе можно строить обратимые вычисления и обратимые логические схемы. В частности, может использоваться как Квантовый вентиль при реализации квантовых компьютеров. Назван в честь Эдварда Фредкина (англ.), предложившего этот вентиль[1].

Вентиль имеет три входа и три выхода. При наличии сигнала управляющей линии (первый вход, c) сигналы двух управляемых линий (второй и третий вход, a и b) меняются местами. При отсутствии управляющего сигнала сигналы управляемых линий проходят напрямую, без действия обмена. Первый выход представляет собой неизмененный сигнал управляющей линии.[2]

Технические характеристики[править | править вики-текст]

В целом, в работе схож с вентилем «управляемое не» (CNOT), однако равнозначность позитивной и негативной логики в сочетании с двумя коммутируемыми входами делают его универсальным и самодостаточным в отличие от «управляемых не».

Причина симметричности вентиля также указана Ричардом Фейнманом в его книге:

Фредкин добавил дополнительное ограничение на входы и выходы рассмотренных им вентилей. От требовал, чтобы не только вентиль был обратимым, но и чтобы количество единиц и нулей никогда не менялось. На это не было весомой причины, но всё же он это сделал.

— Фейнмановские чтения по вычислениям, 2.3 "More on gates: Reversible Gates"

Благодаря сбалансированности количества нулей и единиц (консервативности) этот вентиль может быть реализован в модели Billiard-ball computer[en], также предложенной Фредкиным[3].

Таблица истинности[4]

A B C A' B' C'
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].

Примечания[править | править вики-текст]

  1. «Фейнмановские чтения по вычислениям»: «…В его честь, мы будем называть его вентилем Фредкина…»
  2. Michael A. Nielsen, Isaac L. Chuang, Quantum Computation and Quantum Information: 10th Anniversary Edition // 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 // 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 // Cambridge, 2010, ISBN 9781139495486, page 157 "Figure 3.15 Fredkin gate truth table..."
  5. Technical Report MIT/LCS/TM-151 (1980), также Toffoli, Tommaso (1980). "Reversible computing" in Automata, Languages and Programming, Seventh Colloquium. J. W. de Bakker and J. van Leeuwen: 632-644, Noordwijkerhout, Netherlands: Springer Verlag. DOI:10.1007/3-540-10003-2_104. 

Литература[править | править вики-текст]