Вентиль Фредкина
Вентиль Фредкина (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].
Примечания
Литература
- 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=дублируют друг друга (справка)
- 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»