Interested Article - Вентиль Тоффоли

Графическое представление вентиля Тоффоли

Ве́нтиль То́ффоли (CCNOT) — универсальный контролируемый с тремя входами и выходами, предложенный Томасом Тоффоли в 1980 году .

Доказано, что, используя только этот вентиль, можно построить любую обратимую логическую схему , например, арифметическое устройство или процессор. Является популярным квантовым вентилем при построении обратимых схем квантовых компьютеров .

Вентиль Тоффоли по принципу работы похож на вентиль CNOT . Имеет три входа и три выхода, если два первых входа равны единице, то значение последнего бита обращается. В противном случае все входы подаются на выход неизменными. Таблица истинности и матрица для CCNOT выглядят следующим образом:

Таблица истинности

Матрица преобразования

ВХОД			ВЫХОД
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	0	1
1	1	0	1	1	1
1	1	1	1	1	0

${\begin{bmatrix}1&0&0&0&0&0&0&0\\0&1&0&0&0&0&0&0\\0&0&1&0&0&0&0&0\\0&0&0&1&0&0&0&0\\0&0&0&0&1&0&0&0\\0&0&0&0&0&1&0&0\\0&0&0&0&0&0&0&1\\0&0&0&0&0&0&1&0\\\end{bmatrix}}$

Докажем, что вентиль является универсальным. Если разложить квантовый вентиль Тоффоли на простые булевы операции , то можно заметить, что первый и второй кубиты всегда равны на входе и выходе, а третий кубит на выходе имеет вид C = C XOR (A AND B), где A, B и C — входы и выходы вентиля. Очевидно, что вентиль является универсальным, так как он выполняет любую из операций ( NOT , AND , XOR и ) в зависимости от значений переменных на входе.

Существует другой широко известный универсальный обратимый трехвходовый вентиль — вентиль Фредкина , CSWAP .

Примечания

↑ от 4 января 2015 на Wayback Machine (1980), а также вариант: (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 : . ISBN 3-540-10003-2 .

Литература

(1980), а также
- (1980). J. W. de Bakker and J. van Leeuwen (ed.). (PDF) . Automata, Languages and Programming, Seventh Colloquium. Noordwijkerhout, Netherlands: Springer Verlag. pp. 632—644. doi : . ISBN 3-540-10003-2 .